Microsoft Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
I don't think your solution will work. As minHeap can only return the min element but there is no guarantee that minHeap.get(i + 1) > minHeap.get(i), except for i = 0
@Kelvin
I missed to mention getNthElement(int N) method. here it is ...
I am using concept of heap sort to find Nth element ..But I am not sorting all elements. it will sort only N elements.
public int getNthElement(int N){
int result = 0;
for(int i =0; i<N; i++){
result = minHeap.removeRoot();
minHeap.heapify();
}
return result;
The task is not clear, but i guess, that we are speaking about finding K-th sum from a[i]+b[j] for ANY {i, j}. Becouse if i==j, it is simply binary search, and there is no reason to complicate the task description.
___________________________
This task reduced to another popular task, which has been discussed here many times:
Find K-th element in Sorted Matrix.
Let's imagine that we have N*M Matrix: S[i][j] = a[i]+b[j];
a[0]+b[0] a[0]+b[1] ... a[0]+b[m]
a[1]+b[0] a[1]+b[1] ... a[1]+b[m]
...
a[n]+b[0] a[n]+b[1] ... a[n]+b[m]
A and B was sorted list. So each column and each row is sorted too.
Here is the link to solution:
question?id=6335704
or you can find it, as the most commented question from Google's interview.
I use word 'imagine', becouse we don't need to build it for real.
To solve derivative problem, all numbers from matrix are needed only once, so we can calculate sum in runtime, without saving to matrix.
We can assume matrix with these two array... like A represents rows and B represents columns.
We need only 3rd element, it will lie in 3X3 matrix if more than 7 sums are not same(duplicate).
So first we will check in first 3X3 matrix than move to 6X6 ...9X9 .... so on.
int m = length of first array;
int n = length of second array;
MaxHeap maxHeap = new MaxHeap(3); // Max heap without duplicate, add() method will check if there is duplicate.
int maxLength = max(m,n);
for(k = 0; K < maxLength; K = K+3){
for(int i = K; (i < K+3) && (i < m); i++){
for(int j = K; (j < K+3) && (j < n); j++){
maxHeap.add(A[i]*B[j]);
if(maxHeap.size() == 3){
return maxHeap.root();
}
}
}
}
Could you explain why you used matrix 3x3? If you need only 3rd element, why don't you use matrix 2x2, which gives the first four sums?
We need to find 3rd element, it will be 3rd in row (if row elements are smaller than columns - like in this question) and similar for column, if column's elements are smaller than rows.
If we have duplicates than we have to check for bigger array in next iteration.
I don't think this is correct. Think about the below sample arrays. It cannot get the correct result 8
ArrayA: 1, 1, 1, 2, 2, 2, 3, 3, 3
ArrayB: 5, 5, 5, 10, 10, 10, 20, 20, 20
@digjim
Thanks pointing that out ... this approach will not work. I tried to reduce the number of iteration. It will work with all unique sums in heap. No magic behind this.
public static int getNthElement(int[] A, int[] B){
MinHeap<Integer> maxHeap = new MinHeap<Integer>();
int m = A.length;
int n = B.length;
int maxLength = Math.max(m,n);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
maxHeap.insert(A[i] + B[j]);
}
}
return maxHeap.getNthElement(3);
}
Actually, If there is no duplicated items in Array, your solution is pretty good. What do you think about my solution I posted below. I added below three condition in the for().
i < nth
j < nth
i+j < nth
Since the arrays are sorted, a modified *merge* subroutine (of mergesort) can get the job done in O(n) time and O(1) space.
The arrays' *walk* of merge subroutine can keep track of the previously computed sum and current sum to disregard duplicates and stop when the Nth sum is reached.
The arrays' walk can be done as follows: Given indices i and j, we have previoussum = a[i] + a[j] and currentsum= Min((a[i] + a[j+1]) , (a[i+1] + a[j])). Update the pointers i & j accordingly for the next step in the arrays' walk.
Since we only need to check the matrix on top-left, we can have two loop (i, j) , and i+j must less than the Nth.
array A is {1,3,4,8,10},
array B is {20, 22, 30, 40}.
the sum set will be{21(1+20),23(1+22 or 3+20), 25(3+22), 24(4+20), 26(4+22)...}
the 3rd element in the sum set is 24.
public static int GetNthSum(int[] arrayA, int[] arrayB, int nth)
{
// Remove duplicated first in two arrays
int[] sumList = new int[nth];
int tempSum;
int temp;
int tempCount = 0;
for (int i = 0; i < arrayA.Length && i < nth; i++)
{
for (int j = 0; j < arrayB.Length && j < nth && i + j <= nth; j++)
{
tempSum = arrayA[i] + arrayB[j];
for (int k = 0; k < nth; k++)
{
if (k == tempCount)
{
sumList[k] = tempSum;
tempCount++;
break;
}
else
{
if (tempSum == sumList[k])
{
break;
}
else if (tempSum < sumList[k])
{
temp = sumList[k];
sumList[k] = tempSum;
tempSum = temp;
}
}
}
}
}
if (tempCount == nth)
{
return sumList[tempCount - 1];
}
else
{
return -1;
}
}
I am not sure if this is the approach, or I could explain my logic properly, any clarifications...welcome
This works in nlog(smaller array.length) time, where n is the position of the number we are trying to find
If someone could find any bug then welcome... :-)
a[] = { 1, 3, 4, 8 , 10}
b[] = {20, 22, 30 ,40}
1. create an array index[b.length] )sizeof the smaller array, value 0 for each element
2. index array will contain current index of array a, for each element of array b
3. Create a min heap of size b.length, to get the current min
4. insert sum of a[0] + b[i] into the min heap (20 + 1, 22 + 1, 30 + 1, 40 + 1)
5. Now until we get the nth element, do the following
6. extract the current min (in this case 20+1)
7. increament the corresponding index pointer in this case index of 20 will be increamented to 1 from 0
8. insert this new element in to the heap (in this case 20 + 3 will be inserted into the heap)
//so next time the comparision will be between 20 + 3, 22 + 1, 30 + 1, 40 + 1
9. one thing we need to take care of, like for the below case
a[] = {1,2,3,4,5}
b[] = {20, 60, 80, 100}
if index of an element exceeds the limit like in the above case, 20+1, 20+2, 20+3, 20+4, 20+5 and then it exceeds so insert INT_MAX into the heap,
so that the pointer of 20 will never get increamented again.
We can take care of the duplicate sum like 20+3, 22+1 case through this logic also, by maintaining a prev min and current extracted min.
Here is the solution
class Node implements Comparable<Node> {
int sum, ai, bi;
public Node(int s, int a, int b) {
this.sum = s;
this.ai = a;
this.bi = b;
}
@Override
public int compareTo(Node o) {
return this.sum - o.sum;
}
@Override
public String toString() {
return "Node{" +
"sum=" + sum +
", ai=" + ai +
", bi=" + bi +
'}';
}
}
/**
* Duplicate sum Not allowed
* Algo:
* 1. create all the sum nodes for a[i] + b[0]
* 2. Build priority queue using above nodes
* 3. For each poll
* * 3.1: Insert the appropriate pair in PQ either a[i+1]+b[j] or a[i]+b[j+1] if not seen as pair, not seen as sum
*
* Time Complexity: N length of a[], M length of b[]
* Step 1: O(N)
* Step 2: O(N) Priority queue could be build in O(n)
* step 3: In worst case, all the sum are unique and we need to find the last element. This case PQ will contain max(N,M)+1 elements since we remove 1 and add 2 so effectively adding 1 element.
* That takes O(log(Max(N,M)) time run for n times { n= nth sum element}
* O(n * log(Max(N,M) )
*
* O(N) + O(N) + O(n * log(Max(N,M) ) => O(n * log(Max(N,M) )
*
* Space: O(Max(N,M))
*
*/
class SolutionNthItemInSumOfTwoArraysDuplicateSumNotAllowed {
public int nthItem(int[] a, int[] b, int n) {
if (a == null || a.length == 0) {
if (b.length >= n)
return b[n - 1];
else
return Integer.MIN_VALUE;
}
if (b == null || b.length == 0) {
if (a.length >= n)
return a[n - 1];
else
return Integer.MIN_VALUE;
}
return nthItem(a, b, a.length, b.length, n);
}
private int nthItem(int[] a, int[] b, int aLength, int bLength, int n) {
Set<int[]> seenPair = new HashSet<>();
Set<Integer> sumSeen = new HashSet<>();
List<Node> nodes = new ArrayList<>();
//O(aLength)
for (int i = 0; i < a.length; i++) {
int sum = a[i] + b[0];
if (!sumSeen.contains(sum)) {
nodes.add(new Node(a[i] + b[0], i, 0));
sumSeen.add(sum);
seenPair.add(new int[]{i, 0});
}
}
//O(aLength)
PriorityQueue<Node> priorityQueue = new PriorityQueue<>(nodes);
int i = 0;
Node currentPair = null;
while (i < n && !priorityQueue.isEmpty()) {
currentPair = priorityQueue.poll();
int[] pairWithA = {currentPair.ai + 1, currentPair.bi};
int[] pairWithB = {currentPair.ai, currentPair.bi + 1};
if (!seenPair.contains(pairWithA) && currentPair.ai + 1 < aLength && !sumSeen.contains(a[currentPair.ai + 1] + b[currentPair.bi])) {
seenPair.add(pairWithA);
sumSeen.add(a[currentPair.ai + 1] + b[currentPair.bi]);
priorityQueue.offer(new Node(a[currentPair.ai + 1] + b[currentPair.bi], currentPair.ai + 1, currentPair.bi));
}
if (!seenPair.contains(pairWithB) && currentPair.bi + 1 < bLength && !sumSeen.contains(a[currentPair.ai] + b[currentPair.bi + 1])) {
seenPair.add(pairWithA);
sumSeen.add(a[currentPair.ai] + b[currentPair.bi + 1]);
priorityQueue.offer(new Node(a[currentPair.ai] + b[currentPair.bi + 1], currentPair.ai, currentPair.bi + 1));
}
i++;
}
if (i < n)
return Integer.MAX_VALUE;
assert currentPair != null;
return currentPair.sum;
}
}
Let array a anb array b ,start from start of both i,j i=0 j=0, now a[i]+b[j] is lowest sum possible ,counter =1,now compare a[i+1] with b[j+1] which one is smaller increase the respective value of i or j and find next lower sum and do counter++ do this upto counter!=N
Are you sure comparing a[i+1] with b[j+1] enough?
Do you need a counter? Running loop on condition i+j < N should be enough.
Ahh ic. The question is funky in wording. "Set" and Nth element just do not work together in terms of definition.
Why wouldn't an _idiot_ posting this question give an example at least?
input
0 1 2 20 21 22
10 11 12 14 15 59
output
"What's the order" of this "set of pairs/sums" ?
Guess what, writing the example with automatically give the idiot the algorithm. So let him/her do that? Not my decision.
I am adding both array (start from least significant digits). We need to find sum till (length -n)th element.
Example: Suppose we need to find 2nd sum ...
than we will stop after (5+1 - 2)th element and we will return it.
1 2 3 4 5
1 2 3 4 5
-------------------
- 4 6 9 0
int *AddArrays(int a[], int alen, int b[], int blen, int n)
{
int maxLen = max(alen, blen);
int *c = new int[maxLen + 1];
int acur = alen - 1;
int bcur = blen - 1;
int ccur = maxLen;
int carry = 0;
//Nth from start will be (length of sum array - N)th from end.
int nth = (maxLen + 1 - n);
while(ccur >= 0)
{ if(nth-- == 0){
return c[ccur];
}
int cur = carry;
if(acur >= 0)
cur += a[acur--];
if(bcur >= 0)
cur += b[bcur--];
c[ccur--] = cur % 10;
carry = cur/10;
}
return c;
}
After modification of question, this answer does not make sense so pls avoid this.
Answer should be submitted in single go.... :(
here is the simple impletation in c# with O(n):
static void FindNthCrossSum(int n)
{
int i = 1;
int p1 = 0;
int p2 = 0;
var result = 0;
if (n == 1) {
Console.WriteLine("First:{0}", s1[0] + s2[0]);
return;
}
while (i++ < n && p1 < s1.Length && p2 < s2.Length)
{
result = GetSum(s1, ref p1, s2, ref p2);
}
Console.WriteLine("{0}th result:{1}", n, result);
}
static int GetSum(int[] s1, ref int p1, int[] s2, ref int p2)
{
var sum1 = s1[p1];
if (p2 < s2.Length - 1) { sum1 += s2[p2 + 1];}
var sum2 = s2[p2];
if (p1 < s1.Length -1) { sum2 += s1[p1 + 1] ;}
if (sum1 < sum2)
{
p2++;
return sum1;
}
else if (sum1 == sum2)
{
if (s1[p1] < s2[p2])
{
p2++;
}
else
{
p1++;
}
return sum1;
}
p1++;
return sum2;
}
Here is straight forward and simple solution ....no magic behind this... just putting all unique sums in a min heap.. and returning 3rd element from the heap.
- Ajeet November 02, 2013