Rusty days ahead...
Rust 1.46.0 is out....
Hey Guys,
Hope you’re having an awesome day. Here’s your interview problem and industry news for the day.
Daily Interview Problem
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.
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".
Please reply to this email with your thoughts on how you’d solve this. I read every reply!
Industry News
Rust 1.46.0 is out to the delight of Rust nerds everywhere - Rust 1.46.0 comes with improvements to const fn, a feature where a function that only uses const variables and other const functions can be evaluated at compile time. This can result in a massive speedup. For example, the const-sha1 crate will compute SHA-1 hashes at compile time, resulting in a 40x performance improvement in Microsoft’s WinRT bindings for Rust. Any Rust devs in the house?
iOS 14 may deal a big blow to App Developers - Many iOS developers rely on Facebook Audience Network to monetize their apps with advertising. Facebook Audience Network connects developers with advertisers that are relevant to the app’s users. iOS 14 introduces new privacy changes that would cripple Facebook Audience Network’s ability to place personalized ads in third party apps, dealing a big blow to developers who rely on Facebook’s Network for revenue. However, this would obviously be a win for iOS users who are concerned about privacy.
TikTok CEO resigns and Walmart says they’re working with Microsoft to buy TikTok - Quite a few wtfs were dropped when Kevin Mayer, a former Disney executive, joined TikTok as CEO. Now, wtfs are being dropped again as Mayer announced his resignation less than three months after taking the job. Mayer said that the political environment has sharply changed and that it would be best for him to depart considering the corporate restructuring that’s coming for TikTok. To add a couple more wtfs, Walmart has now confirmed that they’re working with Microsoft to acquire TikTok. The deal is to sell TikTok’s U.S., Canadian, Australian and New Zealand operations for $20 - 30 billion USD.
Yesterday’s Solution
As a refresher, here’s yesterday’s problem
You are given a nonnegative integer as input, k. Write a function that returns the largest integer whose square is less than or equal to k.
For example, if the input is 25, return 5. If the input is 300, return 17.
Solution
The brute force solution is to square each number from 1 to k. We stop once the square has exceeded k. The time complexity of this approach is O(k).
A more efficient solution is to use Binary Search. We maintain an interval consisting of values whose squares might be less than or greater than k. We can terminate when our interval is empty (and we know which number is the largest number with a square less than or equal to k).
We start with the interval [0, k]. We take the middle ( 0 + k // 2) and square it.
If the square of the middle is less than or equal to k, then we can discard the numbers in [0, mid] and focus on [mid + 1, k].
Otherwise, if the square of the middle is greater than k, then we can discard the numbers in [mid, k] and focus on [0, mid - 1].
We will continue this process until our interval is empty (the left side of the interval is greater than the right side of the interval). In this case, every number that is smaller than the left side of our interval has a square that is less than or equal to k. Therefore, we can just return the number that is 1 less than the left side of our interval.
The time complexity of this code is O(log k)