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

Our last tech dives were on Distributed Systems and Database Sharding!

• Distributed Systems Tech Dive

• Database Sharding Tech Dive

Tech Snippets

• Venture Capital funding for startups rises 14% in 2020

  • 2020 was a great year for startups, with Venture Capital funding reaching a new high of $130 billion US dollars.

  • The total number of funding rounds was lower than in 2019, but the rounds were far larger.

  • There was a big increase in megarounds or deals larger than $100 million dollars. The number of unicorns (startups with a valuation of $1 billion dollars or more) ticked up to 225.

  • There was an uptick in funding for cities outside the Bay Area

• A comprehensive introduction to Docker

  • Docker is something every developer should learn.

  • This article goes through what Docker is, what it’s used for and how to use it.

  • You’ll build and use your own docker image.

• Project Zero’s In The Wild Series

  • Project Zero is Google’s Offensive Cyber Security team. They try and find software exploits. They have a policy of a 90 day disclosure deadline before they publicly release the exploit (drop the zero-day).

  • In the Wild is Project Zero’s post series on how they find zero day exploits. A must-read if you’re into cyber security.

Interview Question

You are given a binary tree containing digits from 0 - 9 only.

Each root to leaf path represents a number. A root to leaf path of 1 -> 3 -> 4 represents the number 134.

Find the total sum of all root to leaf numbers.

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

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Here’s the question in Leetcode.

Solution

This question can be solved with Kadane’s algorithm. It’s quite a useful algorithm to be aware of!

We iterate through the array and keep track of the current subarray sum and the max subarray sum that we’ve seen so far.

Now, when we move to the next value in our array, we have two choices…

1. Keep expanding the current subarray

2. Discontinue the current subarray and start with a current subarray sum of 0.

If the current subarray sum is positive, then we should continue expanding our subarray as it will make our subarray sum bigger when we add in the next value.

If the current subarray sum is negative, then we should start a new subarray since keeping it will only make our subarray sum smaller when we add in the next value.

On each iteration, we also update the max subarray sum if the current subarray sum is larger.

Here’s the Python 3 code

The time complexity is linear and the space complexity is constant.

Best,

Arpan