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?
- 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.
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 - True
Input - "Test", "est"
Output - False
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.