Interview Question

Software Engineer Interview Mountain View, CA

Find all (english word) substrings of a given string

  . (every = every, ever, very)
Answer

Interview Answer

5 Answers

0

The real emphasis was on how to make it efficient.

Interview Candidate on Feb 22, 2011
0

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
2

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

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

Anonymous on Feb 26, 2011
1

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

http://en.wikipedia.org/wiki/Margaret_J._Corasick

Vivek on Jun 11, 2012
0

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 question, Sign In with Facebook or Sign Up