Amazon Interview Question SDE1s
Country: India
Interview Type: Written Test
I think there is an error in #3 above. The correct description should be:
3.now in a loop make y=y->next and z=z->next until you reach the end from
y
.
z
then contains the kth node from end.
sorry, formatting got screwed up ... looks like I cannot edit my response. What I meant to say was that in #3, instead of "until you reach the end from z. y then contains the kth node from end", it should read "until you reach the end from y. z then contains the kth node from end"
1) Take two pointers p,q,r points to the head
2) Move p up to kth node in list and point r here
3) Move p, q(starts from head) both upto p reaches end of the list
4) Now r at kth node from begin and q at kth node from end, swap r,q
struct node *swapKthNode(struct node *head,int k)
{
struct node *p=head,*q=head,*r,*temp;
for(int count=0;count<k;count++)
p=p->next;
r=p;
while(p->next!=NULL)
{
p=p->next;
q=q->next;
}
#swap r and q
temp = r->next;
r->next = q->next;
q->next = temp;
return head;
}
typedef struct _item {
item* next;
void* value;
} item;
void swapKthElem(linkedlist list, int k) {
item* head = list->head;
item* kElemFromHead = NULL;
item* kElemFromTail = NULL;
int i = k;
// scan the list for the kth element from head and kth element from tail
while(head!=NULL) {
if( i-- == 0) {
kElemFromHead = head;
kElemFromTail = list->head;
}
if(kElemFromTail!=NULL) {
kElemFromTail = kElemFromTail->next;
}
head = head->next;
}
// swap only if kth item from head and tail is not the same element
if( kElemFromHead != NULL && kElemFromTail != NULL && kElemFromHead!=kElemFromTail ) {
tmp = kElemFromHead->value;
kElemFromHead->value = kElemFromTail->value;
kElemFromTail->value = tmp;
}
}
Let X be the kth node from beginning and Y be the kth node from end. Following are the interesting cases that must be handled.
1) Y is next to X
2) X is next to Y
3) X and Y are same
4) X and Y don’t exist (k is more than number of nodes in linked list)
SOLUTION USING SINGLE LINK LIST
#include<stdio.h>
#include<stdlib.h>
int main()
{
struct node
{
int data;
struct node *next;
}*head;
head=NULL;
int i,num,k,n;
struct node *temp,*temp1,*temp2;
printf("enter the number=");
scanf("%d",&num);
scanf("%d",&k);
for(i=1;i<=num;i++)
{
scanf("%d",&n);
if(head==NULL)
{
head=malloc(sizeof(struct node));
head->data=n;
temp=head;
}
else
{
temp->next=malloc(sizeof(struct node));
temp->next->data=n;
temp=temp->next;
}
}
temp->next=NULL;
temp=head;
i=1;
while(temp!=NULL)
{
if(i==k)
{
temp1=temp;
temp=temp->next;
}
else if(i==num-k-1)
{
temp2=temp;
temp=temp->next;
}
else
{
temp=temp->next;
}
i=i+1;
}
temp=temp1;
int c=temp->data;
temp=temp2;
int d=temp->data;
temp=temp1;
temp->data=d;
temp=temp2;
temp->data=c;
temp=head;
while(temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
return 0;
}
#include<stdio.h>
struct node
{
int value;
struct node *next;
};
struct node *head;
void createLinkList(void);
void swap_element(int elementPosition);
void printList();
main()
{
int elementPosition;
createLinkList();
printf("Enter the Kth Postion to swap: ");
scanf("%d",&elementPosition);
swap_element(elementPosition);
printList();
}
void createLinkList(void)
{
int ch;
struct node *previousNode,*nextNode;
head = previousNode = (struct node *)malloc(sizeof(struct node));
printf("\nPress -1 for Not entering Node. \n\n");
do
{
nextNode = (struct node *)malloc(sizeof(struct node));
if(nextNode)
{
scanf("%d",&nextNode->value);
nextNode->next = NULL;
previousNode->next = nextNode;
previousNode = nextNode;
}
//fflush(ch);
printf("\nEnter -1 for terminate the link list.: ");
scanf("%d",&ch);
}while(ch != -1);
}
void swap_element(int elementPosition)
{
int counter=0;
struct node *swapNode1 = NULL, *swapNode2 =head, *startNode=head;
while(startNode)
{
if(counter == elementPosition)
swapNode1 = startNode;
if(counter>=elementPosition)
swapNode2 = swapNode2->next;
counter++;
startNode = startNode->next;
}
if(swapNode1 && swapNode2)
{
int temp = swapNode1->value;
swapNode1->value = swapNode2->value;
swapNode2->value = temp;
}
}
void printList()
{
struct node *Node=head->next;
while(Node)
{
printf("%d ",Node->value);
Node = Node->next;
}
}
#include<stdio.h>
struct node
{
int value;
struct node *next;
};
struct node *head;
void createLinkList(void);
void swap_element(int elementPosition);
void printList();
main()
{
int elementPosition;
createLinkList();
printf("Enter the Kth Postion to swap: ");
scanf("%d",&elementPosition);
swap_element(elementPosition);
printList();
}
void createLinkList(void)
{
int ch;
struct node *previousNode,*nextNode;
head = previousNode = (struct node *)malloc(sizeof(struct node));
printf("\nPress -1 for Not entering Node. \n\n");
do
{
nextNode = (struct node *)malloc(sizeof(struct node));
if(nextNode)
{
scanf("%d",&nextNode->value);
nextNode->next = NULL;
previousNode->next = nextNode;
previousNode = nextNode;
}
//fflush(ch);
printf("\nEnter -1 for terminate the link list.: ");
scanf("%d",&ch);
}while(ch != -1);
}
void swap_element(int elementPosition)
{
int counter=0;
struct node *swapNode1 = NULL, *swapNode2 =head, *startNode=head;
while(startNode)
{
if(counter == elementPosition)
swapNode1 = startNode;
if(counter>=elementPosition)
swapNode2 = swapNode2->next;
counter++;
startNode = startNode->next;
}
if(swapNode1 && swapNode2)
{
int temp = swapNode1->value;
swapNode1->value = swapNode2->value;
swapNode2->value = temp;
}
}
void printList()
{
struct node *Node=head->next;
while(Node)
{
printf("%d ",Node->value);
Node = Node->next;
}
}
scan the list, when reach kth node, then set kthFromStart to the node, and set kthFromEnd to be the head of the list.
when move to next node, update kthFromEnd to the next of the previous node.
Source from
sites.google.com/site/spaceofjameschen/home/linked-list/swap-kth-element-from-the-beginning-and-kth-element-from-the-end-of-linked-list
public class linkedlistswap {
public static class Node {
private Node next;
private Object data;
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Node(Object obj){
this(obj, null);
}
public void setData(Object obj){
data = obj;
}
public void setNext(Node n){
next = n;
}
public Object getData(){
return data;
}
public Node getNext(){
return next;
}
public String toString(){
String value = String.valueOf(data);
return value;
}
}
public static class singleLinkedList {
private Node head;
public void linkedList(){
this.head = null;
}
public void setHead(Node n){
n.next = head;
head = n;
}
public Node getHead(){
return head;
}
private void add(Node cur, Object obj) {
if (cur.getNext() == null){
Node tmp = new Node(obj);
cur.setNext(tmp);
} else {
add(cur.getNext(), obj);
}
}
public void add(Object obj){
if (getHead() == null) {
Node tmp = new Node(obj);
setHead(tmp);
} else {
add(getHead(), obj);
}
}
public int size(){
Node tmp = this.head;
int i = 0;
while (tmp != null){
i++;
tmp = tmp.getNext();
}
return i;
}
}
public static boolean swapNthElements(singleLinkedList list, int n) {
Node first;
Node second;
Node firstPrev;
Node secondPrev;
Node tmp;
int size = list.size();
firstPrev = secondPrev = list.getHead();
second = secondPrev.getNext();
if (n > size){
System.out.println("LIST IS OF LESSER SIZE");
return false;
} else {
if (n == size || n == 1){ // nodes on each end of the linked list must be swapped
first = list.getHead();
tmp = first.getNext();
while (second.getNext() != null){ //
second = second.getNext();
secondPrev = secondPrev.getNext();
}
tmp = first.getNext();
secondPrev.setNext(first);
list.head = tmp;
first.setNext(null);
list.setHead(second);
} else {
first = list.getHead().getNext();
for (int i = 1; i < n-1;++i){ // first is the nth node from the beginning of the list
first = first.getNext();
firstPrev = firstPrev.getNext();
}
for (int i = 1; i < size - n; ++i){ //second is the nth node from the end of the list
second = second.getNext();
secondPrev = secondPrev.getNext();
}
if (first == second){ // case where the nth node from the beginning and end are the same node -- do nothing
return true;
} else if (firstPrev == second){ // case where the nth node from beginning and nth node from end are adjacent nodes
second.setNext(first.getNext());
secondPrev.setNext(first);
first.setNext(second);
} else if (secondPrev == first){ // case where the nth node from beginning and nth node from end are adjacent nodes
first.setNext(second.getNext());
firstPrev.setNext(second);
second.setNext(first);
} else {
tmp = first.getNext();
first.setNext(second.getNext());
firstPrev.setNext(second);
secondPrev.setNext(first);
second.setNext(tmp);
}
}
}
return true;
}
public static void printList(singleLinkedList list){
Node tmp = list.getHead();
if (tmp != null) {
System.out.print( "{" + tmp.getData());
tmp = tmp.getNext();
}
while (tmp != null){
System.out.print(", " + tmp.getData());
tmp = tmp.getNext();
}
System.out.println("}");
}
public static void main(String[] args) {
singleLinkedList lst = new singleLinkedList();
int k = 5;
for (int amount = 0; amount < 15; ++amount){ lst.add(amount); }
// print list pre-swap
printList(lst);
//perform swap
System.out.println("swapping "+ String.valueOf(k) + "th from first and last position");
if (swapNthElements(lst, k) == true){
//print list post-swap
System.out.println("List post-swap!");
printList(lst);
}
}
}
Here is my java solution. If you needed to save time (time-restricted for written tests/interviews/etc.) you could make simple linked list and node classes. I feel like it is easier to read this way, though. Comments are welcome.
public void swap(int k){
Node slow = head;
Node fast = head;
if(head == null){
System.out.println("not enough members in the list");
return;
}
Node earlier = head;
for(int i =1; i<=k; i++){
fast = fast.next;
if(fast == null){
System.out.println("not enough members in the list");
return;
}
if(i == k-1)
earlier = fast;
}
while(fast != null){
slow = slow.next;
fast = fast.next;
}
Node later = slow;
int temp = later.data;
later.data = earlier.data;
earlier.data = temp;
}
public void SwapKthelement(int k)
{
node n1,n2; //2 pointers which differ by k elements
Node n3;// store the k th element from the last
if(head==null) no elements in the list
{
console.writeline("no elements in the list");
for(i=0;i<k-1;i++)// making n1 and n2 differ by k elements
{
if(n1.next!=null)// checking to see if there are no more elements
{
n1=n1.next;
n2=n1.next.next;
n3=n1;
}
else
{
writeline( "sorry not enuf elements ");
}
}
while(n2.next!=null)// if n2 is not the end keep moving till n2 is the last element in the list
{
n1=n1.next;
n2=n2.next;
}
//swapping data
Node temp=n1;
n1.date=n3.data;
n3.data=temp.data;
}
}
#include <stdio.h>
typedef struct lista{
void *payload;
struct lista *next;
} nodo;
typedef struct lista* Ptrnodo;
*Assume: 0<=posToSwap<=N-1 where N is number of Nodes in List
* ergo No dimension check*/
void frontback_swap(Ptrnodo ptrLista,int posToSwap){
Ptrnodo ptr1=ptrLista,ptr2=ptrLista,ptr3=ptrLista;
void *temp;
int k1=0,k2=0;
while(ptr3){
if(k1<posToSwap){
ptr2=ptr2->next;
k1++;
}
ptr3=ptr3->next;
if(k2<posToSwap) k2++;
else {
if(ptr3)ptr1=ptr1->next;
}
}
temp=ptr1->payload;
ptr1->payload=ptr2->payload;
ptr2->payload=temp;
}
Thinking about shrinking previous code,
Assuming following header
#include <stdio.h>
typedef struct list{
void *payload;
struct list *next;
} nodo;
typedef struct list* Ptrnodo;
I found 2 solutions: first one
O(3/2N) time, O(1) space
/*
* Assume: 0<=posToSwap<=N-1 where N is number of Nodes in List
* ergo No dimension check. O(3/2N) time 0(1)space solution
*/
void frontback_swap(Ptrnodo ptrLista,int k1){
Ptrnodo ptr1=ptrLista,ptr2=ptrLista,ptr3=ptrLista;
void *temp;
while(ptr3){
ptr3=ptr3->next;
if(!k1 && ptr3)ptr1=ptr1->next;
else if(!--k1)ptr2=ptr3;
}
temp=ptr1->payload;
ptr1->payload=ptr2->payload;
ptr2->payload=temp;
}
second one O(N) time O(N) space
void frontback_swap2(Ptrnodo ptrLista,int posToSwap){
Ptrnodo ptr3=ptrLista,ptr2=ptrLista;
void *temp;
int k1=0,nElement=posToSwap+1,first=1;
Ptrnodo buff[nElement];
while(ptr3){
buff[k1%nElement]=ptr3;
if(k1==posToSwap&&first){
first=0;
ptr2=ptr3;
}
ptr3=ptr3->next;
k1=(++k1)%nElement;
}
temp=buff[k1%nElement]->payload;
buff[k1%nElement]->payload=ptr2->payload;
ptr2->payload=temp;
}
here is simple algorithm for that :
suppose u have to swap 4rd from beginning and 4 th from end i.e.
[]->[]->[]->[]->[]->[]->[]->[]->[]
^ ^
then simple take two pointers say p1 and p2 at the head of node,
At first move p1 4 steps away
i.e []->[]->[]->[]->[]->[]->[]->[]->[]
^ ^
p2 p1
now p3=p1
and then start moving p2 (from head) and p1(pointing to 5th node) simultaneously till
p1 reaches at the end of list(i.e ==NULL)
now p3 pointing to kth from beginnig and p2 kth from end
swap p2 and p3
thats all :)
here is simple algorithm for that :
suppose u have to swap 4rd from beginning and 4 th from end i.e.
[]->[]->[]->[]->[]->[]->[]->[]->[]
^ ^
then simple take two pointers say p1 and p2 at the head of node,
At first move p1 4 steps away
i.e []->[]->[]->[]->[]->[]->[]->[]->[]
^ ^
p2 p1
now p3=p1
and then start moving p2 (from head) and p1(pointing to 5th node) simultaneously till
p1 reaches at the end of list(i.e ==NULL)
now p3 pointing to kth from beginnig and p2 kth from end
swap p2 and p3
thats all :)
sorry spaces were not visible above so i m posting it again
void SwapKthFirst_KthLast(int k)
{
try
{
if(head==NULL || head->next==NULL || k<=0) throw "\nInvlaid Entries\n";
}catch(const char *s)
{
puts(s);
return;
}
struct list *tmp1=head,*tmp2=head,*tmp3=NULL;
int cnt=1;
while(tmp1!=NULL)
{
if(cnt<k)
cnt++;
else if(cnt==k)
{
tmp3=tmp1;
cnt++;
}
else
tmp2=tmp2->next;
if(tmp1->next==NULL)
{
if(cnt!=k+1)
{
printf("\nExceeding the List Size 1\n");
return;
}
else
break;
}
tmp1=tmp1->next;
}
if(tmp2==head && k!=cnt-1)
{
printf("\nExceeding the List Size 2\n");
return;
}
int t=tmp2->data;
tmp2->data=tmp3->data;
tmp3->data=t;
}
We can do it in a single scan
- Amit June 21, 20131. find the kth node from start(with previous node) say x(Also keep track of previous node of kth node).If no of nodes<k,return.
2.let z=x,y=head
3.now in a loop make y=y->next and z=z->next until you reach the end from z. y then contains the kth node from end.(Also keep the previous node of this kth element from end,a little modification inside loop can help)
4.swap x and y by the previous nodes we kept in step 1 and 3
5.check if k==1 or k==n and change head if required