Katkat
Back

Can you visit all rooms and score parentheses?

MolocoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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