How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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

Q: Solve Stack Decoding and Fuel-Constrained Paths

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.

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:

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.

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

Return the minimum number of steps needed to reach T. If it is impossible, return -1.

Example:

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.

Solve Stack Decoding and Fuel-Constrained Paths

Quick Overview

Task 1: Decode a Repeated-Pattern String

Task 2: Find the Shortest Grid Path With Refueling Stations

Comments (0)

Solve Stack Decoding and Fuel-Constrained Paths

Quick Overview

Task 1: Decode a Repeated-Pattern String

Task 2: Find the Shortest Grid Path With Refueling Stations

Comments (0)