Bloomberg Interview Questions

Background: Bloomberg's trading systems need to quickly determine the optimal trading paths for stocks to minimize transaction costs. This involves navigating a graph of stock prices, which can change frequently based on market conditions.
Problem statement: You are tasked with implementing a function that calculates the shortest path from a given stock to another where each edge weight represents the transaction cost between two stocks in an undirected graph. You need to handle multiple queries and return the minimum cost for each path efficiently. Use Dijkstra's algorithm for this task.
Function/class signature:

• def min_transaction_cost(prices: List[Tuple[int, int, int]], queries: List[Tuple[int, int]]) -> List[int]:

Example 1:
Input: prices = [(1, 2, 100), (1, 3, 200), (2, 3, 50)], queries = [(1, 3), (1, 2)]
Output: [150, 100]
Explanation: The shortest path from 1 to 3 is via 2 with a cost of 150. The direct cost from 1 to 2 is 100.Example 2:
Input: prices = [(1, 4, 300), (4, 5, 100), (1, 5, 600)], queries = [(1, 5), (1, 4)]
Output: [400, 300]
Explanation: The shortest path from 1 to 5 is via 4 with a total cost of 400.Constraints:

• 1 <= prices.length <= 10^4


• 1 <= queries.length <= 10^4


• 1 <= prices[i][0], prices[i][1] <= 10^6


• 0 <= prices[i][2] <= 10^4


• Each query node exists in the price list.

Background: Bloomberg processes vast amounts of market data in real time. Often, traders need quick access to key metrics like the Kth largest price from a stream of stock prices for decision making.
Problem statement: Implement a class that can efficiently retrieve the Kth largest element from a stream of numbers. You should maintain the Kth largest element at all times as new numbers are added. Class should support adding a new number and retrieving the Kth largest number.
Function/class signature:

• class KthLargest:


• def __init__(self, k: int, nums: List[int]) -> None:


• def add(self, val: int) -> int:

Example 1: With Input: k = 3, nums = [4, 5, 8, 2] → Output after add(3): 4, Explanation: The current stream is [4, 5, 8, 2, 3], and the 3rd largest number is 4.Example 2: With Input: k = 1, nums = [] → Output after add(5): 5, Explanation: There is only one number 5, which is the 1st largest by default.Constraints:

• 1 <= k <= 10^4


• -10^4 <= nums[i] <= 10^4


• -10^4 <= val <= 10^4


• At most 10^4 calls will be made to add.


• It is guaranteed that add will be called at least once.

Background: Bloomberg operates with vast datasets and real-time financial information. To ensure efficient communication and data retrieval, determining the shortest path in a network of connections, such as between servers or financial instruments, is crucial.
Problem statement: Given a graph represented as an adjacency list where each edge has a weight, write a function to calculate the shortest path from a specified starting node to all other nodes in the graph. The function should return a dictionary with nodes as keys and their shortest distances from the start node as values.
Function/class signature:

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

Example 1:
Input: graph = { 'A': [('B', 1), ('C', 4)], 'B': [('C', 2)], 'C': []}, start = 'A'
Output: {'A': 0, 'B': 1, 'C': 3}
Explanation: Starting from A, the shortest path to B is 1 and to C is 3 via B.
Example 2:
Input: graph = { 'X': [('Y', 5)], 'Y': [('Z', 1)], 'Z': []}, start = 'X'
Output: {'X': 0, 'Y': 5, 'Z': 6}
Explanation: Starting from X, the shortest path to Y is 5 and to Z is 6.
Constraints:

• The number of nodes in the graph will be between 1 and 1000.


• The weights of edges will be positive integers not exceeding 100.

Background: In the financial domain, Bloomberg provides tools for stock market analysis, including trading strategies. Understanding how to maximize profit through stock trading is crucial for building robust trading systems.
Problem statement: You are given an array of integers where each integer represents the price of a stock on a given day. You can complete at most k transactions (i.e., buy and sell the stock). Your goal is to maximize your profit. You can assume that you cannot sell a stock before you buy it. You need to implement a function that calculates the maximum profit that can be achieved with at most k transactions.Function signature:

def max_profit(k: int, prices: List[int]) -> int:

Example 1:
Input: k = 2, prices = [2, 4, 1, 7, 5]
Output: 7
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 2. Buy on day 3 (price = 1) and sell on day 4 (price = 7), profit = 6. Total profit = 2 + 6 = 8. Example 2:
Input: k = 1, prices = [3, 2, 6, 5, 0, 3]
Output: 4
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6 - 2 = 4.Constraints:

• 1 <= k <= 100


• 0 <= prices.length <= 1000


• 0 <= prices[i] <= 1000

Background: Bloomberg often works with complex financial data that can be represented as hierarchical structures, such as trees. Efficient algorithms to traverse and analyze these structures are vital for data representation and visualization.
Problem statement: Given a binary tree, write a function that calculates the depth of the tree. The depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.
Function/class signature:

• def maxDepth(root: Optional[TreeNode]) -> int:

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest path is from root (3) to leaf (15) or (7), which counts as 3 nodes.
Example 2:
Input: root = [1,null,2]
Output: 2
Explanation: The longest path is from root (1) to leaf (2), which counts as 2 nodes.
Constraints:

• The number of nodes in the tree is in the range [0, 10^4].


• -100 <= Node.val <= 100


• The tree can have up to 10^4 nodes.

1. Background: Bloomberg manages vast amounts of financial data including stock market information. Understanding the shortest path in a network of stocks can help analysts make effective trading strategies.
2. Problem statement: Given a directed graph where each node represents a stock and each edge represents a transaction cost between two stocks, implement a function that returns the shortest path from a start_stock to an end_stock. If no path exists, return -1.
3. Function/class signature:
- def find_shortest_path(graph: Dict[str, List[Tuple[str, int]]], start_stock: str, end_stock: str) -> int:
4. Example 1:
Input: graph = {'A': [('B', 1), ('C', 4)], 'B': [('C', 2), ('D', 5)], 'C': [('D', 1)], 'D': []}, start_stock = 'A', end_stock = 'D'
Output: 4
Explanation: The path A -> B -> C -> D has a transaction cost of 1 + 2 + 1 = 4.
5. Example 2:
Input: graph = {'A': [('B', 5)], 'B': [('C', 3)], 'C': [], 'D': []}, start_stock = 'A', end_stock = 'D'
Output: -1
Explanation: There is no path from A to D.
6. Constraints:
- The graph has at most 1000 stocks.
- The number of transactions (edges) can be at most 10,000.
- Transaction costs are positive integers less than 1000.
- start_stock and end_stock are guaranteed to be valid stock identifiers in the graph.

Background: Bloomberg provides financial services and information, where managing stock portfolios is essential for users to track their investments and performance.
Requirements:
1. The class should allow adding, removing, and updating stocks in a user's portfolio.
2. It should provide methods to calculate the total value of the portfolio and the performance over time.
3. The service must handle multiple users.
4. It should support concurrency for simultaneous modifications.
5. The portfolio must store the historical prices of stocks for performance analysis.
Class API:

• add_stock(user_id: str, stock_symbol: str, quantity: int) -> None: Adds a stock for the user.


• remove_stock(user_id: str, stock_symbol: str) -> None: Removes a stock from the user's portfolio.


• update_stock(user_id: str, stock_symbol: str, quantity: int) -> None: Updates stock quantity in the portfolio.


• get_total_value(user_id: str) -> float: Returns the total value of the portfolio based on current stock prices.


• get_performance(user_id: str) -> dict: Returns performance metrics like returns over a specified period.

Example 1:
Input: add_stock('user123', 'AAPL', 10) → Output: None → Explanation: Adds 10 shares of AAPL to user 'user123's portfolio.Example 2:
Input: get_total_value('user123') → Output: 1500.00 → Explanation: Total value based on current stock prices of the user's portfolio.
Constraints:

• Max users: 10000


• Max stocks per user: 100


• Concurrent operations should not lead to data inconsistency.