Interview Question
SDE-2sCountry: United States
is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
There are many ways to solve it, depends on how large is the phone book.
Assuming it is not more than N= 10,000 entries ( I mean, seriously ? ) and none of the entries are more than m= 30 character long on the average - we can have an exact (mN) algorithm.
====
1. split input words into characters
2. generate a regex like ^(c.*)+$
3. Match this regex against all entries --> matches are the result.
Example:
J => ^J.*$
JD => ^J.*D.*$
====
Another way of doing it ( slightly optimally ) is imagining a prefix tree structure.
There, the problem is find all where ( same from previous ) in xpath language :
====
1. split input words into characters
2. generate an xpath like //c/*/c/*/
3. Find all that matches that.
====
They are equivalent approaches, however, once you reach a sub-tree, the second approach drastically reduces the no of nodes one needs to look for, it is much better than [1].
However, for an interview and practicality perspective:
The result is not so bad:
- NoOne June 11, 2017