Citadel Hard Interview Questions

Background: In high-frequency trading systems at Citadel, optimizing for concurrency is crucial to maximize throughput and minimize latency. When managing trades and market data, optimizing access and updates to shared resources is essential.
Problem statement: You need to design a function optimizeConcurrency that takes a list of trades to process concurrently. Each trade requires an update to a shared orderBook, but the updates should not conflict. Use appropriate data structures to minimize locking and waiting.
Function/class signature:

• def optimizeConcurrency(trades: List[Dict[str, int]]) -> List[Optional[int]]:


• def updateOrderBook(trade: Dict[str, int]) -> None:

Example 1:

• Input: trades = [{'id':1, 'amount':100}, {'id':2, 'amount':200}, {'id':1, 'amount':150}]


• Output: None


• Explanation: The function should process trades concurrently and reflect the latest amount for each unique trade ID in the order book without conflicts.

Example 2:

• Input: trades = [{'id':3, 'amount':300}, {'id':4, 'amount':400}]


• Output: None


• Explanation: Similar processing for these trades, ensuring each update is atomic and thread-safe.

Constraints:

• 1 <= trades.length <= 1000


• Trade IDs are between 1 and 10000.


• The function should handle up to 100 concurrent updates.

Background: Citadel's trading strategies depend on efficient order book management. An in-memory order book allows traders to process orders quickly and adjust to market conditions dynamically.
Problem statement: You are tasked with optimizing a function that handles buy and sell orders in a thread-safe manner. You should implement a class that supports concurrent access while ensuring that orders are processed correctly. The order book allows for adding and removing orders and retrieving the current best buy and sell prices. The key requirements involve handling multiple threads without introducing race conditions.
Function/class signature:

• class OrderBook


• def add_order(self, order_id: str, price: float, quantity: int, order_type: str) -> None:


• def remove_order(self, order_id: str) -> None:


• def get_best_buy(self) -> Tuple[float, int]:


• def get_best_sell(self) -> Tuple[float, int]:

Example 1:

• Input: add_order('1', 100.0, 10, 'buy')


• Output: None


• Explanation: A buy order with ID '1' for 10 units at $100 is added.

Example 2:

• Input: add_order('2', 105.0, 5, 'sell')


• Output: None


• Explanation: A sell order with ID '2' for 5 units at $105 is added. Now, get_best_buy() should return (100.0, 10) and get_best_sell() should return (105.0, 5).

Constraints:

• 1 <= order_id <= 10^5


• Price and quantity are non-negative floats and integers respectively.


• Concurrent calls to add_order and remove_order may occur, but please ensure consistency in retrieval methods.

Background: Citadel relies on efficient trading algorithms to quickly make transactions across different markets. Understanding the shortest routes between various venues can optimize trade execution.
Problem statement: In a network of trading venues represented as a directed graph, where each edge represents the time taken to execute a trade between two venues, your task is to find the shortest time to get from a source venue to a target venue. Implement Dijkstra's algorithm to determine the minimum execution time.
Function/class signature:

• def shortest_time(venues: List[Tuple[int, int, int]], source: int, target: int) -> int:

Example 1:

• Input: venues = [(0, 1, 5), (0, 2, 10), (1, 2, 2), (2, 3, 1)], source = 0, target = 3


• Output: 8


• Explanation: The shortest path is from 0 -> 1 -> 2 -> 3 with a total time of 5 + 2 + 1 = 8.

Example 2:

• Input: venues = [(0, 1, 8), (1, 3, 6), (0, 2, 7), (2, 3, 2)], source = 0, target = 3


• Output: 9


• Explanation: The optimal path is 0 -> 2 -> 3 with a total time of 7 + 2 = 9.

Constraints:

• 1 <= len(venues) <= 1000


• 0 <= venue index < 100


• Execution time is positive integer and does not exceed 1000.

Background: Citadel often deals with financial algorithms that require efficient pathfinding through complex market data represented as graphs. This problem is crucial for optimizing trade routes.
Problem statement: Given a weighted directed graph represented as an adjacency list, your task is to implement a function that calculates the shortest path from a source node to a target node using Dijkstra’s algorithm. Each edge weight represents the cost for trading between nodes, and you need to return the minimum trading cost.
Function/class signature:

• def shortest_path(graph: Dict[int, List[Tuple[int, float]]], source: int, target: int) -> float:

Example 1:
Input: graph = {0: [(1, 2.0), (2, 4.0)], 1: [(2, 1.0)], 2: []}
Output: 3.0
Explanation: The shortest path from node 0 to node 2 is via node 1 with a total cost of 2.0 + 1.0 = 3.0.Example 2:
Input: graph = {0: [(1, 10.0)], 1: [(2, 5.0)], 2: [(3, 1.0)], 3: []}
Output: 16.0
Explanation: The shortest path is from 0 to 1 to 2 to 3 with total cost 10.0 + 5.0 + 1.0 = 16.0.Constraints:

• 1 <= len(graph) <= 100


• 0 <= source, target < len(graph)


• weights are positive doubles.