Google Interviews · 19

Was asked to solve the following binary tree question

Problem Statement:

Given a binary tree where each node contains either an operator (+, -, *, /) or an integer. The tree represents a mathematical expression where each leaf node is an integer and each internal node is an operator that combines the values of its left and right subtrees. Evaluate the expression represented by the binary tree to return an integer value.

Example:

Input:
        *
       / \
      +   5
     / \
    3   2

Output: 25

Input:
        -
       / \
      *   4
     / \
    6   3

Output: 14

Was asked the robot signals problem, made some mistakes while trying to come up with an optimal approach.

You’re receiving signals from a robot, each with a timestamp (sorted in chronological order) and a message. Your task is to print messages that are unique within the last 10 seconds.

Input:

[{timestamp: 2, message: "Ready"}, {timestamp: 4, message: "Ready"}, {timestamp: 9, message: "Go"}, {timestamp: 15, message: "Stop"}]

Output: "Ready Go Stop"

Follow-up:

Need to drop duplicates that occur both in the past and the future 10-second window

Input:

[{timestamp: 0, message: "Start"}, {timestamp: 3, message: "Start"}, {timestamp: 5, message: "Move"}, {timestamp: 9, message: "Pause"}, {timestamp: 14, message: "Move"}]

Output: "Start Pause"

We can use a hashmap to store the messages as keys and the timestamps as values. Iterate through the list of messages and check whether a message has already been seen and if it falls within the 10-second window.

One of the onsite rounds involved designing a URL shortening service. Have listed some of the requirements below

Requirements:

• Should generate a unique alias for each URL and the generated links should not be predictable

• Redirects to the original URL

• Links should expire after a certain period

• The system needs to be highly available, otherwise all links will fail to redirect

I was asked a weighted cyclic directed graph question in a google doc, where each vertex represents an entity/person. The incoming edges represent the amount owed to that entity, while the outgoing edges represent the amount that entity owes to others. I was asked to output an acyclic graph with updated edge weights. The interviewer was kind and helpful but I wasn’t able to come up with the most optimal solution in time.

Input:

Vertices: A, B, C
Edges:
* A → B (A owes B $50)
* B → C (B owes C $80)
* C → A (C owes A $30, hence forming a cycle) 

Output: an acyclic graph that consolidates the amounts owed

Vertices: A, B, C
Edges:
* A → B (A owes B $20)
* B → C (B owes C $50)

I was asked a fairly easy question but made a mistake or two along the way that the interviewer had to point out so didn't make it to the next round.

Question:

Given an array of integers that might contain negative numbers, return a sorted squared array.

Example:

Input: arr = [3, -1, 10, -4, 0]
Output: [0, 1, 9, 16, 100]

Input: arr = [2, -3, 11, -7, -1]
Output: [1, 4, 9, 49, 121]

I was asked to solve a variation of text justification/word wrap problem from leetcode.

Problem:

You're given a list of strings (words) and a specified line width k. write a function that outputs the number of lines needed to format the words such that each line is exactly k characters wide, with words spaced as evenly as possible.

Example:

words = ["The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
k = 16

Output: 3

I was asked this question during the phone screen round

Problem Statement:

Given a list of songs and an integer k that represents the cooldown period, write a shuffle function for a music player that returns a random song from the list. The function should ensure that no song is played again until at least k other songs have been played.

Example:

songs = [A, B, C] and k = 2

shuffle([A, B, C]) -> B
shuffle([A, _, C]) -> C
shuffle([A, _, _]) -> A
shuffle([_, B, _]) -> B # B is eligible again as 2 songs have been played since it was last selected

Clarifying questions that I asked:

• What if k is greater than the total number of songs? can ignore the cooldown period and replay a song

Possible Approach:

We can keep a queue of size k for the songs we've played. When we play a song, add it to the back of the queue. If the queue gets bigger than k, pop the oldest song from the front and put it back in the list so it can be picked again later.

def shuffle(songs, k):
    played_queue = deque()

    while True:
        eligible_songs = [song for song in songs if song not in played_queue]

        if not eligible_songs:
            break  # if no eligible songs are left

        next_song = random.choice(eligible_songs)
        print("Playing:", next_song)

        # Add the played song to the queue
        played_queue.append(next_song)

        # If the queue exceeds size k, remove the oldest song from the queue
        if len(played_queue) > k:
            played_queue.popleft()

Had a phone screen where the first 5 minutes were introductions and then another 5 mins to go over the question. I was asked the "find the closest value in a binary tree" leetcode question. The last 5-10 mins were for me to go over any questions I had

Problem:

Given a non-empty root of a binary search tree (BST) and a target value k, find the value in the tree that's closest to k

 Input: root = [6, 4, 8, 3, 5, None, 9], k = 7.2

      6
     / \
    4   8
   / \   \
  3   5   9

Output: 8

Approach:

Start at the root and keep track of the closest value we have found so far. If the current value is greater than k then traverse the left subtree, otherwise traverse the right subtree if it's less than or equal to k. Keep doing this and updating the closest value until we've reached the end of the tree.

We talked about my past experiences and the role that I was interviewing for. Gave me tips on preparing by doing leetcode problems and brushing up on data structures and algorithms. Was told to think aloud during the interview, and ask for clarifications.

I was asked to invert a binary tree in a shared google doc. Pretty standard leetcode problem.

Problem: Given the root of a binary tree, invert the tree and return the new root

Approach: Inverting requires swapping the left and right children of all nodes in the tree. Need to use a queue (BFS) to process each node, swap its children, and then add those children to the queue for further processing.

Example:

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

Output:

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

I was asked a DSA question that involved implementing a solution to efficiently insert, search, and remove house addresses. The last 10-15 minutes were for me to ask any questions about the role and overall culture.

Question:

Implement a data structure to efficiently store and manage house addresses. Each house address consists of the following fields: House Number, Street Name, City , ZIP/Postal Code

Need to support the following operations:

• Add address

• Remove address

• Search by house number

• Search by street name (or prefix) (retrieves all houses for the street)

• Search by zip code (or prefix) (retrieves all addresses located within a given zip/postal code)

• Update address (house number, street name, or ZIP code of an existing address)

Solution:

To search for full addresses by house number, we can use a hashmap where the key is the house number and the value is the full address

address_by_house_number = {
    1234: {"house_number": 1234, "street_name": "Elm Street", "zip_code": "12345"},
}

We can make use of a trie for efficiently performing prefix-based searches on street names or ZIP codes. Each node in the Trie represents a character or digit, and the leaves (end nodes) contain references (house numbers) to addresses that match the prefix. At each node where the prefix search completes, we can gather all house numbers that are stored in that node and its descendants. The Trie’s search method will return a set of house numbers.

• Once we have all relevant house numbers from the Trie, we can use the hashmap (address_by_house_number) to look up the full addresses for each of the house numbers.

Quick chat with the recruiter about my background and the role that I applied for and what the next steps would be

Was asked to implement the Allocate Minimum Number of Pages from N books to M students problem. I wasn't able to implement it fully in time

Problem:

You are given N books, where each book has a certain number of pages. These N books need to be distributed among M students such that each student gets at least one book, and the maximum number of pages assigned to a student is minimized.

Catch: Each student can only read books that are next to each other (in a contiguous block).

Example:

Input:

• N = 4 (Number of books)

• M = 2 (Number of students)

• Pages = [12, 34, 67, 90] (Each number represents how many pages are in a book)

Output:

• 113 (the smallest possible number of pages that the student with the most pages has to read)

One possible way to split the books is:

• Student 1: [12, 34, 67] (Total = 113 pages)

• Student 2: [90] (Total = 90 pages)

Approach:

1. Binary Search: Use binary search to find the minimum possible value of the maximum number of pages a student will have to read.

2. Greedy Check: For a given maximum number of pages (mid), check if it’s possible to distribute the books such that no student reads more than mid pages. This involves a greedy approach where you try to allocate books to students and see if you can do it within the given mid value.

I was asked to implement an optimal solution for the question below, but I couldn't come up with one at the time

Question:

You are given a list of distinct positive integers. From this list, you can select any subset of numbers, rearrange them in any order, and use the operators +, -, *, /, along with parentheses to create mathematical expressions. Need to find the smallest positive integer that can't be formed using any combination of these numbers, with each number being used at most once in any expression.

Constraints:

• Can rearrange and reorder the selected numbers in any way.

• Each number from the list can be used only once in a single expression.

• Only results that are positive integers are considered valid.

Sample Input #1:

[1, 2, 6, 7]

Sample Output:

4

• You can form the numbers 1, 2, and 3 using the elements.

• The number 4 cannot be produced from any combination of these numbers with the allowed operators.

Sample Input #2:

[1, 2, 5]

Sample Output:

4

• 1 (directly from the array)

• 2 (directly from the array)

• 3 = 1 + 2

In this example, you can form 1 and 2, but 4 is the lowest possible positive integer that cannot be formed using any combination of the numbers from the array.

The optimal solution involves using the greedy approach, which I wasn't able to think of on the spot

def find_smallest_missing_positive(arr):
    arr.sort()
    smallest_missing = 1
    
    for num in arr:
        if num <= smallest_missing:
            smallest_missing += num
        else:
            break
    
    return smallest_missing

arr = [1, 2, 5]
print(find_smallest_missing_positive(arr))  # Output: 4

• Time Complexity: O(n log n) due to the sorting step, where n is the number of elements in the array.

• Space Complexity: O(1) for the greedy approach, as we use only a constant amount of extra space.

I was asked a leetcode array DSA question, and then we went over my resume and talked about my background. I thought it went okay but didn't move forward.

Question:

Given an array of intervals where each interval is represented as a pair of integers [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example Input:

[[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

• Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

• The rest of the intervals do not overlap with any others.

def merge(intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    merged_intervals = []
    
    for interval in intervals:
        # If merged_intervals is empty or current interval does not overlap with the last merged one
        if not merged_intervals or merged_intervals[-1][1] < interval[0]:
            merged_intervals.append(interval)
        else:
            # If there is an overlap, merge the current interval with the last one in merged_intervals
            # by updating the end of the last interval to the maximum end value
            merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])
    
    return merged_intervals

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
result = merge(intervals)
print(result)  # Output: [[1, 6], [8, 10], [15, 18]]

The interviewer pasted the question in the document, and I asked for some clarifications. They then asked about my previous projects listed on my resume. The questions were fairly standard. At the end, I also had a few questions of my own. Was asked to implement the problem below, which is a variation of the Top K problem.

Question:

Given a continuous stream of integers and a fixed integer n, which remains constant throughout the stream, output the top n most frequent elements from the stream. When a query with the integer 0 is received, output the top n most frequent elements observed so far.

Example:

• Input Stream: [3, 1, 2, 3, 1, 2, 3, 4, 2, 0, 5, 6, 2, 0]

• Value of n: 3

Output:

• After processing up to the first 0 query: [3, 2, 1] (at this point, the element 3 has appeared the most, followed by 2 and 1.)

• After processing up to the second 0 query: [2, 3, 4] (by this time, the element 2 has become the most frequent, followed by 3 and 4, as 4 has now appeared frequently enough to be in the top 3.)

Brute Force Solution:

Suggested that we can use a hashmap to store the frequencies of each element as we process the stream. For each new input or query, we would sort the elements by their frequency and then retrieve the top k elements.

Optimal Solution:

Use a hashmap to track the frequency of each element. Maintain a min-heap of size n to keep track of the top n elements based on their frequency. When a new element arrives, update its frequency in the hashmap and adjust the heap to ensure it contains the most frequent elements. When a query with 0 is received, simply retrieve the elements from the heap.

import java.util.*;

class MinHeap {
    private final int size;
    private final PriorityQueue<HeapNode> heap;
    private final Map<Integer, HeapNode> entryFinder;

    public MinHeap(int size) {
        this.size = size;
        this.heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.frequency));
        this.entryFinder = new HashMap<>();
    }

    public void push(int item, int frequency) {
        if (entryFinder.containsKey(item)) {
            // Remove the old entry
            remove(item);
        }
        HeapNode entry = new HeapNode(frequency, item);
        entryFinder.put(item, entry);
        if (heap.size() < size) {
            heap.add(entry);
        } else if (frequency > heap.peek().frequency) {
            heap.poll();
            heap.add(entry);
        }
    }

    public void remove(int item) {
        HeapNode entry = entryFinder.remove(item);
        if (entry != null) {
            entry.frequency = Integer.MIN_VALUE; // Mark as removed
        }
    }

    public List<Integer> getTopElements() {
        List<Integer> topElements = new ArrayList<>();
        for (HeapNode node : heap) {
            if (node.frequency != Integer.MIN_VALUE) {
                topElements.add(node.item);
            }
        }
        return topElements;
    }

    private static class HeapNode {
        int frequency;
        int item;

        HeapNode(int frequency, int item) {
            this.frequency = frequency;
            this.item = item;
        }
    }
}

class TopKFrequent {
    private final int k;
    private final Map<Integer, Integer> frequencyMap;
    private final MinHeap minHeap;

    public TopKFrequent(int k) {
        this.k = k;
        this.frequencyMap = new HashMap<>();
        this.minHeap = new MinHeap(k);
    }

    public void add(int element) {
        frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        minHeap.push(element, frequencyMap.get(element));
    }

    public List<Integer> getTopK() {
        return minHeap.getTopElements();
    }

    public static void main(String[] args) {
        TopKFrequent topKFrequent = new TopKFrequent(3);
        int[] stream = {3, 1, 2, 3, 1, 2, 3, 4, 2};
        for (int num : stream) {
            topKFrequent.add(num);
        }

        // Query for top k elements
        System.out.println(topKFrequent.getTopK());  // Output: [3, 2, 1]
    }
}

Time Complexity:

• push(int item, int frequency): O(log k)

• remove(int item): O(1)

• getTopElements(): O(k)

Processing stream of N elements: O(N * log k)

The process kicked off with an HR interview. After clearing that, they sent me prep materials for the technical interview and let me choose a date that worked for me.

This round focused on a problem involving sparse matrices, but the interviewer didn't seem very engaged and wasn't really interested in discussing my thought process or decisions while solving the problem.

Problem:

How would you implement a matrix where most of the elements are zero, with only a few non-zero values?

Solution:

You need three lists to set up a sparse matrix using the Coordinate List (COO) format: one for row indices, one for column indices, and one for the non-zero values. When you add a value, you append the row and column indices along with the value to these lists. To retrieve a value, you search through the lists to find the matching row and column. This approach may not be ideal for very large matrices or frequent updates, the Compressed Sparse Row (CSR) format might be more efficient for those cases.

I found the problem pretty difficult. I struggled to grasp the concept at first and had to ask for multiple explanations before I got it. I made the question more complex than it needed to be and should have done a better job of sharing my thought process out loud. We also ended up chatting quite a bit about the weather in New York and what it’s like to live and work there since the job is fully in-person, not remote.

Problem:

Was asked 3 sum

Given an array of integers, find all unique triplets [a,b,c] in the array such that their sum is zero, i.e., a + b + c = 0

Sample Input:

nums = [-1, 0, 1, 2, -1, -4]

Sample Output:

[[-1, -1, 2], [-1, 0, 1]]

I was asked a basic DSA question during the interview and was encouraged to further optimize my solution. The interviewer was friendly and guided me through different stages of the problem. Although there were two interview rounds in the selection process, I was unable to pass the first one.

Problem:

I was given an array of integers and asked to find a pair of indices i and j where the sum of the elements between these indices (excluding the elements at i and j) is as large as possible, and the elements at i and j must be the same.

Example input:

array = [4, 2, 1, 4, 3, 2, 4]

Example output:

The maximum sum of elements between any valid pairs is 12 (between indices 0 and 6).

Possible optimal solution (not the one provided during the interview):

import java.util.HashMap;
import java.util.Map;

public class MaxSumBetweenEqualPairs {

    public static int findMaxSum(int[] array) {
        int n = array.length;
        int[] prefixSum = new int[n + 1];  // Prefix sum array, 1 extra element for easier indexing
        
        // Compute prefix sums
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + array[i];
        }

        // Map to track last occurrence and max sum seen so far for each value
        Map<Integer, Integer> lastOccurrence = new HashMap<>();
        int maxSum = Integer.MIN_VALUE;

        // Iterate over the array
        for (int i = 0; i < n; i++) {
            int value = array[i];

            // Check if the value has been seen before
            if (lastOccurrence.containsKey(value)) {
                // Get the last index where this value was seen
                int lastIndex = lastOccurrence.get(value);

                // Calculate the sum of elements between lastIndex and current index i
                int currentSum = prefixSum[i] - prefixSum[lastIndex + 1];

                // Update maxSum if the currentSum is larger
                maxSum = Math.max(maxSum, currentSum);
            }

            // Update the last occurrence of the value to the current index
            lastOccurrence.put(value, i);
        }

        // Return 0 if no valid pairs were found
        return maxSum == Integer.MIN_VALUE ? 0 : maxSum;
    }

   public static void main(String[] args) {
        int[] array = {4, 2, 1, 4, 3, 2, 4};
        System.out.println(findMaxSum(array));  // Output: 12
    }
}

Time & Space Complexity:

O(n) since we only make a single pass through the array and use prefix sums to efficiently compute subarray sums.

O(n) for the prefix sums and the hash map

The interview kicked off with the interviewer introducing himself over Google Meet. We got started as soon as I opened up the interview document.

Problem:

Given a sorted array of strings and a prefix string, count how many elements in the array begin with the given prefix.

Input:

array = ["apple", "applet", "banana", "berry", "candy", "cane", "carrot", "date", "eggplant", "fig", "grape"]
prefix = "ca"

Output:

The expected output would be 3, since the elements "candy," "cane," and "carrot" all start with the prefix "ca."

Solution:

I initially suggested a linear approach with a time complexity of O(n * k) (where n is the length of the array and k is the length of the prefix).

Interview Experience:

The interviewer was looking for a more efficient solution. I then proposed using binary search to find one element that matched the prefix and then using two pointers to count the number of such elements. Unfortunately, this approach still had a worst-case time complexity of O(n * k), which wasn't ideal.

The interviewer hinted that I should use binary search to find both the start and end points of the range where elements match the prefix. I coded two binary search functions: one to find the leftmost occurrence and another for the rightmost.

The interviewer was pleased with the first binary search (for the left end). However, I missed a condition in the second binary search (for the right end), and with the interview time running out (it was 45 minutes in), I couldn’t solve it in time.

Afterward, the interviewer provided feedback. He mentioned that my communication was good, but I needed to be more open-minded about the problem-solving approach.

Optimal implementation:

def binary_search_left(array, prefix):
    low, high = 0, len(array)
    while low < high:
        mid = (low + high) // 2
        if array[mid] < prefix:
            low = mid + 1
        else:
            high = mid
    return low

def binary_search_right(array, prefix):
    low, high = 0, len(array)
    while low < high:
        mid = (low + high) // 2
        if array[mid] <= prefix:
            low = mid + 1
        else:
            high = mid
    return low

def count_elements_with_prefix(array, prefix):
    # Define the prefix end
    prefix_end = prefix[:-1] + chr(ord(prefix[-1]) + 1)
    
    # Use binary search to find the left and right boundaries
    left_index = binary_search_left(array, prefix)
    right_index = binary_search_right(array, prefix_end)
    
    # The count of elements with the given prefix
    count = right_index - left_index
    
    return count

array = ["apple", "applet", "banana", "berry", "candy", "cane", "carrot", "date", "eggplant", "fig", "grape"]
prefix = "ca"
print(count_elements_with_prefix(array, prefix))  # Output: 3

Time Complexity:

Since we perform binary searches twice (once for the left boundary and once for the right boundary), and each search operation is O(log⁡ n), the total time complexity of the count_elements_with_prefix function is: O(log⁡ n) + O(log ⁡n) = O(log ⁡n)

This round had me solving a pretty standard coding problem - nothing too crazy. I had to come up with an optimal solution and explain my thought process. Overall, it was straightforward and the interviewer seemed happy with my approach.

Question:

Given a string containing placeholders in the format %WORD%, you need to replace each placeholder with the corresponding value from a dictionary. If a placeholder is not found in the dictionary, it can be left unchanged or replaced with an empty string, depending on the specific requirements.

Example:

• Input String: "Hello %NAME%, welcome to %PLACE%!"

• Dictionary: {"NAME": "Alice", "PLACE": "Wonderland"}

• Output String: "Hello Alice, welcome to Wonderland!"

Solution:

1. Traverse the String: Iterate through the string character by character.

2. Identify Placeholders: Detect placeholders by checking for the % character and extract the word between % symbols.

3. Replace Placeholders: Use the dictionary to replace the placeholders with their corresponding values or keep them unchanged if not found.

import java.util.HashMap;
import java.util.Map;

public class PlaceholderReplacer {
    
    public static String replacePlaceholders(String text, Map<String, String> variables) {
        StringBuilder result = new StringBuilder();
        int length = text.length();
        int i = 0;

        while (i < length) {
            if (text.charAt(i) == '%') {
                int start = i + 1;
                // Find the end of the placeholder
                while (i < length && text.charAt(i) != '%') {
                    i++;
                }
                if (i < length) {
                    String key = text.substring(start, i);
                    String replacement = variables.getOrDefault(key, "%" + key + "%");
                    result.append(replacement);
                    i++; // Skip the ending '%'
                }
            } else {
                result.append(text.charAt(i));
            }
            i++;
        }

        return result.toString();
    }

    public static void main(String[] args) {
        String text = "Hello %NAME%, welcome to %PLACE%!";
        Map<String, String> variables = new HashMap<>();
        variables.put("NAME", "Alice");
        variables.put("PLACE", "Wonderland");

        String result = replacePlaceholders(text, variables);
        System.out.println(result);  // Output: "Hello Alice, welcome to Wonderland!"
    }
}

Time Complexity:

O(n)

• Finding placeholders: O(n)

• Replacing placeholders: O(n) for scanning and replacement.

The coding question in this round focused on problem-solving, edge case handling, and code optimization.

Question:

Generate all possible valid sequences of musical notes where:

1. Each sequence sums to exactly 12.

2. Notes can only be 1, 2, or 3.

3. Valid transitions between notes are given by the dictionary {1: [2, 3], 2: [1, 2], 3: [1]} (e.g., after 1, you can only have 2 or 3).

4. The first and last notes in the sequence must have a valid transition according to the dictionary.

   • allowed: [1, 2, 2, 2, 1, 1, 3] (First note 1 can be followed by 2, and last note 3 can follow 1)

   • not allowed: [1, 2, 2, 2, 2, 2, 1] (First note 1 can be followed by 2, but last note 1 cannot follow 1)

Return all possible valid sequences.

Solution:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MusicalNotes {

    private static final int TARGET_SUM = 12;
    private static final int MAX_LENGTH = 11;
    private static final Map<Integer, List<Integer>> transitions = new HashMap<>();

    static {
        transitions.put(1, List.of(2, 3));
        transitions.put(2, List.of(1, 2));
        transitions.put(3, List.of(1));
    }

    public List<List<Integer>> findSequences() {
        List<List<Integer>> results = new ArrayList<>();
        dfs(new ArrayList<>(), 0, results);
        return results;
    }

    private void dfs(List<Integer> current, int currentSum, List<List<Integer>> results) {
        if (currentSum > TARGET_SUM || current.size() > MAX_LENGTH) {
            return; // Prune invalid sequences
        }

        if (currentSum == TARGET_SUM && current.size() > 1) {
            // Check valid transition between first and last note
            if (isValidTransition(current.get(0), current.get(current.size() - 1))) {
                results.add(new ArrayList<>(current));
            }
            return;
        }

        for (int note : transitions.keySet()) {
            if (current.isEmpty() || transitions.get(current.get(current.size() - 1)).contains(note)) {
                current.add(note);
                dfs(current, currentSum + note, results);
                current.remove(current.size() - 1); // Backtrack
            }
        }
    }

    private boolean isValidTransition(int start, int end) {
        return transitions.get(start).contains(end);
    }

    public static void main(String[] args) {
        MusicalNotes musicalNotes = new MusicalNotes();
        List<List<Integer>> sequences = musicalNotes.findSequences();
        System.out.println("Possible sequences:");
        for (List<Integer> sequence : sequences) {
            System.out.println(sequence);
        }
    }
}

• findSequences Method: Starts the search for valid sequences.

• dfs Method: Recursively builds sequences by adding notes, ensuring the sum is 12 and the length does not exceed 11. It checks each sequence for validity based on transitions and constraints.

• Pruning: Sequences are pruned if the sum exceeds 12 or the length exceeds 11, improving efficiency.

Time complexity:

The time complexity is O(n^L), where n is the number of possible notes (3) and L is the maximum length of the sequence (12). In this case:

• Depth of Recursion: Up to 11 levels (max length).

• Branching Factor: Up to 3 possible notes per level.

The question was of medium difficulty but required handling multiple cases which made it a bit long and messy. The interviewer wasn’t super engaged, so it felt like I was on my own for most of the interview.

Question:

Was asked to implement a function to handle three types of queries related to employee management:

1. manager, a, b: Indicates that employee a is the manager of employee b.

2. peer, a, b: Checks if employees a and b have the same manager.

3. is_manager, a, b: Determines if employee a is the manager of employee b.

Can assume that each input is valid and each query is processed one at a time. It's possible for a peer query to pass two employees who do not currently have any manager assigned.

Solution:

import java.util.HashMap;
import java.util.Map;

public class EmployeeManagement {

    private Map<String, String> managerMap;

    public EmployeeManagement() {
        managerMap = new HashMap<>();
    }

    public String handleQuery(String query) {
        String[] parts = query.split(", ");
        String command = parts[0];

        switch (command) {
            case "manager":
                // Set employee `b`'s manager to `a`
                String manager = parts[1];
                String employee = parts[2];
                managerMap.put(employee, manager);
                return null;  // No output for 'manager' command

            case "peer":
                // Check if both `a` and `b` have the same manager
                String a = parts[1];
                String b = parts[2];
                String managerA = managerMap.get(a);
                String managerB = managerMap.get(b);
                // Check if both have the same manager or both have no manager
                if (managerA == null && managerB == null) {
                    return "true";  // Both are managerless
                }
                if (managerA != null && managerA.equals(managerB)) {
                    return "true";
                }
                return "false";

            case "is_manager":
                // Check if `a` is the manager of `b`
                String potentialManager = parts[1];
                String employeeQuery = parts[2];
                String actualManager = managerMap.get(employeeQuery);
                return Boolean.toString(potentialManager.equals(actualManager));

            default:
                throw new IllegalArgumentException("Unknown command: " + command);
        }
    }

    public static void main(String[] args) {
        EmployeeManagement management = new EmployeeManagement();

        // Example queries
        System.out.println(management.handleQuery("manager, Alice, Bob"));      // null
        System.out.println(management.handleQuery("is_manager, Alice, Bob"));   // true
        System.out.println(management.handleQuery("peer, Alice, Bob"));         // false
        System.out.println(management.handleQuery("peer, Charlie, Dave"));      // true (both managerless)
    }
}

Last interview was the Googleyness and leadership interview, discussing how I've handled difficult team dynamics or made decisions with incomplete information/ambiguity