Goldman Sachs Round 2 Coding Interview

I recently interviewed for the Analyst (SDE) role at Goldman Sachs, Bangalore, sharing question that was asked ininterview are

• Gas Station

• Minimum Window Substring

Problem 1: Gas Station

You are given two integer arrays:

• gas[i]: the amount of gas available at station i.

• cost[i]: the amount of gas required to travel from station i to (i+1).

You start at any gas station with an empty tank. Your task is to determine:

If there exists a starting gas station index from which you can travel around the circuit once and return to the same station.

If no such starting station exists, return -1.

Example

Input:

gas = [1,2,3,4,5]  
cost = [3,4,5,1,2]

Output:

3

Explanation:

Start at station 3 (0-based index). The gas collected and spent balances out, allowing a full circuit.

Intuition & Explanation

• First, check the total gas vs. total cost.

• If sum(gas) < sum(cost), it’s impossible to travel around.

• Otherwise, we can always find a starting station.

Use a greedy approach:

• Traverse stations and maintain a running balance (tank).

• If at any point tank < 0, reset the start position to the next station because the previous segment can not be a valid start.

public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        int tank = 0, startIndex = 0;

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];
            // If tank becomes negative, reset start index
            if (tank < 0) {
                startIndex = i + 1;
                tank = 0;
            }
        }

        return totalGas >= totalCost ? startIndex : -1;
    }
}

Time Complexity Analysis

• Time Complexity: O(n) → Single pass through arrays.

• Space Complexity: O(1) → Constant extra space.

Case Analysis:

• Best Case: The first station is valid → still O(n) because we must check all.

• Worst Case: Need to traverse full array → O(n).

• Impossible Case: When total gas < total cost → detected in a single pass.

Problem 2: Minimum Window Substring

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return "".

Example

Input:

s = "ADOBECODEBANC"  
t = "ABC"

Output:

"BANC"

Explanation:

The substring "BANC" is the smallest window in s containing all characters of t.

Intuition & Explanation

• This is a classic sliding window + hashmap problem.

• Count frequencies of characters in t.

• Expand the right pointer (r) until the window contains all characters of t.

• Once valid, shrink from the left (l) to minimize the window.

• Keep track of the smallest valid window.

import java.util.*;

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int required = tMap.size(), formed = 0;
        int minLen = Integer.MAX_VALUE, start = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (tMap.containsKey(c) && window.get(c).intValue() == tMap.get(c).intValue()) {
                formed++;
            }

            // Try to shrink window
            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                if (tMap.containsKey(leftChar) && window.get(leftChar) < tMap.get(leftChar)) {
                    formed--;
                }
                left++;
            }
            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

Time Complexity Analysis

• Time Complexity: O(|s| + |t|)

Each character processed at most twice (once by right pointer, once by left pointer).

• Space Complexity: O(|t|) for hashmap storage.

Case Analysis:

• Best Case: t is very small compared to s. Still O(|s|).

• Worst Case: t has all unique characters → full traversal needed.

• Edge Case: If s.length() < t.length(), return "" immediately.

Final Thoughts

• Both Gas Station and Minimum Window Substring are popular DSA interview problems that test your ability to apply greedy strategies and sliding window techniques effectively.

• Gas Station: Focuses on greedy choice and cumulative balance.

• Minimum Window Substring: Tests your mastery of sliding window and hashmap optimization.

Mastering these will not only help in interviews but also strengthen your problem-solving and optimization skills.