Microsoft software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
Design Rate Limiter Design a rate limiter system that controls the number of requests allowed within a specified time window. The rate limiter is...
Input: StringProblem Statement Design a notification service that supports sending notifications through multiple channels (SMS, Email) and is architected to...
Input: Number(s)Shortest Substring with N Unique Characters *This is a variation of the leetcode problem* Given a string s and an integer n, find the length of...
Question You are given n people labeled from 0 to n - 1. Some pairs of people know each other directly. These relationships are given as a...
OA [CodeSignal] Prime Jumps A game is played with the following rules: - A player starts at cell 0 with a score of 0. - There is a row of n cells...
k substitution operations on a number string s. In each operation, choose any digit in s that is...Input: Stringnums. Rearrange nums so that all even numbers appear before all odd numbers. The relative order of even or odd...Input: Arrayid, op, time, tenant, and key. A put also contains value and sizeMiB. Times are integer seconds, and sizes are positive integer MiB encoded as strings. value is an opaque payload token; its string length does not determine its declared size.(tenant, key). The worker has a 10 MiB capacity and a 5-second TTL. A successful put at time t expires at t + 5; an entry is unavailable when time >= expiresAt.(expiresAt, tenant, key) order; tenant and key comparisons are lexicographic.get returns HIT with the stored value or MISS. A hit makes the entry most recently used but does not extend its TTL. A miss does not change recency.put whose size exceeds 10 MiB is REJECTED by GLOBAL_ITEM_LIMIT. Rejection preserves any existing value and its recency, although expiration still happens first.put, remove the previous version of that identity, if present. Evict least-recently-used entries until the new entry fits, then insert it as most recently used and return STORED. Replacement itself is not an eviction. Operations execute in input order, including operations with equal timestamps.id and status, plus value only for a hit.simulate_cache(records: list[dict[str, str]], policies: list[dict[str, str]] | None = None)Omitting policies, or passing None, selects Part 1.Example 1:{
"records": [
{"id":"1","op":"put","time":"0","tenant":"A","key":"x","value":"range-x","sizeMiB":"6"},
{"id":"2","op":"put","time":"1","tenant":"B","key":"y","value":"range-y","sizeMiB":"4"},
{"id":"3","op":"get","time":"2","tenant":"A","key":"x"},
{"id":"4","op":"put","time":"3","tenant":"B","key":"z","value":"range-z","sizeMiB":"4"},
{"id":"5","op":"get","time":"5","tenant":"A","key":"x"},
{"id":"6","op":"get","time":"6","tenant":"B","key":"z"}
]
}[
{"id":"1","status":"STORED"},
{"id":"2","status":"STORED"},
{"id":"3","status":"HIT","value":"range-x"},
{"id":"4","status":"STORED"},
{"id":"5","status":"MISS"},
{"id":"6","status":"HIT","value":"range-z"}
]6 + 4 = 10 MiB. Reading A/x makes B/y least recently used. Inserting B/z would consume 14 MiB, so evicting B/y restores usage to 10 MiB. A/x expires exactly at time 5; its earlier hit did not refresh its TTL. B/z expires at time 8 and remains a hit at time 6.Part 2 — Tenant budgets and explainable decisionspolicies list, including [], enables Part 2. Each policy is a string-valued map containing tenant and maxMiB; it overrides that tenant's default 6 MiB capacity. Tenant names are unique within this list, and capacities are positive integers. The 10 MiB worker capacity and every Part 1 TTL and recency rule still apply.GLOBAL_ITEM_LIMIT, then TENANT_ITEM_LIMIT. If any rule fails, reject the write. Expiration still happens first.expired, evicted, and violations, even when those arrays are empty. An expired identity is {"tenant":"A","key":"x"}. Each eviction contains its identity and reason, either TENANT_CAPACITY or GLOBAL_CAPACITY, in actual eviction order. Do not include replacements or expirations in evicted.results and final usage. Usage is measured immediately after the last operation, without advancing time, and contains totalMiB and tenantMiB; omit tenants with zero usage.{
"policies": [
{"tenant":"A","maxMiB":"6"},
{"tenant":"B","maxMiB":"8"}
],
"records": [
{"id":"1","op":"put","time":"0","tenant":"A","key":"x","value":"ax","sizeMiB":"4"},
{"id":"2","op":"put","time":"1","tenant":"A","key":"y","value":"ay","sizeMiB":"3"},
{"id":"3","op":"put","time":"2","tenant":"B","key":"z","value":"bz","sizeMiB":"6"},
{"id":"4","op":"put","time":"3","tenant":"C","key":"w","value":"cw","sizeMiB":"4"},
{"id":"5","op":"get","time":"4","tenant":"B","key":"z"}
]
}{
"results": [
{"id":"1","status":"STORED","expired":[],"evicted":[],"violations":[]},
{"id":"2","status":"STORED","expired":[],"evicted":[{"tenant":"A","key":"x","reason":"TENANT_CAPACITY"}],"violations":[]},
{"id":"3","status":"STORED","expired":[],"evicted":[],"violations":[]},
{"id":"4","status":"STORED","expired":[],"evicted":[{"tenant":"A","key":"y","reason":"GLOBAL_CAPACITY"}],"violations":[]},
{"id":"5","status":"HIT","value":"bz","expired":[],"evicted":[],"violations":[]}
],
"usage": {"totalMiB":10,"tenantMiB":{"B":6,"C":4}}
}A/y would give tenant A 4 + 3 = 7 > 6 MiB, so A/x is evicted, leaving 3 MiB. Adding B/z gives 3 + 6 = 9 MiB globally and stays within B's 8 MiB cap. Adding C/w is within C's default 6 MiB cap, but global usage would be 9 + 4 = 13 > 10; evicting the globally oldest entry A/y removes 3 MiB. Final usage is 6 + 4 = 10 MiB, and no entry has expired by time 4.Example 3:{
"policies": [],
"records": [
{"id":"1","op":"put","time":"0","tenant":"A","key":"x","value":"original","sizeMiB":"4"},
{"id":"2","op":"put","time":"1","tenant":"B","key":"y","value":"by","sizeMiB":"6"},
{"id":"3","op":"put","time":"2","tenant":"A","key":"x","value":"oversized","sizeMiB":"11"},
{"id":"4","op":"get","time":"3","tenant":"A","key":"x"},
{"id":"5","op":"put","time":"5","tenant":"A","key":"z","value":"az","sizeMiB":"6"}
]
}{
"results": [
{"id":"1","status":"STORED","expired":[],"evicted":[],"violations":[]},
{"id":"2","status":"STORED","expired":[],"evicted":[],"violations":[]},
{"id":"3","status":"REJECTED","expired":[],"evicted":[],"violations":["GLOBAL_ITEM_LIMIT","TENANT_ITEM_LIMIT"]},
{"id":"4","status":"HIT","value":"original","expired":[],"evicted":[],"violations":[]},
{"id":"5","status":"STORED","expired":[{"tenant":"A","key":"x"}],"evicted":[{"tenant":"B","key":"y","reason":"GLOBAL_CAPACITY"}],"violations":[]}
],
"usage": {"totalMiB":6,"tenantMiB":{"A":6}}
}4 + 6 = 10 MiB. The attempted replacement has size 11, violating both 11 > 10 and 11 > 6, so the original value survives. At time 5, A/x expires despite its time-3 hit, reducing usage to 6 MiB. B/y does not expire until time 6. Adding A/z would consume 6 + 6 = 12 > 10, so B/y is globally evicted, leaving 6 MiB.Notes:def reverse_linked_list(head: Optional[ListNode]) -> Optional[ListNode]:head = [1, 2, 3, 4, 5] [5, 4, 3, 2, 1] head = [1] [1] [0, 5000]. -5000 <= Node.val <= 5000. head. Your task is to reverse the linked list and return the new head node. Ensure that the function can handle edge cases such as an empty list or a single node list.def reverse_linked_list(head: Optional[Node]) -> Optional[Node]: head = 1 -> 2 -> 3 -> None 3 -> 2 -> 1 -> None 1 -> 2 -> 3 to 3 -> 2 -> 1.head = None None None.[0, 5000]. -1000 and 1000. def reverse_linked_list(head: Optional[ListNode]) -> Optional[ListNode]:1 -> 2 -> 3 -> 4 -> 5 -> None5 -> 4 -> 3 -> 2 -> 1 -> None1 -> None1 -> Nonedef reverse_linked_list(head: ListNode) -> ListNode: get(key) and put(key, value). The get method retrieves the value of the key if it exists in the cache. Otherwise, it returns -1. The put method will insert or update the value for a key. If the cache exceeds its capacity, it should invalidate the least recently used item before inserting a new item into the cache.def __init__(self, capacity: int): # Initializes the LRU cache with positive size capacity.def get(self, key: int) -> int: # Returns the value of the key if it exists in the cache, otherwise returns -1.def put(self, key: int, value: int) -> None: # Updates or inserts the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item.cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1)1 1 was accessed and is now the most recently used.cache.put(3, 3)-1 cache exceeds capacity. 2 is evicted.get(key) and put(key, value). The get method retrieves the value of the key if it exists in the cache, otherwise returns -1. The put method updates or adds the value of the key in the cache. When the cache reaches its capacity, it should invalidate the least recently used entry before inserting a new item. def __init__(self, capacity: int): # initialize LRUCache with positive size capacitydef get(self, key: int) -> int: # return the value of the key, or -1 if the key does not existdef put(self, key: int, value: int) -> None: # update the value of the key or insert the key if it is not already presentlru_cache = LRUCache(2)lru_cache.put(1, 1)lru_cache.put(2, 2)print(lru_cache.get(1)) 1 lru_cache.put(3, 3) 1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^8s, you need to return the number of palindromic substrings in s. A palindrome is a string that reads the same backward as forward. def count_palindromic_substrings(s: str) -> int:"aaa", Output: 6, Explanation: Substrings are "a", "a", "a", "aa", "aa", "aaa"."abc", Output: 3, Explanation: Substrings are "a", "b", "c".1 <= len(s) <= 1000s consists of lowercase English letters.nums, implement a function maxSubArray(nums: List[int]) -> int that returns the largest sum of contiguous elements in the array.def maxSubArray(nums: List[int]) -> int: Returns the maximum sum of a contiguous subarray.nums = [-2,1,-3,4,-1,2,1,-5,4]6[4,-1,2,1] has the largest sum 6.Example 2:nums = [1]1Constraints:1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4dijkstra(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.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.graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}, start = 0{0: 0, 1: 3, 2: 1, 3: 4}0 to node 3 is through 2 and then to 1.Example 2:graph = {0: [(1, 2)], 1: [(2, 3)], 2: [(3, 1)], 3: []}, start = 0{0: 0, 1: 2, 2: 5, 3: 6}Constraints:1 <= len(graph) <= 10^40 <= graph[i][j][0] < len(graph)0 < graph[i][j][1] <= 10^3Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free