Apple Interview Question


Team: QA
Country: United States
Interview Type: In-Person




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

There are lots of ways to solve this problem. If M is really small, like single digits small, the best approach is probably to take each element in one list and check it against each element in the second list. For cases (ii) and (iii), prepare a hashset of the smaller list, and use that to see which elements of the larger list are in the smaller list.

- eugene.yarovoi April 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When I said write an algorithm, she actually told me to write the code on the whiteboard.

- apple-maybe? April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, it's entirely reasonable to ask for code for something like this:

List smaller, larger;
If (NList.size() > MList.size())
{
Smaller = MList;
Larger = NList;
}
else
{
Smaller = NList;
Larger = MList;
}
Set H = new Hashset();
foreach item in Smaller
{
H.add(item);
}

List ResultList = new ArrayList()
foreach item in Larger
{
If (H.contains (item)) { resultList.add(item); }
}

Return resultList;

This isn't meant to be 100% syntactically correct, but that's it.

- eugene.yarovoi April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
I saw that you have posted a couple of questions. Eugene, I think has given a good answer to your question.
I would just like to add, In questions like these you should always ask more about the domain.
It is said u have 2 lists of numbers. How are those lists generated?
If, say, those numbers are the "processing time" a web server takes to process queries - then its probably easier for you to "count sort" elements in List B - no matter the size
If, say, the numbers are lengths of various strings - in that case, as suggested by eugene, use a hash map. In case of really large lists one can think of creating BST or MST out of the list with a lower count.

- yogeshnachnani April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When she handed me the piece of paper, I asked her about how the lists are generated and she said randomly.

- apple-maybe? April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the the interviewer was expecting was:
1) when M<<<N the solution is to make a BST with the elements in N and search each of the elements in M. it takes O(M(Log(N))) time.
Similarly for other cases the the complexity is O(N(Log(M))) and O(M(Log(M))) when M==N.

- RK April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

How is it O(M(Log(N))) for M<<<N . Building BST itself is O(N(Log(N)))

- Anonymous July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better way you can sort larger array in NlogN and then binar search each element in smaller array in MlogN
complexity : NlogN + MlogN

- eddy November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (NSArray*)intersectionOfArray:(NSArray*)bigArray withArray:(NSArray*)smallArray {
//Assume big and small are correct otherwise swap them

//Space consuming O(nLog(n))
NSArray *sortedBigArray = [bigArray sortedArrayUsingSelector:@selector(compare:)];
NSMutableArray *result = [NSMutableArray new];
for ( NSObject *item in smallArray){
if([sortedBigArray contains:item]) {
[result addObject:item];
}
}

NSArray *returnVal = [NSArray arrayWithArray:result];
[result release];
return returnVal;
}

- edward.ishaq November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved in many different ways. I guess use of BitSet is much faster.. any thoughts?

private static Set findCommonInUnSortedArray(int a[], int b[]) {
		Set commonSet = new HashSet();
		int[] array1 = null;
		int[] array2 = null;
		if(a.length > b.length) {
			array1 = a;
			array2 = b;
		} else {
			array1 = a;
			array2 = b;
		}

		int array1length = array1.length;
		int array2length = array2.length;
		for(int i =0; i < array1.length; i++) {
			for(int j=0; j<array2length; j++) {
				if(array1[i] == array2[j]) {
					commonSet.add(array1[i]);
				}
			}
		}

		return commonSet;
	}

	private static Set findCommonInUnSortedArrayUsingSet(int a[], int b[]) {
		Set commonSet = new HashSet();
		int[] array1 = null;
		int[] array2 = null;
		if(a.length > b.length) {
			array1 = a;
			array2 = b;
		} else {
			array1 = a;
			array2 = b;
		}

		int array2length = array2.length;

		Set array1Set = new HashSet();
		for(int i =0; i < array1.length; i++) {
			array1Set.add(array1[i]);
		}

		for(int j=0; j<array2length; j++) {
			if(array1Set.contains(array2[j])) {
				commonSet.add(array2[j]);
			}
		}

		return commonSet;
	}

	private static Set findCommonInUnSortedArrayUsingRetainAll(int a[], int b[]) {
		Set commonSet = new HashSet();
		int[] array1 = null;
		int[] array2 = null;
		if(a.length > b.length) {
			array1 = a;
			array2 = b;
		} else {
			array1 = a;
			array2 = b;
		}

		int array2length = array2.length;

		Set array1Set = new HashSet();
		for(int i =0; i < array1.length; i++) {
			array1Set.add(array1[i]);
		}

		Set array2Set = new HashSet();
		for(int i =0; i < array2.length; i++) {
			array2Set.add(array2[i]);
		}

		array1Set.retainAll(array2Set);

		return array1Set;
	}

	@SuppressWarnings("unchecked")
	private static <T> T[] intersection(T[] a, T[] b, Class<? extends T> c) {
	    HashSet<T> s = new HashSet<T>(Arrays.asList(a));
	    s.retainAll(Arrays.asList(b));
	    return s.toArray((T[]) Array.newInstance(c, s.size()));
	}

	private static BitSet findCommonInUnSortedArrayUsingBitSet(int a[], int b[]) {
		BitSet b1 = new BitSet();
		BitSet b2 = new BitSet();
		for(int aa : a){
			b1.set(aa);
		}
		for(int bb : b){
			b2.set(bb);
		}
		b2.and(b1);

		return b2;
	}

	 private static List findCommonInUnSortedArray2(int a[], int b[]) {
	        List commonList = new ArrayList();
	        List[] hashtable;
	        int[] array1;
	        int[] array2;
	        if (a.length > b.length) {
	            hashtable = new ArrayList[a.length];
	            array1 = a;
	            array2 = b;
	        } else {
	            hashtable = new ArrayList[b.length];
	            array1 = b;
	            array2 = a;
	        }
	        Arrays.fill(hashtable, new ArrayList());
	        for (int i = 0; i < array1.length; i++) {
	            hashtable[array1[i] % hashtable.length].add(array1[i]);
	        }
	        for (int i = 0; i < array2.length; i++) {
	            if (hashtable[array2[i] % hashtable.length].contains(array2[i])) {
	                commonList.add(array2[i]);
	            }
	        }
	        return commonList;
	    }

	 private static List findCommonInUnSortedArray3(int a[], int b[]) {
	        List commonList = new ArrayList();
	        List hashtable;
	        int[] array1;
	        int[] array2;
	        if (a.length > b.length) {
	            hashtable = new ArrayList(a.length);
	            array1 = a;
	            array2 = b;
	        } else {
	            hashtable = new ArrayList(b.length);
	            array1 = b;
	            array2 = a;
	        }
	        for (int i = 0; i < array1.length; i++) {
	            hashtable.add(array1[i]);
	        }
	        for (int i = 0; i < array2.length; i++) {
	            if (hashtable.contains(array2[i])) {

	                commonList.add(array2[i]);
	            }
	        }
	        return commonList;
	    }

- Pani Dhakshnamurthy November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution with Set intersection

public Set FindCommonElements(Integer[] first, Integer[] second)
{

    Set<Integer> set1=new HashSet<Integer>(Arrays.asList(first));
    Set<Integer> set2=new HashSet<Integer>(Arrays.asList(second));

    // finds intersecting elements in two sets
    set1.retainAll(set2);

    return set1;

}

- ATuring September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Sort larger array in NlogN and then binary search each element in smaller array in MlogN.
complexity: NlogN + MlogN

- eddy November 19, 2015 | Flag Reply


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