Google L4 interview expereince
Summary
I successfully interviewed for an L4 position at Google, navigating through several challenging technical rounds focusing on algorithms, data structures, and system design, ultimately receiving an offer and joining the Google Hyderabad office.
Full Experience
My interview experience for an L4 position at Google involved several technical rounds. The preliminary screening tested my graph traversal skills with a unique message propagation problem. Round 1 focused on efficient IP address lookups. Round 2 delved into validating molecular structures, requiring careful handling of atom bonds and connectivity. The third round was a classic problem about finding the largest subsequence of digits. Finally, an additional HC round presented a challenging problem related to generating password attack lists from partial keylogger data. I received an offer and have since joined the Google Hyderabad team.
Interview Questions (5)
Let's define a kind of message called "Broadcast & Shut Down." When a router receives this message, it broadcasts the same message to all other routers within its wireless range. Then, that router shuts down, and can no longer send or receive messages.
For example, Router A is at (0, 0); Router B is at (0, 8); Router C is at (0, 17); Router D is at (11, 0). If the wireless range is 10, when Router A sends a message, it could first reach B; the message from Router B would further reach Router C but Router D would never receive this message.
Given a list of routers' locations (their names and the corresponding 2D coordinates), a source router, a destination router, and the wireless range, tell me whether a message from the source router can reach the destination router. Write a method / function with appropriate input and output arguments.
We have a file with the following format each line: startIP, endIP, cityName.
Question: Write a function that takes as input an IP address and outputs its associated cityName.
Example:
File format:
startIP, endIP, cityName
1.0.1.1, 1.0.1.10, NYC
1.0.1.20, 1.0.1.30, SF
...
If the input is 1.0.1.9, the output should be NYC.
Write code for the function.
We define an organic molecule by a list of atoms, and a list of bonds between any two of them. For example, the following formaldehyde molecule:
H
|
H-C=O
is represented as:
atoms: {1: 'C', 2: 'H', 3: 'H', 4: 'O'}
bonds: [[1, 2], [1, 3], [1, 4], [1, 4]]
The input does not have to be strictly in this format, as long as it delivers the information.
Given an input representing a molecule consisting only of Carbon, Oxygen and Hydrogen atoms, determine if it's valid.
A molecule is valid if every atom has the required number of bonds:
C atoms require exactly 4 bonds
O atoms require exactly 2 bonds
H atoms require exactly 1 bond
FOLLOW UP QUESTION:
We assume that each input represents one molecule. Multiple, disconnected molecules are considered invalid. Consider the following example:
O=C=O H-H
which would represented as
atoms: {1: 'C', 2: 'O', 3: 'O', 4: 'H', 5: 'H'}
bonds: [[1, 2], [1, 2], [1, 3], [1, 3], [4, 5]]
This input is invalid because it consists of 2 separate molecules. How would you modify your program to detect this situation?
Given a sequence S of N digits, find a subsequence of K digits such that the number formed by these K digits (in order) is the largest.
S = 4902, K = 2, answer = 92
S = 4902, K = 3, answer = 902
S = 142857, K = 1, answer = 8
S = 142857, K = 2, answer = 87
S = 142857, K = 4, answer = 4857
Generate brute force password attack list from "bad" keylogger and keyword list.
Imagine that you have a "bad" or "weak" keylogger which only has a counter (map) of each key and the number of times it was pressed in the password, unordered.
For instance, it might be a camera pointed at the keyboard, and you can't quite tell the order of the keys. So something like this:
{'a': 4, 'c': 1, 'e': 1, '1': 1}
Your goal, as an elite hacker, is to generate a list of possible passwords for a brute force attack.