View All num of num See all Photos Bloomberg L.P. www.bloomberg.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 1.4k Reviews 4.2k Salaries 2.3k Interviews 778 Jobs Follow Add Review or Salary Follow Add Review or Salary Interview Question Financial Software Developer Interview New York, NY Bloomberg L.P. 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). Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 1 Answer ▲ 5 ▼ 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 Interviews > Financial Software Developer > Bloomberg L.P. Add Answers or Comments To comment on this, Sign In or Sign Up.