## Goldman Sachs Interview Question for Software Engineer / Developers

Team: Strategies Group
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 9 vote

if only linked list could be used, you may want to consider to use Skip List.

Comment hidden because of low score. Click to expand.
0

Is it a single or double link list ? . What about the values of link list are they sorted or unsorted ? .

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

skip list best suited if the linked list contains sorted data.

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

binary tree wors case scenario is linked list so during the time of adding an element if put in a manner of binary tree manner.We can easily jump to that

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

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

Comment hidden because of low score. Click to expand.
0

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

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.

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