Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Google Pre-interview Coaching


Write a program that breaks up a string of words with no spaces into a string with the appropriate spaces.

Follow the following process:

  1. Clarify the problem
  2. Refine the solution
  3. Code it
  4. Last words

Clarify the problem

  1. Consider a general case, like “fastman”
  2. Disambiguate expected result
  3. State the key assumptions
  4. clarify function signature

2 words? null input? where is the words from? We might use a dictionary.

Refine the solution

  1. what if the dictionary cannot fit in RAM
  2. how would you print the most likely of multiple choices
  3. what if the words are not spelled correctly?
  4. Testing

Code it

Write code now, skip.

Last words

Talk naive solution, then come up with a reasonably better one.

Time/Space tradeoff. (like pre-processing or something)

For very big/small input.

White-board practise is important!