Articles

Blogs

MCQ

SQL

Q&A

Tools

Tags

Jobs

News

Community

LogIn

Email

Password

Show Password

Forget Password

I don't have account.Sign Up!

Login

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

Adℹ

✕

Goldman Sachs Round 2 Coding Interview

Ajeet Pawar

Last Updated : 30 August 2026

59 Views

#interview

#dsa

#sde-1

#interview-experience

#goldman-sachs

Adℹ

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.

Trending Developer Reads

Spinny SDE-1 Interview Experience (Selected)

Uber SDE-2 Interview Experience : LLD, HLD, DSA & Hiring Manager Round

Top 50 SQL Interview Questions and Answers (Beginner to Intermediate)

DSA Patterns for Coding Interviews: Complete LeetCode Roadmap (Beginner to Advanced)

Rippling SDE-2 Interview Experience (4+ Years Experience) | Offer Received | Coding, LLD & System Design

Visa Software Engineer 1 (SDE-1) Interview Experience | CodeSignal OA + Graph-Based Technical Rounds

Meesho SDE-1 Online Assessment Interview Experience (Remote) - Rejected

Amazon SDE II Interview Experience (Bangalore, Selected) ~ Aug 2026

Google L4 Software Engineer III interview experience | Selected

Uber SDE 2 Interview Experience (5 Rounds, Selected) - Complete DSA Questions with solution, System Design & Managerial Round

Responses (0)

Write a response

Hide Comments

No Comments yet.

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -34%

iQOO Amazon's Choice

iQOO Z10 Lite 5G — Cyber Green, 4GB RAM, 128GB Storage

Dimensity 6300 · 50MP Sony AI Camera · 6000 mAh · IP64

★★★★★★★★★★ 4.0 (2,052) 500+ bought last month

₹18,997 M.R.P. ₹28,999Save ₹10,002

Buy Now →

\n \n \n \n \n

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

\n
• \n

  Gas Station

  \n
\n
• \n

  Minimum Window Substring

  \n
\n

Problem 1: Gas Station

You are given two integer arrays:

\n
• \n

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

  \n
\n
• \n

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

  \n
\n

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\ncircuit once and return to the same station.

If no such starting station exists, return -1.

Example

Input:

gas = [1,2,3,4,5]  \ncost = [3,4,5,1,2]\n

Output:

3\n

Explanation:

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

Intuition & Explanation

\n
• \n

  First, check the total gas vs. total cost.

  \n
\n
• \n

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

  \n
\n
• \n

  Otherwise, we can always find a starting station.

  \n
\n

Use a greedy approach:

\n
• \n

  Traverse stations and maintain a running balance (tank).

  \n
\n
• \n

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

  \n
\n

public class GasStation {\n    public int canCompleteCircuit(int[] gas, int[] cost) {\n        int totalGas = 0, totalCost = 0;\n        int tank = 0, startIndex = 0;\n\n        for (int i = 0; i < gas.length; i++) {\n            totalGas += gas[i];\n            totalCost += cost[i];\n            tank += gas[i] - cost[i];\n            // If tank becomes negative, reset start index\n            if (tank < 0) {\n                startIndex = i + 1;\n                tank = 0;\n            }\n        }\n\n        return totalGas >= totalCost ? startIndex : -1;\n    }\n}\n

Time Complexity Analysis

\n
• \n

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

  \n
\n
• \n

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

  \n
\n

Case Analysis:

\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

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

  \n
\n

Problem 2: Minimum Window Substring

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

Example

Input:

s = \"ADOBECODEBANC\"  \nt = \"ABC\"\n

Output:

\"BANC\"\n

Explanation:

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

Intuition & Explanation

\n
• \n

  This is a classic sliding window + hashmap problem.

  \n
\n
• \n

  Count frequencies of characters in t.

  \n
\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

  Keep track of the smallest valid window.

  \n
\n

import java.util.*;\n\npublic class MinimumWindowSubstring {\n    public String minWindow(String s, String t) {\n        if (s.length() < t.length()) return \"\";\n        Map<Character, Integer> tMap = new HashMap<>();\n        for (char c : t.toCharArray()) {\n            tMap.put(c, tMap.getOrDefault(c, 0) + 1);\n        }\n        Map<Character, Integer> window = new HashMap<>();\n        int left = 0, right = 0;\n        int required = tMap.size(), formed = 0;\n        int minLen = Integer.MAX_VALUE, start = 0;\n\n        while (right < s.length()) {\n            char c = s.charAt(right);\n            window.put(c, window.getOrDefault(c, 0) + 1);\n\n            if (tMap.containsKey(c) && window.get(c).intValue() == tMap.get(c).intValue()) {\n                formed++;\n            }\n\n            // Try to shrink window\n            while (left <= right && formed == required) {\n                if (right - left + 1 < minLen) {\n                    minLen = right - left + 1;\n                    start = left;\n                }\n\n                char leftChar = s.charAt(left);\n                window.put(leftChar, window.get(leftChar) - 1);\n                if (tMap.containsKey(leftChar) && window.get(leftChar) < tMap.get(leftChar)) {\n                    formed--;\n                }\n                left++;\n            }\n            right++;\n        }\n\n        return minLen == Integer.MAX_VALUE ? \"\" : s.substring(start, start + minLen);\n    }\n}\n

Time Complexity Analysis

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

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

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

Case Analysis:

\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

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

  \n
\n

Final Thoughts

\n
• \n

  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.

  \n
\n
• \n

  Gas Station: Focuses on greedy choice and cumulative balance.

  \n
\n
• \n

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

  \n
\n

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