Hey Guys,

The Previous Solution part of today’s email will be a short explainer on Map Reduce (that was our last interview question).

I’m writing a long-form article on Map Reduce that’ll be published next week. If you want to get the article today, reply back to this email with the title of your favorite book. I’ll reply back with the article.

I’m looking to get some feedback on the article before I publish it, so would love to send some of you guys a sneak peek!

Onto the Interview Problem!

Interview Problem

You are given a list of words as input.

Find all pairs of unique indices such that the concatenation of the two words is a palindrome.

Input - ["bat","dcba","lls","s","sssll", "cat", "tab"]

Output - [[0,6],[3,2],[2,4],[6,0]]

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 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

Apple is stepping up plans to build its own Search Engine

Apple has been working on a search engine for quite a few years now. The company has been using its own web crawlers since 2014 (the crawlers are written in Go!). Those crawlers are used for services like Siri, Apple’s virtual assistant.

Now, Apple is accelerating efforts to develop their own search engine as their current search deal with Google is coming under threat.

Google currently pays Apple an estimated $8-12 billion dollars per year to be the default search engine on iOS devices. In 2018, the sum was 20% of Apple’s services income for the year at a little under $10 billion dollars.

The US Department of Justice has now sued Google for antitrust concerns, and they’re taking aim at these “tying” arrangements that Google has with companies (where Google is paying a company like Apple to make Google Search the default search in iOS). Check out our last email to read more on the Justice Department’s lawsuit!

If a court ends up siding with the DOJ, Google could be forbidden from offering their search services as a default to Apple. In that scenario, Apple could be best served by developing their own search engine.

In 2017, Apple also poached John Giannandrea, Google’s head of search. Ostensibly, he now works on Siri and Apple’s artificial intelligence capabilities, but it’s hard to believe that Apple won’t be asking him about his knowledge on search.

Microsoft reports Earnings

Microsoft reported financial results for their last quarter and had fantastic results. Sales rose 12% to 37.2 billion dollars, generating a net profit of $13.9 billion dollars. Revenue from Azure, Microsoft’s Cloud Services competitor to AWS and GCP, increased 48% compared to one year ago.

The pandemic has created a surge in demand for cloud-computing services and computers. It’s also created a huge boost for video conferencing and workplace collaboration software. Microsoft offers Teams, which competes with Slack and Zoom. Teams now has more than 115 million daily active users, up from 75 million daily active users in April. Satya Nadella stated that many of the changes made during the pandemic to how people work are expected to last.

Previous Solution

As a refresher, here’s the previous question

What is Map Reduce? Why is it useful?

Can you give an example use case?

Solution

Let’s say you have a bunch of text files containing every book that’s ever been published in the english language. You want to scan through all these text files and search for all the names in these books and count the number of times each of those names appears.

Since it’s every book that’s ever been published, that’s a huge number of text files. All those text files can’t fit on one computer, so they’re spread out across hundreds or thousands of machines. How can you accomplish this?

Google Engineers were faced with a similar conundrum, where they had to do data processing tasks on large data sets that were split across thousands of computers. Two Googlers, Jeff Dean and Sanjay Ghemawat, then rose up to the occasion and came up with a solution. Map Reduce.

Jeff and Sanjay realized that the grand majority of data processing tasks could be split into two steps

1. Map

2. Reduce

These two steps do the exact same thing as the Map and Reduce functions in Lisp or any functional programming language you might have used.

You first apply the Map function on your data, where you go to each of the machines and transform your data into a set of key/value pairs.

Going back to our example from the first paragraph, we have a bunch of text files on different machines where each text file represents the words in a book. Our Map function would run simultaneously on all our machines. On each machine, it would scan through every text file (book) and find all the names (using some Name Entity Recognition function in any Natural Language Processing library) and count the number of times that name appears. After running the Map function on the machine, we’ll be left with a bunch of key/value pairs, where the keys represent names in our books and the values represent the number of times each of those names appeared across all the text files on that machine ( an example key/value pair might be Jerry / 23242 ). Again, we ran this same map function on all our machines so now we have a bunch of machines that each have a bunch of key/value pairs.

Now, we take the key/value pairs from each of those machines and send them to new machines where we run our Reduce function. We have to make sure that we send key/value pairs with the same key to the same machine! Our Reduce function will then aggregate all the keys into a single value.

So, with our example with the names in books, our key/value pairs are names/# of times the name occurred. So now we have to aggregate the keys since the key Jerry is most likely on many of the machines (Jerry is a common name, so lots of Map functions probably found the name Jerry in their text files). Therefore, we send key/value pairs with the same key to the same machine. That machine then goes through all the key/value pairs with the same key and adds up the values as the Reduce step. Then, it outputs a final key/value pair with the given key and the value across all the books.

This output can be written to a final text file on a different machine that will contain all the keys in our data set (all the names in the books) and their corresponding values (how many times each of those names appeared in all our books). The final text file can finally be returned by Map Reduce as the answer.

And that’s it!

Again, this is a short summary of Map Reduce. I’m writing a long-form article that’ll be published next week. If you want to get the article today, reply back to this email with the title of your favorite book. Then I’ll send you the article!

Thanks!

Best,

Arpan