Microsoft Interview Question
Country: India
Interview Type: In-Person
He did mention this is simple Merge sort but myself could not realize how..if you do please help me aswell.
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.
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.
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.
Can you please tell whether high pointers are pointed to some random higher pointer or they are just null
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?
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;
}
}
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.
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;
}
}
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.
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;
}
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;
}
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;
}
}
}
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.
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!!
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;
}
}
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.
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! :|
private void setRandomToNextGreater(LinkListNode n){
LinkListNode sorted = n;
n = n.next;
while(n != null){
LinkListNode tmp = sorted;
LinkListNode prev = null;
while(tmp != null && n.data <= tmp.data){
prev = tmp;
tmp = tmp.random;
}
if(prev == null){
n.random = sorted;
sorted = n;
}else{
tmp = prev.next;
prev.next = n;
n.next = tmp;
}
}
}
private void setRandomToNextGreater(LinkListNode n){
LinkListNode sorted = n;
n = n.next;
while(n != null){
LinkListNode tmp = sorted;
LinkListNode prev = null;
while(tmp != null && n.data <= tmp.data){
prev = tmp;
tmp = tmp.random;
}
if(prev == null){
n.random = sorted;
sorted = n;
}else{
tmp = prev.next;
prev.next = n;
n.next = tmp;
}
}
}
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);
}
}
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.
- Victor May 17, 2014Asking again, did interviewer give any hint?