Remove adjacent duplicates and handle tree input
You will be presented with three related coding questions.
1. Remove Adjacent Duplicates (Repeatedly)
Given a string s consisting of lowercase English letters, repeatedly remove any pair of adjacent equal characters until no such pair exists.
- Input:
s - Output: The final string after all removals.
Example:
s = "abbaca" → remove bb → aaca → remove aa → ca
Constraints: 1 <= |s| <= 1e5.
2. Follow-up: Remove Groups of Size K
Given a string s and an integer k, repeatedly remove any group of exactly k adjacent equal characters until no more removals are possible.
- Input:
s,k - Output: The final string.
Example:
s = "deeedbbcccbdaa", k = 3 → output "aa"
Constraints: 1 <= |s| <= 1e5, 2 <= k <= 1e4.
3. Tree Problem: Sum of Left Leaf Nodes (from Level-Order Array)
You are given a binary tree in level-order array form, where null indicates a missing child. Your task is to first build the binary tree from this array representation and then compute the sum of all left leaf nodes. A left leaf node is defined as a leaf node that is the left child of its parent.
- Input: An array
arrof integers andnulls, representing the tree in level-order. - Output: An integer representing the sum.
Example:
arr = [3,9,20,null,null,15,7] → left leaves are 9 and 15 → output 24
Note: You must explicitly construct the tree from the array representation before computing the answer.
AI interview prep
Core dilemma
Optimizing repeated modifications on sequences and complex data structure construction/traversal for efficiency, especially when intermediate changes can trigger further operations, all within strict time and space complexity constraints.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Remove adjacent duplicates and handle tree input
You will be presented with three related coding questions.
1. Remove Adjacent Duplicates (Repeatedly)
Given a string s consisting of lowercase English letters, repeatedly remove any pair of adjacent equal characters until no such pair exists.
- Input:
s - Output: The final string after all removals.
Example:
s = "abbaca" → remove bb → aaca → remove aa → ca
Constraints: 1 <= |s| <= 1e5.
2. Follow-up: Remove Groups of Size K
Given a string s and an integer k, repeatedly remove any group of exactly k adjacent equal characters until no more removals are possible.
- Input:
s,k - Output: The final string.
Example:
s = "deeedbbcccbdaa", k = 3 → output "aa"
Constraints: 1 <= |s| <= 1e5, 2 <= k <= 1e4.
3. Tree Problem: Sum of Left Leaf Nodes (from Level-Order Array)
You are given a binary tree in level-order array form, where null indicates a missing child. Your task is to first build the binary tree from this array representation and then compute the sum of all left leaf nodes. A left leaf node is defined as a leaf node that is the left child of its parent.
- Input: An array
arrof integers andnulls, representing the tree in level-order. - Output: An integer representing the sum.
Example:
arr = [3,9,20,null,null,15,7] → left leaves are 9 and 15 → output 24
Note: You must explicitly construct the tree from the array representation before computing the answer.