Goldman Sachs software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
Question You are given n tasks, each taking a certain number of hours to complete. Tasks may depend on other tasks - a task cannot start until...
id, client, funding_account, amount, and depends_on. depends_on is an empty string or a comma-separated list of payment IDs; all referenced IDs exist in the batch.SINGLE_LIMIT: reject any payment whose amount is strictly greater than $10,000.00.CYCLE: reject every payment belonging to a directed dependency cycle, including a self-dependency. A payment merely downstream of a cycle is not itself a cycle member.DEPENDENCY_REJECTED.id, status (APPROVED or REJECTED), and a lexicographically sorted reasons list. Approved payments have no reasons. The implementation's return type is up to you; the examples show its required JSON representation.release_payments(payments: list[dict[str, str]]) -> candidate_chosen_typeExample 1:{
"payments": [
{"id":"P1","client":"C1","funding_account":"F1","amount":"6000.00","depends_on":""},
{"id":"P2","client":"C1","funding_account":"F1","amount":"10000.01","depends_on":""},
{"id":"P3","client":"C2","funding_account":"F2","amount":"5.00","depends_on":"P2"},
{"id":"P4","client":"C2","funding_account":"F2","amount":"1.00","depends_on":"P5"},
{"id":"P5","client":"C2","funding_account":"F2","amount":"2.00","depends_on":"P4"}
]
}[
{"id":"P1","status":"APPROVED","reasons":[]},
{"id":"P2","status":"REJECTED","reasons":["SINGLE_LIMIT"]},
{"id":"P3","status":"REJECTED","reasons":["DEPENDENCY_REJECTED"]},
{"id":"P4","status":"REJECTED","reasons":["CYCLE"]},
{"id":"P5","status":"REJECTED","reasons":["CYCLE"]}
]release_payments_with_caps(payments: list[dict[str, str]], caps: list[dict[str, str]]) -> candidate_chosen_type. Discuss how the return type changes before implementing this extension.id, field, value, and limit. field is currently client or funding_account; a cap matches when the payment's corresponding field equals value. Cap IDs are unique, but multiple caps may match the same field/value pair. Limits are nonnegative USD amounts with exactly two decimal places.approved_total + payment_amount > limit; equality is allowed. Reject the payment with CAP:<cap_id> for every failing cap, sorted lexicographically. Rejection consumes no budget, including from caps that would have passed.DEPENDENCY_REJECTED. These dependents are not evaluated against caps.decisions in Part 1's representation and cap_totals, a list sorted by cap ID. Each total is {"id": ..., "approved_amount": ...}, with exactly two decimal places; include unused caps with "0.00".{
"payments": [
{"id":"A","client":"C1","funding_account":"F1","amount":"6000.00","depends_on":""},
{"id":"B","client":"C1","funding_account":"F2","amount":"4000.00","depends_on":"A"},
{"id":"C","client":"C2","funding_account":"F1","amount":"3000.00","depends_on":""},
{"id":"D","client":"C2","funding_account":"F1","amount":"4000.00","depends_on":"C"},
{"id":"E","client":"C1","funding_account":"F2","amount":"1.00","depends_on":"B"}
],
"caps": [
{"id":"client-C1","field":"client","value":"C1","limit":"10000.00"},
{"id":"fund-F1","field":"funding_account","value":"F1","limit":"12000.00"}
]
}{
"decisions": [
{"id":"A","status":"APPROVED","reasons":[]},
{"id":"B","status":"APPROVED","reasons":[]},
{"id":"C","status":"APPROVED","reasons":[]},
{"id":"D","status":"REJECTED","reasons":["CAP:fund-F1"]},
{"id":"E","status":"REJECTED","reasons":["CAP:client-C1"]}
],
"cap_totals": [
{"id":"client-C1","approved_amount":"10000.00"},
{"id":"fund-F1","approved_amount":"9000.00"}
]
}{
"payments": [
{"id":"A","client":"C1","funding_account":"F1","amount":"6000.00","depends_on":""},
{"id":"B","client":"C1","funding_account":"F1","amount":"4000.00","depends_on":"A"},
{"id":"C","client":"C1","funding_account":"F1","amount":"3000.00","depends_on":"B"},
{"id":"D","client":"C2","funding_account":"F2","amount":"1.00","depends_on":"C"}
],
"caps": [
{"id":"client-C1","field":"client","value":"C1","limit":"10000.00"},
{"id":"fund-F1","field":"funding_account","value":"F1","limit":"12000.00"}
]
}{
"decisions": [
{"id":"A","status":"APPROVED","reasons":[]},
{"id":"B","status":"APPROVED","reasons":[]},
{"id":"C","status":"REJECTED","reasons":["CAP:client-C1","CAP:fund-F1"]},
{"id":"D","status":"REJECTED","reasons":["DEPENDENCY_REJECTED"]}
],
"cap_totals": [
{"id":"client-C1","approved_amount":"10000.00"},
{"id":"fund-F1","approved_amount":"10000.00"}
]
}get returns the stored value, increments the key's frequency by 1, and updates its recency.get returns -1 and changes nothing.put for an existing key replaces its value, increments its frequency by 1, and updates its recency. It must not evict another key.put for a new key evicts one resident key if necessary, then inserts the new key.put has no effect and every get returns -1.get and put must run in O(1) average time. Recency is determined solely by method-call order; no wall-clock timestamps are needed.Class signatureLFUCache(capacity: int) — initialize an empty cache.get(key: int) -> int — return the value or -1.put(key: int, value: int) -> None — insert or update a key.{
"operations": ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"],
"arguments": [[2], [1, 10], [2, 20], [1], [3, 30], [2], [3], [4, 40], [1], [3], [4]]
}[null, null, null, 10, null, -1, 30, null, -1, 30, 40]
1 raises its frequency to 2, so inserting key 3 evicts key 2, whose frequency is 1. Reading key 3 then raises its frequency to 2. Keys 1 and 3 now tie, but key 1 was used less recently, so inserting key 4 evicts key 1.Example 2:{
"operations": ["LFUCache", "put", "put", "put", "put", "put", "get", "get", "get"],
"arguments": [[2], [7, 70], [8, 80], [7, 75], [8, 85], [9, 90], [7], [8], [9]]
}[null, null, null, null, null, null, -1, 85, 90]
7 and 8 raises both frequencies from 1 to 2. Key 7 was updated first, so it is the least recently used at frequency 2 and is evicted when key 9 arrives. Updates count as accesses even when no get occurs.Constraints:0 <= capacity <= 100000.0 <= key <= 1000000000.0 <= value <= 1000000000; therefore, -1 unambiguously indicates a miss.200000 calls to get and put follow construction.delete(key: int) -> bool, also in O(1) average time. Deleting the final key in the minimum-frequency bucket must correctly identify the next minimum even when frequency values have large gaps. What additional linked structure would you maintain?start to stock end. If there is no path, return -1.def find_shortest_path(graph: Dict[str, Dict[str, int]], start: str, end: str) -> Union[int, List[str]]:graph = {'A': {'B': 5, 'C': 10}, 'B': {'C': 3, 'D': 1}, 'C': {'D': 2}, 'D': {}}[A, B, C, D] A to D is A -> B -> C -> D with a total cost of 5 + 3 + 2 = 10.graph = {'A': {'B': 2}, 'B': {'C': 2}, 'C': {'A': 1}}-1 A to C in this circular transaction graph.min_transaction_cost that takes in the following parameters:stock_count: int: Number of stocks (nodes in the graph)edges: List[Tuple[int, int, int]]: A list of tuples, where each tuple represents a directed edge in the form (source, destination, cost).start: int: Starting stock.end: int: Target stock.start to end. If no path exists, return -1.def min_transaction_cost(stock_count: int, edges: List[Tuple[int, int, int]], start: int, end: int) -> int:stock_count = 5, edges = [(0, 1, 100), (1, 2, 100), (1, 3, 200), (3, 4, 100)], start = 0, end = 4 300 stock_count = 5, edges = [(0, 1, 100), (1, 2, 100), (1, 3, 200), (3, 2, 50), (2, 4, 100)], start = 0, end = 4 350 Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free