Goldman Sachs

I was initially asked about my projects for very few minutes and then the interviewer went on to ask DSA. I was asked a problem equivalent to LeetCode 871 — Minimum Number of Refueling Stops. You are given a target distance, an initial amount of fuel, and several gas stations represented as [position, fuel]. The car consumes 1 unit of fuel per mile and can take all the fuel from a station when it stops there. The task is to find the minimum number of refueling stops required to reach the target. I initially approached it with a brute-force recursive solution, considering whether to stop at each station, giving roughly O(2^n) complexity. I then optimized the approach using 2D dynamic programming, which reduced the complexity significantly. The interviewer seemed okay with the DP approach, but I got the impression that they were expecting me to identify the optimal greedy + max-heap solution, where I keep track of the fuel available from all stations already passed and refuel from the station with the maximum fuel whenever necessary.