Walmart Global Tech Previous Year Coding Questions
Walmart Global Tech (formerly Walmart Labs) is one of the largest tech employers in India, with major engineering centres in Bengaluru and Chennai. The interview process tests strong DSA fundamentals across arrays, dynamic programming, trees, and graphs, followed by Low Level Design (LLD) and High Level Design (HLD) rounds for senior roles. Recent graduates and experienced hires alike report LeetCode medium problems as the sweet spot. The Karat phone screen is a distinctive step in the Walmart process that filters candidates before the main loop begins.
Hiring Process
Step 1: Resume Shortlisting Walmart Global Tech screens resumes for relevant product company experience, DSA competitive programming background, and strong academic credentials from tier-1 and tier-2 engineering colleges in India.
Step 2: Online Assessment (HackerRank) A timed assessment with two to three coding problems ranging from easy to hard. Time window is 90 minutes. Problems typically cover arrays, hashing, sliding window, and basic DP. Automated test cases check correctness and edge cases.
Step 3: Karat Technical Phone Screen A 60-minute live coding interview conducted via Karat (a third-party interviewing platform). Contains 10–15 minutes of domain knowledge discussion, one easy-to-medium LeetCode problem (up to 20 minutes), and one medium-to-hard problem (up to 25 minutes). Clear communication and clean code matter as much as the solution itself.
Step 4: DSA Round 1 A 60-minute round with two medium LeetCode problems. Candidates are expected to explain their approach first before coding. Interviewers probe time and space complexity and ask for optimisations.
Step 5: DSA Round 2 / LLD Round For SDE-2 and above this round shifts to Low Level Design. Common problems include designing a Parking Lot, Inventory Management System, or Notification System. Observer and Factory design patterns appear frequently. For SDE-1 roles this is another DSA round.
Step 6: HLD Round For senior roles (SDE-3+). Candidates design systems like a product catalogue, order management system, or distributed cache. Expect discussion on database schema, microservices, scaling, and trade-offs between SQL and NoSQL.
Step 7: Behavioural and Culture Round Covers conflict resolution, ownership, cross-functional collaboration, and past project impact. Walmart values candidate stories demonstrating scale and business impact.
Tips: The Karat screen is the biggest filter — practice talking through your approach before touching the keyboard. For LLD, master the Observer pattern as interviewers explicitly look for it. Arrays, DP, hashing, and trees cover roughly 70% of all reported DSA questions.
Preparation Resources
Part 1 — OA Questions
1. Maximum Product Excluding One Element Medium
Given an integer array nums, find the maximum product you can obtain by removing exactly one element from the array and multiplying the rest together.
Input: nums = [1, 2, 3, 4]
Output: 24
Explanation: Remove 1, product of [2,3,4] = 24.
Input: nums = [-1, -2, -3, 4]
Output: -6
Explanation: Remove 4, product of [-1,-2,-3] = -6.
Approach: Compute prefix and suffix product arrays. For each index i, the product excluding index i is prefix[i-1] suffix[i+1]. Track the maximum across all indices. Handle the edge case where the array contains zeros carefully.
*Complexity: Time O(n) · Space O(n)
Follow-up: Can you solve it in O(1) extra space?
2. Longest Subarray with Sum Zero Medium
Given an array of integers (possibly negative), find the length of the longest subarray whose elements sum to zero.
Input: arr = [15, -2, 2, -8, 1, 7, 10, 23]
Output: 5
Explanation: Subarray [-2, 2, -8, 1, 7] has sum 0.
Input: arr = [1, 2, 3]
Output: 0
Approach: Use a prefix sum with a hash map storing the first index where each prefix sum value appears. If the current prefix sum has been seen before at index j, then subarray from j+1 to current index has sum zero. Track the maximum such length.
Complexity: Time O(n) · Space O(n)
Follow-up: What if you need to print the actual subarray?
3. Subarray Sum Equals K Medium
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k. The array may contain negative integers.
Input: nums = [1,1,1], k = 2
Output: 2
Input: nums = [1,2,3], k = 3
Output: 2
Approach: Maintain a running prefix sum and a frequency map. At each position, check how many times (currentSum - k) has appeared before in the prefix sums. Add that count to the answer and update the frequency map with the current prefix sum.
Complexity: Time O(n) · Space O(n)
Follow-up: Why does a sliding window not work here when the array has negative numbers?
4. Trapping Rain Water Hard
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
Approach: Use two pointers left and right starting at the ends. Maintain leftMax and rightMax. At each step, process the side with the smaller max boundary. The water trapped at that position is the difference between the boundary max and the bar height. Advance the pointer inward.
Complexity: Time O(n) · Space O(1)
Follow-up: Extend this to a 2D grid (Trapping Rain Water II, LeetCode #407).
5. Gas Station Medium
There are n gas stations arranged in a circle. The gas array gives the fuel available at each station and the cost array gives the fuel needed to travel to the next station. Find the unique starting station index from which you can complete the circuit, or return -1 if impossible.
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Approach: If total gas is less than total cost, no solution exists. Otherwise a solution always exists. Iterate through stations tracking the running tank. Whenever the tank goes negative, reset it to zero and mark the next station as the new candidate start. The candidate at the end is the answer.
Complexity: Time O(n) · Space O(1)
Follow-up: Prove why a solution is always unique when the total gas is at least total cost.
6. Degree of an Array Easy
The degree of an array is the maximum frequency of any element. Find the length of the shortest contiguous subarray that has the same degree as the whole array.
Input: nums = [1,2,2,3,1]
Output: 2
Explanation: degree is 2 (both 1 and 2 appear twice). Shortest subarray with degree 2 is [2,2], length 2.
Input: nums = [1,2,2,3,1,4,2]
Output: 6
Approach: Build three maps tracking the frequency, first occurrence index, and last occurrence index for every element. The degree is the maximum frequency. For every element matching the degree, the subarray length is lastIndex - firstIndex + 1. Return the minimum among all such lengths.
Complexity: Time O(n) · Space O(n)
Follow-up: What if you need the shortest subarray with degree at least k?
Part 2 — Phone Screen Questions
7. First Missing Positive Hard
Given an unsorted integer array nums, return the smallest missing positive integer. Your algorithm must run in O(n) time and use O(1) extra space.
Input: nums = [1,2,0]
Output: 3
Input: nums = [3,4,-1,1]
Output: 2
Input: nums = [7,8,9,11,12]
Output: 1
Approach: Use the array itself as a hash table. Place each number x in position x-1 if x is in range [1, n]. After rearranging, scan for the first index where nums[i] != i+1. That index+1 is the answer. If all positions are correct, the answer is n+1.
Complexity: Time O(n) · Space O(1)
Follow-up: Why does swapping guarantee termination and not infinite loops?
8. Valid Parentheses Easy
Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid. A string is valid if every open bracket is closed by the correct type in the correct order.
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Approach: Use a stack. Push every opening bracket. When you encounter a closing bracket, check if the top of the stack is its matching opener. If not, or if the stack is empty, return false. At the end, the stack must be empty.
Complexity: Time O(n) · Space O(n)
Follow-up: Extend to handle a string with wildcards '*' that can represent any bracket or empty string (LeetCode #678).
9. House Robber II Medium
All houses are arranged in a circle. You cannot rob two adjacent houses. Given the amount of money in each house, return the maximum amount you can rob without alerting the police.
Input: nums = [2,3,2]
Output: 3
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 4.
Approach: The circular constraint means you cannot rob both first and last house. Break into two subproblems: rob houses 0 to n-2, and rob houses 1 to n-1. Apply the standard House Robber DP on each range and return the maximum of both results.
Complexity: Time O(n) · Space O(1)
Follow-up: What if houses are arranged on a tree (LeetCode #337)?
10. Jump Game Medium
Given an integer array nums where each element represents your maximum jump length at that position, return true if you can reach the last index starting from index 0.
Input: nums = [2,3,1,1,4]
Output: true
Input: nums = [3,2,1,0,4]
Output: false
Approach: Track the maximum index reachable so far. At each position i, if i exceeds the maximum reachable index, return false. Otherwise update maxReach to max(maxReach, i + nums[i]). If maxReach reaches or passes the last index, return true.
Complexity: Time O(n) · Space O(1)
Follow-up: What is the minimum number of jumps to reach the last index (LeetCode #45)?
11. LRU Cache Medium
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement get(key) and put(key, value) each in O(1) average time.
Input:
LRUCache(2)
put(1, 1)
put(2, 2)
get(1) → 1
put(3, 3) → evicts key 2
get(2) → -1
get(3) → 3
Approach: Combine a doubly linked list (for O(1) move-to-front and evict-from-tail) with a hash map keyed by cache key pointing to list nodes. On get, move the node to the head. On put, add/update at head; if capacity exceeded, remove tail node and delete its hash map entry.
Complexity: Time O(1) per operation · Space O(capacity)
Follow-up: Implement LFU Cache where the least frequently used item is evicted (LeetCode #460).
12. Subsets II Medium
Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets.
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Input: nums = [0]
Output: [[],[0]]
Approach: Sort the array first. In the backtracking recursion, skip an element at the current recursion level if it equals the previous element (to avoid duplicate subsets). Otherwise include or exclude it normally.
Complexity: Time O(n * 2^n) · Space O(n)
Follow-up: How would you generate all unique permutations of the same array?
13. Top K Frequent Elements Medium
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Approach: Count frequencies with a hash map. Use bucket sort where the bucket index equals the frequency. Iterate buckets from highest to lowest, collecting elements until k are gathered. This avoids an O(n log n) sort.
Complexity: Time O(n) · Space O(n)
Follow-up: Solve it with a min-heap of size k for an O(n log k) solution — when would you prefer that?
Part 3 — Onsite Questions
14. Two Sum Easy
Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Each input has exactly one solution.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Input: nums = [3,2,4], target = 6
Output: [1,2]
Approach: Use a hash map storing value-to-index. For each element, check if (target - current) exists in the map. If yes, return both indices. If no, insert the current element.
Complexity: Time O(n) · Space O(n)
Follow-up: Extend to Three Sum (LeetCode #15) — what is the time complexity?
15. 3Sum Medium
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i, j, k are distinct indices and the three values sum to zero.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = [0,0,0]
Output: [[0,0,0]]
Approach: Sort the array. Fix each element as the first element of a triplet using a loop. Use two pointers on the remaining subarray to find pairs summing to the negation of the fixed element. Skip duplicates by advancing pointers past equal values.
Complexity: Time O(n²) · Space O(1)
Follow-up: Closest Three Sum (LeetCode #16).
16. Merge Intervals Medium
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Approach: Sort intervals by start time. Iterate through sorted intervals. If the current interval's start is greater than the last merged interval's end, add it as a new interval. Otherwise extend the last merged interval's end to the maximum of both ends.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Insert Interval into an already sorted non-overlapping list (LeetCode #57).
17. Number of Islands Medium
Given an m x n 2D binary grid where '1' is land and '0' is water, return the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Input:
grid = [["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
Output: 3
Approach: Iterate every cell. When a '1' is found, increment the island count and run BFS or DFS from that cell, marking all reachable connected '1' cells as visited (mark as '0' or use a visited array). Continue scanning the grid.
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: Max Area of Island (LeetCode #695).
18. Course Schedule Medium
There are numCourses courses labeled 0 to numCourses-1. Given prerequisites pairs, determine if it is possible to finish all courses (i.e., there is no cycle in the prerequisite graph).
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Approach: Build a directed graph from prerequisites. Use Kahn's algorithm (BFS with in-degree tracking) or DFS cycle detection. In Kahn's, start all nodes with in-degree 0, process them, reduce neighbours' in-degrees, enqueue any that hit 0. If processed count equals numCourses, no cycle exists.
Complexity: Time O(V+E) · Space O(V+E)
Follow-up: Return a valid course order (LeetCode #210).
19. Binary Tree Level Order Traversal Medium
Given the root of a binary tree, return the level-order traversal of its node values (i.e., from left to right, level by level).
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Input: root = [1]
Output: [[1]]
Approach: Use a queue initialised with the root. For each iteration, record the current queue size (level size). Process exactly that many nodes, adding their children to the queue, and collect values into a level list. Append each level list to the result.
Complexity: Time O(n) · Space O(n)
Follow-up: Zigzag Level Order Traversal (LeetCode #103).
20. Validate Binary Search Tree Medium
Given the root of a binary tree, determine if it is a valid binary search tree where each node's value is strictly greater than all values in its left subtree and strictly less than all values in its right subtree.
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: Root is 5, right child is 4 which is less than 5.
Approach: Recursively validate each node with an allowed range (min, max). The root has range (-∞, +∞). Going left passes (min, node.val) as the new range; going right passes (node.val, max). If a node's value falls outside its range, the BST is invalid.
Complexity: Time O(n) · Space O(h)
Follow-up: Recover BST with exactly two nodes swapped (LeetCode #99).
21. Lowest Common Ancestor of a BST Medium
Given a BST and two nodes p and q, find their Lowest Common Ancestor (the deepest node that is an ancestor of both p and q).
Input: root = [6,2,8,0,4,7,9], p = 2, q = 8
Output: 6
Input: root = [6,2,8,0,4,7,9], p = 2, q = 4
Output: 2
Approach: Leverage BST ordering. If both p and q are less than the current node, recurse left. If both are greater, recurse right. Otherwise the current node is the split point and is the LCA.
Complexity: Time O(h) · Space O(h)
Follow-up: LCA of a general binary tree without BST property (LeetCode #236).
22. Word Break Medium
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Approach: Create a boolean DP array of size n+1 where dp[i] is true if s[0..i-1] can be segmented. dp[0] is true (empty string). For each position i, check all positions j < i where dp[j] is true and s[j..i-1] is in the dictionary. Use a hash set for O(1) word lookup.
Complexity: Time O(n²) · Space O(n)
Follow-up: Return all possible segmentations (Word Break II, LeetCode #140).
23. Coin Change Medium
Given an array of coin denominations and an integer amount, return the minimum number of coins needed to make up that amount. Return -1 if it is not possible.
Input: coins = [1,5,6,9], amount = 11
Output: 2
Explanation: 5 + 6 = 11.
Input: coins = [2], amount = 3
Output: -1
Approach: Build a bottom-up DP array where dp[i] stores the minimum coins to make amount i. Initialise dp[0] = 0, rest to infinity. For each amount from 1 to target, try every coin denomination c. If c <= i, dp[i] = min(dp[i], dp[i-c] + 1).
Complexity: Time O(amount * n) · Space O(amount)
Follow-up: Count total number of combinations to make the amount (Coin Change 2, LeetCode #518).
24. Unique Paths Medium
A robot starts at the top-left corner of an m x n grid and wants to reach the bottom-right corner. The robot can only move right or down. How many unique paths exist?
Input: m = 3, n = 7
Output: 28
Input: m = 3, n = 2
Output: 3
Approach: dp[i][j] = number of ways to reach cell (i,j). First row and column are all 1 (only one way to reach them). Every other cell dp[i][j] = dp[i-1][j] + dp[i][j-1]. Optimise to a 1D array by updating in place left to right.
Complexity: Time O(m*n) · Space O(n)
Follow-up: Unique Paths II with obstacles (LeetCode #63).
25. Decode Ways Medium
A message encoded with 'A'→'1', 'B'→'2', …, 'Z'→'26'. Given a string of digits, return the number of ways to decode it.
Input: s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12).
Input: s = "226"
Output: 3
Input: s = "06"
Output: 0
Approach: dp[i] = number of ways to decode s[0..i-1]. dp[0]=1 and dp[1]= (s[0]!='0') ? 1 : 0. For each position i>=2, add dp[i-1] if s[i-1]!='0', and add dp[i-2] if the two-digit number s[i-2..i-1] is between 10 and 26.
Complexity: Time O(n) · Space O(1)
Follow-up: What if '*' can represent any digit 1-9 (LeetCode #639)?
26. Spiral Matrix Medium
Given an m x n matrix, return all elements in spiral order (clockwise from top-left).
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Approach: Maintain four boundaries: top, bottom, left, right. Traverse right along top, down along right, left along bottom, up along left. After each direction, shrink the corresponding boundary. Stop when top > bottom or left > right.
Complexity: Time O(m*n) · Space O(1)
Follow-up: Generate a spiral matrix filled with numbers 1 to n² (LeetCode #59).
27. Meeting Rooms II Medium
Given a list of meeting time intervals, find the minimum number of conference rooms required.
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Input: intervals = [[7,10],[2,4]]
Output: 1
Approach: Sort meetings by start time. Use a min-heap of end times. For each meeting, if its start is >= the earliest ending meeting (heap top), reuse that room (pop from heap). Otherwise allocate a new room. Push the current meeting's end time to the heap. Heap size at end is the answer.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Two pointer approach using sorted start and end arrays achieves the same complexity with cleaner code — implement both.
28. Clone Graph Medium
Given a reference to a node in an undirected connected graph, return a deep copy (clone) of the graph.
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
(A new deep-copied graph with the same structure)
Approach: Use a hash map from original node to its clone. BFS from the start node. For each node popped from the queue, iterate its neighbours. If a neighbour has not been cloned yet, clone it, add to map, and enqueue. Add each cloned neighbour to the current clone's neighbour list.
Complexity: Time O(V+E) · Space O(V)
Follow-up: What changes if the graph can contain cycles versus a DAG?
29. Minimum Path Sum Medium
Given an m x n grid filled with non-negative numbers, find the path from top-left to bottom-right (only right or down moves) that minimises the sum of numbers along the path.
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1 = 7.
Approach: Update the grid in-place (or use a 1D DP array). For the first row, accumulate left to right. For the first column, accumulate top to bottom. Each remaining cell becomes min(cell above, cell to the left) + current cell value.
Complexity: Time O(m*n) · Space O(1) (in-place)
Follow-up: What if you could also move diagonally?
30. Serialize and Deserialize Binary Tree Hard
Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree structure.
Input: root = [1,2,3,null,null,4,5]
Serialized: "1,2,null,null,3,4,null,null,5,null,null"
Output after deserialization: same tree structure
Approach: For serialization, use preorder DFS. Output each node's value followed by its left and right subtrees. Use a sentinel (e.g., "null") for null nodes. For deserialization, split the string into tokens and use a recursive preorder reconstruction consuming tokens from a queue.
Complexity: Time O(n) · Space O(n)
Follow-up: Serialize and Deserialize BST (LeetCode #449) — how does the BST property allow a more compact format?
31. Find the Duplicate Number Medium
Given an array nums of n+1 integers where each integer is in [1, n], there is exactly one repeated number. Find it without modifying the array and using only constant extra space.
Input: nums = [1,3,4,2,2]
Output: 2
Input: nums = [3,1,3,4,2]
Output: 3
Approach: Treat the array as a linked list where nums[i] is the next pointer from index i. The duplicate creates a cycle. Use Floyd's cycle detection: a slow pointer advances one step and a fast pointer two steps until they meet. Then reset slow to index 0, advance both one step at a time — their meeting point is the duplicate.
Complexity: Time O(n) · Space O(1)
Follow-up: What if there could be multiple duplicates?
32. Group Anagrams Medium
Given an array of strings strs, group the anagrams together. Return them in any order.
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Approach: Use a hash map keyed by the sorted version of each string (or a character count tuple). All anagrams share the same key. Append each string to its group's list. Return all values.
Complexity: Time O(n * k log k) where k is max string length · Space O(n*k)
Follow-up: Use a character frequency tuple as key to achieve O(n*k) time.
33. Container With Most Water Medium
Given n vertical lines of heights stored in height[], find two lines that together with the x-axis form a container holding the most water.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Input: height = [1,1]
Output: 1
Approach: Two pointers at both ends. Compute area as min(height[left], height[right]) (right - left). Move the pointer pointing to the shorter line inward (moving the taller line cannot increase area). Track the maximum area.
*Complexity: Time O(n) · Space O(1)
Follow-up: Why is it safe to discard the shorter line and not explore all its pairings?
34. Edit Distance Hard
Given two strings word1 and word2, return the minimum number of operations (insert, delete, or replace) to convert word1 to word2.
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse→rorse (replace h→r), rorse→rose (delete r), rose→ros (delete e).
Input: word1 = "intention", word2 = "execution"
Output: 5
Approach: dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]. If the characters match, dp[i][j] = dp[i-1][j-1]. Otherwise dp[i][j] = 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)).
Complexity: Time O(m*n) · Space O(m*n) reducible to O(min(m,n))
Follow-up: Recover the actual sequence of operations (alignment problem).
35. Pacific Atlantic Water Flow Medium
Given an m x n island height matrix, water flows from a cell to adjacent cells with equal or lower height. Return all cells from which water can reach both the Pacific (top/left border) and the Atlantic (bottom/right border).
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Approach: Run reverse BFS (water flows uphill from ocean borders). Pacific BFS starts from the top row and left column; Atlantic from the bottom row and right column. A cell is reachable from an ocean if its height is >= the calling cell's height. Cells in both reachable sets are the answer.
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: What if there are multiple land masses separated by water?
36. Jump Game II Medium
Given a 0-indexed array of non-negative integers nums where each element is the maximum jump from that position, return the minimum number of jumps to reach the last index.
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Jump from index 0 to 1 (value 3), then to the last index.
Input: nums = [2,3,0,1,4]
Output: 2
Approach: Greedy BFS-style. Maintain currentEnd (furthest reachable in the current jump) and farthest (furthest reachable with one more jump). At each position up to currentEnd, update farthest. When currentEnd is reached, increment jumps and set currentEnd to farthest.
Complexity: Time O(n) · Space O(1)
Follow-up: What if some positions are blocked (value 0) — how do you detect whether the end is reachable?
37. Maximum Depth of Binary Tree Easy
Given the root of a binary tree, return its maximum depth (the number of nodes along the longest path from the root to a farthest leaf node).
Input: root = [3,9,20,null,null,15,7]
Output: 3
Input: root = [1,null,2]
Output: 2
Approach: Recursive DFS: return 0 for null, otherwise return 1 + max(depth(left), depth(right)). Iterative BFS also works using a level-order traversal and counting levels.
Complexity: Time O(n) · Space O(h)
Follow-up: Minimum depth of a binary tree (LeetCode #111) — why is minimum depth trickier than maximum depth?
38. Path Sum II Medium
Given the root of a binary tree and a target sum, return all root-to-leaf paths where the sum of the nodes equals targetSum.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Approach: DFS with a running path list and remaining sum. At each node, add it to the path and subtract from remaining. At a leaf node with remaining = 0, add a copy of the path to results. Backtrack by removing the node from the path when returning.
Complexity: Time O(n²) · Space O(n)
Follow-up: Path Sum III where the path does not need to start from root or end at a leaf (LeetCode #437).
39. Word Ladder Hard
Given a beginWord, endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where each intermediate word must be in the wordList.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit→hot→dot→dog→cog (5 words).
Approach: BFS from beginWord. For each word in the queue, generate all possible one-letter mutations. If a mutation is in the word set and not yet visited, add it to the queue and mark visited. Return the level count when endWord is found.
Complexity: Time O(n * m²) where n = word count, m = word length · Space O(n*m)
Follow-up: Find all shortest transformation sequences (Word Ladder II, LeetCode #126).
40. LFU Cache Hard
Design a data structure for a Least Frequently Used (LFU) cache. get and put must each run in O(1). When capacity is reached, evict the least frequently used item, breaking ties by evicting the least recently used.
Input:
LFUCache(2)
put(1, 1)
put(2, 2)
get(1) → 1 (freq[1]=2, freq[2]=1)
put(3, 3) → evicts key 2
get(2) → -1
get(3) → 3
put(4, 4) → evicts key 1 (freq[1]=2, freq[3]=2, but key 1 was least recently used)
Approach: Maintain a key→(value, frequency) map, a frequency→doubly-linked-list-of-keys map (LRU order within a frequency bucket), and a minFreq counter. On get, increment the key's frequency and move it to the higher frequency bucket. On put, if full, evict the tail of the minFreq bucket.
Complexity: Time O(1) per operation · Space O(capacity)
Follow-up: Why does the LFU eviction strategy not always outperform LRU in practice?
41. Rotate Image Medium
Given an n x n 2D matrix representing an image, rotate it 90 degrees clockwise in-place.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Approach: First transpose the matrix (swap matrix[i][j] with matrix[j][i]). Then reverse each row. Together these two operations produce a clockwise 90-degree rotation.
Complexity: Time O(n²) · Space O(1)
Follow-up: How do you rotate 90 degrees counter-clockwise?
42. Two Sum IV — Input is a BST Easy
Given the root of a BST and an integer k, return true if there exist two elements in the BST such that their sum equals k.
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
Approach: DFS traversal with a hash set. For each node, check if (k - node.val) is already in the set. If yes, return true. Otherwise insert node.val into the set and continue.
Complexity: Time O(n) · Space O(n)
Follow-up: How can you leverage the BST structure to avoid the hash set (use iterators for an O(n) time, O(h) space solution)?
43. Find Median from Data Stream Hard
Design a data structure that supports adding integers from a stream and retrieving the median of all elements seen so far in O(log n) add and O(1) find.
MedianFinder()
addNum(1)
addNum(2)
findMedian() → 1.5
addNum(3)
findMedian() → 2.0
Approach: Use two heaps — a max-heap (lower half) and a min-heap (upper half). Always keep their sizes balanced (differ by at most 1). On each insert, add to the max-heap first, then move its max to the min-heap, then rebalance if sizes differ. Median is either the max-heap top (odd count) or the average of both tops (even count).
Complexity: Time O(log n) add · O(1) findMedian · Space O(n)
Follow-up: Sliding Window Median for a window of size k (LeetCode #480).
44. Design Parking Lot Medium
Design a multi-floor parking lot with two types of spaces: type-2 for two-wheelers and type-4 for four-wheelers. Support parking a vehicle, freeing a space, and querying available spots. Vehicles must be assigned the closest available slot.
ParkingLot(floors=3, rows=5, cols=10)
park(vehicleType=2, vehicleId="MH12AB1234") → Slot(floor=0, row=0, col=0)
park(vehicleType=4, vehicleId="MH12AB5678") → Slot(floor=0, row=0, col=5)
free(vehicleId="MH12AB1234")
park(vehicleType=2, vehicleId="NEW123") → Slot(floor=0, row=0, col=0)
Approach: Model Slot, Floor, ParkingLot as classes. Each floor maintains a sorted set (min-heap or TreeSet) of available slots per type. On park, pop the smallest available slot; on free, re-insert the slot back. Use a map from vehicleId to Slot for efficient freeing.
Complexity: Time O(log n) per park/free operation
Follow-up: Add support for reserved slots and monthly pass vehicles.
45. Reformat Date Easy
Given a date string in the format "Day Month Year" (e.g., "20th Oct 2052"), reformat it to "YYYY-MM-DD" format.
Input: date = "20th Oct 2052"
Output: "2052-10-20"
Input: date = "6th Jun 1933"
Output: "1933-06-06"
Approach: Split the string into parts. Extract the numeric day by stripping the ordinal suffix (st, nd, rd, th). Map the month abbreviation to its two-digit number using a lookup table. Format as YYYY-MM-DD with zero-padding.
Complexity: Time O(1) · Space O(1)
Follow-up: Reformat between multiple date string formats dynamically.
46. Longest Increasing Subsequence Medium
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: [2,3,7,101] has length 4.
Input: nums = [0,1,0,3,2,3]
Output: 4
Approach: Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number, binary search in tails for the leftmost value >= current. Replace it, or append if current is larger than all. The length of tails is the LIS length.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Print the actual subsequence, not just its length.
47. Number of Ways to Reach a Position After Exactly k Steps Medium
Given integers startPos, endPos, and k, return the number of different ways to reach endPos from startPos in exactly k steps on an infinite number line, where each step moves left or right by 1. Return the answer modulo 10^9 + 7.
Input: startPos = 1, endPos = 2, k = 3
Output: 3
Explanation: Three paths of 3 steps each reach position 2 from position 1.
Input: startPos = 2, endPos = 5, k = 10
Output: 0
Approach: Let diff = |endPos - startPos|. We need (k - diff) to be non-negative and even (so remaining steps cancel out). If not, return 0. Otherwise the answer is C(k, (k+diff)/2) mod 10^9+7 — the number of ways to choose right-steps from k total steps. Alternatively, memoised recursion: ways(pos, stepsLeft) = ways(pos-1, stepsLeft-1) + ways(pos+1, stepsLeft-1).
Complexity: Time O(k²) with memoization · Space O(k²)
Follow-up: How does the combinatorics approach achieve O(k) time?
48. Inventory Management — Maximum Units on a Truck Easy
Given a list of box types where boxTypes[i] = [numberOfBoxes, numberOfUnitsPerBox] and a truck size, return the maximum total number of units you can put on the truck.
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: Load 1 box of 3 units, 2 boxes of 2 units = 1+2 = 3 boxes, 4-3=1 more box of 1 unit = 3+2+2+1 = 8.
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Approach: Greedy — sort box types by units per box in descending order. Load as many boxes of the highest unit type as possible before moving to the next type. Stop when the truck is full.
Complexity: Time O(n log n) · Space O(1)
Follow-up: What if each box type has a weight constraint and the truck has a weight limit?
49. Minimum Number of Platforms Required Medium
Given arrays of arrival and departure times of all trains at a station, find the minimum number of platforms required so no train waits.
Input: arr = [900,940,950,1100,1500,1800], dep = [910,1200,1120,1130,1900,2000]
Output: 3
Input: arr = [900,1100,1235], dep = [1000,1200,1240]
Output: 1
Approach: Sort both arrays. Use two pointers. Increment platform count when a train arrives before another departs (arr[i] <= dep[j]); otherwise decrement and advance j. Track the maximum platform count reached.
Complexity: Time O(n log n) · Space O(1)
Follow-up: Equivalent to Meeting Rooms II — identify the structural similarity.
50. Design an Inventory Management System Medium
Design a low-level inventory management system for a retail store. Products have stock levels. Support operations: addStock, removeStock, getStock. Notify registered observers (like a reorder service or UI dashboard) whenever stock falls below a threshold.
InventorySystem system = new InventorySystem();
system.addObserver(new ReorderObserver(threshold=10));
system.addProduct("apple", stock=50);
system.removeStock("apple", 45);
// Observer fires: "apple stock is 5, below threshold"
Approach: Product class holds id, name, and quantity. InventorySystem maintains a map of productId→Product and a list of StockObserver. On every stock mutation, check if stock < threshold and notify all observers. This is a direct application of the Observer design pattern. The ReorderObserver can trigger a restocking API or send an alert.
Complexity: Time O(k) per mutation where k = number of observers · Space O(n)
Follow-up: How would you make the system distributed — multiple warehouse nodes each holding partial inventory?
Preparation Tips
Focus your Walmart preparation on three areas: strong DP fundamentals (house robber family, coin change, edit distance), graph algorithms (BFS/DFS, topological sort, cycle detection), and one design pattern for LLD (Observer pattern appears in almost every reported LLD round at Walmart). Practice explaining your approach before coding — the Karat phone screen in particular evaluates communication as heavily as code correctness.
Join Telegram group to connect with other candidates preparing for Walmart Global Tech and get the latest OA questions.