Interview Question
Country: United States
What do you mean by "You have a linked list in which each node is another linked list." ?
What does a Node structure look like?
Build a min-heap which has 7 nodes, traverse all nodes and keep on adjusting the min-heap. Finally, the min-heap top is the answer.
While building min-heap what value you use - the value of the node or the occurrence of the node-vales? If you use former then you've a wrong answer and if you use occurrence then pls explain how do you get occurrence count for each node-value??
Sorry--making one vote down for missing this important info.
Finding distinct values from any collection has to take O(n) at least. In this case O(n*m) where n is total # nodes in outer list where each node contains linked list of m nodes.
- Swapnil August 20, 2012SO traversing all element once is required in any case.
Now when you traverse them put into hash data structure with key as node value and value as count. Once you traverse entire linked list(nm times) then just query hash data structure with value=1 and get the 7th one..
SO it will be O(n*m) to traverse linked list and O(n*m) to put into hash and constant time operation to query hash structure.
So it will be done in O(n*m) time...