View All num of num See all Photos Google This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company?Learn More. www.google.com Employer Engaged Overview Reviews Salaries Interviews Jobs Photos Benefits 3.1k Reviews 11k Salaries 3.8k Interviews 1.7k Jobs Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Engineer Interview Mountain View, CA Google Find all (english word) substrings of a given string . (every = every, ever, very) Tags: See more , See less 8 Answer Add Tags 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_graphUse 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, Sign In or Sign Up.