Goldman Sachs Hard 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.