Amazon Interview Question
Country: United States
Code for
1. Split the second half
2. Reverse the second half
3. Subtract them first and second half and then merge them
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct ll
{
int data;
ll *next;
};
void print(ll *head)
{
while(head!=NULL)
{
printf(" %d ",head->data);
head=head->next;
}
}
void insert(ll **head,int data)
{
ll *n=(ll *)malloc(sizeof(ll));
n->data=data;
n->next=(*head);
(*head)=n;
}
void diff(ll **head1,ll *head2)
{
ll *temp=(*head1);
while(temp&&head2)
{
temp->data=temp->data-head2->data;
temp=temp->next;
head2=head2->next;
}
}
void reverse(ll **head)
{
ll *current=(*head),*prev=NULL,*next;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
(*head)=prev;
}
void splitAndSub(ll **head)
{
ll *slow=*head,*fast=*head,*prev,*head1,*head2;
while(fast->next&&fast->next->next)
{
prev=slow;
slow=slow->next;
fast=fast->next->next;
}
if(fast->next==NULL)
{
head1=*head;
head2=slow->next;
prev->next=NULL;
reverse(&head2);
diff(&head1,head2);
reverse(&head2);
*head=head1;
prev->next=slow;
}
else if(fast->next->next==NULL)
{
head1=*head;
head2=slow->next;
slow->next=NULL;
reverse(&head2);
diff(&head1,head2);
reverse(&head2);
*head=head1;
slow->next=head2;
}
printf("Final List \n");
print(*head);
}
int main()
{
ll *head=NULL;
insert(&head,6);
insert(&head,4);
insert(&head,2);
insert(&head,6);
insert(&head,7);
insert(&head,8);
insert(&head,9);
print(head);
printf("\n");
splitAndSub(&head);
}
C++ proposal:
{
void adjustList(node * ¤t, node * runner, int & length)
{
if(runner == NULL)
{
length /= 2;
return;
}
length++;
adjustList(current, runner->next, length);
if(length >= 0)
{
current->data = runner->data - current->data;
current = current->next;
length--;
}
}
int main()
{
node * head = NULL;
head = addNode(head, 8);
head = addNode(head, 7);
head = addNode(head, 6);
head = addNode(head, 5);
head = addNode(head, 4);
head = addNode(head, 3);
head = addNode(head, 2);
node * current = head;
int length = -1;
adjustList(current, head, length);
printNode(head);
//output: -6 -4 -2 0 4 3 2
}
}
here is my implementation in c++
{{#include<iostream>
#include<conio.h>
using namespace std;
struct LinkedList
{
int data;
struct LinkedList *next;
};
typedef struct LinkedList node;
void modify(node* &h,node *t,bool &f)
{
if(!t)
return;
modify(h,t->next,f);
if(!f && h!=t)
{
h->data=t->data-h->data;
if(h->next==t || h->next->next==t)
f=1;
h=h->next;
}
}
int main()
{
node *head,*t;
int i;
bool f=0;
for(i=1;i<=6;i++)
{
if(i==1)
{
t=new node;
head=t;
}
else
{
t->next=new node;
t=t->next;
}
t->data=i;
}
t->next=0;
t=head;
while(t)
{
cout<<t->data<<"\t";
t=t->next;
}
cout<<"\n\n";
t=head;
modify(t,t,f);
t=head;
while(t)
{
cout<<t->data<<"\t";
t=t->next;
}
cout<<"\n\n";
getch();
}
}
Hope this would help....
first find linked list length - n
startpointer = head
subtract_node = n // this variable used to store n-i iteration
for i = 1 to n/2 {
value = startpointer.value
lastpointer = startpointer
for j = i to (subtracted_node-i) {
lastpointer = lastpointer.next
}
lastvalue = lastpointer.value
startpointer.value = value - lastvalue
startpointer = startpointer.next
subtract_node = subtract_node - 1
}
static int len = 1, mid = 0;
static public LinkListNode modifyList(LinkListNode node, LinkListNode head,
int len) {
if (node.next == null) {
LinkListNode front = head;
front.data = node.data - front.data;
front = front.next;
System.out.println("\n" + len);
if (len % 2 == 0) {
mid = len / 2;
} else {
mid = len / 2 + 1;
}
System.out.println(mid);
return front;
}
LinkListNode front = modifyList(node.next, head, len + 1);
if (len > mid) {
front.data = node.data - front.data;
front = front.next;
} else {
return node;
}
return front;
}
here you hve to use to while 1 traverse to half length and other to traverse the other half of list backward .for traversing backward you can use length decrese the length each time u traverse.
node *rev(node *head, int len)
{
node *w, *e, *r;
int x = 0 , y = 0,l;
w = head;
l = len;
while (y != l / 2)//traversing half of length
{
e = head;
while (x != len-1)//for pointing in reverse .1 pointing the last element than 2nd last
{
e = e->next;
x++;
}
x = 0;
len--;
w->data = w->data - e->data;
w = w->next;
y++;
}
return head;
}
struct node* middle(struct node* head)
{
struct node* p=head;
struct node* q=head;
while(p->next!=NULL && p->next->next!=NULL)
{
p=p->next->next;
q=q->next;
}
return q;
}
void update_values(struct node *new_head,struct node *cur)
{
static struct node* head=new_head;
if(cur==NULL)return;
else
{
update_values(new_head,cur->next);
head->val+=cur->val;
head=head->next;
}
return;
}
void update(struct node *head)
{
struct node *mid=middle(head);
update_values(head,mid);
}
private Node ReverseSubtract(Node root, Node currentNode)
{
if (currentNode == null)
return root;
Node newRoot = ReverseSubtract(root, currentNode.next);
if (newRoot == null || newRoot == currentNode)
return null;
newRoot.data = currentNode.data - newRoot.data;
if (newRoot.next == currentNode)
return null;
return newRoot.next;
}
1. Use two pointers slowPtr and firstPtr
2. Jump slow ptr by 1 and firstPtr by two.
3. When firstPtr is null slowPtr point to middle.
4. Now reverse the list from slowPtr->next
5. Now move from first and also from slowPtr->next and subtract the value
6. When slow ptr reach end finish the subtraction
7. Now reverse the list again ( you can save that position to another pointer)
void
reverse(Node** head) {
Node* prev = NULL;
Node* current = *head;
Node* next = NULL;
while(current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
/* Method for the Problem above */
void
modify(Node** head) {
Node* slowPtr = *head;
Node* firstPtr = (*head)->next;
if ( firstPtr == NULL ) {
return;
}
while(firstPtr->next != NULL) {
slowPtr = slowPtr->next;
firstPtr = firstPtr->next;
if (firstPtr->next != NULL ) {
firstPtr = firstPtr->next;
}
}
reverse(&slowPtr->next);
firstPtr = slowPtr->next;
Node* current = *head;
while(firstPtr != NULL) {
current->data = current->data - firstPtr->data;
current = current->next;
firstPtr = firstPtr->next;
}
reverse(&slowPtr->next);
}
class Link:
start=None
count=0
def __init__(self,info):
self.info=info
self.next=None
def addNode(self,ptr):
if Link.start==None:
Link.start=ptr
Link.count+=1
else:
temp=Link.start
while temp.next!=None:
temp=temp.next
temp.next=ptr
Link.count+=1
def printNode(self,ptr):
if ptr!=None:
print ptr.info,"-->",
self.printNode(ptr.next)
def printPattern(self,ptr):
if ptr==None:
return 1
else:
i=self.printPattern(ptr.next)
temp=Link.start
if i<=(Link.count/2):
j=1
while j<i:
temp=temp.next
j+=1
temp.info=ptr.info-temp.info
i+=1
return i
a=Link(2);a.addNode(a)
a=Link(3);a.addNode(a)
a=Link(4);a.addNode(a)
a=Link(5);a.addNode(a)
a=Link(6);a.addNode(a)
a.printNode(Link.start)
print ""
a.printPattern(Link.start)
a.printNode(Link.start)
public class MinusSinglyLinkedList {
static int length = -1;
static Node current;
public static void main(String[] args) {
Node head = new Node(1);
current = head;
Node node = head;
for(int i=2;i<=11;i++) {
Node newNode = new Node(i);
node.next = newNode;
node = node.next;
}
System.out.println(head.toString());
adjustList(head);
System.out.println(head.toString());
}
public static void adjustList(Node runner) {
if(runner == null) {
length = length/2;
return;
}
length++;
adjustList(runner.next);
if(length > 0) {
current.value = runner.value - current.value;
current = current.next;
length--;
}
}
}
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = this;
while(node != null){
sb.append(node.value+" ");
node = node.next;
}
return sb.toString();
}
}
{{#include<iostream>
using namespace std;
struct node
{
node * next;
int val;
}*head, *m;
node *createNode(int val){
node *temp = new node;
temp->next = NULL;
temp->val = val;
}
void listRecurse(node *p){
if(p==NULL)
return;
listRecurse(p->next);
m->val = p->val - m->val;
m = m->next;
}
void UpdateList(){
node *r, *t;
r=head, t=head;
while(r->next && r->next->next){
t= t->next;
r=r->next->next;
}
m=head;
listRecurse(t->next);
m=head;
while(m!=NULL){
cout<<m->val<<" ";
m=m->next;
}
}
int main()
{
head = createNode(2);
head->next = createNode(4);
head->next->next = createNode(5);
head->next->next->next = createNode(6);
head->next->next->next->next = createNode(16);
head->next->next->next->next->next = createNode(19);
UpdateList();
}
/*#include <iostream>
#include <list>
#include <string>
using namespace std;
bool mycomparison (double first, double second)
{ return first<second; }
int main ()
{
std::list<std::string> mylist;
std::list<std::string>::iterator it;
mylist.push_back ("one");
mylist.push_back ("two");
mylist.push_back ("Three");
mylist.sort();
cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
list<double> first, second;
first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);
second.push_back (3.7);
second.push_back (7.1);
second.push_back (1.4);
first.sort();
second.sort();
first.merge(second);
// (second is now empty)
second.push_back (2.1);
//first.merge(second,mycomparison);
cout << "first contains:";
for (list<double>::iterator it=first.begin(); it!=first.end(); ++it)
cout << ' ' << *it;
cout << '\n';
}*/
}}
1. Have two pointer, slow and fast. slow jumps one node and fast two nodes at a time.
2. Start traversing the list. Keep pushing slow node on to a Stack. When fast node reaches end of the list. Slow pointing to the middle of the list.
3. Now keep start moving slow pointer alone and keep popping the value of popped node with slow->value - popnode->value
4. Return the list head
Oh my bad! But instead of stack, a pointer can be used to keep pointing the slow nodes in reverse order. then removing the nodes from this temp for subtraction.
1) Split the list from the middle.
- kr.neerav June 25, 20142) reverse the 2nd list.
3) perform the minus operation while traversing both simultaneously.
4) Reverse the 2nd list.
5) Merge both the list.