Google Interview Questions Deconstructed: Synonymous Queries

The Mandelbrot set
note words_are_synonyms is purposefully not defined
  • Notice the use of dict.get(). You could type out the “check if the key is in the dict and then get it” implementation, but that’s cluttered whereas this way you can show off your knowledge of the standard library.
  • I’m personally not a fan of code that uses a whole lot of continues, and some style guides ban or discourage their use. I actually introduced a bug in my initial implementation of this code by omitting the continue after the query length check. It’s not bad, just know that it’s error prone.
Note that by producing code we’ve already gone deeper into this solution that I would allow a candidate to go.
Each word between “speedy” and “fast” had its parent updated, then the same happened for “hasty” to “fast.”
  • Analyze a problem statement and recognize where it is ambiguous and under-defined, clarifying where necessary to develop an unambiguous problem statement. Continue doing this as you progress through a solution and encounter new questions. For maximal efficiency, do as much of this stage as early as possible because recovering from errors becomes more costly as your work progresses.
  • Frame the problem in such a way that makes it easier to approach and solve. In this case, the most important point is the observation that you can line up corresponding words in the queries.
  • Implement your solution. This involves choosing optimal data structure and algorithms, as well as designing your logic to be readable and easy to modify in the future.
  • Circle back and try to spot bugs and errors. These could be actual bugs like how I forgot to insert a “continue” statement above, or performance bugs like using an incorrect data structure.
  • When the problem definition changes, repeat this process and adapt your solution whenever appropriate, and scrap it where not. Knowing when to do both is a critical skill, both in an interview and in the real world.
  • Keep your data structures and algorithms knowledge at your fingertips. The disjoint set data structure is not exactly a common structure, but it’s not really that rare and refined either. The only way you can ensure you know the tool for the job is by learning as much as you can.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alex Golec

Alex Golec

Engineering Manager, Ads Optimization and Modeling @ Reddit, ex-Google