Solve three coding tasks from 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.