☕ The Future of Google...
Hey Guys,
Hope you’re all having a fantastic day! Here’s your Tech Snippets, Interview Problem and Previous Solution for the day.
Industry News
Google I/O
Google I/O is Google’s annual developer conference where the company unveils it’s biggest products for developers.
This year’s event revolved around Google’s focus on Artificial Intelligence but also had quite a few new products from other areas. Here’s the breakdown…
LaMDA - Language Model for Dialogue Applications
LaMDA is a language model that Google has been working on specifically designed for conversation.
Similar to many other recent language models (BERT, GPT-3), LaMDA is transformer-based. However, one key difference with LaMDA (vs. BERT or GPT-3) is that it was trained on dialogue. Google designed the language model from the start for Dialogue Applications.
The model is open domain, meaning that it can converse on any topic. You can ask it questions around music, history, space exploration or anything and it can respond with answers
The Android 12 Beta was released 2 days ago, allowing users to test out the new OS as well as developers. The final release of Android 12 will be later this year.
Android 12 launch schedule
There will be a big redesign for Android 12 with a completely new UI based on Material You, a new design language by Google.
Google is betting big on Quantum Computing, building a Quantum AI campus in Santa Barbara, California.
Their goal is to create a “useful, error-corrected quantum computer” by the end of the decade.
Error correction is used in quantum computing to protect quantum information from errors due to decoherence.
Decoherence is caused by the environment interacting with the qubits (quantum bits, the equivalent of a transistor for a quantum computer) and uncontrollably changing their quantum states. This causes information stored by the quantum computer to be lost.
The company wants to build a 1,000,000 physical qubit computer, a big leap from today’s systems of fewer than 100 qubits.
One example of where Quantum computers are useful, is in simulating the real world.
When you want to create more targeted medicines or build better batteries, you need to understand and design molecules better. Classical computers don’t simulate molecules well and quickly run out of computing resources.
Quantum computers, however, use quantum bits (qubits) which can be entangled in a complex superposition of states. This naturally mirrors the complexity of molecules in the real world.
With an error-corrected quantum computer, you could simulate how molecules will behave and interact. That allows you to test and invent new chemical processes before investing in (costly) real-life prototypes.
Project Starline is a video conferencing tool by Google that gives a much greater feel of being in the same room.
Google uses depth sensors and high resolution cameras to capture your shape and appearance from multiple perspectives.
Google then compresses and streams this data to the receiver’s terminal where it recreates your image with depth (using a 3-D display).
Currently, the tech is being tested out in Google’s offices but they plan on expanding it out to other companies.
Google has some big upgrades planned for Google Maps Live View
Live View displays your surroundings in real time on your phone. Then, it uses Augmented Reality to add markers to your surroundings to display things like directions
Google will be adding markers for key landmarks and hotels and also indoor navigation.
Tech Snippets
How Slack scales with Application-Level Edge Caching
When you first start a Slack client, Slack’s servers send a full snapshot of team data to the client (containing info on users, channels, latest messages, DMs, etc.)
Large Slack teams (with thousands of users) start to have an issue with client startup time and overhead.
Slack solves this by implementing lazy loading in their client wherever possible.
In order to make the lazy loading fast, Slack built Flannel, an application-level edge caching service. It is deployed to Slack’s edge points of presence and caches relevant data of users, channels, bots and more. It can predict data that will be requested next and proactively push that data to clients.
Interview Question
You’re given two strings s and p. Both strings will not be empty.
Find all the start indices of p’s anagrams in s.
Example 1:
Input: s: "cbaebabacd" p: "abc"
Output: [0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab"
Output: [0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
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 last question
You are given a character array containing a set of words separated by whitespace. Your task is to modify that character array so that the words all appear in reverse order. Do this without using any extra space.
Example
input - ['A', 'l', 'i', 'c', 'e', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'B', 'o', 'b']
output - ['B', 'o', 'b', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'A', 'l', 'i', 'c', 'e']
Solution
Let’s try and look at simpler version of this question.
What if every word in the sentence was just one letter? How could we solve it then?
Well, we could solve it by just reversing the character array. You can use the two pointer method to reverse it. One pointer goes at the start of the array and one pointer at the end. You swap the characters at both pointers and then increment the first pointer and decrement the last. You’ll terminate the loop when the two pointers cross.
Now, what about in the general case, where each word can be more than one letter?
In that scenario, reversing the character array gets the words in their correct position, but it causes the letters in the word to appear in reverse order (if that word is longer than 1 letter). We can fix that by reversing the individual words.
Use the two pointer method to reverse the entire character array. Then iterate through the character array and look for each individual word. Use the two pointer method again to reverse each word. That’ll give us the correct answer. It runs in O(n) time and uses O(1) space.