## Amazon Interview Question for Software Engineer / Developers

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

My guess is for min. space, mergesort should be applied, which is in-place and
O(N log N).
I am trying to come up with the code.

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

Ok, below is the code in Java. Kind of long.

Basicly what it does is trying to sort lists of length 2 first and then lists of length 4 etc. So on so forth.

The only difference from the classical linked list merge sort is that before the merge sort is called all "nextbigger" references are initialized to "next" references. And then the sort is performed by manipulating the "nextbigger" references and the "next" references are not changed.

Just changed the code from "Simon Tatham's Algorithms Page".

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

Have a [n,2] array. Copy the list value in one column and the corresponding pointer in another column. Sort it based on value column. Revisit the list, for every value, find the value in array, go to next row, pickup the pointer and assign it to next_large.
Complexity :
Array popuplation = n.
Array sorting = nlogn
Next travel = n.
Array search for n elements = nlogn

Overall complexity is O( 2n+2nlogn)

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

Best solution i think is...
Considering a BST on given inputs

struct node
{
int data;
struct node *next;
struct node *next_larger;
}

So each node has link to next node = (left node if available else NULL) as well as its next highest node = (right node if available else its parent node).

Simple!...

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

Awesome solution:
Here's the code in C:
Time complexity : O(nlog(n)), as there are n nodes in list, and inserting each node in BST takes O(log(n)), and finding succesor takes O(log(n)).

``````typedef struct treenode {
int data;
treenode *left;
treenode *right;
} treenode;

treenode *root = NULL;
node *p, *q;
while (p != NULL) {
insertInBst(&root, p->data);
p = p->next;
}
while (q != NULL) {
q->next_larger = findSuccesor(root, q->data);
q = q->next;
}
}

treenode* successor (treenode* r, int x) {
treenode* elem = search(r, x);
if (elem == NULL) {
return NULL;
} else if (elem->right != NULL ) {
return minimum(elem->right);
} else {
treenode *p = elem->parent;
while (p != NULL && p->left != elem) {
p = p->parent;
elem = p;
}
if (p == NULL) {
return NULL;
} else {
return p;
}
}
}

treenode* minimum (treenode* t) {
if (t == NULL) {
return NULL;
}
while (t->left != NULL) {
t = t->left;
}
return t;
}

treenode* search (treenode* r, int x) {
if (r == NULL) {
return NULL;
} else if (r->data == x) {
return r;
} else if (r->data > x) {
return search(r->left, x);
} else {
return search(r->right, x);
}
}``````

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

``````class Node <T>{
public T data;
public Node<T> next;
public Node<T> nextLarge; // To point the next large element in the list

Node (T t)
{
data = t;
}
}

{
else
{

//Split
while(fast.next != null)
{
fast = fast.next;
if(fast.next != null)
fast = fast.next;
else
break;

slow = slow.next;
}

Node<T> List2 = slow.next;
Node<T> copyL2 = List2;

slow.next = null;
// Split complete

// Recursively Split and then merge until we reach a list of sizes 1
List1 = applicationOfMergeSort(List1);
List2 = applicationOfMergeSort(List2);

//Since List1 will ultimately hold the result of merging do lets reset the head to point to List1,
//head will be returned as a result of this function

//Merge
Node<T> prev = null;

while(List1 != null && List2!= null)
{
if((Integer) List1.data < (Integer) List2.data)
{
prev = List1;
List1 = List1.nextLarge;
}
else
{
Node<T> nextList2 = List2.nextLarge;
List2.nextLarge = List1;
if(prev == null)
{
}
else
{
prev.nextLarge = List2;
}

prev = List2;
List2 = nextList2;
}
}

if(List2 != null)
prev.nextLarge = List2;

// Merging Complete

// Now make the connection of next pointers, broken earlier in the split step
slow.next = copyL2;
}
}``````

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

store the linked list value in an array. Sort that array. Now for each data value in linked list find the same data value in array using binary search. After getting the index of data value in sorted array, get next value from array.
complexity will be nlogn

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

look at the Question. we have to set that(next_larger) pointer and not the value..
so in this case complexities changes...

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

In the array, store the node address together with the value. Doesn't change complexity.

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

1) Sort the list ( keeping the original unaltered) : n log n
2) Hash the sorted list ( Key = value, Value = Next pointer in sorted list)
3) Walk through the original list, looking up the hash and setting the next->larger to point to the value in the hash.

Time Complexity: O(n log n) Space = 2n

Or you could do an n2 algorithm walking through the list and finding the next larger element for all the elements

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

seems good !!
but they ask me to write the code...

and they asked me about different approach by reducing the space as well as time complexity.

hope to see some code from you with hashing !!

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

A solution no better than above :

1) Make a binary tree(same structure) out of the given LL.(Structure has two child pointer)
2) For node with data find it in tree.lets sa its 'n' the child greater than n is min(n->right).

Complexity O(nlogn) + O(nlogn) = O(nlogn) for optimum BST
Space O(n)

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

``````class Node {
int value;
Node next;
Node nextbigger;

public void listSort(){

Node list, current, q, e, tail=null;
int insize, merges, psize, qsize, i;

current = this;
while(current != null){
current.nextbigger = current.next;
current = current.next;
}
if(this == null)
return;

insize = 1;

list = this;
while(true){
current = list;
list = null;
tail = null;
merges = 0;

while (current != null) {
merges++;
q = current;
psize = 0;
for (i = 0; i < insize; i++) {
psize++;
q = q.nextbigger;
if (q == null)
break;
}

qsize = insize;

while (psize > 0 || (qsize > 0 && q!=null)) {

/* decide whether next element of merge comes from p or q */
if (psize == 0) {
/* p is empty; e must come from q. */
e = q; q = q.nextbigger; qsize--;

} else if (qsize == 0 || q == null) {
/* q is empty; e must come from p. */
e = current;
current = current.nextbigger;
psize--;

} else if (current.value <= q.value ) {
/* First element of p is lower (or same);
* e must come from p. */
e = current; current = current.nextbigger; psize--;

} else {
/* First element of q is lower; e must come from q. */
e = q; q = q.nextbigger; qsize--;

}

if (tail != null) {
tail.nextbigger = e;
} else {
list = e;
}

tail = e;
}
current = q;
}

tail.nextbigger = null;

if (merges <= 1)   /* allow for merges==0, the empty list case */
return ;

/* Otherwise repeat, merging lists twice the size */
insize *= 2;

}

}

}``````

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

For each node let next_larger = next, and sort the linked list treating next_larger pointer as next pointer, I think this problem is just sorting a linked list, the interviewer was just being wise, which I think is pretty stupid. It is exactly like following: I have following data structure, where initial_next pointer points to its next element while next pointer all points null, sort the list.

``````struct node
{
int data;
struct node *initial_next;
struct node *next;
}``````

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

The above understanding of the problem is correct.

Here's code to sort the list using merge sort in C. Simple merge sort routine has been modified to sort a linked list. Its a no brainer. The quality of the code isn't great.

``````typedef struct node
{
int i;
struct node* nxt;
struct node* nxt_higher;
} Node;

Node * mergeSortList(Node *list){
int len,count;
Node *trav,*L2,*L1;
L1 = list;
len = listlen(list);
if (len ==2)
{
if (list->i > list->nxt->i)
{
list->nxt->nxt = list;
list->nxt=NULL;
}
return list;
}
if (len == 1){
return list;
}
trav=list;
count =1;
while ((trav != NULL) && (count <= len/2))
{
trav=trav->nxt;
count++;
}
L2=trav->nxt;
trav->nxt=NULL;
return mergelist(mergeSortList(L2), mergeSortList(L1));
}

Node * mergelist(Node *L1, Node *L2)
{
Node *L3=NULL, *tempnode=NULL,*lastnode=NULL;
while((L1!=NULL) && (L2!=NULL))
{
tempnode = (Node *)malloc(sizeof(Node));
if (L3 == NULL)
{
L3=tempnode;
}
if (lastnode != NULL)
{
lastnode->nxt = tempnode;
}
if ((L1->i) < (L2->i))
{
*tempnode = *L1;
L1=L1->nxt;
}
else if ((L1->i) == (L2->i))
{
*tempnode = *L1;
L1=L1->nxt;
L2=L2->nxt;
}
else
{
*tempnode = *L2;
L2=L2->nxt;
}
lastnode = tempnode;
}
Node *travel =  NULL;
if (L1 == NULL)
{
travel = L2;
}
else if (L2 == NULL)
{
travel = L1;
}
while (travel !=NULL)
{
tempnode = (Node *) malloc(sizeof(Node));
*tempnode = *travel;
if (L3 == NULL)
{
L3=tempnode;
}
if (lastnode != NULL)
{
lastnode->nxt = tempnode;
}
lastnode = tempnode;
travel=travel->nxt;
}
return L3;
}

{
int count =0;
{
count++;
}
return count;
}``````

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

fuck you man fuck...

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

well i feel better idea would be to use max-heap as a priority queue
Insert all the nodes into the list.
Use an additional variable to store the popped node.
Initially its null

for the given list 3-> 1-> 6-> 5-> 4

Pop the first one 6 and point it to the variable so 6-> null
replace the variable with the current node

then pop next.. here 5 and point 5 to the variable so it is 5-> 6
and so on

overall complexity to add and remove from heap is log n and to traverse the list to push it into the tree is n

therefore it is n + logn = n

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

then u need to have left child pointer and right child pointer in the element struct which is not allowed in the problem !

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

Actually you don't need left and right child pointers in order to build a heap. Because heaps have the property of always being complete, you can use an array. Node i's left child would be i*2+1 in the array, and it's right child would be i*2+2. And even if you couldn't use an array, you can still create a new class called "Node" that encapsulates the struct to build your temporary tree.

I agree with ketz that a max-heap is definitely a very nice solution, but I don't agree on its complexity. It's correct that push and pop is logn, but you need to do push/pop for n nodes. If you're pushing/popping nodes n-number of times, that's actually n*logn complexity.

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

I think BST is a good solution.

If list is 3->1->6->5->4 then we ll make a BST out of it.

3
next / \nxt_bigger
1 6
/
5
/
4

After creating we'll traverse the tree using inorder then we ll get
1->3->4->5->6

This is the desired result.

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

The problem can solve in space with time complexity of nlogn.

list* merge(list* l1,list *l2){
if(!l1) return l2;
if(!l2) return l1;
if(l1->data<l2->data){
l1->next_larger = merge(l1->next_larger, l2);
return l1;
}
else{
l2->next_larger = merge(l1, l2->next_larger);
return l2;
}

}

//use the above merge code

list* sort(list* l){
//split l into 2 parts l1,l2
//merge and return the list
}

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

list* sort(list* l){
//split l into 2 parts l1,l2
//call sort function on l1 and l2 separately
//merge and return the list
}

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

Does not it look like you have a infinite loop of nodes coming and you need to do insert sorted

1) traverse the list
2) update the Nexthigher pointer based on the insertsorted link list logic

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

1) Copy the Next pointer value to Greater pointer
2) Sort using mergesort based upon greater pointer

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

Use min Priority Queue (PQ)
1. Put all number in the PQ - store the node pointer and the data. Min on data
2. Take the min (top most element - say "node")
3. Set the "node"->nextbigger to the top element in the PQ (peek the next element in the PQ)
4. Repeat 2-4 till one element is left in PQ.

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

``````Node* merge(Node* first, Node* second)
{
Node* result = NULL;

if (!first)
return second;

if (!second)
return first;

if (first->data() <  second->data()) {
result = first;
result->setNextLarger(merge(first->nextLarger(), second));
}
else {
result = second;
result->setNextLarger(merge(first, second->nextLarger()));
}

return result;
}

Node* sort(Node* root, int listLength)
{
if (!root || !root->next() || listLength <= 1)
return root;

int middle = listLength / 2;
int index = 0;
Node* middleNode = root;

while (index < middle) {
middleNode = middleNode->next();
index += 1;
}

return merge(sort(root, middle), sort(middleNode, listLength - middle));
}``````

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

it is really easy but asked by smartness hats off to interviewr to ask such easy question with different way good one :)

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

1. Traverse the link list & do next_large = next; //Means next_large points same next node.
2. Now assume its a single link list, which is having one pointer next_large.
3. Now sort this single link list in ascending order.

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

You could copy the value of next into next_larger, then sort the list using nlogn algo, then swap values of next and next_larger.

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.