Microsoft Backend Engineer Coding Questions

Within Microsoft's subscription services, pricing models often require optimal strategies to maximize revenue while considering customer retention.
Problem: You have a list of prices, where prices[i] is the price of a subscription option for the ith month. Write a function maxProfit(prices: List[int], k: int) -> int that returns the maximum profit achievable by buying and selling at most k times. A transaction is when you buy and sell a subscription.- Method: maxProfit(prices: List[int], k: int) -> int
Description: Returns the maximum profit from at most k price transactions.Example 1:
Input: prices = [1, 2, 3, 0, 2], k = 2
Output: 3
Explanation: Buy on month 1 and sell on month 3, then buy on month 4 and sell again for a total profit of 3.Example 2:
Input: prices = [1, 2], k = 1
Output: 1
Explanation: Only one transaction possible.Constraints:
- 1 <= prices.length <= 1000
- 1 <= k <= 100

In Microsoft's Azure services, resource allocation and deployment often include determining the shortest paths for data transfer between different data centers.
Problem: Given a weighted directed graph represented by an adjacency list, where each node represents a data center and each edge represents the time to transfer data, implement a function that finds the shortestPath(source: int, destination: int) -> List[int] that returns the shortest path from source to destination. If no path exists, return an empty list.- Method: shortestPath(source: int, destination: int) -> List[int]
Description: Returns the path with the minimum transfer time from source to destination.Example 1:
Input: source = 0, destination = 4, graph = [[(1, 1), (2, 4)], [(2, 2), (3, 7)], [(3, 3)], [(4, 1)], []]
Output: [0, 1, 2, 3, 4]
Explanation: The shortest path is from data center 0 to 1 to 2 to 3 to 4 with a total cost of 7.Example 2:
Input: source = 0, destination = 3, graph = [[(1, 1), (2, 4)], [(3, 2)], [(3, 5)], []]
Output: []
Explanation: There’s no path from 0 to 3.Constraints:
- 1 <= graph.length <= 100
- 0 <= graph[i][j][0] < graph.length
- 1 <= graph[i][j][1] <= 10^4
- No duplicate edges.