Adobe Interview Question


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
4
of 4 vote

If additional space is provided then

import java.util.HashMap;
import java.util.Scanner;
public class IntwoSetsValueEqualsToAplusB {
public static void main(String[] args) {
Integer setA[]={180,84,168,171,195,42,71,164,59,118,102,135,78,110,204,196,136,154,30,130,3,52,29,172,33,86,27,23,214,46,110,180,131,63,136,112,105,208,62,165,113,165,85,191,60,75,173,197,14,203,112,18,41,142,191,74,13,4,98,13,51,208,193,182,57,115,80,163,110,143,114,8,93,200,199,154,61,158,137,76,147,35,94,188,178,70,49,191,75,147,205,126,141,184,94,198,85,174,146,195};
Integer setB[]={84,71,102,89,87,78,6,6,7,8,89,9};
int value=new Scanner(System.in).nextInt();
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
hm=buildmap(setB);
for(int i:setA) if(hm.containsValue(value-i)) System.out.println(i);
}
private static HashMap<Integer, Integer> buildmap(Integer[] setB) {
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
for(Integer i:setB) hm.put(i.hashCode(),i);
return hm;
}
}


in O(n+m)

- dilip kasana September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Can you give C++ code for this plz.

- dew September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

1.sort first array in ascending order
2.sort second array in descending order.
3.traverse the elements in both array.
4.If sum of two numbers is greater than given sum then move to next element at B
else
move to next element in A.
5.repeat till sum is equal to given sum.

- jinu October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Here is the Algo Say two sets A and B have size a and size b where a<=b
1. Build Hashmap of size a for each element in A
2. Now go through each element of B(say x) and look for (val - x) in HashMap, If found return true.

- loveCoding September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. sort B - nlogn
2. take one element from A, search for the second element in B(using binary search) - nlogn

total - nlogn

- devendar September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Devendar- Dats Not Effecient ..We can Use Dynamic Programming Which will take less than nlogn

- Lucy September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think DP will give a better solution here. Can you please give the explanation.

- Bruce October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

If additional space is provided then

import java.util.HashMap;
import java.util.Scanner;
public class IntwoSetsValueEqualsToAplusB {
public static void main(String[] args) {
Integer setA[]={180,84,168,171,195,42,71,164,59,118,102,135,78,110,204,196,136,154,30,130,3,52,29,172,33,86,27,23,214,46,110,180,131,63,136,112,105,208,62,165,113,165,85,191,60,75,173,197,14,203,112,18,41,142,191,74,13,4,98,13,51,208,193,182,57,115,80,163,110,143,114,8,93,200,199,154,61,158,137,76,147,35,94,188,178,70,49,191,75,147,205,126,141,184,94,198,85,174,146,195};
Integer setB[]={84,71,102,89,87,78,6,6,7,8,89,9};
int value=new Scanner(System.in).nextInt();
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
hm=buildmap(setB);
for(int i:setA) if(hm.containsValue(value-i)) System.out.println(i);
}
private static HashMap<Integer, Integer> buildmap(Integer[] setB) {
HashMap<Integer, Integer> hm=new HashMap<Integer,Integer>();
for(Integer i:setB) hm.put(i.hashCode(),i);
return hm;
}
}

- Anonymous September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution depends on set implementation. If set is implemented using a bst or a red black tree then no sorting is required at all. Locate element greater than equal to sum in a. Now all children are less than equal to the sum. Do the same for b. Now you select one element from a and find if sum - a is found in b.

- Noobie September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. iterate over hastSet1.
2. for every element(lets say i), check if hashSet2.contains(value - i) //where value is a + b
3. if true, return 1

Complexity:
worst case: O(n) - as complexity of contains is O(1) and iterating over hashset has O(n)
best case: O(1) - as at first element you can get elements and it returns 1 when such values are found, so return 1 over there itself.

- milan September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Spock September 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int setABHasSum(int* setA, int aLen, int* setB, int bLen, int val)
{
int i, j;
int a, b;
int bExpected;

if(aLen == 0 || bLen == 0)
return FALSE;


for(i = 0; i < aLen - 1; i++)
{
a = *(setA+i);
bExpected = val - a;
for(j = 0; j < bLen; j++)
{
b = *(setB+j);
if(b == bExpected)
return TRUE;
}
}

return FALSE;
}

- Sid September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main()
{ int a[10]={12,9,7,5,3,2,1};
int b[10]={2,4,6,7,9,10,15};
int m;

cout<<"enter the sum value\n";
cin>>m;
for(int i=0,j=0;i<7&&j<7;)
{ int sum=a[i]+b[j];
if(sum<m)
{ j++;}
else if(sum>m)
{ i++;}
else if(sum==m)
{ cout<<a[i]<<" "<<b[j]<<endl;
i++; j++;
}
}
system("pause");
return 0;
}

- Mukesh Kumar Dhaker October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

guys
i assumed that first first subset is in decending order
and second one is in acending order...
if they are not acending or decending order than first sort them....

- Mukesh Kumar Dhaker October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

qsort arr1 and arr2
i=0
j=sizeof(arr2)-1
do as long possible or match found
if(arr1[i] + arr2[j] >val)
j--
else if(arr1[i]+arr2[j]<val)
i++;

- okaysh October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and 1=

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' and 1=

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

\'

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ookjk85h74

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 OR 1=1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1' OR '1'='1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1'1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' 1 AND 1=1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 AND 1=1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1\'1

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

) or ('1'='1--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' or 1=1/*

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' or 1=1--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

order by 1000/*

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

order by 1000;--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' order by 1000/*

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' order by 1000;--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

' or 1=1--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

" or 1=1--

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

') or ('a'='a

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Find MaxA and MaxB, the largest element in A and B. If their sum is greater than val return true, else return false.

complexity : O(n)

- codac September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong, take for instance this data set:
A = [1, 2, 3] B=[5,6,7] val = 5
your approach says there is such two numbers
whereas no two numbers from A and B sum up to 5

- hr September 19, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More