☕ New iPhone leak

Hey,

Hope you’re having an awesome day!

On to the Interview Problem and Industry News!

Interview Problem

What is Availability in the context of System Design?

How is it measured and how can you increase it?

We’ll send out the 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 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”

Industry News

iPhone 12 lineup’s pricing and release leaked - The next iPhone event is on October 13th and Apple’s line up has already been leaked. Here are the details.

• 4 new iPhones - all feature 5G support

  • iPhone 12 mini - 5.4 inch display and a starting price of $699.

  • iPhone 12 - 6.1 inch display with a starting price of $799.

  • iPhone 12 Pro - LIDAR sensors for AR and telephoto camera with 4x optical zoom. Starting price of $999.

  • iPhone 12 Pro max - 6.7 inch screen with a starting price of $1099. Has three cameras and a LIDAR sensor. Telephoto lens will offer 5x optical zoom.

Significant effects of Apple’s IDFA change for developers- Identifier for Advertisers, known as IDFA, is crucial for advertisers who want to target consumers with ads on the iOS ecosystem. You can think of IDFA as similar to an advertising cookie, they give much better information on consumer preferences and actions. iOS App Developers can then use targeted advertising to significantly boost their revenues from ads.

In June, Apple announced that it would change IDFA to make it opt-in. Apple will ask users if they want to opt-in to being tracked for advertising purposes before any of the tracking happened. Due to the way the opt-in question was worded, observers predict that no more than 20% of users will opt-in.

These changes to IDFA have been heavily criticized by developers. Many are seeing revenue dropping by more than 40%. Facebook said they saw a 50% revenue drop in Facebook Audience Network when personalization was removed from mobile ad install campaigns.

However, they do give Apple users more control over their own data and help Apple align itself with their mission of giving users more privacy.

Previous Solution

As a refresher, here’s the previous question

Design a data structure for an LRU (Least Recently Used) Cache.

Implement the following functions:

• Constructor that takes in the size of the LRU Cache as a parameter.

• get(key) Return the value of the key if the key exists, otherwise return -1. This key is now the most recently used item in the cache.

• put(key,value) Add the key and value to the LRU cache. If the cache is already at capacity, then delete the least recently used item.

Solution

So, when you see the get and put methods, your mind should immediately drift towards using a hash table. Hash tables give you get and put in O(1) time.

However, the tricky part is how to do the cache eviction. When your hash table reaches capacity (the size of the LRU cache), how can you figure out which key was the least recently used (so you can delete it)?

For this part, we can use a doubly linked list. The linked list keeps track of the order in which the keys were last used.

Now, we’ll create helper methods _addKey and _removeKey to help us with adding/removing from our hash table and linked list.

For _addKey, we first create a new node with that key and value and add it to our hash table (with the key being the key given and the value being a reference to the new node). Then, we add the new node to our linked list.

For _removeKey, we can first look for the key in our hash table. From there, we’ll get a reference to the node in our linked list. We can then delete the key from our hash table and use the reference to the node to delete it from our linked list.

Now, we can use _addKey and _removeKey to implement our get and put functions.

With get, we first check if the key is in our hash table. If it isn’t, then we can just return -1. If the key is in our hash table, then we’ll use the node reference to get the associated value. After, we’ll call _removeKey to remove the key from our LRU Cache and _addKey to add it back to our LRU Cache. This is a quick way of putting this key in the front of our linked list and setting it as the “most recently used” item. Then, we can return the value.

With put, we first check if the key is already in our hash table. If it is, then we’ll remove it from the LRU Cache with _removeKey and then add it back to our LRU Cache with _addKey. Again, this has the effect of putting this key in the front of our linked list and setting it as the most recently used item.

If the key is NOT in our hash table, then we can just call _addKey and add it to our LRU Cache. Now, if the size of our hash table is greater than the LRU Cache’s size, then we can look at the tail node of our linked list. This is the least recently used item. We get that node’s key and then we call _removeKey to evict it from our cache.

get and put both run in O(1) time.

Here’s the Python 3 code.

Feel free to reply to this email with any questions!