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

6 Answers

▲

7

▼

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

▲

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.

▲

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?

▲

0

▼

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

# Edge case, should probably ask the interviewer about this.

# 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

▲

0

▼

It can be done using majority voting.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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