Amazon Interview Question for Applications Developers


Country: India
Interview Type: Written Test




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

Syntax might be a little off, haven't done Java in a while

public static Node reverseList(Node head, Node prev){
		Node temp = head.next;
		head.next = prev;
		
		if(temp != null){
			return reverseList(temp, head);
		}
		return head;
	}

- Interviews Suck November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good job

- meow November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

///recursive reverse will work
reverse(Node* node)
{
if (node == NULL) return;
if (node->next == NULL)
{
head = node;
return;
}
reverse(node->next);
node->next->next = node;
node->next = null;
}

- Tarun Kumar October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That uses n pointers.

- mike tyson October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm guessing that accessing the pointers that make up the linked list (node->next->next..) doesn't count toward the 'one pointer' we can use. If this assumption is correct, 'head' is the one pointer in this solution.

- Michael.J.Keating November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It uses an O(n) stack secretly.
And on this stack there are n pointer objects.

The question is dumb.

- S O U N D W A V E November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Urik: You are brainless.

- Anonymous November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous, I know. But I make up for it with an 9.7/10 appearance/body.

- S O U N D W A V E November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Urik: Do you have an clue what 9.7/10 even means, you brainless idiot?

- Anonymous November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am here. Really her. Sow their.

- type O monster November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a tail recursive solution using one pointer. O(n):

public static LinkedList reverse(LinkedList head, LinkedList reversed){
	if(head==null) return reversed;

	LinkedList current = new LinkedList();
	current = head;
	head = head.next;
	current->next = reversed;

	return reverse(head, current);
}

- zahidbuet106 December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 8 vote

A good coder may get irritated when he sees this type of purposeless questions, Wont even waste my time even trying it.

- ab7 November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 votes

+ 10^6

- S O U N D W A V E November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

List* reverse_list(List* head)

{

    List* current = head;

    List* result = NULL;

    while(current != NULL)

    {

        List* next = current->next;

        current->next = result;

        result = current;

        current = next;

    }

    return result;

}

I got this solution from one of the blogspot sites. Unfortunately I am not able to paste link here.


I think, this makes some sense. But if you consider result as a separate pointer storage. This uses two pointers but without any additional storage.

I feel takes o(n)

Is this correct?

- rengasami21 November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution uses 3 pointers - current, result and next. It is as good as using next, previous and current (in fact, the same approach). Although it works fine, it doesn't fulfill the "1 pointer" criteria of the question.

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

@mayank.hey : You are right, I can eliminate next pointer totally here. Thats an additional variable. But how to eliminate the other one? I tried a lot for one pointer and no Additional DS. At the max I can reach here. Can you help me?

- rengasami21 November 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

List* reverse_list(List* head)

{

    List* current = head;

    List* result = NULL;

    while(current != NULL)

    {

        List* next = current->next;

        current->next = result;

        result = current;

        current = next;

    }

    return result;

}

This code looks good to me but it uses two pointers (considering result as a pointer) and it doesnt use any additional storage.

I found it in one of the blogspot site.

It takes O(n). Is this correct?

- rengasami21 November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3

- anony November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

recursion( List *node)
{
Node *p;
if(node->next != NULL)
p = recursion(node->next);
else
return node;
p->next = node;
return node;
}

- Sandeep November 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code will create a loop

- meow November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Node {
   int val;
   Node *next;
}*Node;

void swap(Node *a, Node *b);
void reverselist(Node *head) {
   Node* temp = head;
   while (temp->next != NULL) {
      temp = temp->next;
   }
   while (head <= temp) {
      swap(head++, temp--);
   }
}

void swap(Node *a, Node *b) {
   a->val = a->val ^ b->val;
   b->val = a->val ^ b->val;
   a->val = a->val ^ b->val;
}

- sriram87 November 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Made something in java

public static Node reverse(Node head) {
	if(head == null)
		return(null);
		
	Node n = reverse(head.next);
	if(n == null)
		n = head;
	else {
		head.next = null;
		n.next = head;
	}
	return(head);
}

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

Hi there my version with 1 pointer in java looks as follows (I do assume head is given from the reversed list structure)

public void reverse() {
		reverse(head).next = null;
	}

	private Node reverse(Node current) {
		if (current.next == null) {//last node
			head = current;
			return current;
		} else {
			reverse(current.next).next = current;
		}
		return current;
	}

- Jakub November 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

void reverse_single_pointer(node **head)
{
	node *newone = NULL;

	while(*head)
	{
		(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));
		newone = (node*)((int)(*head)->link ^ (int)(newone));
		(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));

		*head = (node*)((int)(*head) ^ (int)(newone));
		newone = (node*)((int)(*head) ^ (int)(newone));
		*head = (node*)((int)(*head) ^ (int)(newone));
	}

	*head = newone;
}

- algos October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that uses at least 2 pointers

- mike tyson October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

but you are onto something

try xor as much as possible

- mike tyson October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol ok

- mike tyson October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

could be a trick question.
Instead of extra pointer, declare extra int, and keep casting it back and forth.

- mike tyson October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

+1 for solution.
No idea, if Amazon still ask these types of questions. May be there will be other additional constraints or conditions.

- Ajeet November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

all I can think of is to use 2 pointers

- Jay November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

that uses 2 pointers, doesn't matter how you try to sugar coat it

the question is dumb but u _might_ be able to get an idea from "xor linked lists" (google it)

- S O U N D W A V E November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Not sure if this can be a solution but here is the code, seems I am using 1 pointer:

static Node<Integer> reverseList(Node<Integer> node) {
        Node<Integer> last = node;
        while (last.getNext() != null) {
            last = last.getNext();
        }

        while (node != last) {
            if (last.getNext() == null) {
                last.setNext(node);
                node = node.getNext();
                last.getNext().setNext(null);
            }
            else {
                Node<Integer> temp = last.getNext();
                last.setNext(node);
                node = node.getNext();
                last.getNext().setNext(temp);
            }
        }
        return node;
    }

- elbek November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

like algos u use parameter as another more ptr it is 2 or greater

- Vincent November 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Node<Integer> temp - this is an extra pointer.

- shinsetsu November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

do it using three pointers:

reverseList(List list) {
Node previous = null;
Node current = list.head();
Node tmp = null;
while (current != null) {
tmp = current.next;
current.next = previous;
previous = current;
current = tmp;
}
}

- Anonymous October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

/**
 * algorithm to reverse a singly linked list using one pointer 
 * without any additional datastructures
 * @author ksjeyabarani
 *
 */
public class ReverseSingleLinkedList {

	public static void main(String[] args) {
		ReverseSingleLinkedList r = new ReverseSingleLinkedList();
		LList<Integer> l = new LList<Integer>();
		l.add(1);
		l.add(2);
		l.add(3);
		l.add(4);
		System.out.println("List is " + l);
		l.reverse();
		System.out.println("List after 2 pointer reverse " + l);
		l.reverse();
		System.out.println("List reversed back to original " + l);
		l.reverseWithOnePointerAndNoExtraDS();
		System.out.println("List WithOnePointerAndNoExtraDS " + l);
	}
	
	private static class LList<T> {
		
		Node<T> head;
		
		private int size;
		
		public void add(T data) {
			Node<T> n = new Node<T>(data);
			if(null == head) {
				head = n;
			} else {
				Node<T> x = head;
				while(x.next != null) {
					x = x.next;
				}
				x.next = n;
			}
			size++;
		}
		
// uses three pointers - can be improved to use two pointers by accessing third node using two.next
		public void reverse() {
			if((null == head) || (head.next == null)) {
				return;
			}
			
			Node<T> one = head;
			Node<T> two = one.next;
			Node<T> three = two.next;
			
			head.next = null;
			while(two != null) {
				two.next = one;
				one = two;
				two = three;
				if( null != two) {
					three = two.next;
				}
			}
			
			head = one;
		}
		

		public void reverseWithOnePointerAndNoExtraDS() {
			if((null == head) || (head.next == null)) {
				return;
			}
			int mid = size/2;
			int x = 0;
			while (x < mid) {
				T temp;
				temp = get(x).data;
				get(x).data = get((size-1)-x).data;
				get((size-1)-x).data = temp;
				x++;
			}
		}
		
		public Node<T> get(int index) {
			if((index >= size) || (index < 0)) {
				return null;
			}
			Node<T> n = head;
			for(int x = 0; x<index; x++) {
				n = n.next;
			}
			return n;
		}
		
		public String toString() {
			if(null == head)
				return null;
			
			StringBuilder sb = new StringBuilder();
			Node<T> x = head;
			while(x != null) {
				sb.append(x.data + " ");
				x = x.next;
			}
			return sb.toString();
			
		}
		
		private static class Node<T> {
			T data;
			Node<T> next;
			
			public Node(T data) {
				this.data = data;
			}
			
			@Override
			public String toString() {
				return data + " ";
			}
		}
	}
}

- ksjeyabarani October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

no

- anon November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public void reverse(){
		if(head != null){
			/*
			 *  A -> B -> C -> D -> E -> F
			 *  F -> E -> D -> C -> B -> A
			 */
						
			Node nextNode = head.getNext(); //B
			
			//set head's next to null
			head.next = null;
			
			while(nextNode != null){

				Node currentNextNode = nextNode.getNext(); //C
								
				// set the nextNode to head
				nextNode.setNext(head); //B --> A
								
				// B is tempHead node now
				head = nextNode;// (head)B --> A
				
				//get original next to B
				nextNode = currentNextNode;					
			}			
		}
	}

- Amandeep Dhanjal November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its easy, you just store the XOR of the previous pointer and the next pointer in the pointer part of the LinkedList Node and then just extract the Node's next pointer or the previous pointer whenever required by using one of the prev/next pointers. You keep doing this and storing the XOR instead of just the next pointer and you can reverse the linked list using only one pointer.

- bhajatin November 02, 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