Bloomberg L.P.

  www.bloomberg.com
  www.bloomberg.com

Interview Question

Financial Software Developer Interview New York, NY

The chessboard problem. I first mentioned BFS and use of a

  Queue but the interviewer kept asking about some data structure with less memory that I could extract due to the simple structure of the graph. I did not understand what he meant. I eventually mentioned DFS and proved it works uses less memory. The cache problem took a long time. I kind of though I failed it at some point. I had no prior knowledge of the topic since I am not a CS guy. I eventually, used an array to store the access time to different items and O(n) search through it to find the least frequently used one. The interviewer did not raise the complexity. He wanted me to write code on a paper (which is hard, esp. in C).
Answer

Interview Answer

1 Answer

3

The LRU cache problem can be solved in (amortized) O(1) with auxiliary structures:
- bidirectional linked list (last item in the list is the least recently used to be removed)
- hashtable of pointers to the list, to find the key in the list in amortized O(1)
- on each access, the key will be looked up in the hashtable, and the item in the list will be moved to front (which can be done in O(1) for bidirectional list)

Alternatively (if you fear collisions in the hashtable) in O(log n) by replacing the hashtable with a binary search tree (std::map).

dojigiri on Jul 29, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.