Amazon Interview Question


Country: United States




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

3 pointers, p, p->next, p->next->next, do the reverse, then repeat...

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

public void kreverse(int k) {
        SingleLLNode prev = null;
        SingleLLNode temp = this.next;
        int count=0;
        SingleLLNode header = this;
        while(temp!= null) {
            header.next = temp;
            temp =temp.next;
            header.next.next = prev;
            prev = header.next;
            count++;
            if (count == k) {
                while(count > 0) {
                    header = header.next;
                    count--;
                }
                prev = null;
            }
        }
    }

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

this refers to head pointer initially like

Header -> 1->2 -> 3 ->4

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

If the list is 1->2->3->4 and k=2; the above code gives:

1->3->2->4. I thought as per the question, it should have been: 2->1->4->3

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

No add a dummy header before 1 as mentioned in previous comment before. It will work correctly then

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

/* This function prints all nodes that are distance k from a leaf node
   path[] --> Store ancestors of a node
   visited[] --> Stores true if a node is printed as output.  A node may be k
                 distance away from many leaves, we want to print it once */
void kDistantFromLeafUtil(Node* node, int path[], bool visited[],
                          int pathLen, int k)
{
    // Base case
    if (node==NULL) return;
 
    /* append this Node to the path array */
    path[pathLen] = node->key;
    visited[pathLen] = false;
    pathLen++;
 
    /* it's a leaf, so print the ancestor at distance k only
       if the ancestor is not already printed  */
    if (node->left == NULL && node->right == NULL &&
        pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
    {
        cout << path[pathLen-k-1] << " ";
        visited[pathLen-k-1] = true;
        return;
    }
 
    /* If not leaf node, recur for left and right subtrees */
    kDistantFromLeafUtil(node->left, path, visited, pathLen, k);
    kDistantFromLeafUtil(node->right, path, visited, pathLen, k);
}
 
/* Given a binary tree and a nuber k, print all nodes that are k
   distant from a leaf*/
void printKDistantfromLeaf(Node* node, int k)
{
    int path[MAX_HEIGHT];
    bool visited[MAX_HEIGHT] = {false};
    kDistantFromLeafUtil(node, path, visited, 0, k);
}

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

public class Solution {
		
	public static void reverseKNodesLinkedList(List<Integer> list, int k) {	    
	    int len = list.size();
	    int i = 0;
	    int k1 = 0;
	    int kTemp = 0;
	    
	    while ( i + k <= len) {   
	        k1 = i + k - 1;
	        kTemp = i + k;
	        while (i < kTemp && i < k1) {            
	            Integer temp = list.get(i);
	            list.set(i, list.get(k1));
	            list.set(k1, temp);
	            
	            i++;
	            k1--;            
	        }     
	        if (i < kTemp) {
	        	i = kTemp;
	        }
	    }	       
	} 

	public static void main(String[] args) {
	        List<Integer> list = new LinkedList<Integer>();         
	        list.add(1);
	        list.add(2);
	        list.add(3);
	        list.add(4);
	        list.add(5);
	        list.add(6);
	        list.add(7);
	        list.add(8);
	        list.add(9);
	        list.add(10);
	        
	        reverseKNodesLinkedList(list, 5);

	        Iterator<Integer> iter = list.iterator();
	        while (iter.hasNext()) {
	            System.out.print(iter.next() + ",");
	        }                
	}
}

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

/**
 * 
 */
package linkedlist;


import linkedlist.LinkedList;
import linkedlist.Node;

public class ReverseKLL {

	/**
	 * @param args
	 */
	
	Node reverseKLL ( int k , Node head ) {
		
		if ( head == null )
			return head;
		if ( k == 0 )
			return head;
		
		Node t = null;
		Node tNext = null;
		
		if ( head != null )
			t = head.getNext();
		
		if ( t != null )
			tNext = t.getNext();
		
		int k1 = k;
		Node headNew = head;
		Node tNew = t;
		Node tNextNew = tNext;
		
		boolean terminated = false;
		
		while ( k1 > 1 && tNew != null ) {
						
			tNew.setNext(headNew);
			headNew = tNew;
			tNew = tNextNew;
			
			if ( tNextNew != null )
				tNextNew = tNextNew.getNext();
			
			k1--;
		}
		
		if ( tNew == null )
			terminated = true;
		
		if ( terminated )
			head.setNext(null);
		
		t = tNew;
		if ( t != null )
			head.setNext(reverseKLL(k,t));
		
		return headNew;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Object[] a = {1,2,3,4,5,6,7};
		int k = 4;
		
		LinkedList ll = new LinkedList (a);
		Node head = ll.getLL();
		
		ReverseKLL o = new ReverseKLL();
		head = o.reverseKLL(k, head);
		
		ll.display(head);
		
	}

}

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

O(n/2):O(1) time:space

public static void main(String[] args) {
		// TODO Auto-generated method stub
       LinkedList<Integer> list = new LinkedList<>();
       list.add(1);
       list.add(2);
       list.add(3);
       list.add(4);
       list.add(5);
       list.add(6);
       list.add(7);
       reverseKNodes(list, 5);

       for (Integer i : list)
    	   System.out.println(i);
       
	}
	
	public static void reverseKNodes(LinkedList<Integer> list, int k){
		int i,j;
		int loop = list.size() / k;
		
		while (loop != 0){
		  j = loop * k - 1;
		  i = j + 1 - k;
		  while (j > i){
			int temp = list.get(j);
			list.set(j, list.get(i));
			list.set(i, temp);
			j--;
			i++ ;
    	  }
		  loop--;
		}
	}

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

public static void kReverse(Node * st, int k){
		Node *p, *s1, e1;
		int i;
		if(k<2)
			return;
		p = null;
		s1 = e1= st;
		while(s1!=null){
			for(i=0; i< k-1 || e1 != null; i++, e1= e1->nxt);
			
			reverseList(s1,e1);
			
			if(p==null)
				st = s1;
			p = e1;
			s1 = p->nxt;
			e1 = s1;
		}
	}
	
	public static void reverseList( Node * start, Node * end){
		Node *p, *q;
		p = start;
		while(start != end){
			q = start -> nxt;
			start -> nxt = end -> nxt;
			end -> nxt = start;
			start = q;
		}
		end = p;
	}

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

#include <stdio.h>
#include <string.h>
struct list *newnode(int data);
int count1=1;
struct list
{
int data;
struct list *next;
}*p,*p1,*p3,*p4;
main()
{
struct list *root1;
struct list *root=newnode(1);
root->next=newnode(2);
root->next->next=newnode(3);
root->next->next->next=newnode(4);
root->next->next->next->next=newnode(5);
root->next->next->next->next->next=newnode(6);
root->next->next->next->next->next->next=newnode(7);
root->next->next->next->next->next->next->next=newnode(8);
printf(" Before Doing Swapping ");
printf("\n");
linkedlist(root);
printf("\n");
int count =no_nodes(root);
root1=root;
do_swap(root,root1,count,3);
printf(" After Doing Swapping ");
printf("\n");
linkedlist(root);
printf("\n");
}
void linkedlist(struct list *tree)
{
while(tree!=NULL)
{
printf(" %d",tree->data);
tree=tree->next;
}
}
void do_swap(struct list *root,struct list *root1,int count,int n)
{
int count1=count-n;
int i=1;
int j1=1;
if(count1==n)
{
printf(" Cannot Be Done ");
exit(0);
}
if(n>count)
{
printf(" Larger Size Cannot Be Done ");
exit(0);
}
while(i<=n-1)
{
if(i==n-1)
{
p=root->next;
p1=root->next->next;
i++;
}
else
{
root=root->next;
i++;
}
}
while(j1<=count1)
{
if(j1==count1)
{
p3=root1->next;
p4=root1->next->next;
j1++;
}
else
{
root1=root1->next;
j1++;
}
}
root->next->next=NULL;
root->next=NULL;
root1->next->next=NULL;
root1->next=NULL;
root->next=p3;
p3->next=p1;
root1->next=p;
p->next=p4;
}

int no_nodes(struct list *tree2)
{
while(tree2!=NULL)
{
count1++;
tree2=tree2->next;
}
return count1-1;
}

struct list *newnode(int data)
{
struct list *tree1=(struct list *)malloc(sizeof(struct list));
tree1->data=data;
tree1->next=NULL;
return tree1;
}

- Uda Anil Kumar March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node reverse(Node start, int k){
		Node prev = null;
		Node current = start;
		Node next = null ;
		int count = 0;
		while (current != null && count <k) {
			next = current.next;
			current.next = prev;
			prev = current;
			current = next;
			count++;
		}
		if(next != null){
			start.next = reverse(next, k);
		}
		return prev;
	}

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


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