Facebook

  www.facebook.com
  www.facebook.com

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

Interview Answer

6 Answers

1

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
4

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

Scott on Feb 17, 2013
0

It can be done using majority voting.

szilard on Nov 1, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.