Typeahead Talent Buddy

Question

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}

Answer 1

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