Microsoft Interview Question


Country: India
Interview Type: In-Person




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

I am not able to find any O(n) inplace solution. In java, there is a data structure sortedmap, that can be used to make the solution O(n). If anyone has a suggestion, I would love to know it. Also, I am assuming that all nodes hold unique values.
Asking again, did interviewer give any hint?

- Victor May 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

He did mention this is simple Merge sort but myself could not realize how..if you do please help me aswell.

- HardCode May 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Simple mergesort is O(nlogn) but inplace. Anyways, here is what I could get:
1. Find the middle and end of the linked list. Now we have three pointers.
2. Repeat the step 1 (left, middle) and (middle,right) lists until two nodes are lef in each.
3. Merge at the time of return.

Basically the idea is to have all the nodes considered as independent with respect to the pointer which needs to be assigned and use the other one to parse the list.

I'll get the code for this but I hope the algorithm above would work.

- Victor May 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

its not possible to make it O(n) and inplace at the same time. Its like heisenberg uncertainty!

@Victor was right. We could use the TreeMap to store the nodes keyed by the value. The time complexity would be O(n) but not in place and will take O(n) space.

I a suspecting the question is a malformed one.

- zahidbuet106 May 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please describe with an example

- Anonymous May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

given a linked list as 3->2->4->5, having another pointer high for each node, need to populate them, as above example should have high pointer for 3 pointing to 4, for 2 pointing to 3, for 4 pointing to 5 and so on.

- HardCode May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please tell whether high pointers are pointed to some random higher pointer or they are just null

- RJ May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Suppose you could do this in O(n). Then, you could iterate through the list in sorted order in O(n), which would yield an O(n) sorting algorithm.

- eugene.yarovoi May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n) time but requires additional space particurally Stack.

- Anonymous May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So you mean that each linked list object has two pointers - next and a high pointer. We need to arrange high pointers such that 3 is pointing 2 , 4 is pointing to 3 and 5 is pointing to 4 but the next pointers and the order of the linked list will remain the same 3->2->4->5 . Is this so?

- Jasbir Singh May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont think it is possible if the link list has values which are not sorted. I can think by inplace sort it means the node is heavy and create a 'key' array and sort it in O(nlogn) and then rearrange. Or maybe hash the keys and then point them. So a hashtable of only keys will still be required.

- Sugarcane_farmer May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the high pointer of a node (with data = x) supposed to point to a node with data = x+1? not x+2, x+3, ..., x+n

- Anonymous May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@RJ: you are right they are all null

- HardCode May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Jasbir: correct

- HardCode May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anonymous: Its not that way, the high pointers point to null initially and you need to point them to next higher value as simple as that.
consider: 3->2->1->5, then resultant is 3 points to 5, 2 points to 2, 1 points to 2.

- HardCode May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List populateNextHigher(List l) {

if(!l) return NULL;

Node *start = l; //starting of the sorted list
l = l->next;

while(l){ //iterate through the list

if(l->data < start->data){

l->next_higher = start;
start = l;

} else {

Node *p = start;

while(p->next_higher && l->data >= p->next_higher->data) //find the position of l
p = p->next_higher;

l->next_higher = p->next_higher; //insert l
p->next_higher = l;

}

l = l->next;
}

return start;
}

- Rakesh May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List populateNextHigher(List l) {

if(!l) return NULL;

Node *start = l; //starting of the sorted list
l = l->next;

while(l){ //iterate through the list

if(l->data < start->data){

l->next_higher = start;
start = l;

} else {

Node *p = start;

while(p->next_higher && l->data >= p->next_higher->data) //find the position of l
p = p->next_higher;

l->next_higher = p->next_higher; //insert l
p->next_higher = l;

}

l = l->next;
}

return start;
}

- Rakesh May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rakesh : O(n2)...!

- HardCode May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't it more or less sorting of a linklist ?

- Math.random() May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

true

- HardCode May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Saurabh: I can't think of an inplace and order-n solution to this problem. Did interviewer give any hint?

- Victor May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
recursive solution: for each node, find the next higher node in two steps -search from head to current -if not found search from current->next to end of the linked list -if found current.higher = result setHigher(head, cur){{{ //1. find next higher in the left part of the current node next = head.next, minNode; min = max_integer; while(next && next ! = cur){{{ if(next.value < min && next.value > cur.value) {{{ min = next.value; minNode = next; }}} next = next.next; }}} //2. find the right part of the current next = cur.next; while(next){{{ if(next.value < min && next.value > cur.value) {{{ min = next.value; minNode = next; }}} next = next.next; }}} cur.higher = minNode; //repeat for the next node if(cur.next) setHigher(head, cur.next); }}} - td May 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

came across this interesting solution in another thread - algohub.blogspot.in/2014/03/replace-each-array-element-with.html

- anon123 May 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The way I understand "next higher node" is "first node that is higher than the current node when traversing further down the linked list" (there is no O(n) sorting algorithm, so it can't really be the next higher node overall).
Ex: if 3->2->4->1->6
then 3 and 2 point to 4, 4 and 1 point to 6.

The following code should do that in O(n):

void assignhigh( Node * head) {
	Node * small = head;
	Node * curr = head;
	while (curr->next) {
		if (curr->next->value > curr->value) {
			while (small != curr->next) {
				small->high = curr->next;
				small = small->next;
			}
		} else {
			curr=curr->next;
		}
	}
}

- Sylvain Reboux May 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not O(n) .. O(n2) precisely. Counter example: 5--> 4-->3-->2-->1-->6

- zahidbuet106 May 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is O(n).

For each iteration of the first while loop, either curr or small is incremented. And small is always lagging behind curr. So each element is touched at most twice (once by "curr" and once by "small").

But it's wrong....
Counter example:
5->4->3->2->3
All the "high" pointers will be pointing to the last node, and they shouldn't.

- sylreboux May 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

are we allowed to use any extra variables?? say two or three extra variables other than the space required for the linked list???
and if a certain number doesnt have the next higher number then do we make it null?? as in
7->9->17->8->11->NULL
so make 17's higher as NULL!! is that it???
please answer!! thanks in advance!!

- swpnl.borse June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I understood the problem exactly as Sylvain Reboux:
"next higher node" is "first node that is higher than the current node when traversing further down the linked list"
Ex: if 3->2->4->1->6
then 3 and 2 point to 4, 4 and 1 point to 6.

That problem can be solved in O(n) time and with O(1) space (that is in-place). My idea is:
1) Find the end of the list.
2) Iterate the nodes from the last to the first.
3) For every 'current' node compare it with the 'current->next' node.
a) if 'current->next' is greater than 'current' then 'current->higher' pointer should point to 'current->next'
b) otherwise compare 'current' with 'current->next->higher' then with 'current->next->higher->higher' and so on. Eventually we will find the node that is higher than 'current' node.

To iterate in backward direction we can use a trick. We can populate the higher pointers of each node with pointer to a previous node. That is we effectively create a doubly-linked list. Then we rewrite the higher pointers when we iterate the list in backward direction.

It can be shown that each node will be checked twice at most (by the steps 2 and 3). So the time complexity is O(n).

My implementation:

struct Node {
	int val;
	Node* next;
	Node* high;
};

void Solve(Node* head) {
	if (!head || !head->next)
		return;
	Node* cur = head;
	Node* prev = nullptr;
	
	// The trick: find the end of the list and convert the list
	// to a doubly-linked list at the same time.
	while (cur) {
		cur->high = prev;
		prev = cur;
		cur = cur->next;		
	}
	
	// Now iterate the list in backward direction and rewrite high
	// pointers
	cur = prev;
	prev = cur->high;
	cur->high = nullptr;	
	cur = prev;
	prev = cur->high;
	
	while (cur) {
		if (cur->next->val > cur->val)
			cur->high = cur->next;
		else {
			Node* high = cur->next->high;
			// that loop will touch each node of list twice in total at most,
			// so the time complexity is O(n)
			while (high && high->val <= cur->val)
				high = high->high;
			cur->high = high;
		}
		cur = prev;
		if (cur)
			prev = cur->high;
	}
}

- Alex Antonov July 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here next higher node means that the nearest node whose value is greater than the value at the current node. Not sure sorting would be good here.

The algo to find the maximum area rectangle in histogram can be applied here. Keep pushing in the stack if the next node is of lesser value. When you find a node with greater value pop from stack until the top of stack has value >= the current node. All the popped nodes would have the high pointer point to the current node. Push the current node to the stack.
Since each element is pushed and popped once, you get O(n) complexity.

- Learn July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I know we have to do it in-place, but if that condition was relieved, I'd use a max heap.
With an array based implementation of Max heap, you can get the 'next higher' node with (i + 1). This would be an O(N) Time and O(N) space.

Any thing better than this ?
I don't see how stacks would be useful here.
I can't think of a O(N) sol without any extra space! :|

- Rushabh October 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem that many are having addressing this question is that you are assuming in place means O(1) memory, which it does not! You can do this easily by using recursion!

- Juan Gomez October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

First we need to find the lowest number in O(n) and then starting from there rearrange high pointers.

Code:

void Rearrange(highNode* head)
{
    if(head == NULL)
        return;
    int min = head->data;
    highNode* curr = head;
    highNode* minNode = head;

    while(curr)
    {
        if(curr->data < min)
        {
            min = curr->data;
            minNode = curr;
        }
        curr = curr->next;
    }

    while(minNode->high)
    {
        highNode* temp = minNode->high;
        minNode->high = minNode->high->high;
        minNode = temp;
    }
}

- Brandy May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont understand what you are doing. It says that you have to populate high pointers. So we can assume they all point to null or random junk. So after say 5th node is minNode. so its high pointer points to null. Hence minNode->high will be null and your second loop won't execute.

- Sugarcane_farmer May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad... I dont think a O(n) solution is possible inplace. Here is O(n2) insertion sort kind-of solution

void Rearrange(highNode* head)
{
    highNode* highList = head;
    highNode* curr = head;
    while(curr)
    {
        if(curr->data < highList->data)
        {
            curr->high = highList;
            highList = curr;
        }
        highNode* highIter = highList;

        while(highIter->high && highIter->high->data < curr->data)
        {
            highIter = highIter->high;
        }

        highNode* temp = highIter->high;
        highIter->high = curr;
        curr->high = temp;

        curr = curr->next;
    }
}

- Brandy May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n) solution based on the assumption that high points to a node with an x+1 value.

import java.util.HashMap;
import java.util.Map;

public class HigherLinkedList {
  static class Node {
    Node next;
    Node high;
    int data;

    public Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }
  }

  public static void main(String[] args) {
    int[] input = {3, 2, 4, 5};
    Node header = null;
    for (int i = input.length - 1; i >= 0; i--) {
      header = new Node(input[i], header);
    }
    printList(header);
    System.out.println("After assignment:");
    assignHigh(header);
    printList(header);
  }

  public static void assignHigh(Node header) {
    Map<Integer, Node> map = new HashMap<Integer, Node>();
    Node temp = header;
    while (temp != null) {
      int value = temp.data;
      map.put(value, temp);
      Node lower = map.get(value - 1);
      Node higher = map.get(value + 1);
      if (lower != null) {
        lower.high = temp;
      }
      if (higher != null) {
        temp.high = higher;
      }
      temp = temp.next;
    }
  }

  public static void printList(Node header) {
    String nextStr = "next: ", highSrt = "";
    Node temp = header;
    while (temp != null) {
      nextStr = nextStr + temp.data + "->";
      highSrt =
          highSrt + "high of " + temp.data + "->" + (temp.high != null ? temp.high.data : "null")
              + ", ";
      temp = temp.next;
    }
    System.out.println(nextStr + null);
    System.out.println(highSrt);
  }
}

- Anonymous May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice, but it's not 'in place' (memory wise) - meaning you can't use the hashtable.

- Michael.J.Keating May 13, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More