Solve string grouping and tree right-view problems
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Problem 1: Group words that are anagrams
You are given an array of strings `words`.
Two strings are **anagrams** if they contain the same characters with the same frequencies (order can differ).
**Task:** Group the strings into lists where each list contains all strings that are anagrams of each other.
- **Input:** `words: string[]`
- **Output:** `string[][]` (order of groups and order within each group can be arbitrary)
- **Constraints (typical):** `1 <= words.length <= 10^4`, each word length `<= 100`, lowercase English letters.
**Example**
- Input: `["eat","tea","tan","ate","nat","bat"]`
- Output: `[["eat","tea","ate"],["tan","nat"],["bat"]]`
---
## Problem 2: Right-side view of a binary tree
You are given the root of a binary tree. Imagine looking at the tree from the **right side**; return the values of the nodes you can see, ordered from top to bottom.
**Task:** Return an array of the rightmost node’s value at each depth.
- **Input:** `root` (binary tree node)
- **Output:** `int[]`
**Example**
For the tree:
- `1` has left child `2` and right child `3`
- `2` has right child `5`
- `3` has right child `4`
Right-side view is: `[1, 3, 4]`
**Note (interview setting):** You may need to define the tree node structure, build a tree from test data, and write basic test cases yourself.
Quick Answer: This combined prompt evaluates string-processing and grouping concepts for anagram detection alongside binary tree traversal and visibility reasoning for the right-side view, assessing algorithmic thinking, data structure usage, and complexity reasoning.
Part 1: Group Words That Are Anagrams
Given a list of lowercase strings `words`, group the words so that each group contains words that are anagrams of one another. Two words are anagrams if they contain exactly the same letters with the same frequencies, possibly in a different order.
For consistent testing, return the result in a deterministic order:
1. Sort each individual group in lexicographic order.
2. Sort the list of groups by the first word in each group.
If the input list is empty, return an empty list.
Constraints
- 0 <= len(words) <= 10^4
- 0 <= len(words[i]) <= 100
- Each word contains only lowercase English letters.
Examples
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Expected Output: [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
Explanation: The words are grouped by anagram class, then each group and the final list are sorted for deterministic output.
Input: []
Expected Output: []
Explanation: Edge case: no words means no groups.
Hints
- Words that are anagrams share the same canonical form. What simple transformation makes all anagrams look identical?
- A hash map can collect all words that belong to the same signature.
Part 2: Right-Side View of a Binary Tree
You are given a binary tree and must return the values visible when looking at the tree from the right side, from top to bottom.
For this problem, the tree is provided as a level-order list representation where `None` means a missing child. For example, `[1, 2, 3, None, 5, None, 4]` represents a tree whose right-side view is `[1, 3, 4]`.
Return the value of the rightmost node at each depth.
Constraints
- 0 <= number of actual nodes <= 10^4
- -10^9 <= node value <= 10^9
- The input list uses level-order serialization with `None` for missing children.
Examples
Input: [1, 2, 3, None, 5, None, 4]
Expected Output: [1, 3, 4]
Explanation: At each depth, the visible node from the right is 1, then 3, then 4.
Input: []
Expected Output: []
Explanation: Edge case: an empty tree has no visible nodes.
Hints
- A breadth-first search processes the tree one level at a time. Which node at each level should be recorded?
- You can also solve this with depth-first search by visiting the right child before the left child.