Katkat
Back

Solve three coding tasks from onsite

BloombergSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle three distinct algorithmic scenarios: greedy logic for circular traversal, stack-based syntax validation, and state-space exploration on a 2D grid.

Task 1: Circular Fuel Circuit

You are given two arrays, gas and cost, each of size n, where gas[i] is the amount of fuel at station i, and cost[i] is the fuel required to travel to station (i + 1) % n. Find the starting index such that you can complete a full circuit in a clockwise direction. If no such index exists, return -1. Assume a solution is unique.

def can_complete_circuit(gas: List[int], cost: List[int]) -> int:

Task 2: Valid Parentheses Sequence

Given a string containing only '(', ')', '{', '}', '[', and ']', determine if the input string is valid. A string is valid if every opening bracket is closed by the same type of bracket in the correct order.

def is_valid(s: str) -> bool:

Task 3: Grid Reachability with Battery

You are in a grid of size m x n. You start at (0, 0) with an initial battery level k. Moving to an adjacent cell costs 1 unit of battery. Some cells contain battery chargers that add c units. Find if you can reach (m-1, n-1) without your battery level ever dropping below 0.

def can_reach_destination(grid: List[List[int]], k: int) -> bool:

Examples

Task 1: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. Starting at index 3 allows you to complete the loop because you gain more than you spend at every step. Task 2: s = "()[]{}" returns True. s = "([)]" returns False.

Hints

Hint 1

For the fuel circuit, if the total gas is less than total cost, it is impossible; otherwise, track your current tank balance and reset the starting point whenever it drops below zero.

Hint 2

For the parentheses, use a stack to store opening brackets and compare the top of the stack with the current closing bracket encountered in the string.

Hint 3

For the grid, treat this as a shortest-path problem where each state is defined by the coordinate `(row, col)` and the current `battery_level`, potentially using Dijkstra's algorithm if battery can be regained.

Follow-up questions

  • How would you optimize Task 1 if you needed to find all possible starting indices instead of just one?
  • How would you modify the parentheses validator to handle strings that might contain alphanumeric characters that should be ignored?
  • In Task 3, what if the grid had obstacles that were impassable? How would your state-space complexity change?