Goldman Sachs Interview Question for Developer Program Engineers


Country: India
Interview Type: In-Person




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

It can be done using one pointer but not without extra space. You can store the addresses of all the nodes visited in a hashmap. And for every next node, check its presence in hashmap.

- Ashish Anand March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

Actually, you CAN :)
1. keep the first node of the list
2. go through the list and reverse the direction of links.
if you reach to NULL , the answer is "NO loop"
if during step 2 you reach the kept first node than the answer is "YES, the is a loop"

- Tigran March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

First thing u are not allowed modify the list.
Second will you be able to modify the with only one pointer?

- PCB March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are right (I was thinking about not comparing two walking pointers),
this one may take long but satisfies to your requirements:
while walking through the list keep max and min addresses of nodes and check
if n*(address size) > max-min then there is a loop

- Tigran March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tigran, we can't even check address, as each node of linked list is created dynamically. So we cannot predict address of any node.

I feel whatever Ashish has suggested is right way.

- PCB March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is totally a funny question that you can have a hash, but can not use a second pointer.

- chenlc626 March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

With one pointer and additional memory to store each node traversed we can find out if linked list has loop. This is O(n2) solution and O(n) space.

- Survivor March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not simply mark a node as "visited" and iterate through the Linked List?

- Varun March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. This works when you are permitted to modify linked list structure.

- Suryaamsh March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are allowed to use extra space then this problem can be solved in O(n) space and O(n) time complexity. store the memory in a list once a node is visited. on each visit check list whether it contains the memory location if not add the memory of the item else the point will be the loop point.

- King007 July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

maintain sorted list of visited memory address, this will further reduce time complexity while comparing addresses

- Nitin Taur September 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, just create a hashmap for the memory nodes visited. As you retrive the next node check in the hashmap if that value exists. Else keep adding it to the hashmap.

- Balu July 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

while(start != null){
if (!set.add(start)) {
isCyc = true;
break;
}
start = start.next;
}

System.out.println(isCyc);

Make Sure that there is hashCode and equals for your LinkedList and hashcode calculation should not include next.

- pranit May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Boolean isCyc = false;
		Set<LinkedList> set = new HashSet<LinkedList>();
		
		while(start != null){
			if (!set.add(start)) {
				isCyc = true;
				break;
			}
			start = start.next;
		}
		
		System.out.println(isCyc);

- Pranit October 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Revert list. If you reach root, there is a loop, if not, there is no loop.
2) Store address of highest element passed. If you find this element again, there is a loop. If reach end of list, there is no loops.

Ok, technically you use second pointer. Lets store unambiguous hash of root or highest element pointer...

- mike October 24, 2014 | Flag Reply


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