find an element in an rotated integer array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently?
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
int rotated_binary_search(int A[], int N, int key) {
ReplyDeleteint L = 0;
int R = N - 1;
while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;
// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}