Alexa, are you hiring?

What’s up fellow Nerds,

Hope you’re having a fantastic day. Here’s your interview problem and industry news for the day!

Daily Interview Problem

You are given a character array containing a set of words separated by whitespace. Your task is to modify that character array so that the words all appear in reverse order. Do this without using any extra space.

Example

input - ['A', 'l', 'i', 'c', 'e', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'B', 'o', 'b']

output - ['B', 'o', 'b', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'A', 'l', 'i', 'c', 'e']

Industry News

• Amazon Alexa Division pauses hiring amid pressure to make money - Amazon has paused hiring in the Alexa division due to growing pressure to make money from the voice-activated digital assistant. There’s been no official announcement of a hiring pause, but according to Bloomberg, the Alexa division has been told to refrain from bringing on new people. The accelerating push for profits has prompted the company to consider selling ads on the Alexa service.

• Luminar, a self-driving car company that works on LIDAR technology is going public - Luminar is going public at a $4.3 billion dollar valuation. It’s not going through the traditional IPO process, but is instead going public by merging with a “SPAC”. Luminar makes heavy use of Unity for their technology stack, and they like to hire engineers who have a background in game development.

• Epic Games wins a temporary restraining order against Apple - So, just in case you haven’t been following the Epic vs. Apple showdown… Epic Games is the creator of Unreal Engine (and they’ve also made Fortnite). Epic retaliated against Apple’s 30% tax by adding an in-app payment system that circumvented Apple’s payment system (in violation of app-store rules). Apple responded by removing Fortnite from the App Store and also retaliated by terminating the developer accounts Epic used to support Unreal Engine. In a legal ruling, Judge Yvonne Gonzalez Rogers has now decided that Apple can’t retaliate against Epic by terminating the developer account Epic used to support Unreal Engine. However, Rogers also ruled that Apple will not be required to bring Fortnite back to the App Store.

Yesterday’s Solution

As a refresher, here’s the last problem

How would you build a spelling correction system?

Possible Follow On Questions

• How would you check if a word is misspelled?

• How would you find possible suggestions?

• How would you rank the suggestions for the user?

Solution

The core idea for most spell-check systems is based on the Levenshtein distance. The Levenshtein distance from the intended word should be one or two edits. Therefore, if we can keep a hash table for all the words in our dictionary and then look for words that have a Levenshtein distance of 2 or less from the text, we can find the intended word. If the text is already in our dictionary, then it’s not misspelled.

The words in our dictionary that have a Levenshtein distance of 2 or less from our text may be too many to list out for the user. Therefore, it’s important that we rank our suggestions and implement a cut-off for the number of suggestions that we list. There are several ways of ranking our suggestions

• History of refinements - users often provide a great amount of data about the most likely misspellings by first entering a misspelled word and then correcting it. This data can be collected and then used to implement rankings.

• Typing errors model - spelling mistakes are usually a result of typing errors (typos). Therefore, these errors can be modeled based on the layout of a keyboard (mran -> mean)

• Phonetic modeling - spelling errors also happen when the user knows how the word sounds but doesn’t know the exact spelling. Therefore, we can map the text to phonemes and then find all the words that map to the same phonetic sequence.