Over 10,000 Software Engineers get Big Tech Interview Problems (and Solutions!), Tech Snippets and Deep Dives from Quastor Daily

You can join (for free!) by subscribing here:

Hey Guys,

Here’s your Tech Snippets and Interview Problem for the Day! Plus, we have a solution to our last Facebook interview question!

Tech Snippets

• Microsoft Azure had a 14 hour outage on March 15th resulting in Office 365, Xbox Live, and a bunch of other Microsoft services being down.

  • The root cause of the outage was with Azure Active Directory, which is Azure’s identity and access management service (used for user authentication).

  • An error occurred in the rotation of keys used to support Azure AD’s use of OpenID and other protocols for signing cryptographic transactions.

  • Private keys are the “secret” that you use to sign a cryptographic transaction and prove that it was from you. A breach of your private keys means that anyone can sign a transaction as you.

  • Microsoft practices key rotation, part of which includes removing keys that are no longer in use.

  • However, over the last few weeks, a particular key was marked “retain” for longer than normal to support a complex cross-cloud migration. This exposed a bug where the automation incorrectly ignored that “retain” state and removed that key.

  • Once the key was removed, applications using those protocols with Azure AD stopped trusting tokens that were signed with the removed key. This caused dependent applications to go down.

• Google is expanding Big in 2021

  • Google is investing massively in the US this year, with a $7 billion dollar investment in offices and data centers across the US.

  • Google plans to hire 10,000 new full-time Googlers in the US alone.

  • Thousands of roles will be added in Atlanta, Washington D.C., Chicago and New York

• Fireblocks, a cryptocurrency infrastructure provider, raises $133 million dollars

  • Fireblocks is a cryptocurrency custody solution that allows institutions to store, transfer and issue digital assets with their platform.

  • They currently store $400 billion dollars in cryptocurrencies, belonging to banks, fintech startups and other financial institutions.

  • The company uses Multi-Party Computation (MPC) for custody, where creating a wallet results in multiple private keys that are all needed to sign a transaction. This eliminates a single point of failure.

  • The company also allows you to issue and manage stablecoins (tokens that are backed by fiat currencies), that work on multiple layer 1s (blockchains).

  • DeFi, or Decentralized Finance, is a term that refers to financial applications that are mostly being built on the Ethereum blockchain.

  • The DeFi space has been exploding over the past several months, growing more than 40x over the past year (in terms of TVL or Total Value Locked). You can keep track of the DeFi space and protocols here.

Interview Question

Design a stack (CustomStack) with an increment function.

Your class should implement the following functions

• CustomStack(int maxSize) - Initializes the object with maxSize which is the maximum number of elements in the stack.

• void push(int x) - Adds x to the top of the stack if the stack hasn't reached the maxSize.

• int pop() - Pops and returns the top of stack or -1 if the stack is empty.

• void inc(int k, int val) - Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Is it possible to design it so all operations are O(1) time?

Here’s a link to the question on LeetCode

We’ll send a detailed solution in our next email, so make sure you subscribe to Quastor Daily!

Previous Solution

As a refresher, here’s the last question

You are given an array nums of distinct positive integers.

Return the number of tuples (a, b, c, d) such that

a * b = c * d

where a, b, c and d are elements of nums and

a != b != c != d

Here’s the question in LeetCode.

Solution

The naive solution would be to use 4 nested for loops.

We iterate through nums in 4 nested loops with each loop representing a, b, c and d respectively.

Then, we can count the number of tuples where a * b = c * d.

This would result in a time complexity of O(n^4).

Can we do better?

We can if we make a tradeoff by using more memory in exchange for less time.

We start by splitting up our calculations.

First, we calculate every possible product of a * b.

We use a nested for loop (only 2 loops this time) with the first loop representing a and the second loop representing b.

In our inner for loop, we calculate the possible products for a * b.

We’ll store all of these products in a hash table where the keys of the hash table are the products and the values are how many times each of those products appeared as a result of a * b.

After, we’ll have a second nested for loop, with the first loop representing c and the second loop representing d.

We calculate the value of c * d and then check our hash table for how many times this product appeared.

Then, we can add up how many times the product appeared to a counter that keeps track of this.

However, we must remember to avoid double counting due to the condition that

a != b != c != d

In order to do this, we subtract the value from our hash table by 2 (counting the two times where a = c, b = d and a = d, b = c.

After tallying up all the counts, we can return the total number of tuples.

Here’s the Python 3 code.

Can you analyze the time 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).

Over 10,000 Software Engineers get Big Tech Interview Problems (and Solutions!), Tech Snippets and Deep Dives from Quastor Daily

You can join (for free!) by subscribing here: