Implementing basic data structures in programming interviews [closed]

Question

Closed. This question is opinion-based. It is not currently accepting answers.

---

Want to improve this question? Update the question so it can be answered with facts and citations by editing this post.

Closed 6 years ago.

Improve this question

I have been preparing to do my first technical interview in a month, and I have a question about implementing common data structures like stacks or linked lists. I plan to do the interview in either Python or Java but I am not sure which one to use yet.

I was practicing and tried to implement a stack in Python, using already built-in lists. However, lists in Python already have all stack methods, while there is still some work to do when arrays in Java are used to implement a stack.

If I am asked to implement a stack and my language of choice is Python, what should I do? Should I define Node class? Would I not even be asked to implement such low-level data structure in Python anyway?

Answer 1

They'll probably be more interested in if you understand what a stack/linked list is, how they work, and so on. Basically, could you implement one in C, C++ if you had to do it, assuming you knew the language? If those things are a standard part of the languages you listed, you probably wouldn't be asked to implement them in a raw way.

But like I mentioned, they'll want you to prove that you understand the logical concepts behind the data structures if the question is coming up. For example in answering the question on stacks, stacks are LIFO structures, where what you add last is taken off first. It's like a stack of plates where you can only add or remove the top plate. Then if you go into implementation, you simply take an array of a certain size, keep track of the capacity, and only operate off of that index value. For instance, Delphi/Pascal implementation:

const
  maxstacksize = 500;
type
  TIntegerStack = class
  private
    elements: array[1..maxstacksize] of integer;
    capacity: integer;
  public
    procedure place(element: integer);
    function remove: integer;
  end;

procedure TIntegerStack.place(element: integer);
   begin
     if capacity = maxstacksize then
       // error, trying to place element on full stack, i.e. stack overflow
     else
       begin
         inc(capacity);
         elements[capacity] := element;
       end;
   end;

function TIntegerStack.remove: integer;
   begin
     Result := -1;
     if capacity = 0 then
       // error, trying to remove element from empty stack
     else
        begin
          Result := elements[capacity];
          dec(capacity);
        end;
   end;

Most interviewers probably won't need you to take it that far to prove you know what stacks are and how they work, but it gives you an idea of what the interviewer is expecting.