Microsoft Interview Questions
- DSA
- LLD
- HLD
Q1: Validate Binary Search Tree
Description: Given a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST must have all left subtree nodes < root and all right subtree nodes > root, recursively for all nodes. In-order traversal or recursion with min/max bounds is typically used.
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Q2: Balanced Binary Tree
Check whether a binary tree is height-balanced. A tree is balanced if for every node, the heights of left and right subtrees differ by at most one.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Q3: Linked List Cycle II
Detect if a linked list has a cycle, and return the starting node of the cycle if it exists. Use two pointers (slow/fast, Floyd’s Tortoise and Hare).
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Q4: Lowest Common Ancestor of a BST
Given a binary search tree and two nodes, return their lowest common ancestor—the deepest node that has both as descendants.
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Q5: Search in Rotated Sorted Array
Description: Find target in a rotated sorted array (in O(log n)), using binary search with careful pivoting.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Example 3:
Input: nums = [1], target = 0 Output: -1
Q6: Copy List with Random Pointer
Description: Return a deep copy of a linked list where each node has a random pointer; do this in O(n) space, preferably in O(1) extra space via interleaving new nodes.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Q7: LRU Cache
Description: Design and implement an LRU (Least Recently Used) cache supporting O(1) operations for put and get. Combines hashmap + doubly linked list.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Q8: Two Sum
Description: Given nums and target, return indices of two numbers such that they add up to target. Hashmap is the standard method for O(n) time.
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6 Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]
Q9: Longest Substring Without Repeating Characters
Description: Given a string, find length of longest substring without repeating characters. Sliding window and hashset/hashmap are used.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that"bca"and"cab"are also correct answers.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Q10: Subarray Sum Equals K
Description: Find the total number of continuous subarrays within array that sum to k. Use prefix sum + hashmap for O(n) time solution.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Q1. Design a Parking Lot System
Description: Build a class structure for a parking lot with vehicles (car, bike), slots, entry/exit handling, ticket issuance, slot allocation, and possibly payment. Should allow for extension to electric/handicapped spots etc.
Q2. Design a File System
Description: Implement classes for a hierarchical file system: Folder, File; methods for create, delete, move, and search. Ensure efficient lookups and modular design; may support permissions and versioning.
Q3. Multi-Level Charging Station
Description: Design an extensible class set for charging stations supporting multiple levels. Discuss requirements, modular design, implement strategies (e.g., allocation, payment, usage)
Q4. Chess Game
Description: Modular and extensible class-based design for chess (Board, Piece, Move, Game), supporting Human vs AI opponents.
Q5. File System Design
Description: Design classes for a file system with folders, files, and operations: create, delete, search. Choose appropriate data structures (e.g., tree or trie), ensure modularity and ease of extension.
Q6. Snake and Ladder Game
Description: Implement class structure (Board, Player, Dice, Ladder, Snake, Game), support moves, game state, and possible extensions.
Q1. Distributed Caching System
Description: Architect a system (like Redis/Memcached at scale) for distributed, high-throughput caching with topics including: API design (get/set/invalidate), partitioning/sharding, consistency, cache invalidation, durability, and fault-tolerance.
Expected artifacts: High-level architecture diagrams, discussion of CAP theorem, read/write path.
Q2. Microsoft Teams-like Messaging Platform
Description: Full-scale backend for a messaging/communication platform: chatrooms, group and direct messaging, message delivery, retries, notifications, attachments, real-time updates, horizontal scaling.
