Microsoft Hard Interview Questions

Considering the real-time capabilities of Azure, create a basic Twitter API that can fetch user feeds. This design must include necessary features for users to follow others and retrieve their latest tweets in real-time.
Problem statement: Design a Twitter class that supports the following methods:
- postTweet(userId: int, tweetId: int) -> None: Record a new tweet.
- getNewsFeed(userId: int) -> List[int]: Retrieve the 10 most recent tweet IDs in the user's news feed.
- follow(followerId: int, followeeId: int) -> None: Allow a follower to follow a followee.
- unfollow(followerId: int, followeeId: int) -> None: Allow a follower to unfollow a followee.Method Signatures:
- def postTweet(self, userId: int, tweetId: int) -> None
- def getNewsFeed(self, userId: int) -> List[int]
- def follow(self, followerId: int, followeeId: int) -> None
- def unfollow(self, followerId: int, followeeId: int) -> NoneExample 1:
Input: twitter = Twitter()
twitter.postTweet(1, 5)
twitter.getNewsFeed(1)
Output: [5]Example 2:
Input: twitter.follow(1, 2)
twitter.postTweet(2, 6)
twitter.getNewsFeed(1)
Output: [6, 5]Constraints:
- 0 <= userId, followerId, followeeId, tweetId <= 10^4
- The number of tweets will not exceed 10^4. At most 3 * 10^4 follow operations will occur.

Microsoft Azure commonly uses caching to speed up responses to repeated API requests. Implement an LRU (Least Recently Used) Cache to maintain efficient access and updates.
Problem statement: Design and implement an LRUCache class that supports get(key: int) -> int and put(key: int, value: int) -> None methods. The cache will have a limited capacity.
- Method Signatures:
- def get(self, key: int) -> int: Returns the value of the key if present, otherwise -1.
- def put(self, key: int, value: int) -> None: Updates the value of the key or adds it if it's not already present. When the cache reaches its capacity, it invalidates the least recently used item before inserting a new item.Example 1:
Input: cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
Output: 1Example 2:
Input: cache.put(2, 1)
cache.put(2, 2)
cache.get(2)
Output: 2Constraints:
- capacity will be between 1 and 3000.
- key and value are integers within the range of a 32-bit signed integer.

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