Hi Everyone!

Hope you’re all having a great day!

Here’s your Interview Problem, Yesterday’s Solution and Tech Snippets for the day!

Tech Dive

• Divide and Conquer Algorithms and The Master Method

• RESTful APIs, GraphQL, WebHooks and more!

Industry News

• Google has an amazing Q4 with the stock reaching an all-time high. The company is now valued at $1.41 trillion dollars

  • Earnings - Google earned $22.30 per share in Q4. This crushed analyst expectations of $15.90 per share.

  • Revenue - $56.90 billion dollars in Q4 which beat analyst expectations of $53.13 billion dollars.

  • Google Cloud - $3.83 billion dollars in Q4 which matched analyst expectations of $3.81 billion dollars.

  • YouTube Ad Revenue - $6.89 billion dollars in Q4 which beat analyst expectations of $6.11 billion dollars.

  • Total advertising revenue for Q4 came in at $46.20 billion dollars, which is up 22% from $37.93 billion in Q4 in 2019. This shows an amazing turn around by Google from the huge drop in advertising revenues in March of 2020 due to the COVID pandemic.

  • Google Cloud has also been growing extremely quickly with 47% growth year over year.

    • This means Google Cloud is currently growing much faster than AWS, although AWS is much larger.

    • AWS has plateaued at 33% market share in the cloud space while Microsoft’s Azure has increased their market share to 20%. Google Cloud is in third place with 9% of the market.

  • Google is expecting to accelerate hiring in 2021, especially in Google Cloud.Read More

Tech Snippets

• The Elements of Computing Systems just released their second edition! This is a fantastic book to learn about the internals of computers and gain knowledge of hardware, computer architecture, operating systems and compilers.

  • The book is inspired from the Nand2Tetris course.

• Apple and Kia are pushing towards a deal for the Apple Car. The Apple Car will be fully autonomous and is tentatively scheduled to go into production in 2024.

• Snap and Unity both warn investors that Apple’s new privacy changes (relating to IDFA) will hurt their revenues.

Interview Question

Given an integer, convert it to a Roman Numeral.

Example

Input: 3

Output: “III”

Input: 4

Output: “IV”

Input: 1994

Output: “MCMXCIV”

Here’s the question in LeetCode

We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

• On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"

• On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Previous Solution

As a refresher, here’s the previous question

You are given a string s that contains only digits.

Return all possible valid IP addresses that can be obtained from s (without changing the order of the digits in s).

Example

Input: “25525511135”

Output: ["255.255.11.135","255.255.111.35"]

Input: "0000"

Output: ["0.0.0.0"]

Input: "010010"

Output: ["0.10.0.10","0.100.1.0"]

Input: "101023"

Output:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3", "101.0.2.3"]

Here’s the question in LeetCode

Solution

This question can be solved with backtracking, where you can imagine a search tree of all the possible IP addresses.

With backtracking, we search the search-tree in a depth-first manner and we backtrack (or recurse) whenever we reach a candidate solution that cannot be an IP address.

Remember that an IP address consists of 4 integers that are all between 0 and 255.

We start off with our result array, which keeps track of all the IP addresses that can be formed.

Then, we call our backtrack function with an empty string as our current candidate and we pass in s.

When our candidate has 4 distinct integers and we’ve used up all the digits in s, then we can add the candidate to result.

Otherwise, if we need more integers, then we can continue to iterate s.

We’ll run a for loop that iterates through the next 1 - 3 digits in s and uses them as potential integers for our IP address.

Then, we’ll remove those digits from s (since we’ve used them) and backtrack on the rest of s with our current candidate solution.

Here’s the Python 3 solution

Can you analyze the time/space complexity of our solution?

Reply back with your estimate!

We’ll tell you if you’re correct (or we’ll tell you the answer if you’re wrong).

Best,

Arpan