Anirban
BAN USER- 0of 0 votes
AnswersAn operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array.
- Anirban in India
Eg :- 3124
Output: 2 (3124->1243->1234)
How to do it less than O(n^2) ?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Apart from doing BFS you can use recursion also. The main idea is to remember the level visited for the first time so the you dont print the nodes of the same level when you visit them later.
int visited = -1;
void LeftMostInEveryLevel (struct node *root, int level) {
if (root != NULL) {
if (level > visited) {
cout << "Level = " << level << ", Node = " << root->data << endl;
visited = level;
}
LeftMostInEveryLevel (root->left, level + 1);
LeftMostInEveryLevel (root->right, level + 1);
}
}
This greedy approach works for most inputs but there are inputs where it would fail. For example consider [4,14,15,16,17]. The approach would put the numbers into sets as [17, 14] and [16, 15, 4] with difference between them as 4. But the optimal arrangement would be like this [17, 16] and [15, 14, 4] with difference 0
- Anirban November 23, 2012Find the LCA of x and z. Let it be P. Traverse the tree from P to find x and store the path by explicitly maintaining a stack. Check if y is in the stack or not. If yes return true, else do the same for the path between P and z. If y is present return true else return false.
- Anirban August 29, 2012@shondik
Dont you think doing (1+3^0.5)^n for large n can lead to precision errors and can sway a lot from the actual answer which would be an interger as the equation func(n) = 2*(func(n-1)+func(n-2)) does not contain any floating point value. This can be solved in O(logn) as proposed by Boson and without any floating point operations.
We can use a stack
Prev_Smaller_Element[0] = Null
stack.push(arr[0])
for i = 1 to N - 1
if(stack.top() < arr[i])
Prev_Smaller_Element[i] = stack.top()
else
while(stack.top >= arr[i] && !stack.empty())
stack.pop()
if(!stack.empty())
Prev_Smaller_Element[i] = stack.top()
else
Prev_Smaller_Element[i] = Null
stack.push(arr[i])
Complexity :- O(N)
- Anirban June 23, 2012
- Anirban August 02, 2013