Two Sigma Interview Questions

Background: Two Sigma often deals with large datasets and requires efficient algorithms for data processing and analytics. Finding optimal paths in graphs can significantly enhance data-related tasks, such as trading algorithms and routing.Problem statement: Given a weighted directed graph represented as an adjacency list, write a function shortest_path that finds the shortest path from a starting node to a destination node using Dijkstra's algorithm. You should return the path as a list of node identifiers and the total weight of that path.Function/class signature:

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

Example 1:

• Input: graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}, start = 0, end = 3


• Output: ([0, 2, 1, 3], 5)


• Explanation: The path 0 -> 2 -> 1 -> 3 has a total weight of 5.

Example 2:

• Input: graph = {0: [(1, 10), (2, 5)], 1: [(3, 2)], 2: [(1, 3), (3, 1)], 3: []}, start = 0, end = 3


• Output: ([0, 2, 3], 6)


• Explanation: The path 0 -> 2 -> 3 has a total weight of 6.

Constraints:

• The number of nodes in the graph will not exceed 10^5.


• The edges' weights are positive integers.


• You can assume the graph is connected and directed.

Background: Two Sigma requires an fast and scalable storage solution for data used in its trading algorithms. This key-value store can be utilized to cache data points that need to be fetched quickly during computation processes.
Problem statement: Implement a class KeyValueStore that allows for storing, retrieving, and deleting key-value pairs. The operations should have O(1) time complexity. The class should also provide a method to check if a key exists in the store.
Function/class signature:

• def set_key(key: str, value: Any) -> None: # Adds or updates a key-value pair


• def get_value(key: str) -> Optional[Any]: # Returns the value associated with the key, or None if it doesn't exist


• def delete_key(key: str) -> None: # Removes the key from the store


• def key_exists(key: str) -> bool: # Returns True if the key exists, else False

Example 1: Input: set_key('alpha', 100), get_value('alpha') → Output: 100. Explanation: 'alpha' is set to 100, therefore retrieving it returns 100.
Example 2: Input: set_key('beta', 200), delete_key('beta'), get_value('beta') → Output: None. Explanation: 'beta' is deleted, so retrieving it returns None.
Constraints:

• Total number of keys (1 ≤ key length ≤ 100)


• Store can handle up to 10^6 entries


• The value can be any data type


• Operations should complete in O(1) time complexity.

1. Background: In performance-critical applications like the ones Two Sigma develops, efficient memory management is essential to store and retrieve frequently accessed data without excessive latency. An efficient LRU (Least Recently Used) cache helps in keeping the most relevant data in memory for quick access.
2. Problem statement: Design and implement a LRUCache class that supports the following operations: get(key) and put(key, value). The get method should return the value of the key if it exists in the cache, otherwise return -1. The put method should insert or update the value of the key. If the number of keys exceeds the capacity, the least recently used key should be removed.
3. Function/class signature:
- class LRUCache:
- def __init__(self, capacity: int): # initializes the LRU cache with a positive capacity.
- def get(self, key: int) -> int: # returns the value of the key if it exists.
- def put(self, key: int, value: int) -> None: # updates or adds the key-value pair.
4. Example 1: Input: put(1, 1); put(2, 2); get(1) → Output: 1 Explanation: Key 1 is found, returning 1.
5. Example 2: Input: put(3, 3); get(2) → Output: -1 Explanation: Key 2 was evicted when putting key 3 since the capacity is 2.
6. Constraints:
- Capacity (1 <= capacity <= 3000)
- Each key and value (0 <= key, value <= 10^4)
- All operations are guaranteed to be called with valid keys.

Background: Two Sigma often deals with complex algorithms for optimizing quantitative analysis. Efficient pathfinding is crucial in scenarios such as navigating through large datasets represented as grids.
Problem statement: Given a grid represented by a 2D list of integers, where 0 represents an open cell and 1 represents an obstacle, write a function that returns the length of the shortest path from the top-left corner (0,0) to the bottom-right corner (n-1,m-1). You can only move right, left, up, or down. If there is no such path, return -1.
Function/class signature:

• def shortest_path(grid: List[List[int]]) -> int:

Example 1:
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 4
Explanation: The path is down -> down -> right -> right.
Example 2:
Input: [[0,1],[0,0]]
Output: 3
Explanation: The path is down -> right -> right.
Constraints:

• 1 <= n, m <= 100


• The grid will contain only 0s and 1s.


• The starting and ending cells will always be 0.

Background: Two Sigma requires efficient pathfinding algorithms to navigate and analyze potential trading routes, using grid-like representations of financial landscapes. This problem models a grid system, where certain cells are obstructed, complicating the route selection.
Problem statement: Given an m x n grid represented by a 2D array, where each cell is either 0 (open space) or # (obstacle), determine the shortest path from the starting point (0, 0) to a destination point (x, y). You may move up, down, left, or right but may not traverse the cells containing obstacles (#). Return the length of the shortest path if it exists, otherwise return -1.
Function/class signature:

• def shortest_path(grid: List[List[str]], destination: Tuple[int, int]) -> int:

Example 1:

• Input: grid = [['0', '0', '#'], ['0', '0', '0'], ['#', '0', '0']], destination = (2, 2)


• Output: 4


• Explanation: The path is [(0,0), (0,1), (1,1), (2,1), (2,2)], which has 4 steps.

Example 2:

• Input: grid = [['0', '#', '0'], ['0', '0', '0'], ['#', '#', '0']], destination = (2, 2)


• Output: 5


• Explanation: The path is [(0,0), (1,0), (1,1), (1,2), (2,2)], which has 5 steps.

Constraints:

• 1 ≤ m, n ≤ 100


• grid[i][j] is either '0' or '#'.


• destination must be within the grid bounds.

Background: In a trading environment, Two Sigma needs to manage data efficiently to provide real-time insights and analytics. A Least Recently Used (LRU) cache is essential to store frequently accessed items, thus improving the speed and efficiency of data retrieval.Problem statement: Implement a thread-safe LRUCache class that supports the following operations: get and put. The get(key) method retrieves the value if the key exists, otherwise returns -1. The put(key, value) method updates the value if the key is present, or inserts a new key-value pair. If the cache reaches its limit, it should remove the least recently used item before inserting a new item.Function/class signature:

• def __init__(self, capacity: int):


• def get(self, key: int) -> int:


• def put(self, key: int, value: int) -> None:

Example 1:

• Input: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1)


• Output: 1


• Explanation: The cache is {1=1, 2=2}. The value for key 1 is returned, and key 2 becomes the least recently used.

Example 2:

• Input: cache.put(3, 3); cache.get(2)


• Output: -1


• Explanation: The cache reaches capacity and removes key 2; hence, trying to access it returns -1.

Constraints:

• 1 <= capacity <= 3000


• 0 <= key, value <= 100000


• get and put operations are called at most 10^4 times.