Facebook Interview Question / Airbnb files IPO paperwork!

August 20, 2020

Hey Guys & Gals,

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

Daily Interview 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?

Industry News

  • Airbnb has filed paperwork to IPO - Airbnb has submitted a draft registration to the SEC for an IPO. The company had somewhat of a “deadline” to file due to the upcoming expiration of RSU grands that were issued in early 2014. The value of the RSUs has slipped, while they were valued at $150in 2019, they’ve recently only fetched $104. Read More.

  • Alibaba posts 124% gain in quarterly profit, seeing Chinese retail back to pre-pandemic retails - Chinese E-Commerce group Alibaba posted an extremely strong earnings this quarter and noticed that Chinese retail has recovered back to pre-pandemic levels. Cloud Computing was the company’s second biggest revenue contributor, as sales grew by 60% to 12.3 billion yuan. Alibaba Cloud will be hiring a record 5000 people. Read More.

  • Global Smartwatch Market Revenue up 20% in first half of 2020 - The global smartwatch market posted a 20% revenue growth despite the COVID-19 pandemic . India saw a massive 60% YoY increase and Apple continues to dominate the global market capturing half of the market in terms of revenue. Read More.

Yesterday’s Solution

As a refresher, here’s yesterday’s problem

You are given two strings as input. Write a function to check if one string is a rotation of the other string. An example of a rotation is "CodingInterview", "erviewCodingInt".

You will also be given a function isSubstring that will return a boolean that is True if one string is a substring of the other. You can only call this function once.

Input - "CodingInterview", "erviewCodingInt"Output - TrueInput - "Test", "est"Output - False

Solution

Let's label the input strings x1 and x2.

If x1 is a rotation of x2 then there must be a rotation point. An example is if x1 is "erviewCodingInt" and x2 is "CodingInterview". Then, the rotation point is after "CodingInt". We can imagine splitting x2 at the rotation point into a and b where a is "CodingInt" and b is "erview".

Then, x1 is ba and x2 is ab.

x1 = erviewCodingInt = b + a = erview + CodingInt

x2 = CodingInterview = a + b = CodingInt + erview

So, we want to see if we can split x2 into a and b so that ba = x1 and ab = x2.

We can also see that ba will always be a substring of ab + ab, as there is a ba after the first a. Therefore, x1 will always be a substring of x2 + x2.

So, we can check if x1 is a rotation of x2 by seeing if x1 is a substring of x2 + x2.