This set evaluates skills in string parsing and nested-structure decoding, optimization and stateful decision-making in one-dimensional arrays, and grid-based graph traversal for counting connected components.
You are given three independent coding questions.
Given an encoded string s, decode it using the following rule:
k[encoded_string]
mean that
encoded_string
is repeated exactly
k
times.
k
is a positive integer and may have multiple digits.
Example: s = "3[a2[c]]" should decode to "accaccacc".
Task: Return the decoded string.
Assumptions/constraints (you may state any reasonable ones in your solution):
s
contains only digits, letters, and brackets
[
]
.
Given a 1D array arr of integers and starting at index 0, you can make a decision at each index i:
arr[i]
, then jump to index
i + 1 + arr[i]
.
0
, then move to index
i + 1
.
You may stop when your index is out of bounds (i.e., i >= n).
Task: Compute the maximum total profit achievable.
How does your approach change if arr can contain negative numbers?
i
, you still gain
arr[i]
, and you still move to index
i + 1 + arr[i]
(which could move backward if
arr[i] < 0
).
Given an m x n grid of characters '1' and '0':
'1'
represents land
'0'
represents water
Two land cells are connected if they are adjacent horizontally or vertically (4-directional adjacency).
Task: Return the number of connected components of land (i.e., the number of “islands”).
Example:
1 1 0
0 1 0
1 0 1
Answer: 3.