## Amazon Interview Question

Country: United States

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

1) Split the list from the middle.
2) reverse the 2nd list.
3) perform the minus operation while traversing both simultaneously.
4) Reverse the 2nd list.
5) Merge both the list.

Comment hidden because of low score. Click to expand.
0

How will you do step #2 reverse of second half, without additional memory.

Comment hidden because of low score. Click to expand.
0

step #2 can be done in O(n) time without extra memory.

Node * newcurr = null;
while(curr){
Node * temp = curr->next;
curr->next = newcurr;
newcurr = curr;
curr = temp;
}

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

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;
};

{
{
}
}
{
ll *n=(ll *)malloc(sizeof(ll));
n->data=data;
}
{
{
temp=temp->next;
}
}
{
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
}
{
while(fast->next&&fast->next->next)
{
prev=slow;
slow=slow->next;
fast=fast->next->next;
}
if(fast->next==NULL)
{
prev->next=NULL;
prev->next=slow;
}
else if(fast->next->next==NULL)
{
slow->next=NULL;
}
printf("Final List \n");
}
int main()
{
printf("\n");
}``````

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

C++ proposal:

``````{
void adjustList(node * &current, node * runner, int & length)
{
if(runner == NULL)
{
length /= 2;
return;
}

length++;

if(length >= 0)
{
current->data = runner->data - current->data;
current = current->next;
length--;
}
}

int main()
{

int length = -1;

//output: -6 -4 -2 0 4 3 2
}``````

}

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

here is my implementation in c++
{{#include<iostream>
#include<conio.h>
using namespace std;

{
int data;
};

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()
{
int i;
bool f=0;

for(i=1;i<=6;i++)
{
if(i==1)
{
t=new node;
}

else
{
t->next=new node;
t=t->next;
}
t->data=i;
}
t->next=0;

while(t)
{
cout<<t->data<<"\t";
t=t->next;
}
cout<<"\n\n";

modify(t,t,f);

while(t)
{
cout<<t->data<<"\t";
t=t->next;
}
cout<<"\n\n";

getch();
}
}

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

Hope this would help....

first find linked list length - n
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
}

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

``````static int len = 1, mid = 0;

int len) {

if (node.next == null) {
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;
}

if (len > mid) {

front.data = node.data - front.data;
front = front.next;
} else {
return node;
}
return front;

}``````

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

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 *w, *e, *r;
int x = 0 , y = 0,l;
l = len;
while (y != l / 2)//traversing half of length
{

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++;
}
}

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

``````struct node* middle(struct node* 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)
{
if(cur==NULL)return;
else
{
}
return;
}
{
}``````

Comment hidden because of low score. Click to expand.
0

Not valid , recursion involves stack.

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

``````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;
}``````

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

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
Node* prev = NULL;
Node* next = NULL;

while(current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}

}

/* Method for the Problem above */

void

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;

while(firstPtr != NULL) {
current->data = current->data - firstPtr->data;
current = current->next;
firstPtr = firstPtr->next;
}

reverse(&slowPtr->next);
}``````

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

start=None
count=0
def __init__(self,info):
self.info=info
self.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=ptr
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)
j=1
while j<i:
temp=temp.next
j+=1
temp.info=ptr.info-temp.info
i+=1
return i

print ""

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

``````public class MinusSinglyLinkedList {
static int length = -1;
static Node current;

public static void main(String[] args) {
for(int i=2;i<=11;i++) {
Node newNode = new Node(i);
node.next = newNode;
node = node.next;
}
}

public static void adjustList(Node runner) {
if(runner == null) {
length = length/2;
return;
}

length++;

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();
}
}``````

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

{{#include<iostream>
using namespace std;
struct node
{
node * next;
int val;

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;
while(r->next && r->next->next){
t= t->next;
r=r->next->next;

}
listRecurse(t->next);
while(m!=NULL){
cout<<m->val<<" ";
m=m->next;

}
}
int main()
{
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';
}*/
}}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

But the question says no extra memory to be used

Comment hidden because of low score. Click to expand.
0

As mentioned in the question no extra memory is to be used.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

time complexity will be too much in case if we use pointers to reverse the first half of list twice.

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.

### 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.