Can you visit all rooms and score parentheses?
Problem 1: Visit All Locked Rooms with Keys
There are n rooms, labeled 0 to n-1. All rooms are initially locked except for room 0.
When you enter a room i, you will find a set of keys, represented by rooms[i]. Each key k is an integer that unlocks room k. You are allowed to collect and carry all keys you find.
Task: Given rooms: List[List[int]], where rooms[i] is the list of keys found in room i, determine if you can eventually visit every room, starting from room 0. Return true if all rooms can be visited, otherwise return false.
Constraints (Typical):
1 <= n <= 10^40 <= rooms[i].length <= 10^4- Keys are integers in the range
0ton-1(duplicate keys may exist).
Problem 2: Compute the Score of a Balanced Parentheses String
You are given a balanced parentheses string s consisting only of '(' and ')' characters.
Define the score of a balanced parentheses string recursively as follows:
- The string
"()"has a score of1. - If
AandBare balanced parentheses strings, thenscore(A + B) = score(A) + score(B). - If
Ais a balanced parentheses string, thenscore("(" + A + ")") = 2 * score(A).
Task: Return the score(s) for the given balanced parentheses string s.
Constraints (Typical):
1 <= s.length <= 10^5- The string
sis guaranteed to be balanced.
AI interview prep
Core dilemma
Effectively applying graph traversal and string parsing algorithms while managing state, recursion depth, and optimizing for time/space complexity across distinct problem types.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Can you visit all rooms and score parentheses?
Problem 1: Visit All Locked Rooms with Keys
There are n rooms, labeled 0 to n-1. All rooms are initially locked except for room 0.
When you enter a room i, you will find a set of keys, represented by rooms[i]. Each key k is an integer that unlocks room k. You are allowed to collect and carry all keys you find.
Task: Given rooms: List[List[int]], where rooms[i] is the list of keys found in room i, determine if you can eventually visit every room, starting from room 0. Return true if all rooms can be visited, otherwise return false.
Constraints (Typical):
1 <= n <= 10^40 <= rooms[i].length <= 10^4- Keys are integers in the range
0ton-1(duplicate keys may exist).
Problem 2: Compute the Score of a Balanced Parentheses String
You are given a balanced parentheses string s consisting only of '(' and ')' characters.
Define the score of a balanced parentheses string recursively as follows:
- The string
"()"has a score of1. - If
AandBare balanced parentheses strings, thenscore(A + B) = score(A) + score(B). - If
Ais a balanced parentheses string, thenscore("(" + A + ")") = 2 * score(A).
Task: Return the score(s) for the given balanced parentheses string s.
Constraints (Typical):
1 <= s.length <= 10^5- The string
sis guaranteed to be balanced.