Interview Question for Software Engineer at Google:

It will be a queue.
getlist() will return head of queue - O(1)
access(str) will check if str will exist and if not, insert at the head - O(1)

space - O(1)

To the above answer:

I don't think that will work. first of all, a queue is usually defined as FIFO, so you can only add to the tail of the queue. Secondly, using a queue to check if an item exists will take O(n) time, not O(1) as you suggested. So insertion will take O(n). also using a queue does not guarantee the fixed length. think of the MS example, your first accessed item will eventually get pushed out of the list when you keep accessing new files.

To above, actually we need to use a stack instead.

Checking against the stack won't be O(n) since the size of the stack is constant (5). It will be O(1).

For what it's worth, the final solution I arrived at with the Google engineer--and he confirmed he was satisfied with it--was to use a dictionary with the strings as keys for O(1) lookup, where the values in the dictionary act as doubly-linked lists for O(1) insertion & removal.

He wanted to be sure I covered all 3 logical cases every time I improved my solution towards the final one:
* Returning the sequence in appropriate MRU order
* Maintaining the order at insertion
* Maintaining the maximum list size at insertion

Anonymous, your point about constant size, while technically correct, might feel like a bit of a cop-out in an interview. It's a good observation, but I think I would point it out and then ask if the analysis should assume arbitrary n for the maximum size. Since this is Google, processing infinite streams of data daily, we might assume they want an MRU list that could be used for arbitrary n. In that case I believe we do need a little more machinery than a plain stack or queue.

To add to my above response, taking n to be the size of the list (though technically bounded by a constant at instantiation), we would have to say that space use is O(n) rather than O(1). While Anonymous's observation that the max size 5 is given in the problem definition is both correct and astute, I think that interviewers would appreciate a candidate to then go further and assume arbitrary n for the max size. Then the candidate has an opportunity to display understanding of the purpose of asymptotic notation, which is not to prove O(1) by whatever means possible but instead to give an informed analysis of resource usage for a proposed design. Again, either O(1) or O(n) in this problem can be correct, provided you explain what your variable n means and give its domain. In the context of an interview, I think I would run through both analyses and most importantly, talk talk talk to the interviewer about my thoughts as I proceed.

Thanks Chris for your explanation - I agree.

Did they get back to you with an offer?

They got back to me but they turned me down for now. I didn't ask for more information, but I imagine it's because I look like a big risk. I have sort of sabotaged myself with too much schooling & TA/RA work and too little paid experience.

My 2 cents:
I don't think using either a stack or a map(dictionary if you will) would be a very good solution as maintaining the order would be important in this case. stack must be LIFO, and a map is simply not good for ordering.

A special case must be considered is when an item already exists in the list but not the top, then when this item gets accessed, it should pop to the top while pushing other items down. though none of the elements already in the list should be removed in this case.

in order to maintain order and satisfy the above special case, an array for fixed size or an array-based queue/list would be a better fit. note i specifically said array-based queue as they are easier to sort and manipulate ordering than a linked list. sorting a linked list is simply nightmare.

finally an alternative, and also good solution would be to use a binary search tree structure with the tree sorted based on the access order. this would give pretty good general case performance for both fixed size and arbitrary length.

I would use a hash table with the strings as keys and a string pair as the values, as Chris described. I would also have two sentinel elements that would hold the most recently used string and the least recently used string.

The basic access(myStr) algorithm:

// Check if str is MRU, O(1)
if (myStr == mru) return;

// Remove LRU, O(1)
tmp = lruStr.successor
tmp.predecessor = null
remove lru from table
lru = tmp

// Check if myStr in table, O(1)
if (myStr in table)
   // "Remove" myStr, O(1)
   myStr.predecessor.successor = myStr.successor
   myStr.successor.predecessor = myStr.predecessor
endif

// Add myStr as head, O(1)
myStr = mruStr.successor
myStr.predecessor = mruStr
mruStr = myStr

Comments, corrections, and advice greatly appreciated.