Facebook Interview Question: Given N credits cards, determ... | Glassdoor

## Interview Question

Software Engineer Intern Interview

# Given N credits cards, determine if more than half of them

belong to the same person/owner. All you have is an array of the credit card numbers, and an api call like isSamePerson(num1, num2).

2

I guess this should work:

def MoreThanHalfBelongToSameOwner(array):
dict = {}
for number in array:
newNumber = True
for key in dict.keys:
if(isSameOwner(number,key)):
dict[key] = dict[key] + 1
newNumber = False
if(dict[key] > len(array) / 2):
return True
if(newNumber)
dict[number] = 1

return False

David Anderson on Dec 4, 2012
8

Hi David,
The complexity of your algorithm is O(n^2). Can we do better?
If we could reduce this problem to finding major element, then it would be solved in linear time. http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Alex on Dec 26, 2012
0

Worst case linear number of comparisons 1/2n + 1/4n + ... = O(n) to find the number that is repeated the most. Then, compare it with all the numbers in O(n) and return true if at least half are equal to it. The proof as to why this works is a bit complicated.

SP on Jan 7, 2013
0

I didn't get how we can do it in O(n). You don't have a list of repeated numbers, you have n distinct credit card numbers and some of them might belong to the same person. But in order to check that, you need to make an api call.

In this case, how come there can be a O(n) solution?

Anonymous on Feb 7, 2013
1

Anon: The reason the O(n) solution that Alex posted works is because it never compares more than 2 things at once. Comparing two things is very possible in terms of the API.

To see this in action, here is some python code implementing that algorithm:

def half_same_person(ccs):
num_ccs = len(ccs)
# Need to divide by 2.0, not 2, to make sure it gets casted as a float
threshold = num_ccs / 2.0
# I figure False is most likely answer
if num_ccs == 0:
return False
# Clearly True
if num_ccs == 1:
return True
counter = 0
for cc in ccs:
if counter == 0:
majority = cc
counter = 1
else:
if is_same_person(cc,majority):
counter += 1
else:
counter -= 1
# By the end of this loop, 'majority' will hold a credit card owned by the person
# with the most cards. Now we just have to find out if this person has more than half
# of the cards
num_majority = 0
for cc in ccs:
if is_same_person(cc,majority):
num_majority += 1
return num_majority > threshold

Scott on Feb 17, 2013
0

It can be done using majority voting.

szilard on Nov 1, 2014