4 ms·
If you couldn't solve that question, maybe you shouldn't work at Google... def valid(S:str, word:str) -> bool: s = S for l in word: pos = s.find(l)
by pbalau 8y ago
If you couldn't solve that question, maybe you shouldn't work at Google...
def valid(S:str, word:str) -> bool:
s = S
for l in word:
pos = s.find(l)
if pos == -1:
return False
s = s[pos+1:]
if not s:
return False
return True
if __name__ == '__main__':
D = ["able", "ale", "apple", "bale", "kangaroo"]
S = "abppplee"
in_s = {len(w): w for w in D if valid(S, w)}
keys = list(in_s.keys())
sorted(keys)
print(f"longest is {in_s[keys[-1]]}")
- commandlinefan 8y agoYeah, whenever I see a question like that one, I think it's pretty straightforward but then I wonder if my straightforward solution isn't the "brute force" solution and the interviewer isn't looking for some tricky "elegant" solution. Still, if I were asked that in an interview, I'm sure I'd put together something like your solution; I can't think of a "better" way to solve it.
- pbalau 8y agoI was trained by fb for interviewing, the phone screen, sw part. You start with a simple enough problem. See how fast the candidate can come up with a solution. Then complicate the problem to find more stuff. Like, what if you have unlimited memory? What if you have very little memory? etc. You are supposed to look for signals. Can the candidate improve the solution based on some random constraints/hints? Is the candidate good enough with the language they picked (eg, append vs extend in python, or why i copied S into s). We were not looking for tricks and the entire idea that big companies are looking for tricks in their interviews was spread by either people that never been in such an interview or were bad enough to be rejected.