☕ Microsoft is reopening

Microsoft is reopening some of their offices this month. Plus, an answer to our last Google Interview Question. Also, how websites identify users without their permission (even if they're incognito!)

Hey Guys,

Hope you’re all having a fantastic day!

Here’s your Industry News, Tech Snippets and Interview Problems!

As always, feel free to reply to this email with any questions, comments or insults.

I’m all ears!

source - XKCD

Industry News

Microsoft to start reopening headquarters on March 29th

Microsoft will be reopening their Redmond and Seattle offices later this month in a limited fashion.

Currently, Microsoft has work sites in 21 countries that have been able to accommodate additional workers in its facilities, which it said represents about 20% of its global workforce.

The company will be taking a gradual approach while sticking to Washington State capacity limits.

They are currently on Stage 4 of their 6 stage reopening plan.

Microsoft has found that 73% of workers surveyed wanted to continue with flexible remote work.

Therefore, the company is now considers working from home part-time as standard for employees.

The company said it planned to allow employees to work remotely less than 50% of the time. Employees can also request approval from their managers to work remotely full time or to potentially move to a new location.

Tech Snippets

• How the Web Audio API is used for browser fingerprinting

  • You can identify a specific user’s web browser without using cookies or asking for permission!

  • Browser fingerprinting is the process of reading browser attributes and combining them to get an identifier for the user. The identifier is stateless and works well even if the user is incognito.

  • One method of fingerprinting is with the Web Audio API, an API built to allow developers to do advanced things with audio on their website (add effects and different filters).

• How MDN’s site-search works

  • If you’ve ever done any web development, you’ve probably visited MDN Web Docs. They’re the most comprehensive resource on the internet for web dev.

  • MDN consists of 11,619 articles and 40,000 translated documents. In English alone, there are 5.3 million words on the site.

  • MDN stores their content on a public GitHub repo, where anyone can propose edits. A script then indexes the content, strips the HTML and then sends it to Elasticsearch.

Interview Question

Given the root of a Binary Tree, return the sum of the values in the trees’ deepest leaves.

Example

Answer = 15 since 7 + 8 = 15

Here’s the question in LeetCode

We’ll send a detailed solution in our next email, 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 last 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

Solution

The question is asking us to implement a stack. The only difference is that we need an increment function that will take in k and val and then increment all the indices below k by val.

We can use Python’s list data structure as our stack as it handles push and pop operations in O(1) time. The tricky part is our increment function.

The brute force solution is to implement the increment function by iterating through the first k items in our array and incrementing them all by val.

This would make our time complexity O(1) for push, O(1) for pop and O(k) for increment.

Can we do better?

We can! We’ll have to tradeoff space for time and use a hash table.

Instead of incrementing k items every time in increment, we can just keep track of the increment in a hash table.

We’ll add a (key, value) pair in our hash table with (k, val).

Then, we’ll do the increments in our pop function.

Whenever we have to pop an item from our stack, we first check if the current index is in our hash table.

If so, then we increment the current index by val. Then, we can remove that index from our hash table (since we’ve already incremented by it). Remember, however, that val should be incremented to every index below k. Therefore, we’ll add val back to the hash table, except this time at the index 1 lower than the current index ( current index - 1).

Now, we can pop the last item off our current stack and return it!

Here’s the Python 3 code.

Not bad!