Can you visit all rooms and score parentheses?
Company: Molocoads
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem 1: Visit all locked rooms with keys
There are **n** rooms labeled **0..n-1**. All rooms are locked except room **0**.
- When you enter room **i**, you find a set of keys `rooms[i]`.
- Each key is an integer `k` that unlocks room `k`.
- You may collect and carry all keys you find.
**Task:** Given `rooms: List[List[int]]`, return `true` if you can eventually visit **every** room starting from room `0`, otherwise return `false`.
**Input/Output**
- Input: `rooms`, where `rooms[i]` is the list of keys in room `i`
- Output: boolean
**Constraints (typical):**
- `1 <= n <= 10^4`
- `0 <= rooms[i].length <= 10^4`
- Keys are in range `0..n-1` (may include duplicates)
---
## Problem 2: Compute the score of a balanced parentheses string
You are given a **balanced** parentheses string `s` consisting only of `'('` and `')'`.
Define the score recursively:
1. `"()"` has score `1`
2. Concatenation: if `A` and `B` are balanced, then `score(A + B) = score(A) + score(B)`
3. Nesting: if `A` is balanced, then `score("(" + A + ")") = 2 * score(A)`
**Task:** Return `score(s)`.
**Input/Output**
- Input: balanced string `s`
- Output: integer score
**Constraints (typical):**
- `1 <= s.length <= 10^5`
- `s` is guaranteed balanced
Quick Answer: The first problem evaluates graph traversal and reachability by modeling rooms and keys as an implicit graph, and it is commonly asked to assess reasoning about connectivity and exploration in graph-theoretic settings; this falls under the algorithms/graph theory domain and emphasizes practical application of traversal techniques.
Visit All Rooms with Keys
Return whether all rooms can be visited starting from room 0.
Examples
Input: ([[1], [2], [3], []],)
Expected Output: True
Explanation: All reachable.
Input: ([[1, 3], [3, 0, 1], [2], [0]],)
Expected Output: False
Explanation: Room 2 locked forever.
Input: ([[0]],)
Expected Output: True
Explanation: Single room.
Score of Balanced Parentheses
Return the recursive score of a balanced parentheses string.
Examples
Input: ('()',)
Expected Output: 1
Explanation: Base pair.
Input: ('(())',)
Expected Output: 2
Explanation: Nested pair.
Input: ('()()',)
Expected Output: 2
Explanation: Concatenation.
Input: ('(()(()))',)
Expected Output: 6
Explanation: Mixed nesting.