Amazon Interview Question for SDE-2s


Country: India
Interview Type: Written Test




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

1. Traverse k nodes forward and set temp to the k+1th node
2. Reverse k nodes traversed in step 1.
3. Set next of the last node in this k length list to temp.
4. Traverse next k nodes which are to be skipped.
5. Recursively call steps 1-3 for reversing next k nodes.

Code and Credits: IDeserve (Reverse every alternate k nodes of a Linked List)

- r.s December 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct listNode
{
	int data;
	listNode *next;
	listNode(int val) :data(val), next(NULL){}
};

listNode * createLinkedList(int numberOfNodes)
{
	listNode *head = new listNode(1);
	int i = 2;
	listNode *p = head;
	while (i <= numberOfNodes)
	{
		p->next = new listNode(i);
		p = p->next;
		i++;
	}
	return head;
}


void printLinkedList(listNode *head)
{
	while (head != NULL)
		cout << head->data << ", ", head = head->next;
	cout << endl;
}

listNode * reverseFirstKNodes(listNode *head, int k)
{
	if (head == NULL || head->next == NULL)
		return head;
	listNode *p = head;
	listNode *q = head->next;
	while (k > 1 && q != NULL)
	{
		listNode *r = q->next;
		q->next = p;
		k--;
		p = q;
		q = r;
	}
	head->next = q;
	return p;
}

void reverseKAlternateNodes(listNode *&head, int k)
{
	if (k < 2 || head == NULL || head->next == NULL)
		return;
	listNode *p = head;
	listNode *tail = NULL;
	head = NULL;

	while (p != NULL)
	{
		if (head == NULL)
		{
			head = reverseFirstKNodes(p, k);
			p = head;
		}
		else
		{
			tail->next = reverseFirstKNodes(p, k);
			p = tail->next;
		}

		// skip 2*k -1 nodes

		int  i = 2 * k - 1;
		while (i > 0 && p != NULL)
		{
			p = p->next;
			i--;
		}

		if (p != NULL)
		{
			tail = p;
			p = p->next;
		}
	}
}

int main()
{
	listNode *head = createLinkedList(11);
	reverseKAlternateNodes(head, 3);
	printLinkedList(head);
	// free list head

	getchar();
	return 0;
}

- siva.sai.2020 November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

duplication of your own question: question?id=5766819132473344.
Difference is only in order (begin from end, begin from start)

- zr.roman November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node reverseKAlt(Node head, int k){
if(head == null ) return head;

Node p = head;
Node q = head->next;

p->next = null;

while(q!= null){
var r = q->next;
p = q;
if( (k/3) % 2 != 0)
	q->next = p;
q = r
}
return p;
}

- ankushbindlish November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not work,
returns 1 node, which point to himself (forever loop).

- zr.roman November 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

using System;

namespace SinglyLinkedListReverse {

    class Program {

        private static void ReverseAltKNodes<T>( ref Node<T> headNode, int k ) {

            int i = -1;
            var arr = new Node<T>[ k ];
            var currNode = headNode;
            Node<T> prevNodeBeforeGroup = null;

            while ( currNode != null ) {

                i++;

                if ( i <= k*2 - 1 && i >= k) {
                    prevNodeBeforeGroup = currNode;
                    currNode = currNode.NextNode;
                    i = ( i == k * 2 - 1 ) ? -1 : i;
                    continue;
                }

                arr[ i ] = currNode;
                if ( currNode.NextNode != null && i < k - 1 ) {
                    currNode = currNode.NextNode;
                    continue;
                }
                
                var nextNode = currNode.NextNode;
                for ( int j = i; j > 0; j-- ){
                    arr[ j ].NextNode = arr[ j - 1 ];
                }
                arr[ 0 ].NextNode = nextNode; 

                if ( prevNodeBeforeGroup == null )
                     { headNode = currNode; }
                else { prevNodeBeforeGroup.NextNode = currNode; }

                currNode = nextNode;

                prevNodeBeforeGroup = arr[ 0 ];
                arr = new Node<T>[ k ];
            }
        }

        private const int limit = 18;

        private static Node<int> CreateSinglyLinkedList( int n = 1 ) {

            var node = new Node<int> { Data = n };
            if ( n < limit ) {
                node.NextNode = CreateSinglyLinkedList( ++n );
            }
            return node;
        }

        public class Node<T> {
            public T Data { get; set; }
            public Node<T> NextNode { get; set; }
        }

        static void Main(string[] args) {
         
            var headNode = CreateSinglyLinkedList();
            ReverseAltKNodes( ref headNode, 4 );

            var currNode = headNode;
            while ( currNode != null ) {
                 Console.WriteLine( currNode.Data );
                currNode = currNode.NextNode;
            }
            Console.ReadLine();
        }
    }
}

- zr.roman November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdlib.h>
#include <iostream>
using namespace std;
    // to reverse the linkedlist, I will use recursion to the end/right of the list, reverse the last k nodes there, return its new head, and link the last reversed list to the left side list. and operate on the section with k nodes, and then on next left k nodes... until reach the head    
    
struct ListNode{
    int value;
    ListNode* next;
    ListNode(int v) : value(v), next(NULL){}    
};    

ListNode* reverseKNodes(ListNode* head, int k, int sec){
    
    
    
    // find the head of the next section (k nodes)
    ListNode* curr = head;
    for(int i = 0; i < k; i++){
        
        if(curr == NULL){
            return head;    
        }
        
        curr = curr->next;        
    }    
    
    ListNode* end = head;
    for(int i = 0; i < k - 1; i++){
        end = end->next;
    }    
    
    ListNode* next = curr;        // head of the next section
    
    // reverse the this section (k nodes) only if this is an odd section
    if(sec % 2 == 1){
        ListNode *prev = NULL;
        curr = head;
        for(int i = 0; i < k; i++){
            ListNode* t = curr->next;
            curr->next = prev;
            prev = curr;
            curr = t;
        }
        
        head->next = reverseKNodes(next, k, sec + 1);        // link to the next section
        
        // the new head of this section is prev
        return prev; 
    }
    else{
        
        end->next = reverseKNodes(next, k, sec + 1);        
        return head;
    }
}

ListNode* reverse(ListNode* head, int k){
    return reverseKNodes(head, k, 1);
}
 
 
int main(){
    
    ListNode* head = new ListNode(0);
    
    ListNode* curr = head;
    
    for(int i = 0; i < 21; i++){
        curr->next = new ListNode(i+1);
        curr = curr->next;
    }
    
    ListNode* result = reverse(head, 5);
    
    cout << "******************" << endl;
    
    while(result != NULL){
        cout << result->value << " ";
        result = result->next;
    }
    cout << endl;
    
    return 0;
}

- PoWerOnOff November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What I understood is to reverse the first K nodes in the case of alternative we need to navigate ti the staring node.
Note. I dont have a compiler but is the idea.

public class ListNode
{
    int Data;
    ListNode Next;
}

public ReverseFirstKNodes(ListNode list, int k)
{
    if (list == null)
        return null;

    ListNode root = new ListNode();
    ListNode p = list;
    ListNode last = list;

    int i = 0;
    while (i < k && p != null)
    {
        ListNode q = p.Next;
        p.Next = root.Next;
        root.Next = p;
        p = q;
        i++;
    }


    last.Next = p;
    return root.Next;
}

- hnatsu December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in O(n), read the linked list in reverse order

public String getKElementsReverse(int n, int k){
		String ret = ",";
		boolean extra = false;
		int seek= 0;
		while((seek + k) <= n){
			seek += k;
			if(seek != n){
				seek++;
				extra = true;
			}
			else{
				extra = false;
			}
		}
		if(extra){
			seek--;
		}
		Node temp = this;
		for(int i= seek; i<=n; i++){
			temp = temp.prev;
		}
		while(temp != null){
			//temp = temp.prev;
			for(int i=k; i>0; i--){
				ret += temp.getContent() + ",";
				temp = temp.prev;
			}
			if(temp != null){
				temp = temp.prev;
			}
			ret += ";";
		}
		return ret;
	}

then display nodes from front, with blocks of size k extracted from the end of "ret"

static String printKPartsReversed(Node temp, String[] kParts, int n, int k){
		//temp= temp.getNext();
		String full = "";
		int count = 0;
		int seek = 0;
		int l = kParts.length;
		while(seek < n){
			full += kParts[l -1 - count++];
			for(int i=0; i<k; i++){
				temp = temp.getNext();
			}
                       if(temp.getNext() == null){
                          //indicates tail reached
				break;
			}
			seek += k+1;
			full += temp.getContent() + ", ";
			temp = temp.getNext();
		}
		return full;
	}

Overall time complexity= O(n)
tests on cases that i considered ... but test it no your input before using

- sojourner6 December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) time and O(N) space. Solution written in C#:

public static void Reverse (ref Node root, int number)
        {
            if (number < 0)
                throw new ArgumentOutOfRangeException("number");

            Stack<Node> reversedNodes = new Stack<Node>();

            Node iteratingNode = root;
            for (int cnt = 0; cnt < number && iteratingNode != null; iteratingNode = iteratingNode.Next, cnt++ ) {
                reversedNodes.Push(iteratingNode);
            }

            var linkWith = iteratingNode;

            Node previous = null;
            
            for (; reversedNodes.Count > 0;)
            {
                var node = reversedNodes.Pop();
                if (previous == null)
                    root = node;
                else
                    previous.Next = node;

                previous = node;
            }

            if (previous != null)
                previous.Next = linkWith;

}

- aurelian.lica December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* reverseListAlt(node *record, int k)
{
  int count= 0;
  node* head, *prev;
  node* first= record;
  node* last= record;

  if (k<0)
    head= record;
  else if(k==0)
    head= reverseList(first, NULL);
  else
  {
    //reverse first k nodes
    while(count < k && last!= NULL)
    {
      last= last->next;
      count++;
    }
    head= reverseList(first, last);

    // Reverse Alternate k nodes
    while(last != NULL)
    {
      //Skip k ndoes
      while(count > 0 && last!=NULL)
      {
        prev= last;
        last= last->next;
        count--;
      }

      //Reverse K nodes
      first= last;
      while(count < k && last!=NULL)
      {
        last= last->next;
        count++;
      }
      prev->next= reverseList(first, last);
    }
  }

  return head;
}

node* reverseListAlt(node *record, int k)
{
  int count= 0;
  node* head, *prev;
  node* first= record;
  node* last= record;

  if (k<0)
    head= record;
  else if(k==0)
    head= reverseList(first, NULL);
  else
  {
    //reverse first k nodes
    while(count < k && last!= NULL)
    {
      last= last->next;
      count++;
    }
    head= reverseList(first, last);

    // Reverse Alternate k nodes
    while(last != NULL)
    {
      //Skip k ndoes
      while(count > 0 && last!=NULL)
      {
        prev= last;
        last= last->next;
        count--;
      }

      //Reverse K nodes
      first= last;
      while(count < k && last!=NULL)
      {
        last= last->next;
        count++;
      }
      prev->next= reverseList(first, last);
    }
  }

  return head;
}

- Manku September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the function. Well tested.

node* reverseList(node *head, node* last)
{
  node* prev= last;
  node* cur=head;
  node* next;

  if (head == NULL)
    return NULL;

  while(cur != last)
  {
    next= cur->next;
    cur->next= prev;
    prev= cur;
    cur= next;
  }

  return prev;
}

node* reverseListAlt(node *record, int k)
{
  int count= 0;
  node* head, *prev;
  node* first= record;
  node* last= record;

  if (k<0)
    head= record;
  else if(k==0)
    head= reverseList(first, NULL);
  else
  {
    //reverse first k nodes
    while(count < k && last!= NULL)
    { 
      last= last->next;
      count++;
    }
    head= reverseList(first, last);

    // Reverse Alternate k nodes
    while(last != NULL)
    {
      //Skip k ndoes
      while(count > 0 && last!=NULL)
      { 
        prev= last;
        last= last->next;
        count--;
      }

      //Reverse K nodes
      first= last;
      while(count < k && last!=NULL)
      {
        last= last->next;
        count++;
      }
      prev->next= reverseList(first, last);
    }
  }

  return head;
}

- Manku September 08, 2016 | 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