russoue
BAN USERI got this solution from here: discuss.joelonsoftware.com/default.asp?interview.11.506320.10
If A has no children, just insert the node normally into B.
If the root of A < the root of B:
A1 = A.right
A.right = NULL
Merge A with B.left
Merge A1 with B
Otherwise:
A1 = A.left
A.left = NULL
Merge A1 with B
Merge A with B.right
Kadane's 2D algorithm definitely solves in O(n^3) time. However, here is another O(n^3) solution:
for (i = 0; i < n; i++)
{
array[n] <- m[i];
for (j = i + 1; j < n; j++)
{
array[n] <- array[n] & m[j]
foreach contiguous 1's
{
number of ones <- (j - i) * number_of_contiguous_ones;
if (number_of_contiguous_ones > max)
max <- number_of_contiguous_ones
}
}
}
For the next number, scan from left to right to find the last 01 pair, swap it and then sort all the 1's and 0's right of the pair in ascending order.
For the previous number, scan from right to left to find the first 10 pair, swap it and then sort all the 1's and 0's right of the pair in descending order.
I think it can be done by sorting the numbers by using the value as the index where it should be. This can be done in O(n) time. We can start from the index 1. For the first duplicate number we encounter, we will find the first copy already in its place. We can use any number not in the range as marker indicating that the element has been moved.
For example:
int a [] = { 3 1 2 3 };
int tmp;
We try to move a[1] to a[3] (1 based indexing).
{ -1, 1, 3, 3 }
tmp = 2
Next we work with 2 which we just replaced.
{ -1, 2, 3, 3 }
tmp = 1
Next work with 1
{ 1, 2, 3, 3 }
tmp = -1
Now tmp has the marker -1. So move on to the next position a[2]. But it is OK, so is a[3]. When we reach a[4], we find that a[3] already has 3. Hence, 3 is the first duplicate.
This runs in O(n) as each element is accessed at most twice.
Here is another one:
int findRotation(int *array, int length)
{
if (!length || 1 == length) return 0;
int start = 0;
int end = length - 1;
if (array[start] < array[end])
return 0;
int middle;
while (start != end)
{
middle = (start + end) / 2;
if (array[start] > array[middle])
{
if (array[middle + 1] > array[end])
start = middle + 1;
else if (array[middle] > array[middle + 1])
return middle + 1;
else
end = middle;
}
else
return middle + 1;
}
}
Assuming the sorting order is ascending and all the values are unique the following can be a solution:
int findRotation(int *array, int length)
{
if (!length || 1 == length) return 0;
int start = 0;
int end = length - 1;
if (array[start] < array[end])
return 0;
int middle;
while (start != end)
{
middle = (start + end) / 2;
if (array[start] > array[middle])
{
if (array[middle + 1] > array[end])
start = middle + 1;
else if (array[middle] > array[middle + 1])
return middle + 1;
else
end = middle;
}
else
return middle + 1;
}
}
I think the confusion is arising because of the wording. Probably by "next biggest" the smallest value in the tree greater than the given value is meant. Likewise, the "next smallest" means the largest value in the tree less than the given value. Please correct me if I am wrong.
- russoue February 04, 2010I think the following works:
Node *removeDup(Node *ptr) {
if (!ptr)
return NULL;
if (!ptr->next)
return ptr;
if (ptr->val != ptr->next->val) {
ptr->next = removeDup(ptr->next);
return ptr;
}
else {
while (ptr && ptr->next && ptr->val == ptr->next->val) {
Node *tmp = ptr->next;
delete ptr;
ptr = tmp;
}
Node *tmp = ptr->next;
delete ptr;
return removeDup(tmp);
}
}
Does concatenating the reversed string work if the palindrome is a suffix of the string? For example, concatenating reverse of ANN yields ANNNNA. The longest common duplicate sub-string here is "A" whereas the answer should be "NN". Please correct me if I am wrong.
- russoue February 03, 2010
I guess this solution does not apply here. Microsoft does not use anything like Hadoop which uses MapReduce.
- russoue February 16, 2010