Facebook coming after YouTube?

Hello fellow nerds!

Hope y’all are having a fantastic day. Here’s your interview problem and industry news for the day.

Daily Interview Problem

You are given a string as input. Write a function to check if the letters in the string can be rearranged to form a palindrome (or if the input is already a palindrome). You can ignore spaces in the string.

Input - “car race”

Output - True (the letters can be rearranged to form “racecar”)

Industry News

• Facebook Watch Tops 1.25 Billion Monthly Active Users - Facebook Watch is the social giant’s two-year-old video streaming platform and it is now serving more than 1.25 billion users each month. This is a credible challenge to YouTube, which currently has north of 2 billion logged-in visitors per month. However, it’s still unclear how long people are staying on the Watch platform. Facebook counts everyone who has streamed as little as 1 minute of video as an active user.

• Looking for a musical that goes through AWS’s 168 services in 2 minutes? Look no further, Forrest Brazeal has you covered! Check out his hilarious musical here. I know it’s not “industry news”, but this is too awesome not to link.

• The Chinese government emphasizes right to approve tech deals as TikTok Sale Looms - China has emphasized it’s right to approve or block the sale of technology companies abroad, which confirms that the government will play a critical role in the sale of TikTok’s U.S. operations to Microsoft and Oracle. Beijing has also added several artificial intelligence features to a list of export-restricted technologies, giving them the right to block a deal by targeting features such as TikTok’s recommendation algorithm.

Previous Solution

As a refresher, here’s the last question

You’re given two strings s and p. Both strings will not be empty.

Find all the start indices of p’s anagrams in s. The strings consist of lowercase English letters only and the length of both strings s and p will be less than 10,000.

Example 1:

Input: s: "cbaebabacd" p: "abc"Output: [0, 6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc".The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s: "abab" p: "ab"Output: [0, 1, 2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab".The substring with start index = 1 is "ba", which is an anagram of "ab".The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution

This question uses the Sliding Window technique.

We create a “sliding window” of all the characters in p.

Then, we iterate through s.

• If we come across a character that is NOT in our sliding window, then we add it in to the window.

• If we come across a character that is in our sliding window, then we delete it from the window.

• If our sliding window is empty, then that means we’ve come across an anagram of p in s and we can add it to our list of indices.

The time complexity is O(p + s) and the space complexity is O(p).

You can view a REPL with the solution and test cases here.