Amazon Interview Question Backend Developers
Country: India
typedef struct _Node
{
int value;
struct _Node* next;
} Node;
void ReorganizeLinkedList(Node*& head)
{
Node* slow=head, *fast = head;
while (fast && fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
//Reverse the second half
Node* nextNode=NULL, *tail = slow->next;
slow->next = NULL;
Node* current = tail, *prevNode = NULL, *reverseHead = tail;
while (current != NULL)
{
nextNode = current->next;
current->next = prevNode;
prevNode = current;
current = nextNode;
}
reverseHead = prevNode;
//Merge two lists
current = head;
nextNode = reverseHead;
tail = NULL;
while (current && nextNode)
{
prevNode = current->next;
if (tail)
tail->next = current;
current->next = nextNode;
tail = nextNode;
current = prevNode;
nextNode = nextNode->next;
}
//Check if either list has some nodes left
if (current && tail)
tail->next = current;
if (nextNode && tail)
tail->next = nextNode;
}
Node class
class Node(object):
def __init__(self, x):
self.val = x
self.next = None
#self.prev = None
def __str__(self, *args, **kwargs):
return str(self.val)
LinkedList class
class LinkedList(object):
def __init__(self, argList):
self.size = 1
self.head = Node(argList[0])
if argList[1:]:
self.setTail(argList[1:])
def setHead(self, headNode):
self.head = headNode
def setTail(self, argList):
currentNode = self.head
for i in argList:
currentNode.next = Node(i)
currentNode = currentNode.next
self.size += 1
def getNthNode(self, n):
c = self.head
for i in range(n-1):
if c:
c = c.next
else:
c = None
return c
def size(self):
return self.size
Solution
# this will return linklist for given list
ll = LinkedList([1,2,3,4,5,6])
i = 1
cnode = ll.head
while i <= ll.size//2 and cnode.next:
t2 = ll.getNthNode(ll.size - i)
t3 = ll.getNthNode(ll.size - i + 1)
t2.next = t3.next
t3.next = cnode.next
cnode.next = t3
cnode = cnode.next.next
i += 1
void
modify_int (node **head, node *cur, int *done) {
node *tmp = NULL;
if ((cur == NULL)) {
return;
}
modify_int(head, cur->next, done);
if (*done == 1) {
return;
}
if ((*head) == cur) {
cur->next = NULL;
*done = 1;
return;
}
tmp = (*head)->next;
(*head)->next = cur;
cur->next = tmp;
(*head) = tmp;
if (cur->next == cur) {
cur->next = NULL;
*done = 1;
}
}
void
modify (node *head) {
int done = 0;
if (!head)
return;
modify_int(&head, head->next, &done);
}
public void pattern(){
if(head==null)
throw new RuntimeException();
Node iterator=head;
Node prev=null;
while(iterator!=null){
Node curr = iterator.next;
while(curr!=null && curr.next!=null){
prev=curr;
curr=curr.next;
}
if(curr!=null){
curr.next = iterator.next;
prev.next=null;
iterator.next = curr;
iterator = curr.next;
}else{
iterator=iterator.next;
}
}
}
public void pattern(){
if(head==null)
throw new RuntimeException();
Node iterator=head;
Node prev=null;
while(iterator!=null){
Node curr = iterator.next;
while(curr!=null && curr.next!=null){
prev=curr;
curr=curr.next;
}
if(curr!=null){
curr.next = iterator.next;
prev.next=null;
iterator.next = curr;
iterator = curr.next;
}else{
iterator=iterator.next;
}
}
}
private Node changePointers(Node head,Node node) {
if(head==null || node == null)
return head;
head = changePointers(head,node.next);
if(head == null)
return null;
Node temp = head.next;
head.next = node;
node.next = temp;
head = temp;
if(temp == node) {
node.next = null;
return null;
}
return temp;
}
package com.sumit.linkedlist;
import java.io.FileNotFoundException;
public class RearrangeInPlace {
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
Node head = null;
CreateList cl = new CreateList();
for(String s : FIleUtil.getValue("re.txt")){
head = cl.createList(head,Integer.parseInt(s));
}
cl.printList(head);
System.out.println();
Node n = new RearrangeInPlace().rearrnage(head);
cl.printList(n);
}
public Node rearrnage(Node head){
Node slow = head;
Node fast = head.getNext();
Node s = slow;
Node f = fast;
while(fast != null && fast.getNext() != null){
slow = slow.getNext();
fast = fast.getNext().getNext();
}
f = slow.getNext();
slow.setNext(null);
return alternate(s,reverse(f));
}
public Node alternate(Node n1,Node n2){
Node list = n1;
Node s = n1;
Node f = n2;
while(s != null && f != null){
Node t1 = s.getNext();
Node t2 = f.getNext();
s.setNext(f);
f.setNext(t1);
s = t1;
f = t2;
}
return list;
}
public Node reverse(Node head){
Node pre = null;
Node te = null;
while(head != null){
te = head.getNext();
head.setNext(pre);
pre = head;
head = te;
}
return pre;
}
}
I saw two main points: 1) this is a linked list, 2) you are essentially folding it in half but don't know where the middle is.
So my thought was to use a stack:
public Node jumbleLinkedList (Node root){
Stack<Node> nodeStack = new Stack<Node>();
Node temp = root;
Node newList;
// put nodes into a stack
while(temp.next != null){
nodeStack.Push(temp);
temp = temp.next;
}
// now slice in the nodes until you reach yourself
temp = root;
while(temp.next != null && nodeStack.peek() != null){
Node tempNext = temp.next;
temp.next = nodeStack.pop();
temp.next.next = tempNext;
if(temp.next == tempNext.next || temp.next == tempNext){
tempNext.next = null;
break;
} else {
temp = tempNext;
}
}
return root;
}
public struct Node {
int value;
Node next;
}
//============================================================================
// Name : SwapLinkedListElem.cpp
// Author : Nitish Raj, Scientist DRDO
// Version :
// Copyright : Your copyright notice
// Description : Swapping of elements of Linklist
//============================================================================
#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 swap(node **p){
node *tmp = *p;
int size = determineSize(tmp);
int counter = 1;
queue<int> myQ;
stack<int> myS;
tmp = *p;
while(tmp != NULL && counter <= size){
if(size%2?counter<=size/2 +1:counter<=size/2)
myQ.push(tmp->data);
else
myS.push(tmp->data);
tmp = tmp->next;
counter++;
}
node *temp = *p;
while(myQ.size()>0 && myS.size()>0){
temp->data = myQ.front();
myQ.pop();
temp = temp->next;
temp->data = myS.top();
myS.pop();
temp = temp->next;
}
if( myQ.size() != 0)
{
temp->data = myQ.front();
temp->next = NULL;
}
}
int main() {
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);
swap(&start);
cout<<"PRINTING LINKLIST AFTER SWAP :: ";
printLinkList(start);
return 0;
}
I think it is quite easy:
struct node* temp=root;
while(temp->next->next)
{
struct node* prev=null;
struct node* current=root;
while(current->next)
{
prev=current;
current=current->next;
}
current->next=temp->next;
prev->next=null;
temp->next=current;
temp=current->next;
}
}
Please comment if anything seems wrong.
There you go. Recursively done in Java:
public static Node reOrder(Node root) {
if(root == null ||
root.next == null ||
root.next.next == null) return root;
Node secondLast = root;
Node last = null;
while(secondLast.next.next != null) {
secondLast = secondLast.next;
last = secondLast.next;
}
last.next = root.next;
root.next = last;
//System.out.println("Moved : " + last.data);
secondLast.next = null;
reOrder(last.next);
return root;
}
public static Node reOrder(Node root) {
if(root == null ||
root.next == null ||
root.next.next == null) return root;
Node secondLast = root;
Node last = null;
while(secondLast.next.next != null) {
secondLast = secondLast.next;
last = secondLast.next;
}
last.next = root.next;
root.next = last;
//System.out.println("Moved : " + last.data);
secondLast.next = null;
reOrder(last.next);
return root;
}
public static Node reOrder(Node root) {
if(root == null ||
root.next == null ||
root.next.next == null) return root;
Node secondLast = root;
Node last = null;
while(secondLast.next.next != null) {
secondLast = secondLast.next;
last = secondLast.next;
}
last.next = root.next;
root.next = last;
//System.out.println("Moved : " + last.data);
secondLast.next = null;
reOrder(last.next);
return root;
}
Solution #1:
1). Make a copy of linked list
2). Reverse the copy
3). Merge the original list with the copy up to the middle
Solution #2:
1). Write a function to swap data of "i"th and "N-i"th item of the list:
The sub-function for that is to find "N-i"th item of the list, using 2 pointers (normal one and shifted one).
2). Use that function from i=0 to i = N/2
Node* rearrangeLinkedList(Node* head){
Node* slow = head;
Node* fast = head;
// find the middle node
while(fast and fast->next and fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
// Reverse the second half
Node *prev = NULL, *nxt = NULL, *curr = slow->next;
while(curr){
nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
// prev is pointing to the first node of reversed half part of
// original linked list
slow->next = NULL; // terminate first half
Node *odd = head, *even = prev, *oNext = *eNext = NULL;
while(odd and even){
oNext = odd->next;
eNext = even->next;
odd->next = even;
even->next = oNext;
odd = oNext;
even = eNext;
}
return head;
}
static class butter {
public void solve(int testNumber, Scanner in, PrintWriter out) {
Node nd = null;
if (in.hasNext())
nd = new Node(Integer.parseInt(in.next()));
int cnt = 1;
while (in.hasNext()) {
int num = Integer.parseInt(in.next());
nd.add(num);
++cnt;
}
Node gimme = interleave(nd, out, cnt);
gimme.print(out);
out.close();
}
private Node interleave(Node nd, PrintWriter out, int n) {
Node rev = nd.clone().reverse();
Node nl = new Node(nd.data);
int cnt = 1;
Node s1 = nd.next;
Node r1 = rev;
while (r1.next != null) {
nl.add(r1.data);
if (++cnt == n) break;
nl.add(s1.data);
if (++cnt == n) break;
r1 = r1.next;
s1 = s1.next;
}
return nl;
}
class Node {
int data;
Node next;
Node(int d) {
data = d;
}
void print(PrintWriter pw) {
Node cur = this;
while (cur != null) {
pw.print(cur.data + " ");
cur = cur.next;
}
}
void add(int n) {
Node newnode = new Node(n);
Node cur = this;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newnode;
}
protected Node clone() {
Node nd = new Node(this.data);
Node cur = this;
while (cur.next != null) {
cur = cur.next;
nd.add(cur.data);
}
return nd;
}
public Node reverse() {
Node prev = null;
Node cur = this;
Node nxt;
while (cur.next != null) {
nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
cur.next = prev;
return cur;
}
}
}
package com.company;
public class Main {
public static void main(String args[]) {
LLNode head = new LLNode(1);
LinkedList originalLinkedList = new LinkedList(head);
originalLinkedList.addNode(new LLNode(2));
originalLinkedList.addNode(new LLNode(3));
originalLinkedList.addNode(new LLNode(4));
originalLinkedList.addNode(new LLNode(5));
originalLinkedList.addNode(new LLNode(6));
originalLinkedList.addNode(new LLNode(7));
originalLinkedList.addNode(new LLNode(8));
originalLinkedList.addNode(new LLNode(9));
originalLinkedList.addNode(new LLNode(10));
final int headValue = originalLinkedList.head.value;
final int secondValue = originalLinkedList.tail.value;
LinkedList modified = new LinkedList(new LLNode(headValue));
modified.addNode(new LLNode(secondValue));
int currentIndex = 2;
int endIndex = originalLinkedList.length / 2;
int ctr = 0;
while (currentIndex <= endIndex) {
int currValue = originalLinkedList.getNodeAt(currentIndex);
ctr++;
int nextValue = originalLinkedList.getNodeAt(originalLinkedList.length - ctr);
modified.addNode(new LLNode(currValue));
modified.addNode(new LLNode(nextValue));
currentIndex++;
}
modified.printNodes();
}
static class LinkedList {
public LLNode head;
public LLNode tail;
public int length = 1;
public LinkedList(LLNode head) {
this.head = head;
this.tail = head;
}
public void addNode(LLNode node) {
length++;
tail.next = node;
tail = node;
}
public void printNodes() {
LLNode tempHead = head;
while (tempHead.next != null) {
System.out.print(tempHead.value + " ");
tempHead = tempHead.next;
}
System.out.print(tempHead.value);
}
public int getNodeAt(int index) {
if (index == 1) {
return head.value;
}
if (index == length) {
return tail.value;
}
LLNode tempHead = head.next;
int ctr = 2;
while (tempHead.next != null) {
if (ctr == index) {
return tempHead.value;
} else {
tempHead = tempHead.next;
ctr++;
}
}
return -1;
}
}
static class LLNode {
public LLNode next;
public int value;
public LLNode(int value) {
this.value = value;
this.next = null;
}
public LLNode(int value, LLNode next) {
this.value = value;
this.next = next;
}
}
}
package com.company;
public class Main {
public static void main(String args[]) {
LLNode head = new LLNode(1);
LinkedList originalLinkedList = new LinkedList(head);
originalLinkedList.addNode(new LLNode(2));
originalLinkedList.addNode(new LLNode(3));
originalLinkedList.addNode(new LLNode(4));
originalLinkedList.addNode(new LLNode(5));
originalLinkedList.addNode(new LLNode(6));
originalLinkedList.addNode(new LLNode(7));
originalLinkedList.addNode(new LLNode(8));
originalLinkedList.addNode(new LLNode(9));
originalLinkedList.addNode(new LLNode(10));
final int headValue = originalLinkedList.head.value;
final int secondValue = originalLinkedList.tail.value;
LinkedList modified = new LinkedList(new LLNode(headValue));
modified.addNode(new LLNode(secondValue));
int currentIndex = 2;
int endIndex = originalLinkedList.length / 2;
int ctr = 0;
while (currentIndex <= endIndex) {
int currValue = originalLinkedList.getNodeAt(currentIndex);
ctr++;
int nextValue = originalLinkedList.getNodeAt(originalLinkedList.length - ctr);
modified.addNode(new LLNode(currValue));
modified.addNode(new LLNode(nextValue));
currentIndex++;
}
modified.printNodes();
}
static class LinkedList {
public LLNode head;
public LLNode tail;
public int length = 1;
public LinkedList(LLNode head) {
this.head = head;
this.tail = head;
}
public void addNode(LLNode node) {
length++;
tail.next = node;
tail = node;
}
public void printNodes() {
LLNode tempHead = head;
while (tempHead.next != null) {
System.out.print(tempHead.value + " ");
tempHead = tempHead.next;
}
System.out.print(tempHead.value);
}
public int getNodeAt(int index) {
if (index == 1) {
return head.value;
}
if (index == length) {
return tail.value;
}
LLNode tempHead = head.next;
int ctr = 2;
while (tempHead.next != null) {
if (ctr == index) {
return tempHead.value;
} else {
tempHead = tempHead.next;
ctr++;
}
}
return -1;
}
}
static class LLNode {
public LLNode next;
public int value;
public LLNode(int value) {
this.value = value;
this.next = null;
}
public LLNode(int value, LLNode next) {
this.value = value;
this.next = next;
}
}
}
Java solution without recursion
Complexity is O(2N)
Memory usage ~ N elements
1. Search for the middle of list
2. Split into two lists by middle
3. Reverse second list
4. Mix two list.
public class TestClass{
public static void main(String[] args) {
Node root = new Node(null, "1");
Node node = root;
for (int i = 2; i < 7; i++) {
node.next = new Node(null, i + "");
node = node.next;
}
node = findMiddle(root);
node = reverse(node);
mixTwoList(root, node);
print(root);
}
static void mixTwoList(Node one, Node two) {
while (one != null && two != null) {
Node oneNext = one.next;
Node twoNext = two.next;
one.next = two;
two.next = oneNext;
one = oneNext;
two = twoNext;
}
}
static Node findMiddle(Node root) {
Node preMiddle = null;
Node middle = root;
Node end = root;
while (middle != null && end != null && end.next != null) {
preMiddle = middle;
middle = middle.next;
end = end.next.next;
}
if (end != null) {
preMiddle = middle;
middle = middle.next;
}
// should split list in the middle
preMiddle.next = null;
return middle;
}
public static Node reverse(Node node) {
Node next = node.next;
node.next = null;
while (node != null && next != null) {
Node lnext = next.next;
Node lnode = next;
next.next = node;
node = lnode;
next = lnext;
}
return node;
}
static void print(Node node) {
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println("");
}
static class Node {
String value;
Node next;
public Node(Node next, String value) {
this.next = next;
this.value = value;
}
}
}
I don't get what is wrong witch such simple implementation?
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addAll(Arrays.asList(1, 2, 3, 4, 5, 6));
int left = 1;
int right = linkedList.size()-1;
while(left < right){
linkedList.add(left,linkedList.get(right));
linkedList.remove(right+1);
left+=2;
}
System.out.println(linkedList);
my C/C++ solution
#include <iostream>
/*
given a LinkedList like 1->2->3->4->5->6
Modify it as :
1->6->2->5->3->4
*/
struct linkednode {
int val;
linkednode *next;
};
int main()
{
//build -----------------------------------------------------------------
linkednode* root = new linkednode();
root->val = -1;
root->next = NULL;
linkednode* succ = NULL;
linkednode* last = NULL;
linkednode* base = root;
for (int i = 1; i <= 6; i++)
{
succ = new linkednode();
succ->val = i;
succ->next = NULL;
base->next = succ;
base = succ;
}
last = succ;
// printout -----------------------------------------------------------------
base = root->next;
printf(" initial ---------\n");
while (base != NULL)
{
printf("%d\n", base->val);
base = base->next;
}
// reverse -----------------------------------------------------------------
base = root->next;
linkednode* candidate = last;
linkednode* precandidate = NULL;
while (base->next != NULL && base->next != precandidate)
{
// find the previous before the latest candidate
linkednode* appcursor = root->next;
while (appcursor->next != NULL)
{
precandidate = appcursor;
appcursor = appcursor->next;
}
//make the substitution
appcursor = base->next;
candidate->next = base->next;
base->next = candidate;
precandidate->next = NULL;
candidate = precandidate;
base = appcursor;
}
// printout again -----------------------------------------------------------------
printf(" reversed ---------\n");
base = root->next;
while (base != NULL)
{
printf("%d\n", base->val);
base = base->next;
}
system("PAUSE");
return 1;
}
private void doOperation(LinkedListNode root) {
System.out.println();
printLinkedList(root);
// Identify the size of the linked list
int totalSize = 1;
LinkedListNode node = root;
do {
totalSize++;
node = node.next;
} while (node != null);
// TODO: Check for even or odd
// Put all the nodes after size/2 into a Stack
int middleIndex = totalSize / 2;
int size = 1;
node = root;
Stack<LinkedListNode> stack = new Stack<LinkedListNode>();
do {
size++;
if (size > middleIndex) {
stack.push(node);
}
node = node.next;
} while (node != null);
size = 1;
node = root;
do {
if (size %2 == 1 && !stack.isEmpty()) {
LinkedListNode tmpNode = stack.pop();
LinkedListNode tmpRef = node.next;
node.next = tmpNode;
tmpNode.next = tmpRef;
}
size++;
node = node.next;
} while (node != null && size < totalSize);
node.next = null;
System.out.println();
printLinkedList(root);
}
private void printLinkedList(LinkedListNode root) {
LinkedListNode node = root;
do {
System.out.print(node.value + ",");
node = node.next;
} while (node != null);
}
// 1->2->3->4->5
// 1->5->2->4->3
node* revLink(node*& first, node*& end) {
if (end == NULL)
return NULL;
node* node = revLink(first, end->next);
if (first == NULL || first->next == NULL)
return node;
if (first->val == end->val) {
first->next = NULL;
return node;
}
node* temp = first->next;
first->next = end;
end->next = temp;
cout << first->val << std::endl;
cout << first->next->val << std::endl;
cout << first->next->next->val << std::endl;
if (node == NULL)
node = first;
first = temp;
return node;
}
// 1->2->3->4->5
// 1->5->2->4->3
node* revLink(node*& first, node*& end) {
if (end == NULL)
return NULL;
node* node = revLink(first, end->next);
if (first == NULL || first->next == NULL)
return node;
if (first->val == end->val) {
first->next = NULL;
return node;
}
node* temp = first->next;
first->next = end;
end->next = temp;
cout << first->val << std::endl;
cout << first->next->val << std::endl;
cout << first->next->next->val << std::endl;
if (node == NULL)
node = first;
first = temp;
return node;
}
Clarify what happens when N ( = # of nodes) is odd.
/*
public class ListNode{
public int val;
public ListNode next;
public ListNode(int num)
{
val = num;
}
}
*/
public ListNode ModifyList(ListNode head)
{
if(head == null)
return head;
int numOfNodes = 0;
ListNode temp = head;
while(temp != null)
{
numOfNodes++;
temp = temp.next;
}
Stack<ListNode> st = new Stack<ListNode>();
Queue<ListNode> q = new Queue<ListNode>();
temp = head;
int count = 0;
while(count < Math.Ceil(numOfNodes/2))
{
q.Enqueue(temp);
temp = temp.next;
count++;
}
while(count <= numOfNodes)
{
Stack.Push(temp);
temp = temp.next;
count++;
}
while(st.Count > 0 && q.Count > 0)
{
temp = q.Dequque();
temp.next = st.Pop();
temp = temp.next;
}
if( q.Count != 0)
{
temp.next = q.Dequque();
temp.next.next = null;
}
return head;
}
- Anonymous July 30, 2016typedef struct _Node { int value; struct _Node* next; } Node; void ReorganizeLinkedList(Node* head) { Node* slow=head, *fast = head; while (fast && fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } //Reverse the second half Node* nextNode=NULL, *tail = slow->next; slow->next = NULL; Node* current = tail, *prevNode = NULL, *reverseHead = tail; while (current != NULL) { nextNode = current->next; current->next = preNode; preNode = current; current = nextNode; } reverseHead = preNode; //Merge two lists current = head; nextNode = reverseHead; tail = NULL; while (current && nextNode) { preNode = current->next; if (tail) tail->next = current; current->next = nextNode; tail = nextNode; current = preNode; nextNode = nextNode->next; } //Check if either list has some nodes left if (current && tail) tail->next = current; if (nextNode && tail) tail->next = nextNode; }