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!

Tech Snippets

• Google comments on Apple’s IDFA policy changes

  • Apple is introducing a new policy called App Tracking Transparency (ATT) in iOS 14. This policy will require developers to ask for additional user permissions when using personal data for advertising purposes.

  • Many user tests have shown that users won’t allow it, meaning they can’t be tracked for advertising purposes.

  • This change could have a huge impact on mobile advertising, resulting in companies like Facebook suffering a massive revenue hit. Smaller app developers who rely on advertising for revenue will also be hit big.

  • Google has mostly stayed out of the fray, but now they’ve published a blog post detailing how they plan on preparing.

  • Google is encouraging users to upgrade to the latest version of the Google Mobile Ads SDK to take advantage of new additions like SKAdNetwork, which is Apple’s substitute for app developers to track ad campaigns.

  • For Google’s iOS Apps, the company states that they will no longer use information that falls under Apple’s ATT (App Tracking Transparency) policy. Therefore, Google iOS apps will not have to prompt the user for the extra permissions.

  • Google has not yet stated how they will follow up with these changes for the Android ecosystem.Read More

Interview Question

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

(Converting the strings to integers, multiplying them and the converting back to a string doesn’t count as a solution lol)

Example

Input - “2”, “3”

Output - “6”

Input - “123”, “456”

Output - “56088”

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

Design a Skiplist data structure without using any built-in libraries.

A Skiplist is a data structure that takes O(log n) for insertion, deletion and search.

The data structure behind a Skiplist is a linked list.

Here’s the question in LeetCode

Solution

Skip lists are an incredibly useful data structure that allow for log(n) insertion and log(n) search.

They’re basically an augmented linked list, where you can get quick access (logarithmic) to nodes in the middle/end of your linked list.

Skip Lists are commonly used in the industry. A couple examples are

• Redis - uses skip lists for their implementation of ordered sets

• MemSQL - uses skip lists as it’s prime indexing structure for it’s database

This video provides a fantastic explanation of how Skip Lists work. It’s hard to understand without graphics, so I thought it’d be better explained through a video as opposed to text in an email.

If you’re interested in gaining a better understanding of the mathematics behind Skip Lists, this lecture is great.

Here’s the Python 3 implementation of Skip List.

Special thanks to Justin Yuan for the code.

Best,

Arpan