Goldman Sachs Interview Questions

Background: Goldman Sachs often deals with stock transactions, where understanding the pathways between stocks can lead to optimizations in trading strategies. This problem is essential for developing applications that recommend stock trades based on historical trends.
Problem statement: You are tasked with creating a function that finds the shortest path between two stocks in a weighted graph. Each node represents a stock, and edges represent transaction potentials with weights indicating transaction costs. Given a directed graph, return the shortest path from stock start to stock end. If there is no path, return -1.
Function/class signature:

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

Example 1:

• Input: graph = {'A': {'B': 5, 'C': 10}, 'B': {'C': 3, 'D': 1}, 'C': {'D': 2}, 'D': {}}


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


• Explanation: The shortest path from A to D is A -> B -> C -> D with a total cost of 5 + 3 + 2 = 10.

Example 2:

• Input: graph = {'A': {'B': 2}, 'B': {'C': 2}, 'C': {'A': 1}}


• Output: -1


• Explanation: There is no path from A to C in this circular transaction graph.

Constraints:

• The number of stocks (nodes) is between 1 and 1000.


• The number of transactions (edges) can be at most 10,000.


• Stocks are represented by uppercase letters A-Z.


• Weights of edges are positive integers up to 1000.

Background: Goldman Sachs operates in a fast-paced trading environment where decisions are based on real-time data and market conditions. Efficiently determining the shortest path in stock transactions can lead to reduced latency and improved trading strategies.
Problem statement: You are given a directed graph where each node represents a stock and the edges represent the transaction costs between stocks. Your task is to find the minimum transaction cost to move from one stock to another. Implement a function 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.

Returns the minimum transaction cost to get from start to end. If no path exists, return -1.
Function/class signature:

• def min_transaction_cost(stock_count: int, edges: List[Tuple[int, int, int]], start: int, end: int) -> int:

Example 1:
Input: stock_count = 5, edges = [(0, 1, 100), (1, 2, 100), (1, 3, 200), (3, 4, 100)], start = 0, end = 4
Output: 300
Explanation: The shortest path is from 0 -> 1 -> 3 -> 4 with a total cost of 300.
Example 2:
Input: stock_count = 5, edges = [(0, 1, 100), (1, 2, 100), (1, 3, 200), (3, 2, 50), (2, 4, 100)], start = 0, end = 4
Output: 350
Explanation: The shortest path is from 0 -> 1 -> 2 -> 4 with a total cost of 350.
Constraints:

• 1 <= stock_count <= 1000


• 0 <= edges.length <= 2000


• 0 <= cost <= 10^4


• All stock indices in edges will be between 0 and stock_count - 1.

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.