Amazon Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




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

public void swap(LinkedList<Integer> ll, int index) {
		System.out.println(ll.size());
		System.out.println(index);
		if (ll.size() -1 < index ) {
			System.out.println("given index is greater then list size");
		} else {
			int firstValue = ll.get(index);
			int secondValue = ll.get(ll.size() - index - 1);
			ll.set(index, secondValue);
			ll.set(ll.size() - index - 1, firstValue);
		}
	}

- Rohan Tare July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice use of the Java LinkedList data type, with convenient access to list size. However you need to be careful how you define your index parameter. The problem definition says Kth position from the start and end of a linked list. Since Java uses a zero-based index, if you passed K=2 into your method, you’d actually be swapping 4 & 5, instead of 2 & 7.

- funktional September 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The previous algorithm will fail for some conditions, like linked list having 5 items and we need to swap 4 th element. So we need two pointers for holding the location, once the from node is found then upcoming iterations we need to increment the to pointer from start. Sudo code is below

void swapNodeValue(Node*head,const int n)
{
	if(n < 1)
		return; #wrong n value
	Node* from = NULL;
	Node* to = head;
	int counter = 0;
	bool isFromMet = false;
	
	while(head->next !=NULL)
	{
		counter++;
		if(counter > n)
		{
			to = to->next;
		}
		else if(counter == n)
		{
			from = head;
		}
		head = head->next;
	}
	if(counter < n)
		return; #not enough length
	
	int value = to->data;
	to->data = from->data;
	from->data = value;
}

- aneeshas.kollam July 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Close but I believe your while loop needs to be:

while(head != NULL)
	{
	    ...

- funktional September 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void swap(LinkedList<Integer> ll, int index) {
System.out.println(ll.size());
System.out.println(index);
if (ll.size() -1 < index ) {
System.out.println("given index is greater then list size");
} else {
int firstValue = ll.get(index);
int secondValue = ll.get(ll.size() - index - 1);
ll.set(index, secondValue);
ll.set(ll.size() - index - 1, firstValue);
}
}

- Rohan Tare July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SwapKthElements {

	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		head.next.next = new ListNode(4);
		head.next.next.next = new ListNode(5);
		head.next.next.next.next = new ListNode(7);
		head.next.next.next.next.next = new ListNode(8);
		head = swapKthElements(head, 2);
		printList(head);
	}

	public static ListNode swapKthElements(ListNode head, int k) {
		int n = 0;
		int i = 1; // start from head as index 1
		
		ListNode node = head;
		ListNode node1 = null;
		while (node != null) {
			if (i == k) {
				node1 = node;
			}
			node = node.next;
			i++;
		}
		int i2 = i - k; // kth from last 
		node = head;
		i = 1;
		ListNode node2 = null;
		while(node != null) {
			if (i == i2) {
				node2 = node;
			}
			node = node.next;
			i++;
		}
	
		int temp = node1.val;
		node1.val = node2.val;
		node2.val = temp;
		return head;
	}
}
// output: 1 - 7 - 4 - 5 - 2 - 8

- guilhebl July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void swap(int k){
node tmp = head;
node b = head;
int cntfirst = 1;
int cntsecond = 1;
int cnt =0;
while(tmp != null){
tmp = tmp.next;
cnt++;
}

for(int i=1 ;i <= cnt - k ; i++){
b = b.next;
}

node a = head;
while(cntfirst !=k){
a = a.next;
cntfirst++;

}

int real;
real = b.data;
b.data = a.data;
a.data = real;
}

- hiteshp2489 July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapNodeValue(Node*head,const int n)
{
	Node* from = NULL;
	Node* to = NULL;
	int counter = 0;
	bool isFromMet = false;
	if(n > size())
		return;
	while(head->next !=NULL)
	{
		counter++;
		if(counter > n)
		{
			to = head;
		}
		else if(counter == n)
		{
			from = head;
		}
		head = head->next;
	}
	
	int value = to->data;
	to->data = from->data;
	from->data = value;
}

- Bupa July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

void swapNodeValue(Node*head,const int n)
{
	Node* from = NULL;
	Node* to = NULL;
	int counter = 0;
	bool isFromMet = false;
	if(n > size())
		return;
	while(head->next !=NULL)
	{
		counter++;
		if(counter > n)
		{
			to = head;
		}
		else if(counter == n)
		{
			from = head;
		}
		head = head->next;
	}
	
	int value = to->data;
	to->data = from->data;
	from->data = value;
}

- Bupa July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapNodeValue(Node*head,const int n,int size)
{
	Node* from = NULL;
	Node* to = NULL;
	int counter = 0;
	bool isFromMet = false;
	if(n > size)
		return;
	while(head->next !=NULL)
	{
		counter++;
		if(counter > n)
		{
			to = head;
		}
		else if(counter == n)
		{
			from = head;
		}
		head = head->next;
	}
	
	int value = to->data;
	to->data = from->data;
	from->data = value;
}

- b4bhupal July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Anybody please explain the logic

- rifat July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def swap(l, k):
    """
    Swap the elements in Kth position from the start and end of a link list.
    input: list: 1,2,4,5,7,8 & K=2
    output: 1,7,4,5,2,8
    """
    cur = l.front
    i = 1
    while not (i == l.size - k + 1):
        if i == k:
            a = cur
        cur = cur.next_
        i += 1
    a.value, cur.value = cur.value, a.value

- Ivan July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapNthFromBeginningLast(Node* head, int n)
{
    int len = 0, i;
    struct node *temp = head;
 
    // 1) count the number of nodes in Linked List
    while (temp != NULL)
    {
        temp = temp->next;
        len++;
    }
 
    // check if value of n is not more than length of the linked list
    if (len < n)
      return;
 
    Node* nthFromLast = head;
    Node* nplus1FromLast;
    Node* nthFromBeginning = head;
    Node* nminu1FromBeginning;
 
    for (i = 0; i < len-n; i++){
       nthFromLast = nthFromLast->next;
       if(i==len-n-2)
           nplus1FromLast = nthFromLast->next;   
     }
 
    for (i = 0; i < n; i++){
       nthFromBeginning = nthFromBeginning->next;
       if(i==n-2)
           nminu1FromBeginning = nthFromBeginning->next;     
     }
    //swap place
    Node* temp;
    nplus1FromLast->next = nthFromBeginning;    
    nminu1FromBeginning>next = nthFromLast;   
    temp = nthFromLast->next;
    nthFromLast->next = nthFromBeginning->next;
    nthFromBeginning->next = temp; 
    return;
}

- Moe July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapNthFromBeginningLast(Node* head, int n)
{
    int len = 0, i;
    struct node *temp = head;
 
    // 1) count the number of nodes in Linked List
    while (temp != NULL)
    {
        temp = temp->next;
        len++;
    }
 
    // check if value of n is not more than length of the linked list
    if (len < n)
      return;
 
    Node* nthFromLast = head;
    Node* nplus1FromLast;
    Node* nthFromBeginning = head;
    Node* nminu1FromBeginning;
 
    for (i = 0; i < len-n; i++){
       nthFromLast = nthFromLast->next;
       if(i==len-n-2)
           nplus1FromLast = nthFromLast->next;   
     }
 
    for (i = 0; i < n; i++){
       nthFromBeginning = nthFromBeginning->next;
       if(i==n-2)
           nminu1FromBeginning = nthFromBeginning->next;     
     }
    //swap place
    Node* temp;
    nplus1FromLast->next = nthFromBeginning;    
    nminu1FromBeginning>next = nthFromLast;   
    temp = nthFromLast->next;
    nthFromLast->next = nthFromBeginning->next;
    nthFromBeginning->next = temp; 
    return;
}

- Moe July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapNthFromBeginningLast(Node* head, int n)
{
    int len = 0, i;
    Node *temp = head;
 
    // 1) count the number of nodes in Linked List
    while (temp != NULL)
    {
        temp = temp->next;
        len++;
    }
 
    // check if value of n is not more than length of the linked list
    if (len < n)
      return;
 
    Node* nthFromLast = head;
    Node* nplus1FromLast;
    Node* nthFromBeginning = head;
    Node* nminu1FromBeginning;
 
    for (i = 0; i < len-n; i++){
       nthFromLast = nthFromLast->next;
       if(i==len-n-2)
           nplus1FromLast = nthFromLast->next;   
     }
 
    for (i = 0; i < n; i++){
       nthFromBeginning = nthFromBeginning->next;
       if(i==n-2)
           nminu1FromBeginning = nthFromBeginning->next;     
     }
    //swap place
    nplus1FromLast->next = nthFromBeginning;    
    nminu1FromBeginning>next = nthFromLast;   
    temp = nthFromLast->next;
    nthFromLast->next = nthFromBeginning->next;
    nthFromBeginning->next = temp; 
    return;
}

- Moe July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//============================================================================
// Name        : SwapLinkedListElem.cpp
// Author      : Nitish Raj, Scientist DRDO
// Version     :
// Copyright   : Your copyright notice
// Description : Swapping of elements of Linklist at Kth Pos
//============================================================================

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

struct node{
	int data;
	node *next;

	node(int val)
	{
		data = val;
		next = NULL;
	}

};

void addTolinklistInEnd(node **p, int val){

	node *tmp = new node(val);
	if(*p == NULL) {
		*p = tmp;
		return;
	}
	node *Q = *p;
	while(Q->next != NULL){
		Q = Q->next;

	}
	Q->next = tmp;
}
int determineSize(node *p)
{
	if(p == NULL) return 0;
	int count = 1;

	while(p->next != NULL){
		count++;
		p = p->next;
	}
	return count;
}
void printLinkList(node *p)
{

	if(p == NULL) return;
	while(p !=NULL){
		if(p->next != NULL)
			cout<<p->data<<"->";
		else
			cout<<p->data<<endl;

		p = p->next;

	}

}


void swapAtKthPos(node **p,int k){

	node *temp = *p;
	if(temp == NULL) return ;
	int size = determineSize(*p);
	if(k>size) return;

	if(k>size/2) k = size - k + 1;
	int counter = 1;
	node *tmpNode;
	while(temp != NULL)
	{
		if(counter == k)	tmpNode = temp;
		if(counter == size - k +1){
			int val = temp->data;
			temp->data = tmpNode->data;
			tmpNode->data = val;
			return;
		}
	 temp = temp->next;
	 counter++;
	}

}
int main() {

    // Guys this program is running successfully but if you define any variable of let say
	//   int type , process occurs segmentation fault. Pse tell me reason mail me raj.nitp@gmail.com
    // gcc version 4.4.7 20120313
	// int thisOccurSegmentationfaultOnUncommenting;
	node *start;
	addTolinklistInEnd(&start, 1);
	addTolinklistInEnd(&start, 2);
	addTolinklistInEnd(&start, 3);
	addTolinklistInEnd(&start, 4);
	addTolinklistInEnd(&start, 5);
	addTolinklistInEnd(&start, 6);
	addTolinklistInEnd(&start, 7);
	addTolinklistInEnd(&start, 8);


	cout<<"PRINTING LINKLIST BEFORE SWAP :: ";
	printLinkList(start);

    swapAtKthPos(&start,2);

	cout<<"PRINTING LINKLIST AFTER SWAP :: ";
	printLinkList(start);

	return 0;
}

- raj.nitp@gmail.com August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can it be done in this way:

struct node* first-null, firstprev=null, second=null, secondprev=null;

first=root;

//get the first node from start
k=k-1;
while(K)
{
prevfirst=first; //1
first=first->next; //2
k--;
}

//for 2nd node: since k=2 here, if you go till root->next->next != null, it will always give you last 2nd node from end
second=root;
while(second->next->next)
{ secondprev=second->next; //5
second=second->next->next; //7
}

//now we have both of the nodes, just need to swap
first->next=secondprev->next->next; //2->8
second->next=firstprev->next->next; //7->4
firstprev->next=second; //1->7
secondprev->next=first; //5->2

Solution comes correct but I'm not sure if it is a proper answer to give in the interviews. Please do give suggestions :)

- undefined August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node* f, fp, s, sp;
//f= required node from start, fp= previous of required node from start, s= required node from end, sp=previous of required node from end

//to get from start
fp=root;
k=k-1;
whie(k)
{
fp=f; //1
f=f->next; //2
}

//to get from last: since k=2, if you go till k->next->next != null, it will always return last 2nd node from end
s=root;
while(s->next->next)
{
sp=s->next; //5
s=s->next->next; //7
}

//now we have links to both nodes, just swap them
f->next=sp->next->next; //2->8
s->next=fp->next->next; //7->4
fp->next=s; //1->7
sp->next=f; //5->2

//solution gives correct result but i'm not sure if it is advisable to answer in interviews in this way. Please do give suggestions :)

- Poon August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node* f, fp, s, sp;
//f= required node from start, fp= previous of required node from start, s= required node from end, sp=previous of required node from end

//to get from start
fp=root;
k=k-1;
whie(k)
{
fp=f; //1
f=f->next; //2
}

//to get from last: since k=2, if you go till k->next->next != null, it will always return last 2nd node from end
s=root;
while(s->next->next)
{
sp=s->next; //5
s=s->next->next; //7
}

//now we have links to both nodes, just swap them
f->next=sp->next->next; //2->8
s->next=fp->next->next; //7->4
fp->next=s; //1->7
sp->next=f; //5->2

//solution gives correct result but i'm not sure if it is advisable to answer in interviews in this way. Please do give suggestions :)

- Poon August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oops sorry to have replied same thing 3 times. it wasn't showing whenever i tried to submit so I had to type it 3 times.

- Poon August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* swapKthNodes(Node *head){
    Node *kstart = head, *kend = head, *curr = head;

    int i = 0;
    while(curr->next){
        i++;
        if(i == k){
            kstart = curr;
            kend = head;
        }
        if(i > k){
            kend = kend->next;
        }
        curr = curr->next;
    }

    swap(kstart->val, kend->val);
    return head;
}

- swapnilsj August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;

public class Main {
    public static void main(String args[]) {
        Node head = new Node(1);
        LinkedList originalLinkedList = new LinkedList(head);
        originalLinkedList.addNode(new Node(2));
        originalLinkedList.addNode(new Node(3));
        originalLinkedList.addNode(new Node(4));
        originalLinkedList.addNode(new Node(5));
        originalLinkedList.addNode(new Node(6));
        originalLinkedList.addNode(new Node(7));
        originalLinkedList.addNode(new Node(8));

        System.out.println("----BEFORE----");
        originalLinkedList.printNodes();
        System.out.println("\n"+"----AFTER----");
        originalLinkedList.swap(3);
    }

    static class LinkedList {
        public Node head;
        public Node tail;
        public int length = 1;

        public LinkedList(Node head) {
            this.head = head;
            this.tail = head;
        }

        public void addNode(Node node) {
            length++;
            tail.next = node;
            tail = node;
        }

        public void printNodes() {
            System.out.println("\n");
            Node tempHead = head;
            while (tempHead.next != null) {
                System.out.print(tempHead.value + " ");
                tempHead = tempHead.next;
            }
            System.out.print(tempHead.value);
        }

        public int getNodeValueAt(int index) {
            if (index == 1) {
                return head.value;
            }
            if (index == length) {
                return tail.value;
            }
            Node tempHead = head.next;
            int ctr = 2;
            while (tempHead.next != null) {
                if (ctr == index) {
                    return tempHead.value;
                } else {
                    tempHead = tempHead.next;
                    ctr++;
                }
            }
            return -1;
        }

        public Node getNodeAt(int index) {
            if (index == 1) {
                return head;
            }
            if (index == length) {
                return tail;
            }
            Node tempHead = head.next;
            int ctr = 2;
            while (tempHead.next != null) {
                if (ctr == index) {
                    return tempHead;
                } else {
                    tempHead = tempHead.next;
                    ctr++;
                }
            }
            return null;
        }

        public void swap(int pos) {
            final int nodePosFromEnd = length - (pos - 1);
            final int firstNodeValue = getNodeValueAt(nodePosFromEnd);
            final int secondNodeValue = getNodeValueAt(pos);

            getNodeAt(pos).value = firstNodeValue;
            getNodeAt(nodePosFromEnd).value = secondNodeValue;

            printNodes();
        }
    }

    static class Node {
        public Node next;
        public int value;

        public Node(int value) {
            this.value = value;
            this.next = null;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }


}

- maccaroni August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def swap(head, k):
	if k < 1:
		return head

	current = head
	fromNode = None
	toNode = head
	counter = 0

	while current:
		counter += 1
		if toNode:
			toNode = toNode.next
		if counter == k:
			fromNode = current
			toNode = head
		current = current.next

	if fromNode and toNode:
		temp = fromNode.value
		fromNode.value = toNode.value
		toNode.value = temp
	return head

- domji August 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ {{{public void replaceKthPos(int k){ if(head==null) return; if(k > noOfNodes || k<=0) return; if(k > noOfNodes/2) k = noOfNodes - (k-1); int count = noOfNodes - 2*(k-1); Node curr= head; Node prev=head; while(count > 1){ curr=curr.next; count--; } count=k-1; while(count>0){ curr=curr.next; prev=prev.next; count--; } String temp = curr.val; curr.val = prev.val; prev.val=temp; } }}}}}} - Anonymous August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution:

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;
int main()
{
	list<int> alist={1,2,4,5,7,8,12};
	int K=4;

	int num=alist.size();
	int Kx=min(K, num-K+1);
	int Ky=max(K, num-K+1);


	list<int>::iterator tmp_it, it;
	int val, n;
	for (it=alist.begin(), n=1; it != alist.end(); ++it, ++n){
		if(n==Kx) tmp_it = it;
		if(n==Ky) {val=*tmp_it; *tmp_it=*it; *it=val;}
	}

	for(auto it: alist) cout << it <<" ";
	cout << endl;
}

/*
1 2 4 5 7 8 12 
*/

- echang September 23, 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