How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bloomberg.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bloomberg during technical interviews.

Solve Stack Decoding and Fuel-Constrained Paths

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given two independent coding tasks. ### Task 1: Decode a Repeated-Pattern String Given a valid encoded string, return its fully decoded form. The encoding rule is: `k[substring]` means the substring inside the brackets should be repeated exactly `k` times. Encodings may be nested. Examples: - Input: `3[a]2[bc]` → Output: `aaabcbc` - Input: `3[a2[c]]` → Output: `accaccacc` - Input: `2[abc]3[cd]ef` → Output: `abcabccdcdcdef` Assume: - The input string is valid. - Repeat counts are positive integers. - The decoded output length fits in memory. Implement a function that returns the decoded string. ### Task 2: Find the Shortest Grid Path With Refueling Stations You are given an `m x n` grid. Each cell is one of the following: - `S`: starting position - `T`: target position - `.`: empty cell - `#`: blocked cell that cannot be entered - `G`: gas station You are also given an integer `fuelCapacity`. Moving one step up, down, left, or right costs 1 unit of fuel. You start at `S` with a full tank of `fuelCapacity`. When you enter a gas station cell `G`, your remaining fuel is reset to `fuelCapacity`. You may visit the same cell multiple times if your remaining fuel differs. Return the minimum number of steps needed to reach `T`. If it is impossible, return `-1`. Example: ```text grid = [ "S..#", ".G.#", "...T" ] fuelCapacity = 4 ``` A valid solution should use BFS over states such as `(row, col, remainingFuel)`, because reaching the same cell with more remaining fuel can lead to different future possibilities.

Quick Answer: This prompt evaluates proficiency in parsing and string manipulation for nested repeated-pattern decoding and in graph search and state-space modeling for fuel-constrained shortest paths.

Part 1: Decode a Repeated-Pattern String

Given an encoded string s, decode it using the rule k[substring], where substring is repeated exactly k times. Repeat counts may have multiple digits, and encoded sections may be nested. The input is guaranteed to be valid. Return the fully decoded string. If s is empty, return an empty string.

Constraints

0 <= len(s) <= 100000
s contains lowercase English letters, digits, and the characters '[' and ']'
Repeat counts are positive integers
The encoded string is valid
The decoded output length fits in memory

Examples

Input: '3[a]2[bc]'

Expected Output: 'aaabcbc'

Explanation: 'a' is repeated 3 times and 'bc' is repeated 2 times.

Input: '3[a2[c]]'

Expected Output: 'accaccacc'

Explanation: First decode 'a2[c]' into 'acc', then repeat it 3 times.

Input: '2[abc]3[cd]ef'

Expected Output: 'abcabccdcdcdef'

Explanation: Two repeated sections are expanded, then the trailing 'ef' is appended.

Input: '10[a]'

Expected Output: 'aaaaaaaaaa'

Explanation: This checks that multi-digit repeat counts are handled correctly.

Input: ''

Expected Output: ''

Explanation: Edge case: an empty input should produce an empty output.

Hints

Use one stack for repeat counts and another stack for the string built before each '['.
If the repeat count has multiple digits, keep building the number instead of treating each digit separately.

Part 2: Find the Shortest Grid Path With Refueling Stations

You are given a grid containing exactly one start cell 'S' and one target cell 'T'. Empty cells are '.', blocked cells are '#', and gas stations are 'G'. You start at 'S' with a full tank of fuelCapacity. Moving one step up, down, left, or right costs 1 unit of fuel. When you enter a gas station, your fuel is reset to fuelCapacity. Return the minimum number of steps needed to reach 'T', or -1 if it is impossible. Because arriving at the same cell with different remaining fuel can lead to different future options, the search state must include remaining fuel.

Constraints

1 <= m, n <= 60
1 <= fuelCapacity <= 100
Each grid cell is one of 'S', 'T', '.', '#', or 'G'
There is exactly one 'S' and exactly one 'T'
You may revisit the same cell if the remaining fuel is different

Examples

Input: (['S..#', '.G.#', '...T'], 4)

Expected Output: 5

Explanation: A shortest valid route is S -> right -> down to G -> down -> right -> right to T.

Input: (['ST'], 1)

Expected Output: 1

Explanation: Edge case: the target is adjacent to the start.

Input: (['S.T'], 2)

Expected Output: 2

Explanation: A simple straight path with exactly enough fuel.

Input: (['S..', '...', '..T'], 3)

Expected Output: -1

Explanation: The shortest path needs 4 steps, but there is no gas station and the tank holds only 3.

Input: (['S#T'], 5)

Expected Output: -1

Explanation: The wall blocks the only possible path.

Hints

A normal BFS over only (row, col) is not enough; include remaining fuel in the state.
After spending 1 fuel to move into a neighbor, reset fuel to fuelCapacity if that neighbor is a gas station.

Quick Overview

This prompt evaluates proficiency in parsing and string manipulation for nested repeated-pattern decoding and in graph search and state-space modeling for fuel-constrained shortest paths.