Google | SWE-3 | Interview Questions

Experience: 5 Years
Current Company: Mid-size product based company.

I got call through referral. There are 4 rounds for me. 3 technical and 1 Googleyness.

Round-1: Expected Result: Lean Hire

Problem-1: Set Difference of Floating-Point Ranges
You are given two lists of floating-point ranges, a and b. Each list contains zero or more disjoint ranges, represented as pairs [start, end), where start is inclusive and end is exclusive. The ranges within each list are not necessarily sorted.
Your task is to compute the "set difference" of these ranges, specifically a - b. This means you need to find all the segments within the ranges of a that do not overlap with any range in b.
The result should be returned as a list of disjoint ranges, also in the [start, end) format, preferably sorted by their start value.
Example 1:
Input:
a = [[2.5, 7.5]]
b = [[4.3, 9.3]]
Output: [[2.5, 4.3]]
Example 2:
Input:
a = [[2.5, 7.5], [9.0, 10.4]]
b = [[4.3, 9.3], [9.5, 11.0]]
Output: [[2.5, 4.3], [9.3, 9.5]]

Problem 2: Nth License Plate Generator
An office issues license plates following a specific sequence composed of six distinct patterns concatenated together:
Range 1: 5 digits (00000 to 99999)
Range 2: 1 letter followed by 4 digits (A0000 to Z9999)
Range 3: 2 letters followed by 3 digits (AA000 to ZZ999)
Range 4: 3 letters followed by 2 digits (AAA00 to ZZZ99)
Range 5: 4 letters followed by 1 digit (AAAA0 to ZZZZ9)
Range 6: 5 letters (AAAAA to ZZZZZ)
The sequence starts with 00000, then 00001, ..., up to 99999, immediately followed by A0000, A0001, ..., Z9999, then AA000, and so on, until ZZZZZ. Note that this is not a simple base-36 conversion; the number of letters and digits is fixed within each range (e.g., 12CD5 is invalid).

Write a function getNthLicensePlate(n) that takes a 0-indexed integer n and returns the nth license plate in this sequence as a string.

Example 1:
Input: n = 0
Output: "00000"

Example 2:
Input: n = 1
Output: "00001"

Example 3:
Input: n = 99999
Output: "99999" (Last plate of Range 1)

Example 4:
Input: n = 100000
Output: "A0000" (First plate of Range 2)

Round-2: Expected Result: Lean Hire

Problem: Find Undirected Cycle in Directed Graph 
You are given a directed graph represented by its number of nodes n (labeled from 0 to n-1) and an adjacency list adj.
Your task is to determine if there is a cycle in the graph when considering its edges as undirected. That is, for every directed edge u -> v present in the input, you should treat it as an undirected edge u -- v for the purpose of cycle detection.
If such an undirected cycle exists, return a list of integers representing the nodes in one such cycle. The path should start and end with the same node, and list the nodes in the order they are visited in the cycle. The specific starting node or the direction of traversal (clockwise/counter-clockwise) does not matter, any valid cycle is acceptable.
If no such undirected cycle exists in the graph, return an empty list.
Example 1:
Input: n = 4, adj = [[1], [2], [0], []] (Edges: 0->1, 1->2, 2->0)
Output: [0, 1, 2, 0] (or [1, 2, 0, 1], etc.)
Explanation: Treating edges as undirected (0--1, 1--2, 2--0), the cycle 0-1-2-0 exists.
Example 2:
Input: n = 4, adj = [[1], [2], [3], []] (Edges: 0->1, 1->2, 2->3)
Output: []
Explanation: Treating edges as undirected (0--1, 1--2, 2--3), the graph forms a line (path), which is acyclic.
Example 3:
Input: n = 5, adj = [[1, 2], [3], [], [4], [1]] (Edges: 0->1, 0->2, 1->3, 3->4, 4->1)
Output: [1, 3, 4, 1]
Explanation: Treating edges as undirected (0--1, 0--2, 1--3, 3->4, 4->1), the cycle 1-3-4-1 exists. Note that node 2 is connected but not part of this cycle.
Example 4:
Input: n = 3, adj = [[], [0], [1]] (Edges: 1->0, 2->1)
Output: []
Explanation: Undirected edges are 1--0 and 2--1. This forms the path 0--1--2, which has no cycles.

Round-3: Expected Result: Strong Hire

Title: Simplify Algebraic Expression With Parentheses
You are given a string formula representing a mathematical expression. The expression consists of:
Lowercase English letters ('a' through 'z') representing variables.
Addition ('+') and subtraction ('-') operators.
Parentheses ('(' and ')').
Each variable implicitly has a coefficient of 1. Your task is to simplify the given formula by removing all parentheses and combining like terms, producing an equivalent expression.
The resulting expression should follow these rules:
Terms should be ordered alphabetically by variable name.
Each variable should appear at most once.
Coefficients of 1 should be omitted (e.g., a instead of 1a).
Coefficients of -1 should be represented only by the minus sign (e.g., -b instead of -1b).
Terms should be joined by + or - signs as appropriate. Do not include a leading + sign.
If the simplified expression evaluates to zero (all terms cancel out), return "0".
Input:
formula: A string representing the algebraic expression.
Output:
A string representing the simplified algebraic expression according to the rules above.
Example 1:
Input: formula = "a-(b+c)"
Output: "a-b-c"
Explanation: The parentheses are removed, distributing the minus sign: a - b - c. Terms are already sorted.
Example 2:
Input: formula = "a-(a-b)"
Output: "b"
Explanation: a - a + b. The a terms cancel out, leaving b.
Example 3:
Input: formula = "(a+b)-(c-d)"
Output: "a+b-c+d"
Explanation: a + b - c + d.
Example 4:
Input: formula = "a-(b-(c+a))"
Output: "2a-b+c"
Explanation: a - (b - c - a) -> a - b + c + a. Combining like terms gives 2a - b + c. Sorting gives the same result. (Self-correction: Original examples didn't explicitly show coefficients other than 1/-1. Added this example to clarify combining terms like a+a -> 2a). Let's refine the rules slightly based on this - coefficients are needed if > 1 or < -1. The original prompt implied only +/- 1 coefficients. Assuming the user meant full simplification including combining terms:

Round-4: Expected Result: Strong Hire

Basic behavioural questions. 
Nothing complex, just be honest and make sure your communication is good and on point.

Result is not out yet.

Interviewers are very helpful and push your limits. Probably I wont make it to google this time but this is very good interview experience for me and next i will prepare strategically from this experience and will try again. Keep grinding.