Problem is Talent Buddy.

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

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

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}

• "can any one suggest different paradigm solving the problem" - yes, in exactly that post @Josay just linked to. Commented Jun 24, 2014 at 13:29
• @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 Commented Jun 24, 2014 at 13:35
• @sundarnataraj: Have you timed them to see which is faster? Have you profiled your code to see where the bottlenecks are? Commented Jun 24, 2014 at 13:42

def typeahead(usernames, queries):
from bisect import bisect_left
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 :)