Typeahead Talent Buddy 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:


Sorted the usernames lexicographically
sorted usernames of small letters(this used in bisect)
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(&lt;module&gt;)
        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(&lt;module&gt;)
        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(&lt;module&gt;)
        1    0.000    0.000    0.000    0.000 keyword.py:11(&lt;module&gt;)
        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}
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 :)