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.

- Jacques January 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mr.karthik.p February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nishant.cena February 14, 2013 | Flag Reply
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

- vikrant April 14, 2013 | Flag Reply
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;
		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.

- Parikksit Bhisay April 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Parikksit Bhisay April 20, 2013 | 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