Bloomberg LP Interview Question Financial Software Developers

  • bloomberg-lp-interview-questions
    2
    of 2 votes
    5
    Answers

    Q: If I give you a new book, and ask you to create the index which is found at the end of the book, how will you do it.
    A: I said for constant addition time of words (and page numbers) in the data structure, we can use Hashmap or TRIE. But since output has to be in alphabetic order, we will use a Trie DS, where at the end of each word, we simple store a list of page numbers.

    - Aditya on April 14, 2013 in United States Report Duplicate | Flag
    Bloomberg LP Financial Software Developer Data Structures

Country: United States
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
1
of 1 vote

I think either option is fine, but given that you're going to do a lot more inserts / lookups than index generation (which only happens once) it might be more efficient to use a hashmap for the O(1) lookup and insertion per word, and then to spend the time sorting all indices with O(N*logN) rather than having to navigate the trie each time when adding a word to the index.

- Anonymous on April 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We always say hashmap takes O(1) time in lookup and insertion, but doesn't generation of the hashcode effectively depend on our string length too? So that will automatically counter the disadvantage of navigating trie each time there is an insertion.

- Aditya on April 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can use a hashmap: <String, ArrayList<Integer>> and a trie. The hashmap is used to store the word and the page numbers in increasing order. The trie is used for storing all words in alphabetical order.

Whenever you find a new word or an existing word in the hashmap, insert or put the word in the hashmap and append the page number arraylist. Meanwhile, insert the word in the trie if it's not there.

- crazyguy on April 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this you end up storing your entire dataset twice, effectively wasting a lot of space, and still carrying out all the operations of BOTH the data structures. How does that help?

- Aditya on April 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A TreeMap of word and linked list of page number (TreeMap<String, LinkedList<String>>)will be better solution. Since all entry in TreeMap is stored in key order.

- Huan on February 09, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More