Goldman Sachs Medium Interview Questions

Background: Goldman Sachs engages in complex trading across different financial instruments. Efficiently finding the shortest path in a trading network can assist in optimizing transaction costs and improving trading strategies.
Problem statement: Given a graph representing a trading network, where nodes are different financial instruments and edges represent the cost of trading between them, implement a function that finds the shortest trading path between two given instruments. Use Dijkstra's algorithm for this purpose.
Function/class signature:

• def shortest_trading_path(graph: Dict[str, List[Tuple[str, int]]], start: str, end: str) -> List[str]:

Example 1:

• Input:

graph = {  
    'A': [('B', 1), ('C', 4)],  
    'B': [('C', 2), ('D', 5)],  
    'C': [('D', 1)],  
    'D': []  
}  
start = 'A'  
end = 'D'

• Output: ['A', 'B', 'C', 'D']


• Explanation: The shortest path from A to D is A → B → C → D with a total cost of 4.

Example 2:

• Input:

graph = {  
    'X': [('Y', 2)],  
    'Y': [('Z', 2), ('U', 1)],  
    'Z': [('U', 3)],  
    'U': []  
}  
start = 'X'  
end = 'U'

• Output: ['X', 'Y', 'U']


• Explanation: The shortest path from X to U is X → Y → U with a total cost of 3.

Constraints:

• 1 ≤ |graph| ≤ 10^4 (number of financial instruments)


• Each edge can have a positive integer cost ranging from 1 to 10^3.


• The graph is connected.

Background: Goldman Sachs operates within complex trading environments where determining optimal transaction routes is critical for minimizing costs and maximizing efficiency. This problem relates to their trading algorithms where the path of trades can significantly impact profit margins.
Problem statement: You are given a directed weighted graph representing a trading network, where nodes represent different financial instruments and edges represent trading routes with associated transaction costs. Write a function shortest_path(start: str, end: str, edges: List[Tuple[str, str, int]]) -> List[str] to find the shortest path (in terms of transaction cost) from a start instrument to an end instrument. If no path exists, return an empty list.
Function/class signature:

• shortest_path(start: str, end: str, edges: List[Tuple[str, str, int]]) -> List[str]

Example 1:

• Input: start = "A", end = "D", edges = [("A", "B", 1), ("B", "C", 2), ("C", "D", 1), ("A", "C", 4)]


• Output: ['A', 'B', 'C', 'D']


• Explanation: The shortest path is A -> B -> C -> D with a total cost of 4.

Example 2:

• Input: start = "A", end = "E", edges = [("A", "B", 1), ("B", "C", 2), ("C", "D", 1)]


• Output: []


• Explanation: There is no path from A to E.

Constraints:

• Max 100 nodes


• Max 200 edges


• Cost values range between 1 and 1000


• All edges are positive integers

Background: In financial applications, analyzing user data efficiently is critical for understanding patterns. At Goldman Sachs, processing user inputs quickly can inform decisions and enhance user experience.Problem statement: Given a string s, write a function that returns the first non-repeating character in s. If there are no non-repeating characters, return null.Function/class signature:

• def first_non_repeating_character(s: str) -> Optional[str]:

Example 1:

• Input: "abracadabra"


• Output: "c"


• Explanation: The character "c" appears exactly once in the string.

Example 2:

• Input: "level"


• Output: "v"


• Explanation: The character "v" appears exactly once in the string.

Constraints:

• 1 <= len(s) <= 10^5


• s consists of only lowercase letters.

1. Background: Goldman Sachs frequently handles transactions in a massive scale across numerous accounts. To ensure consistency and integrity, identifying discrepancies in transaction records is crucial for maintaining trust and operational efficiency.
2. Problem statement: Given a list of transaction amounts and a separate list containing completed transaction amounts, determine which amounts are missing from the completed transactions. You can assume that all amounts in the completed list should exist in the transaction list post-processing for a record of transactions tied to user accounts.
3. Function/class signature:
- def find_missing_transactions(transactions: List[int], completed: List[int]) -> List[int]:
4. Example 1:
- Input: transactions = [100, 200, 300, 400, 500]
- completed: [200, 300, 500]
- Output: [100, 400]
- Explanation: Transaction amounts 100 and 400 are missing from the completed transactions.
5. Example 2:
- Input: transactions = [1000, 2000, 3000]
- completed: [1000, 3000]
- Output: [2000]
6. Constraints:
- 1 <= len(transactions) <= 10000
- 1 <= len(completed) <= len(transactions)
- Transaction amounts range from 1 to 10^6.

Background: In financial systems, identifying cycles in transaction graphs can prevent fraudulent activities and ensure data integrity. Goldman Sachs deals with vast amounts of transaction data, making efficient cycle detection crucial for operational safety.
Problem statement: Given a directed graph represented as an adjacency list, write a function to determine if the graph contains a cycle. Return true if a cycle exists, otherwise return false. Use the following input nodes format:

{<node>: [<neighbor_one>, <neighbor_two>, ...]}

Function/class signature:

• def has_cycle(graph: Dict[int, List[int]]) -> bool:

Example 1:

• Input: graph = {0: [1], 1: [2], 2: [0], 3: [4]}


• Output: True


• Explanation: Node 0 points to 1, 1 points to 2, and 2 back to 0, forming a cycle.

Example 2:

• Input: graph = {0: [1], 1: [2], 2: []}


• Output: False


• Explanation: No cycles exist, as all nodes lead to termination.

Constraints:

• 0 <= |graph| <= 10^4


• Each node is a unique integer.


• The graph can be represented as an acyclic directed graph or contain cycles.