kill
BAN USERHmmm hitman, you are correct. The algorithm earlier is WRONG, my apologies.
The number(ptr) to be swapped is the number that BREAKS the increasing trend when working from the last digit to the first digit. Let me suggest a change:
"Start from the last digit and work your way backwards keeping a running min of digits encountered.
When you encounter a digit < previous digit, stop and replace with the min digit > ptr. Sort the rest of the digits."
This should work.
Eg 1: 121832
ptr=2;
ptr=3;
ptr=8;
ptr=1 < 8
swap(ptr,min_digit > 1 from (8,3,2)) = swap(ptr,2);
Number = 122831
ptr now points to the third digit where we swapped 1 with 2.
Sort the rest of the number from the swapped ptr to the units place.
Numbers to sort here is 831 => sorted order 138
hence result => 122138
Eg2: 12342
ptr = 2;
ptr = 4;
ptr = 3 < 4;
swap(3, min >3(4,2))
Number = 12432
ptr now points to the third digit where we swapped 3 with 4.
Sort the rest of the number from the swapped ptr to the units place.
Number = 12423
Edit: Changed 02/07/2012 as per Hitman's suggestions
The number(ptr) to be swapped is the number that BREAKS the increasing trend when working from the last digit to the first digit.
"Start from the last digit and work your way backwards.
When you encounter a digit < previous digit, stop and replace with the min digit > ptr. Sort the rest of the digits."
This should work.
Eg 1: 121832
ptr=2;
ptr=3;
ptr=8;
ptr=1 < 8
swap(ptr,min_digit > 1 from (8,3,2)) = swap(ptr,2);
Number = 122831
ptr now points to the third digit where we swapped 1 with 2.
Sort the rest of the number from the swapped ptr to the units place.
Numbers to sort here is 831 => sorted order 138
hence result => 122138
Eg2: 12342
ptr = 2;
ptr = 4;
ptr = 3 < 4;
swap(3, min >3(4,2))
Number = 12432
ptr now points to the third digit where we swapped 3 with 4.
Sort the rest of the number from the swapped ptr to the units place.
Number = 12423
Keep in mind there is no answer for numbers that do not break the increasing trend.
For eg: 6520 => No ans
4321 => No ans
9531 => No ans, etc.
First pass
>> Copy the basic linked list structure from old list to new list
>> You'll have data and nextLink fields filled properly
>> Hash the data in each node and store the memory address of the node in the buckets
Second pass
>> Examine what data the randomLink points to in the original list.
>> Look up the hash table with data as key and you'd get memory location of the data in the new list.
>> Fill up the randomLink field in the new list accordingly
PS: I think the hint was too big a hint
There's an elegant solution(publicized, not my own) to this problem.
Median of a continuous stream of numbers can be found out by:
>> Maintaining two heaps.
>> Max heap and a Min heap
>> Max heap keeps track of first half of the numbers.
>> Min heap keeps track of the second half.
>> The root elements along with the TOTAL number of elements will give you enough info to find the median
>> Take care in adding new elements to the heaps. You might need to delete and push into the other heap.
Use recursion to first find downwards distance
Signature is:
kDistDown(node *root, node *start, int k) {
<check for halting condition: k=0 and start !=null >
kDistDown(node *root, node *start->left, k-1)
kDistDown(node *root, node *start->right, k-1)
}
Now to check the upwards condition.
This is kind of a hack really. By no means elegant.
Write a recursive function to exhaustively search a tree for a given node returning the distance from the ROOT as the output.
Call the function TWICE passing root->left and root->right as args.
Now you'll know which subtree our start node is on. Left or right.
Also you'll know the distance from root to the start node.
Let this be 'n'.
Exhaustively search for all nodes at a distance k-n in the OPPOSITE subtree.
3521
- kill March 06, 2012ptr = 1
ptr = 2
ptr = 5
ptr = 3 < 5
swap(ptr, min_digit > 3 ) = swap (ptr, 5)
Number = 5321
Sort the rest => 5123
5123 is the number