Amazon Interview Question


Country: United States




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

Here is the function that works with a LinkedList class that I implemented.

public Element<T> reverseEveryK(int k) {
        Element<T> currHead = head; // to iterate
        Element<T> iterator = head;
        Element<T> tempIterator = iterator;
        Element<T> prevHead = null;
        int len = 1;
        while(iterator.getNext() != null) {
            if(len%k == 0 || iterator.getNext().getNext() == null) {
                //iterator = (iterator.getNext().getNext() == null)?iterator.getNext():iterator;
                tempIterator = iterator.getNext();  // store next in chain
                iterator.setNext( null );   // make this the new tail
                Element<T> kListTail = reverseList(currHead); // tail end recursion
                kListTail.setNext( prevHead );
                prevHead = iterator;
                currHead = tempIterator;
                iterator = tempIterator;    // move to next element
            }
            else {
                iterator = iterator.getNext();
            }
            len++;
        }

        tempIterator.setNext( prevHead );
        this.head = tempIterator;   // for printing entire list
        return tempIterator;
    }

The reversal function implements tail-end recursion. Here it is:

private Element<T> reverseList(Element<T> head) {
        if(head.getNext() == null) {
            //this.head = head;
            return head;
        }
        Element<T> curr = reverseList(head.getNext());
        curr.setNext(head);
        head.setNext( null );
        return head;
    }

- Killedsteel February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Important thing to note: This question demands for reversing a linked list, followed by the return of the _tail_ element (unlike usual reversal, which requires the return of the head).

Please ignore any comments/code using the "this" operator. That is something I need for this function to work with my class.

Edge case left as exercise: The original input list, is of length less than k. I'd recommend adding a small while loop in the beginning of the above function that counts till (currHead.getNext() == null || elemCount >= k)

- Killedsteel February 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverse_every_k(Node*& head, int k)
{
	Node *prev, *cur, *tmp, *new_head;
	prev = NULL;  cur = head;
	while( cur ) {
		*tmp_prev = prev; 
		Node *tmp_tail = cur; 		
		
		int cnt = k;
		while( cnt>0 ) {
			tmp = cur->next;
			cur->next = prev;
			prev = cur;
			cur = tmp;
			cnt--;
			if( !cur ) break;
		}
		
		if( !tmp_prev ) 
			new_head = prev;
		else 
			tmp_prev->next = prev;

		tmp_tail->next = cur;
		prev = tmp_tail;
	}
	head = new_head;
}

- mombasa February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* reverseKnodes(Node *curnt, int k){
    Node *temp = NULL;
    Node *prev = NULL;
    
    while(curnt != NULL && k > 0){
        temp = curnt ->next;
        curnt->next = prev;
        prev = curnt;
        curnt = temp;
        k--;
    }
    
    temp = prev;
    
    while(temp->next != NULL)
        temp = temp->next;
    temp->next = curnt;
    curnt = prev;
    return curnt;
}


Node* ReverseSpecial(Node *n, int k){
    Node *head = n;
    Node *tail = n;
    
    int i = 0;
    while(n != NULL && i < k){
        n = n->next;
        if(i < k - 1)
            tail = tail->next;
        i++;
    }
    
    if(n != NULL)
        tail->next = ReverseSpecial(n, k);
    
    head = reverseKnodes(head, k);
    
    return head;
}

- NECO February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

private LinkedListNode<T> Reverse(LinkedListNode<T> head, int k)
{
LinkedListNode<T> current = head;
LinkedListNode<T> last = null;
int i =0;
while(current != null)
{
i++;
if(i%k == 0)
{
head.Next = Reverse(current.Next, k);
break;
}

LinkedListNode<T> next = current.Next;
current.Next = last;
current = next;
}
return current;
}

- kc February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private LinkedListNode<T> Reverse(LinkedListNode<T> head, int k)
        {
            LinkedListNode<T> current = head;
            LinkedListNode<T> last = null;
            int i =0;
            while(current != null)
            {
                i++;
                if(i%k == 0)
                {
                    head.Next = Reverse(current.Next, k);
                    break;
                }

                LinkedListNode<T> next = current.Next;
                current.Next = last;
                current = next;
            }
            return current;
        }

- kc February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

missed
last = current
in the loop

- Anonymous February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And
return last;
instead of
return current;

- kc February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node reverse(Node head, int k) {
        // after reverse, the return node is
        // the last node in the first K nodes in the original list
        // which is also the head node in the reversed list
        Node returnNode = null;

        // for the ith K sub list, the two "previous" pointers
        // would point to the (i-1)th K sub list's head and tail "after" reverse
        // This means, after reversing 3,2,1, previousTail points to 3 and previousHead points 1
        Node previousTail = null;
        Node previousHead = null;

        while(head != null) { // not reached the end of the list
            Node tail = head;
            for(int i = 1; i < k & tail.next() != null; i ++) {
                tail = tail.next();
            }
            Node nextHead = tail.next();
            reverse(head, tail);
            if( previousHead == null || previousTail == null) {
                // first K sub list
                previousHead = tail;
                previousTail = head;
                returnNode = tail;
            } else
                previousTail.setNext(tail);

            head.setNext(nextHead);
            head = nextHead;
        }
        return returnNode;
    }

    private Node reverse(Node current, Node tail) {
        if(current == tail) {
            return current;
        }

        Node next = reverse(current.next(), tail);
        next.setNext(current);
        return current;
    }

- zouzhile February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node reverseList (Node head, int k) {
    Node ret_value = null;

    int counter = 0;
    Node previous = null;
    Node headSequence = head;
    while (head != null) {
        counter++;
        if ( counter <= k) {
       	    Node next = head.next;
            head.next = previous;
            previous = head; 
            head = next;
        } else {
            counter = 0;
            headSequence.next = head;
            if ( !ret_value )
		ret_value = previous;
            previous = null;
        }
    }
    
    return previous;
}

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

struct node * reverse(struct node *head)
{
     struct node *p=(struct node *) malloc(sizeof(struct node));
     struct node *q=(struct node *) malloc(sizeof(struct node));
     struct node *temp=(struct node *) malloc(sizeof(struct node));
     temp=head;
     p=head->next;
     head->next=NULL;
     while(p!=NULL)
     {
         q=p->next;
         p->next=head;
         head=p;
         p=q;
     }
     return temp;
}

void revert(struct node *head,int k)
{
     int counter=0,found=0;
     struct node *p=(struct node *) malloc(sizeof(struct node));
     struct node *q=(struct node *) malloc(sizeof(struct node));
     struct node *start=(struct node *) malloc(sizeof(struct node));
     while(head!=NULL)
     {
          p=head;
          while(counter++<k-1 && head!=NULL)
             head=head->next;
          if(head==NULL)
             break;
          q=head->next;
          head->next=NULL;
          if(found==0)
          {
             start=head;
             found=1;
          }
          head=q;
          while(--counter>0 && head!=NULL)
             head=head->next;
          if(head==NULL)
             head=q;
          reverse(p)->next=head;
          counter=0;
          head=q;
     }
     while(start != NULL)
     {
        printf("%d\t",start->val);
        start = start->next;
     }
     printf("\n");
}

- Nitin March 02, 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