Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

There are many ways to do it.. One simple technique is
1) Traverse to the middle node
2) Seperate the list starting from the next node of middle node.
So now you will have two list...

List1 - header to middle node
List2 - next of middle node to tail

3) Do a two- way merge on List1 and List2

complexity: O(n), n is the total no of nodes in the list,
space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm..

- arsragavan March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are right.
For your question : "space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm."

my answer is that when you are traversing to middle of the list you are just forwarding the pointer towards middle node, which is O(1) space operation.
Hence it is surely O(1) space solution.

- pavi.8081 March 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but how would you know which node is middle node. unless you traverse till the end you will not know the middle element. so we need to traverse again then it would be O(n2).
Please clarify.

- shreyask March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Middle node can be found by using fast and slow pointer. When fast pointer will reach to the last node, slow pointer will point the middle node. Then merge can be done.

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

Node convertList(Node first, Node middle)
{
  if(middle == null)
     return null;

  Node tempFirst = first.next;
  Node tempMiddle = middle.next;
  
  first.next = middle;
  middle.next = convertList(tempFirst, tempMiddle);

  return first;
}

- Anonymous March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the pattern contains more alphabets, such that, say resultant should be like a1->b1->c1-d1-a2->b2->c2-d2-a3->b3->c3-d3, then do we need to have a 'n'-way merge mechanism?

- Learner March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

*curr = head;
* temp = head;
for(int i=0; i < length/2 ; i++) {
  	curr=curr->next;
}
while(cure->next!=null) {
	temp1 = temp->next;
	temp2 = curr->next;
	temp->next = curr;
	curr->next =temp1;
	temp = temp1;
	curr = temp2; 
}

- Rahul June 13, 2015 | 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