Bloomberg LP Interview Question
Financial Software DevelopersA 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.
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.
@ gekko gordan, Yes correct, We can do it with one hash table . Thansk for correction .
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.
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.
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
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
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 .
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 .
3) now THREE times you added 3 , then linked list becomes
4) to make above node swapping in O(1) time complexity you can use hashing technique.
Hash table1:
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.
- siva.sai.2020 January 19, 20116) 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)