Queue Interview Code basic methods made from struct Node optimized

Question

Using feedback from my previous implementation I'm writing a very simple Queue of struct Nodes with only these methods get_front(), get_back(), pop_front(), push_back(), and a ostream friend method. I want this to be reviewed as production code and is to be treated as code that could be used in an interview. I'm really curious about the approach I've taken here to keep track of the size, empty status, and back and front pointers. I resolved some of the padding issues in my data structures, not sure if that's over kill or would look good to show my C++ proficiency.

I'd like to know also if my member functions for the Queue have any edge cases I am not catching and any improvements I can make to run time efficiency overall. Anyway I can simplify this code further with c++11 features, shorter variable names or smart pointers would be appreciated.

Lastly if you optionally would like to share the memory/space complexity for my code that would be a huge help! I have noted some examples in the member data of my Node struct.

#include <iostream>
#include <string>

class Queue
{
    private:
        struct Node
        {
            int data;
            char padding[4];
            Node* previous;
            Node(int data) : data(data), previous(nullptr) { }
        };
        int _size{0};
        char padding[4];
        Node* _back{nullptr};
        Node* _front{nullptr};
    public:
        ~Queue() {
            while(_front) {
                auto n = _front;
                _front = _front->previous;
                delete n;
            }
        }

        void pop_front() {
            --_size;
            if (!_back) {
                throw std::out_of_range{"cannot get data from empty queue"};
            }
            else if (_front->previous) {
                auto danglingptr = _front;
                _front = _front->previous;
                delete danglingptr;
            }
            else {
                _front = _back = nullptr;
            }
        }
        void push_back(int data) {
            auto n = new Node(data);
            ++_size;
            if (!_back) {
                _front = _back = n;
            }
            else {
                _back->previous = n;
                _back = _back->previous;
            }
        }
        int get_back() { return _back ? _back->data : 0; }
        int get_front() { return _front ? _front->data : 0; }
        std::size_t get_size() { return _size; }
        bool is_empty() { return _size > 0; }

        friend std::ostream& operator<<(std::ostream& os, const Queue& queue) {
            int size = queue._size;
            if (size == 0) {
                os << "Queue is empty";
            }
            else {
                for (int i = 1; i < size*2; i++) { os << "_"; }
                os << std::endl;
                std::string queue_string = "";
                auto current = queue._front;
                for(; current; current = current->previous) {
                    queue_string =  std::to_string(current->data) +  " " + queue_string;
                }
                os << queue_string << std::endl;
                for (int i = 1; i < size*2; i++) { os << "_"; }
            }

            return os;
        }
};

int main()
{
    Queue queue;

    queue.push_back(9);
    queue.push_back(8);
    queue.push_back(7);
    queue.push_back(6);
    queue.push_back(5);

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
    queue.pop_front();
    queue.pop_front();

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
    queue.pop_front();

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
}

Answer 1

This is going to be somewhat more conversational on things to do or don't looking at it as if you'd shown this in the course of an interview. Any response with respect to an interview example would always take into account the amount of experience that the candidate is claiming to have. Note, I am also writing this in the way I am looking at the code, noticing superficial things first and then looking closer and closer at the implementation.

My first question would be about the padding, and if you wouldn't be able to answer as to why it is important here or why you added it (saying that there was a warning wouldn't be a sufficient answer), what it does, and what the issues are whether this works under 32 and 64 bit architectures, etc... . If you can't answer these questions it would be a bad sign for me. For interviews don't use features in your code that you can't explain.

I'd definitely ask you why you didn't use std::unique_ptr as this would remove large swaths of the code, it's a feature of c++11 in an interview i'd probably expect to see that. I'd probably also ask whether you thought about making the interface closer to the standard library calls e.g. get_back() vs back() or is_empty() vs empty().

Note that most of these are actually superficial but they are really easy to pick up on a first look, without even having to think about if the code is correct or not (which would be more work on my side) there are already a ton of things to talk about that might let me exclude you as a candidate. The quicker you can be excluded, the less work for everybody.

So on closer look, you'd get dinged for returning a valid piece of data on failure in get_back() and get_front(). Here you are return 0 if there aren't any items, this is really a big issue. This would start a discussion on error handling in general, what could you have done, what did you do just a few lines above that section.

I see a bug in pop_front() first I'd ask you to look at it and we'd try to find it together. You decrease size before the check if the queue is empty, this would make size incorrect. Looking at the bug also made me notice that you never tested popping from the empty list. Now that I have seen the first bug, i'm looking closer and there is another bug that leaks the first nodes memory if its the last item. If we haven't talked about unique_ptr up to this point, I'd ask now.

Depending on how your responses are we might talk about some general points, i'd comment that you're probably putting out too much text on <<, i'd ask if the to_string() in the demo code is really necessary. I'd comment on your style for member variables (pet peeve). Leading underscores are iffy at best with regard to their use, the standard reserves names with leading underscores in combination with capital letters and double underscores, so you're just one keystroke away from code that violates that. I'd also remark that the test code could have used some assertions rather than just output, this would have made things much more like a unit test, and if there is time we might talk about what you know about unit testing.

When I interview, i take any issue I see as an opportunity to talk about what caused it, what might remedy it, why the candidate did this. The answers to these questions may matter more than the actual code.