Microsoft Interview Question
Software Engineer / DevelopersCountry: India
It works.
Hash all the possible sums and look for the numbers in c in the hash. Complexity is O(a.length*b.length)
Here is the psudo code -
for each element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = -x
end
The outer loop will run for O(n) and inner loop also for O(n), so total complexity will be O(n^2).
To find a pair A[i], B[j] s.t A[i] + B[j] = k.
First make i point to the start of array A and point j to the end of array B.
check -
1. If A[i] + B[j] == k, we found our elements so just exit.
2. If A[i] + B[j] > k, we have to decrease our sum. Decrement j.
3. If A[i] + B[j] < k, we have to increase our sum. Increment i.
So this will run for O(n). Thus making the complexity of the complete method as O(n^2).
here we are assuming, elements are sorted in the array, but this fact is not mentioned in the question.
o(nlogm) solution can be done with some modification. Like take every element from a[0...n] subtract from and do binary search in the b[0...m].
that will be n^2 logn
pick every element from a, subtract from every element of c and binary search b
private static class Pair
{
int a, b;
public Pair(int a, int b)
{
this.a=a;
this.b= b;
}
public String toString()
{
return "i: "+a+", j: "+b;
}
}
public static void ultraQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 , Hashed. Get better hashing?
{
boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
int LEN= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
int OFFSET= CON?c[0]:a[0]+b[0];
ArrayList[] hashedArray= new ArrayList[LEN+1];
for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
for(int j=0; j<b.length; j++)
if(a[i]+b[j]-c[0]>=0&&a[i]+b[j]-OFFSET<hashedArray.length)
{
if(hashedArray[a[i]+b[j]-OFFSET]==null)
hashedArray[a[i]+b[j]-OFFSET]= new ArrayList<Pair>();
hashedArray[a[i]+b[j]-OFFSET].add(new Pair(i, j));
}
for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
if(c[i]-OFFSET<hashedArray.length&&hashedArray[c[i]-OFFSET]!=null)
System.out.println(hashedArray[c[i]-OFFSET]+", k: "+i);
}
public static void resultHashedQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 . Efficient hashing.
{
boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
int MINMAX= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
int OFFSET= CON?c[0]:a[0]+b[0];
String[][] hashedArray= new String[(int)Math.ceil((double)(MINMAX-OFFSET)/(0x1<<8))][];
double alphaRatio= Math.ceil((double)(MINMAX-OFFSET)/(double)hashedArray.length);
for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
{
int correctedNumber= c[i]-OFFSET;
int index= (int)((double)correctedNumber/alphaRatio);
if(index>=0&&index<hashedArray.length)
{
if(hashedArray[index]==null)
hashedArray[index]= new String[(int)Math.ceil(alphaRatio)];
int offsetIndex= correctedNumber-(int)((double)index*alphaRatio);
hashedArray[index][offsetIndex]=hashedArray[index][offsetIndex]==null?"":hashedArray[index][offsetIndex];
hashedArray[index][offsetIndex]+="k: "+i;
}
}
for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
for(int j=0; j<b.length; j++)
{
int correctedNumber= a[i]+b[j]-OFFSET;
int index= (int)(((double)correctedNumber)/alphaRatio);
if(index>=0&&index<hashedArray.length&&hashedArray[index]!=null)
{
if(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]!=null)
System.out.println(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]+", i: "+i+", j: "+j);
}
}
}
public static void main(String ar[]){
int arr1[]={1,2,3,4,5,6};
int arr2[]={1,2,3,4,5,6};
int arr3[]={1,2,3,4,5,6};
int i, j, k=0;
while( k<arr3.length ){
for( i=0;i<arr1.length;i++ ){
if( arr1[i]<arr3[k]){
for( j=0;j<arr2.length;j++ ){
if( arr1[i]+arr2[j]==arr3[k] ){
System.out.println( arr1[i]+"/"+arr2[j]+"/"+arr3[k] );
}
else if( arr1[i]+arr2[j]> arr3[k]){
break;
}
}
}
}
k++;
}
}
output:
1/1/2
1/2/3
2/1/3
1/3/4
2/2/4
3/1/4
1/4/5
2/3/5
3/2/5
4/1/5
1/5/6
2/4/6
3/3/6
4/2/6
5/1/6
that is the simplest of the solution we can give for the problem with time complexity O(n^2) or O(mn)....
any idea how we can improve it
Can be solved in O(n^2) time and O(n) space.
1. Store all the values of c array in a hashmap with value as index - O(n) space
2. Then get the sum of all the pairs of elements of array a and array b and check whether they are present in hashmap.
3. If present then print the values.
Assuming that each array contains n elements.
Can be easily modified for different elements also
Hashmap is no doubt a smart approach which reduces the computational complexity. But you missed one thing- what if c contains negative numbers?
@ramblesrm: It could be easily done by using C++ maps, would work for negative elements also
Thanks for the information. I would like to read about that. Could you provide me a link please?
And help me out here, but our algorithm should be language-independent..
A couple things. 1) there is absolutely no reason a HashMap couldn't work with negative numbers 2) to avoid needlessly wasting space, you should use sets instead of maps here. You only need keys here, not key-value pairs. 3) C++-style sets are called TreeSet in Java, and many languages have some sort of support for these.
i = j =k = 0;
while(k<k_max && i<i_max && j<j_max) {
if (a[i] + b[j] == c[k]) {
// print a,b,c
k++;
}
else if (a[i] + b[j] > c[k]) {
k++;
}
else if (a[i] + b[j] < c[k]) {
if (a[i+1] < b[j+1] )
i++;
else
j++;
}
}
UPDATE: this code does'n work.
to shondik:
I'm sorry I forget add '1' in line if (a[i] < b[j] ).
But it been in my mind.
Try it again.
This code assumes that there will be only one pair of (i,j) that would satisfy the given condition which is not correct.
Try with example a = b = [1,2,3], c= [4].
@zprogd : please write your final code including the statement { if(a[i]<b[j]) } which you forgot to write
1.Take two pointers, i pointing to the start of a[] & j pointing to the start of b[].
2. for every item in c[], find a pair of items in a[] & b[](O(m+n)).
So, time complexity is: k(m+n) where c[] contains k elements.
@shondik:
Your algorithm doesn't give all the pairs
Take a[]={1,3,6}
b[]={1,6,7}
For an item = 7 in c
Your algo will print (1,6,7) and not (6,1,7)
Bcoz that can't be done in O(m+n) time
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i=0,a[]={1,5,7,9,12};
int j=0,b[]={3,8,14,15,19,20};
int k=0,c[]={5,12,17,23,25,26,30};
int ie=(int)sizeof(a)/sizeof(a[0]);
int je=(int)sizeof(b)/sizeof(b[0]);
int ke=(int)sizeof(c)/sizeof(c[0]);
int t=1;
while(1)
{
if(a[i]+b[j]==c[k])
{
printf("a[%d]=%d , b[%d]=%d , c[%d]=%d \n",i+1,a[i],j+1,b[j],k+1,c[k]);
j++;
k++;
}
else if(a[i]+b[j]>c[k])
{
if(a[i]>b[j])
while(1)
{ i--;
if(a[i]+b[j]<c[k])
{ k++;break; }
else if(a[i]+b[j]==c[k]) break;
}
else {
while(1)
{ j--;
if(a[i]+b[j]<c[k])
{ k++;break; }
else if(a[i]+b[j]==c[k]) break;
}
}
}
else {
if(a[i]>=b[j])
j++;
else i++;
}
if(i>=ie||j>=je||k>=ke)
break;
}
return 0;
}
#include<stdio.h>
main()
{
int i,j,n,m;
int c[100];
int a[100];
int b[100];
printf("both array size are same\n");
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n");
for(i=0;i<m;i++)
scanf("%d",&b[i]);
if(n==m)
{
for(i=0;i<n;i++)
c[i]=a[i]+b[i];
for(i=0;i<n;i++)
printf("%3d\n",c[i]);
}
else
printf("arrey size is note same");
}
static void Main(string[] args)
{
int[] a = new int[2] { 1, 2};
int[] b = new int[3] { 2, 4, 5};
int[] c = new int[3] { 3, 4, 6};
int i, j=0, k=0, alen = a.Length, blen = b.Length, clen = c.Length;
for (i = 0; i < alen; i++)
{
j = k = 0;
while(j<blen)
{
if (k >= clen)
{
j++;
continue;
}
else if (a[i] + b[j] == c[k])
{
Console.WriteLine(a[i] + "-" + b[j] + "-" + c[k]);
k++;
if (j > blen-1)
break;
}
else
{
k++;
if (k >= clen)
{
j++;
k = 0;
}
}
}
I initially had a O(n^3), but later brought this down to O(n^2). Not tried to check if it can still be brought down to linear (O(n)).
package com.dsna.puzzles;
import java.util.HashMap;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
//given 3 arrays, array a, array b, array c.
//find all pairs where a[i] + b[j] = c[k]
//a, b , c are sorted
public class ArrayAdditionPuzzle {
int[] arrayA = new int[]{10,20,30,40,50,60,70,80,90,100,200};
int[] arrayB = new int[]{20,40,60,80,300};
int[] arrayC = new int[]{40,80,100};
public static void main(String[] args) {
new ArrayAdditionPuzzle().findPairs();
}
public void findPairs(){
int maxArrayC = arrayC[arrayC.length-1];
HashMap<Integer,Integer> arrayCContents = new HashMap<Integer, Integer>();
for(int i=0;i<arrayC.length;i++){
arrayCContents.put(arrayC[i], i);
}
for(int i=0 ; i< arrayA.length ; i++){
if(arrayA[i] > maxArrayC){
break;
}
for(int j=0; j<arrayB.length;j++){
if(arrayB[j]> maxArrayC || arrayA[i]+arrayB[j] > maxArrayC){
break;
}else{
if(arrayCContents.containsKey(arrayA[i] + arrayB[j])){
System.out.println("arrayA[" +i + "] + arrayB[" +j + "] = arrayC[" + arrayCContents.get(arrayA[i]+arrayB[j]) +"]" );
}
}
}
}
}
}
Just search 3SUM on wikipedia. I swear I'm not making you look for porn.
- eugene.yarovoi June 28, 2012