Goldman Sachs Interview Question
Software Engineer / DevelopersTeam: Strategies Group
Country: India
Interview Type: In-Person
I searched the answers given here and based on the SkipList concept, with a rush, I tried this solution. I considered 1000 elements and element to be searched 769.
So now, we create an array of the class type. i.e.
SLL index = new SLL[50]
Now I looped through the list and after every 20~25 elements, added the node to the array.
private static void createIndex(SLL[] index, SLL head){
int count=0;
SLL temp = head;
while(temp!=null)
{
count++;
temp = temp.next;
if((count==23){
index[i] = temp;
i++;
count=0;
}
}
}
Now finally the 'find' function. In that function, I first take the input element say 769 as I said, and I go through the 'index' array and find index[i]>769. Thus, now I pass head = index[i-1] and tail = index[i] to the 'find' function. It will then search between a short range of 23 elements for 769. Thus, I calculated that it takes a total of 43 jumps (including the array jumps and the node=node.next jumps) to find the element I wanted which otherwise would have taken 769 jumps.
It has horrible space complexity, but I just gave an attempt. Its my own thinking and I tried to provide a solution in rush, please give me your feedback, thanks.
List of 1000 is assumed to be sorted. I wrote a function to create a list with node.data = 1 to 999. Its a Singly Linked List.
Also, I do not consider the complexity of creating the index array in the function of finding it. (I consider that we do the indexing only AFTER we have created the entire list OR maybe with regular time intervals, just like a newly made website takes time to show up in google searches.)
if only linked list could be used, you may want to consider to use Skip List.
- Jacques January 02, 2013