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(<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}