Interview Question


Country: United States




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

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.
SO 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...

- Swapnil August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

What is most unique.? It's like saying coldest ice...:-)..

- Prashant R Kumar August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Most unique as in, if a number appeared only once its the 1st most unique. If a number appeared twice in the entire list its the 2nd most unique. So on and so forth.

- Anonymous October 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Martin August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Each node from the main link list will have 2 pointers. One pointing to the next node in the main list and the other pointing to a fresh linklist. So each node will have its own linklist. Look up how to resolve hash collision. One of the techniques used is this.

- Anonymous October 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

what does it mean by "7th most unique element" ?

- rkt August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterate through all the nodes and put the node value as key and value as no. of occurance of the num.. Once done , iterate through hash map and sort it based on value get the 7th number for ascending order and key corresponding to it is 7th most unique element

- Anonymous August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a hashMap key = num and value= count. Create a MinHeap and 7th operation of heapification will ive required value.

- Anonymous August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

- Chengyun Zuo August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- buckCherry November 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Abe lodi... Kya bakwas pel rahi hai?? Tuze pakad pakad ke chodu...

- Vss August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

chod de

- rahul August 20, 2012 | 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