Jagat
BAN USERThat %2 business is not required. Just return node.value - lv - rv no matter what. That'll give you odd - even, assuming the root is at odd level. Invert the value obtained in the end to get even - odd.
f(root) = root.value - f(root.left) - f(root.right)
= root.value - [root.left.value - f(root.left.left) -
f(root.left.right)] - [root.right.value - f(root.right.left) - f(root.right.right)]
= root.value - root.left.value - root.right.value + f(root.left.right) + f(root.left.left) + f(root.right.left) + f(root.right.right)
You see where it's going.
- Jagat January 18, 2013For the DP solution given by Cerberuz, we can optimize the implementation for space by observing that f(N) depends only on f(N+1) and hence we just need two 1d array, which we keep alternating.
public class Main {
public static int maxPath(int[][] arr) {
int N = arr.length;
int[] sum = new int[N];
for(int i = 0; i < N; i++)
sum[i] = arr[N-1][i];
for(int i = N-2; i >=0; i--) {
System.out.println(Arrays.toString(sum));
int[] temp = new int[N];
for(int j=0; j<N; j++) {
int val = sum[j];
if(j > 0)
val = Math.max(sum[j-1], val);
if(j < N-1)
val = Math.max(sum[j+1], val);
temp[j] = val + arr[i][j];
}
sum = temp;
}
int mx = sum[0];
for(int i = 1; i<N; i++)
mx = Math.max(mx, sum[i]);
return mx;
}
public static void main(String[] args) {
System.out.println(maxPath(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
}
}
Create a counter array of 778 elements (each representing a 3 digit number that represents a 3-page sequence 111 to 888)
Create a hash map of (user:current_sequence) where current sequence is an integer representing the current 3-page sequence. After a page "p" is read for a user, reset the hash value to (cur_seq%100)*10+p. When the resultant number is >100, increment the corresponding index (cur_seq-111) in the counter array.
O(num_users + 800) space complexity. O(n) time complexity, where n is the total number of records.
Dynamic Programming
def getMaxPath(matrix):
m, n = len(matrix), len(matrix[0])
maxPath = [[0] * (n+1) for i in range(m+1)]
maxStreak = 0
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if(matrix[i][j] == 1):
maxPath[i][j] = 1 + max(maxPath[i+1][j], maxPath[i][j+1])
if(maxStreak < maxPath[i][j]):
maxStreak = maxPath[i][j]
return maxStreak
print(getMaxPath([[0, 0, 1, 1], [1, 1, 1, 0], [1, 0, 1, 0], [0, 1, 0, 1]]))
If two different objects have the same hashCode, what happens depends on the output of equals. If key2.equals(key1), then (key1, val1) is replaced with (key2, val2), else a new entry (key2, val2) is added to the same bucket of the hash map.
Please note that hashCode determines which bucket the key-val pair goes to while equals determines whether the object exists on not.
A more interesting question would be "What happens if two objects that are équal' returns different hash codes". In that case, they would hash to different buckets and hence will result in duplicate entries.
The question was confusingly stated. It should have been
There's a BST, with each node having a parent pointer. Given that BST, a pointer to a node (any node), and a value, find the path from the given node (pointer) to the node with the given value.
Assuming the tree is balanced, you can do it in O(log n) time.
Find the lowest common ancestor for the two nodes using the parent pointers. Then it's just a matter of unioning the path from the two nodes to the lowest common ancestor.
Or even better.
If P1 is the path from A to the root and P2 is the path from B to the root. Path from A to B is (P1 - P2) U (P2 - P1), where the subtraction operation is performed on the edges.
Maintain three binary search tree, one for each day.
Each node of the binary search tree is keyed by the username and values are the number of pages searched on that day. Increment the value for that username after each search
At the end of three days, perform an iterative inorder traversal of the three trees and print the customer who appears in exactly two of the three trees and the total count is atleast 3.
Analysis:
Binary search tree to balance for efficient insertion (log n) as well as 3-way merge post-processing (O(N))
Three binary search trees because having a single BST affects the performance (3nlog3n vs 3nlogn for insertion).
Anyway, having a single BST instead of three and adding an additional value <date> makes the process much simpler without compromising much on the performance.
Here's the implementation of the algorithm given by Matt, which is just the Merge algorithm used by merge sort, with a preprocessing step before that to find the second sorted set.
void merge(node** list) {
if(list == null || *list == null)
return;
node* head = *list;
node* p1 = head, p2 = head->next;
while(p2 != null) {
if(p1.data > p2.data) {
p1->next = null;
break;
}
p1 = p1->next;
p2 = p2->next;
}
if(p2 == null)
return; //Already sorted
p1 = head
node* cur = (p1->data < p2->data ? p1 : p2);
*list = cur;
if(cur == p1) p1 = p1->next;
else p2 = p2->next
}
while(true) {
if(p1 == null) {
cur->next = p2;
break;
}
else if(p2 == null) {
cur->next = p2;
break;
}
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
}
}
@hint
No, it's just O(n) where n is the length of the linked list. The first loop finds the start of the second sorted set and the second loop performs the merge and touches each node just once. If you notice, the loops are not nested. They're O(n) independently and hence O(n) overall.
Edit: Peng's loop that is supposed to find the second sorted set is buggy. It doesn't shift the pointers to the next nodes after it has examined a pair of nodes.
Consider arr[][3] as a linkedlist where arr[i][1] stores the data, arr[i][0] stores the previous index, and arr[i][2] stores the next index. Adding an element is trivial. To delete an element, modify the next index of the prev element and prev index of the next element. To prevent possible "holes" in the array on multiple deletions, maintain a "free list" that you can use to add an element to the deleted index instead of using a new slot altogether.
- Jagat September 21, 2012Sort the given array(O(nlogn). Consider every possible combinations of k-1 elements in the given array{nC(k-1) = O(n^(k-1)}. For each combination 'y'=(y1, y2, y3), binary search through the given array to find if there is an element not in 'y' that is equal to x - y1 - y2 - y2
Total time complexity = O(n^(k-1)*logn
Create an array S of size nC2(i.e.,n(n-1)/2), each element of which contains {s:A[i] + A[j], i, j}. Array S should be sorted by s.
Loop through the given array A and for each A[k]; Binary search in S for -A[k]=s where i != k and j != k. If there's such an element, i, j and k form such a triplet.
Space: O(n^2)
Time: O(nlog n)
Maintain a HashTable h(with default val 0 for each key) and update h as you traverse forward through the array A
For each element a (in A)
if h(a) == 0, then h(a) = h(a+1) + h(a-1) + 1
If h(a) > eleWithMax
max = h(a)
eleWithMax = a
Sequence containing eleWithMax is the max sequence. To get this range/sequence, do this.
min=eleWithMax
max=eleWithMax
while(h(--min) > 0 || h(++max) > 0){};
--min; ++max;
Time complexity - O(n), since for each element a, you're only checking h(a+1) and h(a-1).
Space - O(n) I guess, depending on how the hash table is implemented. Any thoughts?
For those looking for a pseudo code
0. Initialize max_area to 0.
1. For each bar in the histogram, traverse forward and backward as long as the bars are at least as tall as the current bar.
1.1. Calculate the area of the rectangle formed (area = current_height * num_of_bars_traversed)
1.2. Update max_area if the area calculated in step 2 is larger.
2. max_area is the area of the rectangle with max area.
RepEllaWilliams, Analyst at A9
I am a perceptive systems analyst adept at designing innovative IT solutions and enhancing existing systems with new features. I ...
Reptunbanataba, Court Reporter at Wildlife officer
I am a court reporter . My work is often licensed and to record proceedings using a steno type machine. through ...
Replvadorjimen, General clerk at Freedom Map
I am a General clerk . I handle a wide range of clerical duties, from filing paperwork to answering phones and ...
Perform the normal "swap-and-permute-the-rest" routine. But....but.... don't swap when it is the same character as the first one.
- Jagat January 18, 2013