Microsoft Software Engineer Coding Questions

In services like Azure Data Lake, it is important to find the maximum throughput of data streams over given segments. This requires identifying the largest sum of neighboring data packets for optimization.
Problem statement: Given an integer array nums, implement a function maxSubArray(nums: List[int]) -> int that returns the largest sum of contiguous elements in the array.
- Method Signature: def maxSubArray(nums: List[int]) -> int: Returns the maximum sum of a contiguous subarray.Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The contiguous subarray [4,-1,2,1] has the largest sum 6.Example 2:
Input: nums = [1]
Output: 1Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4

Microsoft Azure needs to optimize routing between data centers. The goal is to find the shortest path between nodes in the network to enhance performance and reduce latency.
Problem statement: Given a directed graph represented as an adjacency list, implement a function dijkstra(graph: Dict[int, List[Tuple[int, int]]], start: int) -> Dict[int, int] that calculates the shortest path from a starting node to all other nodes.
- Method Signature: def dijkstra(graph: Dict[int, List[Tuple[int, int]]], start: int) -> Dict[int, int]: Returns a dictionary where keys are node indices and values are the shortest distances from the start.Example 1:
Input: graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}, start = 0
Output: {0: 0, 1: 3, 2: 1, 3: 4}
Explanation: The shortest path from node 0 to node 3 is through 2 and then to 1.Example 2:
Input: graph = {0: [(1, 2)], 1: [(2, 3)], 2: [(3, 1)], 3: []}, start = 0
Output: {0: 0, 1: 2, 2: 5, 3: 6}Constraints:
- 1 <= len(graph) <= 10^4
- 0 <= graph[i][j][0] < len(graph)
- 0 < graph[i][j][1] <= 10^3