Interview Experience

Experience: 1.5 years Position: L3 Date: October - November 2024

Phone Screen Grid question with some constraints.

Onsite 1: DSA

You are given a number (very long) and an integer K. Find the largest K-digit number that can be formed from the original number (preserve the order).

Example: S = "3582", K=2
Output: "82"

Follow up 1: Solve in O(n) time
Follow up 2: Solve in O(n) time and O(k) space

Approach: Solved using a monotonic stack.

Onsite 2: DSA

Get all sequences that sum to a particular number if digits 1 & 2 can be used.

Example: Sum=4
Result: ["1111", "112", "121", "211", "22"]

Follow up 1: What if we are allowed to use first K digits (1,2,3,...,K)?

Approach: recursion /backtracking solution.

Note: For the original question, the time complexity is not O(2^N), but as it is a Fibonacci sequence, the complexity is (golden ratio)^n i.e., 1.618^n. I spent a couple of minutes discussing the time complexity; I couldn't come up with 1.618^n but was able to point out the tree pruning.

Follow up 2: What if we have to only count the number of sequences for the original question?

Follow up 3: Count the number of sequences when K digits are allowed

Simple O(n) dp. For the 3rd follow up, use prefix sum for better time and space complexity.

Onsite 3: DSA

Given an expression with some variables, operands (+ and -) and parenthesis, return the simplified expression.

Example: a-(a-b)-c
Output: b-c

Count the variables with a map.

Follow up:
What if nested parentheses are allowed?

Example: a-(b-(c-a)) + c
Output: -b+2c

Along with a map, we need a stack to store the latest sign. For this round, the focus was more on clean code and covering the edge cases.

Onsite 4: Googliness Behavioral questions

Had 2 team matches, both successful.

Offer was released in December.