Google Interview Question: Find all (english word) subst... | Glassdoor

Interview Question

Software Engineer Interview Mountain View, CA

Find all (english word) substrings of a given string

 . (every = every, ever, very)

Interview Answer

5 Answers


The real emphasis was on how to make it efficient.

Interview Candidate on Feb 22, 2011

Get A english dictionary using Trie and then look for each substring in that if exists.
Creating a trie is preprocessing.
Actually it will take o(n2) time after dictionary is ready for reference.

NehaGupta on Feb 23, 2011

Use this instead. Uses less memory and can be more efficient.

Anonymous on Feb 26, 2011

Aho–Corasick string matching algorithm is the most appropriate for this.

Vivek on Jun 11, 2012

I was asked this question too... I got as far as trie

Carter Cole on Dec 28, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.