Phone Screen Round

Imagine you are standing at an incoming conveyor belt of items that need to be packaged into boxes of exactly three items that all fit together and placed on a second, outgoing, conveyor belt. You have sufficient storage space to place items off to the side while you wait for a full triplet that all fit together.

Conveyor belt items are floating point numbers. Three items that "fit together" means that all items are within distance d of each other. Once a 3 tuple is formed, those items must be discarded (should not be considered for future tuples).

input_stream = [1.0, 11.0, 12.0, 13.0, 2.0, 3.0]
d = 3

Output:
[[11.0, 12.0, 13.0], [1.0, 2.0, 3.0]]

Distance is calculated by absolute values of the items for example
|1.0-2.0| = 1 <= 3
|2.0 - 3.0| = 1 <= 3
|1.0-3.0| = 2 <= 3

Input will not be given as an array but instead is a stream of numbers. The question is the same as here. Look at user foraccode's reply for the code. I gave the same solution but instead of using an array, used a binary search tree.

Follow Up

If instead of just floating point numbers, you were given points on an X-Y plane, how would you modify the solution?

Round 1

Question 1

Given a node in a Binary Search Tree (BST), find the next largest (inorder successor) and next smallest (inorder predecessor) node. It is guaranteed that these nodes always exist (i.e the input node will never be the smallest or largest node in the BST).

You are only given a pointer to the node, and each node has a parent pointer.

The structure is as follows:

struct Node {
    int value;
    Node* left_child;
    Node* right_child;
    Node* parent;
};

Consider this BST:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

If the given node is 3, the next largest (successor) is 4, the next smallest (predecessor) is 2.

To find the next largest (successor), we must consider 2 cases:

1. Node has a right child - In this case, the successor is the leftmost node in the right subtree.

2. Node has no right child - In this case, move up to the parent until the current node is a left child. That parent is the successor.

Similarly, for the next smallest (predecessor), just flip the above logic:

1. Node has a left child - The predecessor is the rightmost node in the left subtree.

2. Node has no left child - Move up to the parent until the current node is a right child. That parent is the predecessor.

def find_successor(node):
    if node.right_child:
        curr = node.right_child
        while curr.left_child:
            curr = curr.left_child
        return curr
    else:
        while node.parent and node != node.parent.left_child:
            node = node.parent
        return node.parent

def find_predecessor(node):
    if node.left_child:
        curr = node.left_child
        while curr.right_child:
            curr = curr.right_child
        return curr
    else:
        while node.parent and node != node.parent.right_child:
            node = node.parent
        return node.parent

Question 2

Given a source, destination and corrupted node, find if it is possible to reach the destination from the source.

This is a straightforward BFS / DFS question. Just don't traverse the corrupted node.

Follow Up

Return the minimum distance of every node from the source node. The edge weights can all be considered as 1.

Since I had used BFS to solve the question initially, I just modified it to store the distances as well (Since all edge weights are the same, we don't need to use Djikstra).

Round 2

This was a Googliness round. We went over my resume and general questions were asked. You can search up these questions quite easily on Google, Leetcode and YouTube. It was just a general discussion.

Round 3

Question 1

Given 2 strings, return if they are buddies. 2 strings are buddies if the distance between each char of the strings is the same. dist('a', 'b') = 1 and dist('b', 'a') = 25. Also, dist('z', 'a') = 1.

This was an extremely easy question. I was honestly surprised.

def are_buddies(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False

    # Compute the circular distance between characters
    diff = (ord(a[0]) - ord(b[0])) % 26

    for i in range(len(a)):
        if (ord(a[i]) - ord(b[i])) % 26 != diff:
            return False

    return True

Follow Up

Given a list of strings, group all buddies together.

This can be solved in O(NK) where N is the number of words and K is the average length of the word. The idea is to generate a hashable signature for each word based on the relative character distances. If two strings are buddies, their signatures will be the same.

"abc" → differences:
b - a = 1, c - b = 1 → hash = "1#1"

"def" → differences:
e - d = 1, f - e = 1 → hash = "1#1" → buddies with "abc"

This signature helps group all buddy strings together.

from collections import defaultdict

def get_buddy_key(word: str) -> str:
    key = []
    for i in range(1, len(word)):
        diff = (ord(word[i]) - ord(word[i - 1])) % 26
        key.append(str(diff))
    return '#'.join(key)

def group_buddies(words):
    groups = defaultdict(list)
    for word in words:
        key = get_buddy_key(word)
        groups[key].append(word)
    return list(groups.values())

Round 4

You are given a list of N elements. Each element is a tuple (value, can_decrement) where:

• value is an integer (positive or negative),
• can_decrement is a boolean indicating how the value can be adjusted:
  If True, you are only allowed to decrement the value.
  If False, you are only allowed to increment the value.

You are allowed to increment/decrement each number as much as you want, but only in the allowed direction. Your task is to determine whether it's possible to transform all values into a valid permutation of [1, 2, ..., N].

If it's possible, return the mapping in the form {original: transformed}
If it's not possible, return an empty dictionary.

This was the toughest question I got across all interviews. I took around 30 minutes to arrive at this solution. I started with a suboptimal solution. The interviewer nudged me in the correct direction and I was able to come up with this idea. She was satisfied and I coded this up.

This was my solution:

def can_transform(input_list):
    decrement_list, increment_list = [], []
    for value, can_decrement in input_list:
        if can_decrement:
            decrement_list.append(value)
        else:
            increment_list.append(value)
    
    decrement_list.sort()
    increment_list.sort()

    target = 1 # Try to start making the permutation from 1 ... N
    mapping = {}
    for value in decrement_list:
        if value < target:
            return {}
        mapping[value] = target
        target += 1
    
    for value in increment_list:
        if value > target:
            return {}
        mapping[value] = target
        target += 1
    
    return mapping

Follow Up

How many elements can be moved from the decrement list to the increment list and still allow a permutation to be made?

I thought for a while and tried to answer it. I wasn't happy with my answer and I don't remember what it was either. Maybe someone can help out in the comments here. Maybe there is an answer here using binary search, now that I think about it. But I don't want to :)

Closing

Anyway, those were all the questions I got! 1 day after the interviews, I had my team matching round. Around 3 days later I got news that the hiring manager's feedback was positive and I got an offer! Good luck to everybody trying to land a job at Google!

Compensation Overview: https://leetcode.com/discuss/post/6661297/google-l3-bangalore-by-anonymous_user-irpc/