What’s up fellow nerds!
Hope y’all are having a great day. Here’s your interview problem and industry news for the day!
Daily Interview 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
You can write your code in this REPL. Unit Tests are provided.
Once you start editing the code then REPL will automatically fork it for you!
I’ll send you the solution to this question tomorrow!
- Facebook will be requiring Oculus users to use Facebook accounts - Facebook will be ending support for separate Oculus accounts in 2023. Instead, all users will be required to sign up with their Facebook accounts. As I’m sure you’re all aware, Facebook isn’t exactly the most popular company around right now, so there’s been a tremendous amount of backlash on social media. Palmer Lucky (founder of Oculus) actively chimed on on the Reddit thread where this decision was being discussed.
- Mobile Game Developer Playdots acquired for $200 million dollars - Playdots is a mobile game developer responsible for the games Dots, Two Dots and Dots & Co. You can see their iOS developer page here. They were acquired for $192 million dollars in a cash and stock deal by Take-Two Interactive. Read More.
- Google Maps is being redesigned - Google Maps is getting a big redesign to make it easier to distinguish natural features in the environment. This is due to a new color-mapping algorithmic technique that Google is using. Street Maps are also getting a lot more detailed in select cities. Google doesn’t seem to have job postings for the Maps team specifically, but you can apply directly to Waze if you’re interested in mapping. Read More.
As a refresher, here’s yesterday’s problem
You’re given an N x N matrix where some of the items in the matrix are 0. If any of the items are 0, then set the item’s entire row and column to 0. Items that are not 0 will be represented by an integer.
Input - [
Output - [
Your initial thought might be to iterate through the matrix and set the row and column to 0 whenever you come across a 0. The issue with that, however, is that the original matrix may have multiple zeros. After we encounter the first 0, we'll come across another 0 and we won't know if that 0 was from the original matrix, or if it was created when we were adding 0's to the row and column of the first 0.
An easy way around this is to use two passes. When we encounter a 0 on the first pass, then we'll set the row and the column to None (if we encounter another zero, we will not set that to None, since we'll want to set that item's row and column to None later in the loop).
Then, we can have a second pass where we set all the items with None to 0.
The time complexity of this approach is O(nm) where n is the number of rows and m is the number of columns. The space complexity is O(1).