2
\$\begingroup\$

I had an interview question like this:

In a company there are different people. One can measure how well they suits for pair coding as follows:

First, let us compute the PAIRS-value which is the number of letters P, A, I, R, S given in two people names. Then compute the sum of consecutive digits and sum of digits if the result is over 9.

Then do the same for the numbers one got in previous step: sum two adjacent numbers and again, compute the sum of digits of every number if that number is > 10. Repeat this until you have only two digits, which measures the goodness of pairs. For example, "Erkki Esimerkki" and "Matti Meikäläinen" has PAIRS-value 58:

First [P = 0, A = 1, I = 6, R = 2, S = 1] and then

[0 + 1 = 1, 1 + 6 = 7, 6 + 2 = 8, 2 + 1 = 3]
[1 + 7 = 8, 7 + 8 = 15 => 1 + 5 = 6, 8 + 3 = 11 => 1 + 1 = 2]
[8 + 6 = 14 => 1 + 4 = 5, 6 + 2 = 8]
[5, 8] = 58%

Now, there are many worker names given in http://reaktor.fi/wp-content/uploads/2014/08/fast_track_generoitu_nimilista.txt . Find the number of perfect pairs, i.e. those who have PAIRS-value 99%.

Is there a faster way to solve as the following code:

import urllib.request

def sum_digits(number):
    while number > 9:
       temp = number
       y1 = number//10
       y2 = temp % 10
       number = y1 + y2
    return number

def compute_percent(pairs):
    x1 = sum_digits(pairs[0] + pairs[1])
    x2 = sum_digits(pairs[1] + pairs[2])
    x3 = sum_digits(pairs[2] + pairs[3])
    x4 = sum_digits(pairs[3] + pairs[4])
    x5 = sum_digits(x1 + x2)
    x6 = sum_digits(x2 + x3)
    x7 = sum_digits(x3 + x4)
    x8 = sum_digits(x5 + x6)
    x9 = sum_digits(x6 + x7)
    return 10*x8+x9

if __name__ == '__main__':
    address1 = 'http://reaktor.fi/wp-content/uploads/2014/08/'
    address2 = 'fast_track_generoitu_nimilista.txt'
    address = address1 + address2
    agents1 = 'Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36' 
    agents2 = '(KHTML, like Gecko) Chrome/37.0.2049.0 Safari/537.36'
    agents = agents1 + agents2

    req = urllib.request.Request(address, headers={'User-Agent': agents})
    r = urllib.request.urlopen(req)
    datas = r.read().decode('utf8')

    name = ""
    names = list()
    pairs = [0] * 5
    matches = list()
    for i in range(0,len(datas)):
        if (datas[i] == "\n"):
            names.append(name)
            name = ""
        else:
            name += datas[i]

    for i in range(0,len(names)):
        for j in range(i + 1,len(names)):
            common = names[i].lower() + names[j].lower()
            for i in range(0,len(common)):
                if (common[i]) == "p":
                    pairs[0] += 1
                if (common[i]) == "a":
                    pairs[1] += 1
                if (common[i]) == "i":
                    pairs[2] += 1
                if (common[i]) == "r":
                    pairs[3] += 1
                if (common[i]) == "s":
                    pairs[4] += 1
                for i in range(0,len(pairs)):
                    pairs[i] = sum_digits(pairs[i])

                percent = compute_percent(pairs)
                if percent == 99:
                    pari = "" + names[i] + " and " + names[j]
                    matches.append(pari)
    matches = list(set(matches))
    print(len(matches))
\$\endgroup\$
1
\$\begingroup\$

This answer has two parts. First part to show some suggestion to your code, keeping the same algorithm performance. Second one to suggest a \$O(n)\$ algorithm (where yours is \$O(n^2)\$).

PART ONE

The sum_digits function can be written as:

def sum_digits(n):
    if n>0:
        n = n % 9
        if n == 0:
             n = 9
    return n

(this is something one can learn in algebra courses but which is very commonly used in elementary school maybe under the name of "casting out nines") or more literally:

def sum_digits(n):
    while n>9:
        n = sum(map(int,str(n)))
    return n

The compute_percent(pairs) function would be more clearly implemented by a reduce(lst) defined as follows:

def reduce(lst):
  return [x+y for (x,y) in zip(lst[1:],lst[:-1])]

and then iterating:

def compute_percent(lst):
   while len(lst)>2:
      lst = reduce(lst)
   return lst[0]*10+lst[1]  

The for loop iterating over the characters of common can be replaced by:

for i,c in enumerate('pairs'):
    pairs[i] = common.count(c)

All these simplification do not change the algorithmic complexity of your code.

PART TWO

Your algorithm is \$O(n^2)\$ since you are iterating on all pairs of names in a huge list of length \$n\$. This can be terribly slow when \$n\$ is becoming very large... so you should try to find if it is possible to make a single iteration on the list.

The key point, here, is that the computation on a pair of persons only depends on the number of occurence of the characters P,A,I,R,S in their names. So if two person share the same count of P,A,I,R,S occurences they share the same perfect pairs (if they have any).

So you can start by construction a dictionary mapping "PAIRS count" to the number of people with such a count. Moreover every PAIRS count can be reduced modulo 9 (because we use modulo 9 arithmetic) hence the number of items in the dictionary is bounded by \$9^5\$ which gives constant time access and update of the dictionary. So the dictionary can be constructed by a linear sweep over the list of names in \$O(n)\$ time complexity and constant memory.

Once the dictionary is constructed you can make the double iteration on the dictionary. Every match in the keys of the dictionary must be multiplied by the counts of both "PAIRS" to get the count of actual people matching. Since the dictionary has less than 100000 entries this counts as a constant time operation.

Of course when \$n<100000\$ this could be not better than your algorithm (but also not worse) but I would predict that even for smaller numbers you have a gain, since real people names are not so long and contain very few occurence of five choosen letters (imagine any name with a (9,9,9,9,9) PAIRS count) hence I expect a lot of collisions in the hash dictionary which will sensibly reduce the runtime of the algorithm.

Possible implementation:

from collections import defaultdict
from itertools import combinations
import urllib2

def compute_key(name):
    return tuple(name.lower().count(c) for c in "pairs")

def reduce(n):
    while n>9:
        n = sum(map(int,str(n)))
    return n

def is_perfect_match(key1,key2):
    key = [a+b for a,b in zip(key1,key2)]
    while len(key)>2:
        key = [x+y for x,y in zip(key[1:],key[:-1])]
    return map(reduce,key) == [9,9]

d = defaultdict(int)

url = 'http://reaktor.fi/wp-content/uploads/2014/08/fast_track_generoitu_nimilista.txt'
req = urllib2.Request(url, headers={'User-Agent': "Magic Browser"})

for name in urllib2.urlopen(req).readlines():
    d[compute_key(name)] += 1

count = 0

#  compute count of matchings of names with different keys:                                                                          
for key1,key2 in combinations(d,2):
    if is_perfect_match(key1,key2):
        count += d[key1]*d[key2]

#  compute count of matchings of names with equal keys:                                                                              
#  (a name cannot be matched with itself)                                                                                            
for key in d:
    if is_perfect_match(key,key):
        count += d[key]*(d[key]-1)

print count

The execution is much faster, even if the input is only 1000 names (1sec vs 1min). And gives 5910 as a result (vs 995).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ sum_digits(n) can't be just n%9. For example sum_digits(9)=9 but 9%9=0. \$\endgroup\$ – cs-junior Sep 9 '14 at 18:26
  • \$\begingroup\$ Also, the number of S affects the PAIRS value. I computed manually [P = 0, A = 1, I = 6, R = 2, S = 0] gives 1 7 8 2 => 8 6 1 => 5 7 Maybe you meant that the S won't affect what is the leftmost digit of PAIRS-value? \$\endgroup\$ – cs-junior Sep 9 '14 at 18:52
  • \$\begingroup\$ cs-junior: you are right in both comments, I have modified my answer. \$\endgroup\$ – Emanuele Paolini Sep 10 '14 at 6:48
1
\$\begingroup\$

There is a significant flaw in your code; this line:

pairs = [0] * 5

only occurs once, and I couldn't spot pairs being emptied anywhere.


The code to create the list of names is very inefficient, this:

name = ""
names = list()
...
for i in range(0,len(datas)):
    if (datas[i] == "\n"):
        names.append(name)
        name = ""
    else:
        name += datas[i]

Could be written as:

names = data.split("\n")

Note also that for char in data would have been a more Pythonic loop construct.


You can use itertools.combinations to get pairs of names:

for name1, name2 in combinations(names, 2):

You can use collections.Counter to simplify getting the initial numbers:

counter = Counter(name1.lower())
counter.update(name2.lower())
pairs = [sum_digits(counter[c]) for c in "pairs"]

Your compute_percent only works when exactly five letters are chosen, you can make it much more general (and shorter):

def compute_percent(pairs):
    while len(pairs) > 2:
        pairs = [sum_digits(n1+n2) for n1, n2 in zip(pairs, pairs[1:])]
    return (10 * pairs[0]) + pairs[1]

I would split the if __name__ == "__main__" section into more, smaller functions, something like:

  • get_names to extract the names from the file;
  • perfect_pairs to pair them off; and
  • score_pair to calculate the score.

Then all you have in the last block is:

print(len(perfect_pairs(get_names())))
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.