Amazon Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
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.
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;
}
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);
}
}
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
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
//============================================================================
// 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;
}
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 :)
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 :)
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 :)
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;
}
}
}
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
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
*/
- Rohan Tare July 27, 2016