3
\$\begingroup\$

Problem is Talent Buddy.

Your task is to

  • write a function that prints to the standard output (stdout) for each query the user name that matches the query
  • if there are multiple user names matching the query please select the one that is the smallest lexicographically
  • all string matches must be case insensitive
  • if no match is found for a given query please print "-1"

Note that your function will receive the following arguments:

usernames - which is an array of strings representing the user names

queries - which is an array of strings representing the queries described above

Data constraints - the length of the array above will not exceed 100,000 entries - each name or query string will not exceed 30 characters

Efficiency constraints

  • your function is expected to print the requested result and return in less than 2 seconds

Example

Input 
names: ["james", "jBlank"]
queries: ["j", "jm", "jbl", "JB"]

Output
james
-1
jBlank
jBlank

The above is an example testcase.

My algorithm:

def typeahead(usernames, queries):
        from bisect import bisect_left
        wordlist=sorted(usernames,key=str.lower)
        l_wordlist=map(str.lower,wordlist)
        for i in queries:
            word_fragment=i.lower()
            k=wordlist[bisect_left(l_wordlist, word_fragment): bisect_left(l_wordlist, word_fragment[:-1] + chr(ord(word_fragment[-1])+1))][:1]
            print k[0] if k else  -1

Steps:

  1. Sorted the usernames lexicographically

  2. sorted usernames of small letters(this used in bisect)

  3. using word_fragment i am bisecting the total array

When I profiled my method, I got this testcase:

         250005 function calls in 0.715 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 bisect.py:1(<module>)
        1    0.480    0.480    0.715    0.715 py1.py:24(typeahead)
   100000    0.146    0.000    0.146    0.000 {_bisect.bisect_left}
    50000    0.009    0.000    0.009    0.000 {chr}
        1    0.010    0.010    0.010    0.010 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    50000    0.013    0.000    0.013    0.000 {method 'lower' of 'str' objects}
    50000    0.006    0.000    0.006    0.000 {ord}
        1    0.050    0.050    0.050    0.050 {sorted}

The problem is that when I run it in the Talent Buddy, it is showing that it takes more than 2 seconds. How can I further optimise my code?

Edit as reference with another question with this testcase. The efficient code provided took the below time:

        147936037 function calls in 52.394 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.002    0.002 collections.py:1(<module>)
        1    0.000    0.000    0.000    0.000 collections.py:26(OrderedDict)
        1    0.000    0.000    0.000    0.000 collections.py:381(Counter)
        1    0.000    0.000    0.000    0.000 heapq.py:31(<module>)
        1    0.000    0.000    0.000    0.000 keyword.py:11(<module>)
        1   27.895   27.895   52.394   52.394 py.py:24(typeahead)
   100000    0.014    0.000    0.014    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.002    0.002    0.002    0.002 {method 'join' of 'str' objects}
   100000    0.025    0.000    0.025    0.000 {method 'lower' of 'str' objects}
147736029   24.457    0.000   24.457    0.000 {method 'startswith' of 'str' objects}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Not sure if this can help you but there is another question about this problem in Python too : codereview.stackexchange.com/questions/54480/… \$\endgroup\$
    – SylvainD
    Jun 24, 2014 at 13:13
  • 1
    \$\begingroup\$ "can any one suggest different paradigm solving the problem" - yes, in exactly that post @Josay just linked to. \$\endgroup\$
    – jonrsharpe
    Jun 24, 2014 at 13:29
  • \$\begingroup\$ @jonrsharpe i have edited my question. i feel my approach is faster than OP in that link. more over there are repeated iterations in the solution causing it slower than me \$\endgroup\$ Jun 24, 2014 at 13:35
  • \$\begingroup\$ @sundarnataraj: Have you timed them to see which is faster? Have you profiled your code to see where the bottlenecks are? \$\endgroup\$ Jun 24, 2014 at 13:42

1 Answer 1

0
\$\begingroup\$
def typeahead(usernames, queries):
        from bisect import bisect_left
        wordlist=sorted(usernames,key=str.lower)
        l_wordlist=map(str.lower,wordlist)
        for i in queries:
            word_fragment=i.lower()
            x=bisect_left(l_wordlist, word_fragment)
            try:
                if word_fragment in l_wordlist[x]:
                    print wordlist[x]
                else: print -1                    
            except: print -1

i have increased it performance by

k=wordlist[bisect_left(l_wordlist, word_fragment): bisect_left(l_wordlist, word_fragment[:-1] + chr(ord(word_fragment[-1])+1))][:1]

there are two bisects functions in above by removing one and converting to below

            x=bisect_left(l_wordlist, word_fragment)
            try:
                if word_fragment in l_wordlist[x]:
                    print wordlist[x]
                else: print -1                    
            except: print -1

by profiling

 100004 function calls in 0.542 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.329    0.329    0.542    0.542 reducer.py:21(typeahead)
    50000    0.116    0.000    0.116    0.000 {_bisect.bisect_left}
        1    0.013    0.013    0.013    0.013 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    50000    0.020    0.000    0.020    0.000 {method 'lower' of 'str' objects}
        1    0.063    0.063    0.063    0.063 {sorted}

reduced the system calls by half from 250005 to 100004 did the magic :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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