Solve three coding tasks from onsite
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given three separate coding tasks (solve each independently). Provide an algorithm and implement it.
## 1) Circular route with gas and cost
You are given two integer arrays `gas[0..n-1]` and `cost[0..n-1]` describing a circular route of `n` stations.
- At station `i`, you can add `gas[i]` units of fuel.
- Traveling from station `i` to station `(i+1) mod n` consumes `cost[i]` units of fuel.
- You start with an empty tank.
**Task:** Return an index `s` such that starting at station `s` allows you to complete one full loop and return to `s` without the fuel ever going negative. If it is impossible, return `-1`. If multiple answers exist, returning any one is acceptable.
**Constraints (typical):** `1 <= n <= 2e5`, `0 <= gas[i], cost[i] <= 1e9`.
---
## 2) Validate bracket sequence using a stack
Given a string `s` consisting only of the characters `'('`, `')'`, `'{'`, `'}'`, `'['`, `']'`.
**Task:** Determine whether `s` is a valid bracket sequence:
- Every opening bracket must be closed by the same type of bracket.
- Closing brackets must occur in the correct order.
- Empty string is valid.
Return `true` if valid, otherwise `false`.
**Constraints (typical):** `0 <= |s| <= 2e5`.
---
## 3) Grid reachability with fuel and refueling cells
You are given:
- An integer `G` = initial fuel in the tank.
- A 2D grid of size `R x C` with cells of the following types:
- `S`: start cell
- `T`: target cell
- `.`: free cell (no fuel gained)
- `#`: obstacle (cannot enter)
- digit `'0'`–`'9'`: a refuel cell; when you enter this cell, your fuel increases by that digit value (fuel gain happens upon entering).
Movement rules:
- From a cell, you may move up/down/left/right to an in-bounds non-obstacle cell.
- Each move costs **1** unit of fuel.
- You may not move if you have 0 fuel.
- Refuel can enable revisiting cells (i.e., cycles are possible).
**Task:** Return whether it is possible to reach `T` from `S`.
**Clarifications to make explicit in your solution:**
- If you revisit a digit cell, specify whether fuel can be collected again or only once (state your assumption and handle accordingly). A common interview assumption is **fuel is gained every time you enter** the cell.
**Constraints (typical):** `1 <= R,C <= 200`, `0 <= G <= 1e5`.
Quick Answer: This set of tasks evaluates array-based greedy reasoning for circular route feasibility, stack-based parsing for bracket matching, and grid/graph reachability under resource constraints, testing algorithmic problem solving, state management, and implementation accuracy.
Part 1: Circular Route with Gas and Cost
You are given two integer arrays gas and cost of the same length n, representing a circular route of gas stations. At station i, you gain gas[i] fuel, and traveling from station i to station (i + 1) mod n consumes cost[i] fuel. You start with an empty tank. Return an index s such that starting at station s lets you complete one full loop without the fuel ever becoming negative. If no such start exists, return -1. If multiple valid answers exist, returning any one is acceptable.
Constraints
- 1 <= n <= 2 * 10^5
- 0 <= gas[i], cost[i] <= 10^9
- gas and cost have the same length
Examples
Input: ([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
Expected Output: 3
Explanation: Starting from index 3 gives enough fuel to complete the full circle.
Input: ([2, 3, 4], [3, 4, 3])
Expected Output: -1
Explanation: Total gas is less than total cost, so no valid start exists.
Input: ([5], [4])
Expected Output: 0
Explanation: Single-station edge case: you can leave and return successfully.
Input: ([0], [1])
Expected Output: -1
Explanation: Single-station edge case: there is not enough fuel to travel.
Hints
- First check a necessary condition: the total amount of gas over all stations must be at least the total cost.
- If starting from station a fails before reaching station b, then no station between a and b can be a valid start.
Part 2: Validate Bracket Sequence
Given a string s containing only the characters (), {}, and [], determine whether it is a valid bracket sequence. A sequence is valid if every opening bracket is closed by the same type of bracket and closing brackets appear in the correct order. The empty string is valid.
Constraints
- 0 <= len(s) <= 2 * 10^5
- s contains only '(', ')', '{', '}', '[' and ']'
Examples
Input: ("()[]{}",)
Expected Output: True
Explanation: All bracket pairs are correctly matched and ordered.
Input: ("([)]",)
Expected Output: False
Explanation: The types are crossed: '(' is closed after '[' has opened.
Input: ("{[]}",)
Expected Output: True
Explanation: Nested brackets are matched in the correct order.
Input: ("",)
Expected Output: True
Explanation: The empty string is valid.
Input: ("(",)
Expected Output: False
Explanation: A single opening bracket is unmatched.
Hints
- Use a stack to store opening brackets that have not been matched yet.
- When you see a closing bracket, it must match the most recent unmatched opening bracket.
Part 3: Grid Reachability with Fuel and Refueling Cells
You are given an initial amount of fuel G and a grid represented as a list of strings. Each cell is one of: S (start), T (target), . (empty), # (obstacle), or a digit 0-9 (a refuel cell). You may move up, down, left, or right to an in-bounds non-obstacle cell. Each move costs 1 fuel, and you may not move if your fuel is 0. If you enter a digit cell, your fuel increases by that digit value immediately. Assume this fuel is gained every time you enter that cell, even on revisits. Return whether it is possible to reach T from S.
Constraints
- 1 <= R, C <= 200
- 0 <= G <= 10^5
- grid contains exactly one S and one T
- Fuel from a digit cell is collected every time you enter that cell
Examples
Input: (1, ['S2T'])
Expected Output: True
Explanation: Move from S to 2, gain fuel, then move to T.
Input: (1, ['S.T'])
Expected Output: False
Explanation: You can make only one move, but T is two steps away and there is no refuel.
Input: (1, ['S30..T'])
Expected Output: True
Explanation: Because entering digit cells gives fuel every time, you can revisit 3 and 0 to build enough fuel before heading to T.
Input: (10, ['S#T'])
Expected Output: False
Explanation: The obstacle blocks the only path.
Input: (0, ['ST'])
Expected Output: False
Explanation: You need one move to reach T, but you start with zero fuel.
Hints
- The state depends on both position and remaining fuel; reaching the same cell with more fuel is always better.
- You never need to keep fuel larger than the number of passable cells, because that is already enough to follow a simple path to any reachable cell in the component.