Microsoft Software Engineer Coding & Algorithms Interview Questions
Practice the exact questions companies are asking right now.
Solve binary-tree reverse printing and LPS
You are given a binary tree node definition: - TreeNode { int val; TreeNode left; TreeNode right; } Answer the following two algorithmic questions. 1)...
Assemble DNA payload strings from tagged fragments
You are given a list of DNA-like fragments. Each fragment is a tuple: - start_tag: string - end_tag: string - payload: string A valid DNA chain is for...
Solve four classic algorithm problems
You are given four independent coding tasks. For each task, implement the required function. --- Problem 1: Zigzag level-order traversal of a binary t...
Find longest substring without repeating characters
Problem Given a string s, return the length of the longest contiguous substring that contains no repeated characters. Input - s: a string (may contain...
Implement a calendar with non-overlapping bookings
Problem Design a calendar booking system that stores half-open time intervals [start, end) (inclusive of start, exclusive of end). Implement a class w...
Find lowest common ancestor in tree
You are given the root of a binary search tree (BST) and two distinct nodes p and q that are guaranteed to exist in the tree. Task (BST case): - Find ...
Merge overlapping intervals
You are given an array of intervals, where each interval is represented as a pair of integers [start, end] with start <= end. The intervals may be uns...
Find max consecutive elements with sum below target
You are given: - An integer array nums of length n, sorted in non-decreasing order. - An integer index such that 0 ≤ index < n. - An integer target. S...
Count integer pairs satisfying 1/x + 1/y = 1/N
You are given a positive integer N (\(1 \le N \le 10^6\)). Consider the Diophantine equation: \[ \frac{1}{x} + \frac{1}{y} = \frac{1}{N}, \] where x a...
Find shortest substring with n unique letters
Problem You are given a string s consisting of lowercase English letters and an integer n (1 ≤ n ≤ 26). Find the length of the shortest contiguous sub...
Merge multiple sorted arrays using min-heap
Problem You are given k sorted arrays of integers: - arrays[0], arrays[1], ..., arrays[k-1] - Each arrays[i] is sorted in non-decreasing order. - The ...
Reverse linked list in fixed-size groups
Problem You are given the head of a singly linked list and an integer k (k >= 1). Reverse the nodes of the list in-place in groups of size k: - The no...
Solve three scheduling and array problems
In this round you are given three separate coding problems to solve. --- Problem 1: Schedule tasks with cooldown You are given: - A list of tasks, whe...
Build a time-based key-value store
Problem Design a data structure that stores multiple values for the same key at different timestamps, and can retrieve the most recent value as of a g...
Design cache with least-recently-used eviction
You are asked to design an in-memory key–value cache that supports a least-recently-used (LRU) eviction policy. The cache must support the following o...
Implement a Tic-Tac-Toe game class
Problem Implement a class that supports playing an n × n Tic-Tac-Toe game. Requirements Create a class TicTacToe(n) with: - move(row, col, player) -> ...
Implement tree traversals, BFS, and subsets generation
1) Define a TreeNode class for a binary tree with an integer value and left/right pointers. Implement preorder, inorder, and postorder traversals: (a)...
Count k for consecutive-sum generator
An array generator service produces a consecutive-integers array starting at a positive integer k: [k, k+1, ..., k+m−1] for some m ≥ 1. The service re...
Solve load balancing and perfect pairs
1) Contiguous load balancing: You have n identical resources (servers) and m ordered tasks with processing times burstTime[0..m-1]. Each server must b...
Count non-decreasing arrays by digit sums
You are given an array required_sums of length n. Count how many non-decreasing arrays result[1..n] of integers satisfy all of the following: ( 1) for...