Aditya
BAN USERMaster's Student,Computer Science
- 9of 9 votes
AnswersQ: If you have all the companies that are traded, and live inputs are coming of which company is being traded and what is the volume, how do you maintain the data, so that you can carry out operation of giving the top 10 most traded companies by volume of shares most efficiently.
- Aditya in United States
A: I juggled between Hash Map and Max Heap. I said Max Heap, since I can take out top 10 companies in a jiffy with a Max Heap. But then he asked you will need to find a company everytime there is a trade, which will take quite some time in Heap. He pointed out that in real world scenario, number of trades happening, and hence searching of the company and updating it, will be many times more than finding top 10. Which bought me to HashMap. Updations can happen in Real time, while finding top 10 can be done in O(n) or O(nlog(n)) time.
Even that wasn't optimal obviously. The interviewer was very nice and friendly type guy. He stressed that at every trade, at most, only 1 company will change in my top 10. This hit me and got me to the correct answer that we keep all actual data in HashMap, but also maintain a MinHeap of 10 most traded company.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 2of 2 votes
AnswersQ: 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.
- Aditya in United States
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.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 1of 1 vote
AnswersQ: Do you know what is a Binary tree? How would you go about coding for addition of a new element to Binary tree?
- Aditya in United States
A: I asked if they want a Binary Tree or a BST? When he said BST I just said we can have a recursive function in which we pass the root of the tree and see if the value to be added is smaller or bigger than the root, and depending on result, we go to left or right of the tree, assuming the left (or right) is not null. If null, just use new to create a memory location, put the value, and use the left reference of the root to link to this new memory. Simple basic stuff.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Coding - 3of 3 votes
AnswersQ: Do you know what is a stack? Explain
- Aditya in United States
A: Yes, explained LIFO push pop peek
Q: In stack, Push and Pop are constant. What will you do if you want an operation which gives the min of the stack also in constant time?
A: Question is straight out of Gayle's Book. You just maintain a new stack of minimum number till that point.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Stacks
1) Still not sure how you will get O(1) search. Can you please give an example? (Also, you are now using 2 arrays, twice d space).
2) In your approach, each modification requires O(log(N)) comparisons to determine the position. That will not be the case in a 10 element min heap and a HashTable, the solution I proposed after the hint from the interviewer.
3) Not sure how you intend to implement the Set Interface. That will dictate how much time it will take for you to find and update the trade load value of companies in both the sets. If that's taken care of, this look good, at least to me. The only thing, though outside the scale of this specific problem is, what if the query of top 10 changes, say, to a 100, or a 1000. Maintaining a min heap still scales better, as a new entry in the heap will require a operation of logN time, while sorting a set (or array, whatever you are using) will need more time.
1) In your original approach, even searching isn't O(1), since the array was sorted by number of trades, and not some company index.
2) In your current approach, if the company is in the heap, and the number of trades isn't sufficient for it to qualify as top 10, you still end up re-balancing the heap in O(log(N)) time, which isn't good. You will end up re-balancing the heap at every trade, not just when you need the top 10.
Few problems with this
1) you are emptying the stack to find the min/max....in turn destroying your data
2) The moment you empty the stack to make a list, your constrain of being Constant time is gone for a toss. You will spend as much time as the number of elements. Similarly, sorting will require O(N lgN) time
I think bloomberg has bigger focus on c++, because their work is mainly in that, except a couple of team who work in JAVA. That said, if u are strong in JAVA and not C++, dnt say to d interviewer that you will give the interview in C++. To them it doesn't matter that much I believe, as long as you can show that you understand the approach to the problem sufficiently well.
- Aditya June 19, 2013Everyday u create a new heap and hasmap. 1st 10 companies traded automatically enter and create the heap, as they are the most (and only) traded company till then. Then, as and when more trades happen, every time there is a live update, you check the updated record with the min heap only, so only, a constant number of 10 checks. If the company is in the Heap already, you update the number of shares, and rebalance the heap if required. If the company is not in the heap, you just see if the total trade of this new company is more than the trade of the root company. If yes, you replace the root with the new company, and rebalance if required.
- Aditya May 30, 2013Nope, never said you find top 10 from HashMap. For the top 10, you maintain a min heap, and everytime there is a live update, you check the updated record with the min heap only, so only, a constant number of 10 checks. If the company is in the Heap already, you update the number of shares, and rebalance the heap if required. If the company is not in the heap, you just see if the total trade of this new company is more than the trade of the root company. If yes, you replace the root with the new company, and rebalance if required.
- Aditya May 30, 2013Because at any time I need to change/throw 1 company out of the heap, I would like the one which has been traded the minimum. If I keep maximum heap, every time a company is traded, I have to check that company's number of share, with the current heap's minimum, because that's the only 1 which will be thrown out of the heap
- Aditya April 28, 2013
Pretty sure running didn't mean that. Even if that is what he would have meant, his solution will end up taking more space
- Aditya April 17, 2014