Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

closed as primarily opinion-based by gnat, GlenH7, Kilian Foth, MichaelT, Bart van Ingen Schenau Oct 13 '13 at 11:06

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
If you were, just use Python if you're more comfortable. You can still implement a linked list in Python and you can always ask interviewers what they want to reinvent/use the standard lib for –  jozefg Oct 9 '13 at 4:20
2  
Thank you for your help :) –  Maximus S Oct 9 '13 at 4:51
1  
@MaximusS DONT ask an interviewer what they want to reinvent.... These interviews are to test your cunning and ability to solve, in many cases over complicated or almost impossible solutions. They just want to see if you are going to get frustrated and quit or if you have a grasp on problem solving. Giving them a snarky answer will ensure you don't get the job –  Anthony Russell Oct 9 '13 at 19:16

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
"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." is usually a sufficient answer for most of the interviews I've been in. The next sentence usually works if they want you to prove you know how to implement one. Most won't go as far as ask you to code a stack. –  Glenn1234 Oct 9 '13 at 4:39
    
After interviewing over 100 developers, I usually ask 1 or 2 data structures questions just to check whether the candidate understands static vs dynamic size, how to address list, stack, queue, tree, hash table, vector/dynamic array, O() complexity, memory management, etc. –  ChuckCottrill Oct 9 '13 at 5:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.