Apple Interview Question
Team: QA
Country: United States
Interview Type: In-Person
When I said write an algorithm, she actually told me to write the code on the whiteboard.
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.
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.
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.
- (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;
}
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;
}
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;
}
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