Bloomberg LP Interview Question for Financial Software Developers






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

1. We have to use TWO hash tables and ONE Double linked list .
2. Time complexity O(1) to add a number and delete a number.

Approach:

1. Store numbers in double linked list. Highest frequency number first node and least frequency number last node .

number frequency
  5      2
  4      3
  3      1
  2      10

2) linked list looks :

I don't know how to represent double linked list diagrammatically, so in below example i am using single linked list .

2->4->5->3

3) now THREE times you added 3 , then linked list becomes

2->3->4->5

4) to make above node swapping in O(1) time complexity you can use hashing technique.

Hash table1:

number  | Frequency     
-------------------
        |
        |

Hash table 2:

Frequency  | First node   | Last node 
-------------------------------------
           |              |
           |              |

5) From First hash table you can get number frequemncy and by using frequency on second Hash table you can get Linked list location where you to insert node.

6) I know above explanation bit confusing. I could not showed my solution properly in diagrammetic way .

7) My solution works O(1) time complexity.
8) Space complexity: O(n) + Hash tables space O(1)

- siva.sai.2020 January 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A modification to your code, you dont need two hash tables. only one which contains the following for every number
key=Number, value=(Frequency, PrevNode,NextNode)
The frequency of a number changes by only 1 at a point of time (assuming numbers are input 1 by 1). so all you need is to check the Frequency(prevNode->value) i.e. hash.find(prevNode->value).frequency and if it is greater than swap.

- gekko gordan January 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I couldn't understand how to access a particular number if we don't keep a pointer to its associated node.

What I understand is that, we intend to keep a sorted (based on frequency) linked list of number. To access a number in O(1) complexity, we use a hash table key=number, value=<frequency,nodePointer>. As it's a doubly linked list, we can access Prev or Next node in O(1) time.

Thanks.

- anonymous January 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ gekko gordan, Yes correct, We can do it with one hash table . Thansk for correction .

- siva.sai.2020 January 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity isn't O(1) unless you have a perfect hash table, which you don't. Usually good hashtable implementations have a redblack tree behind them, so your insert is logn.

Stil a good algorithm though.

- Anonymous January 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can do this using 1 hash table and 1 singly linked list.
Hash Table :
key = number
value = node in linked list

Linked List:
- by default, insert new element at the start, update pointer in Hash Table
- if a number is already present in hash table, then go to its linked list node, increment its counter and check with next nodes; if next node's counter is less, then put the current node ahead of it.

This will give an ascending order linked list. In case of printing, push all values into stack and pop for printing. This is a trade-off, whether you want use doubly linked list in place of singly linked list or a stack for printing.

- nharryp December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Max Priority Queue

- Anonymous January 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Max Priority Queue

- Anonymous January 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not store the entire data as in a huffman coded tree ? I suppose that would have the number with the highest frequency at the top and the one with the lowest at the bottom.

- Aman January 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not use a Splay tee??

- Ab March 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not LGBT tree?

- &troller March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@gekko and siva
In a hash table, the order of the tuples is not guaranteed.
You'll need to use a TreeMap.

- Anonymous January 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer is close to Aman answer, its a sort of tree called optimal binary search tree which is comparable to Huffman tree. Applications, spellcheckers or frequently used items, Requirement, Need to know the frequency and number of items in advance,

Else Max heap is the only option i believe

- yogesh January 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make a node of symbol and the frequency. Create a priority queue.

- Coder March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May be I misunderstood the question, but if we have a string with a sequence of numbers that we need to store according to a frequency then the easiest way is to use a map to store a number and its frequency and then create another multimap and revert key with a values.
Here is the simple input and output:

1222345566777891012
first map:
1 1
2 3
3 1
4 1
5 2
6 2
7 3
8 1
9 1
10 1
12 1
now multimap with reverse of key value of the first map


3 2
3 7
2 5
2 6
1 1
1 3
1 4
1 8
1 9
1 10
1 12

and now we can print out a sequence if we need to

2227775566134891012

- ilyaw77 March 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry forgot to mention that multimap has to be sorted in descending order:
multimap<int,int, greater<int>> myMultiMap;

- ilyaw77 March 15, 2014 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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