BoredCoder
BAN USER- 2 Answers Programming Problem
Input: Given 2 integer arrays A[M], B[N], where M, N ranges from 1 to 30K and A[i], B[i] can range between 1 to 1000K.
- BoredCoder November 13, 2012
Generate an output array Z[M] such that:
(1) For each j in B[j]; find the min index i in A[i] such that A[i] >= B[j] and then increase A[i-1] by 1.
(2) If B[j] > A[i] for all i then no effect
(3) If B[j] <= A[0] then no effect.
After processing this way generate the output from the above operations to A.
Complexity Constraints: Worst-case time should be O(M+N+H) where H=max(B[N]) and worst-case should be O(M) apart from the input arrays A and B. You can modify the input arrays also.| Flag | PURGE
Also, if(p.data==q.data) is not correct. Here we are comparing nodes by reference and not by values since two different nodes may have the same value.
Rather, it should be: if(p==q)
Perform image segmentation to get the number of islands.
- BoredCoder December 01, 2012A and B are unsorted.
Example: A={1, 2, 0, 4, 3, 2, 1, 5, 7} B={2, 8, 0, 7, 6, 5, 3, 4, 5, 6, 5} then o/p array Z={2, 2, 2, 4, 3, 3, 5, 6, 7}
I also thought like that initially. There can be 2 types. The one you are talking about is by-value. But the one solved above, is by-reference. If it is by reference then it has to be Y-shaped, since at the moment the 2 node reference matches then they will merge since the junction node is actually a single node referenced by 2 lists and then both the list should follow the same path by-reference. If it is by-value, then we need to have a different strategy which cannot be solved in O(n); the best will be sorting both the lists separately and then linear search to find the intersection nodes which will be then O(NlogN).
- BoredCoder December 05, 2012