Introduction

In this blog post, we'll share the most commonly asked coding interview questions at PhonePe. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Count the Number of Arrays with K Matching Adjacent Elements

You are given three integers n, m, k. A good array arr of size n is defined as follows: Each element in arr is in the inclusive range [1, m]. Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i]. Return the number of good arrays that can be formed. Since the answer may be very large, return it modulo 109 + 7. Example 1: Input: n = 3, m = 2, k = 1 Output: 4 Explanation: There are 4 good arrays. They are [1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1]. Hence, the answer is 4. Example 2: Input: n = 4, m = 2, k = 2 Output: 6 Explanation: The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1]. Hence, the answer is 6. Example 3: Input: n = 5, m = 2, k = 0 Output: 2 Explanation: The good arrays are [1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2. Constraints: 1 <= n <= 105 1 <= m <= 105 0 <= k <= n - 1

Topics: Math, Combinatorics

Problem #3: Find Beautiful Indices in the Given Array II

You are given a 0-indexed string s, a string a, a string b, and an integer k. An index i is beautiful if: 0 <= i <= s.length - a.length s[i..(i + a.length - 1)] == a There exists an index j such that: 0 <= j <= s.length - b.length s[j..(j + b.length - 1)] == b |j - i| <= k Return the array that contains beautiful indices in sorted order from smallest to largest. Example 1: Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 Output: [16,33] Explanation: There are 2 beautiful indices: [16,33]. - The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15. - The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15. Thus we return [16,33] as the result. Example 2: Input: s = "abcd", a = "a", b = "a", k = 4 Output: [0] Explanation: There is 1 beautiful index: [0]. - The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4. Thus we return [0] as the result. Constraints: 1 <= k <= s.length <= 5 105 1 <= a.length, b.length <= 5 105 s, a, and b contain only lowercase English letters.

Topics: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function

Problem #4: Frequencies of Shortest Supersequences

You are given an array of strings words. Find all shortest common supersequences (SCS) of words that are not permutations of each other. A shortest common supersequence is a string of minimum length that contains each string in words as a subsequence. Return a 2D array of integers freqs that represent all the SCSs. Each freqs[i] is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order. Example 1: Input: words = ["ab","ba"] Output: [[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] Explanation: The two SCSs are "aba" and "bab". The output is the letter frequencies for each one. Example 2: Input: words = ["aa","ac"] Output: [[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] Explanation: The two SCSs are "aac" and "aca". Since they are permutations of each other, keep only "aac". Example 3: Input: words = ["aa","bb","cc"] Output: [[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] Explanation: "aabbcc" and all its permutations are SCSs. Constraints: 1 <= words.length <= 256 words[i].length == 2 All strings in words will altogether be composed of no more than 16 unique lowercase letters. All strings in words are unique.

Topics: Array, String, Bit Manipulation, Graph, Topological Sort, Enumeration

Problem #5: Maximum Amount of Money Robot Can Earn

You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time. The grid contains a value coins[i][j] in each cell: If coins[i][j] >= 0, the robot gains that many coins. If coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value of coins[i][j] coins. The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells. Note: The robot's total coins can be negative. Return the maximum profit the robot can gain on the route. Example 1: Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]] Output: 8 Explanation: An optimal path for maximum coins is: Start at (0, 0) with 0 coins (total coins = 0). Move to (0, 1), gaining 1 coin (total coins = 0 + 1 = 1). Move to (1, 1), where there's a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1). Move to (1, 2), gaining 3 coins (total coins = 1 + 3 = 4). Move to (2, 2), gaining 4 coins (total coins = 4 + 4 = 8). Example 2: Input: coins = [[10,10,10],[10,10,10]] Output: 40 Explanation: An optimal path for maximum coins is: Start at (0, 0) with 10 coins (total coins = 10). Move to (0, 1), gaining 10 coins (total coins = 10 + 10 = 20). Move to (0, 2), gaining another 10 coins (total coins = 20 + 10 = 30). Move to (1, 2), gaining the final 10 coins (total coins = 30 + 10 = 40). Constraints: m == coins.length n == coins[i].length 1 <= m, n <= 500 -1000 <= coins[i][j] <= 1000

Topics: Array, Dynamic Programming, Matrix

Problem #6: Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi. Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue). Example 1: Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue. Example 2: Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]] Constraints: 1 <= people.length <= 2000 0 <= hi <= 106 0 <= ki < people.length It is guaranteed that the queue can be reconstructed.

Topics: Array, Binary Indexed Tree, Segment Tree, Sorting

Problem #7: Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity better than O(n2). Example 1: Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13 Example 2: Input: matrix = [[-5]], k = 1 Output: -5 Constraints: n == matrix.length == matrix[i].length 1 <= n <= 300 -109 <= matrix[i][j] <= 109 All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order. 1 <= k <= n2 Follow up: Could you solve the problem with a constant memory (i.e., O(1) memory complexity)? Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

Topics: Array, Binary Search, Sorting, Heap (Priority Queue), Matrix

Problem #8: Split Array into Consecutive Subsequences

You are given an integer array nums that is sorted in non-decreasing order. Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true: Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer). All subsequences have a length of 3 or more. Return true if you can split nums according to the above conditions, or false otherwise. A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not). Example 1: Input: nums = [1,2,3,3,4,5] Output: true Explanation: nums can be split into the following subsequences: [1,2,3,3,4,5] --> 1, 2, 3 [1,2,3,3,4,5] --> 3, 4, 5 Example 2: Input: nums = [1,2,3,3,4,4,5,5] Output: true Explanation: nums can be split into the following subsequences: [1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5 [1,2,3,3,4,4,5,5] --> 3, 4, 5 Example 3: Input: nums = [1,2,3,4,4,5] Output: false Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more. Constraints: 1 <= nums.length <= 104 -1000 <= nums[i] <= 1000 nums is sorted in non-decreasing order.

Topics: Array, Hash Table, Greedy, Heap (Priority Queue)

Problem #9: Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0. Constraints: 1 <= k <= num.length <= 105 num consists of only digits. num does not have any leading zeros except for the zero itself.

Topics: String, Stack, Greedy, Monotonic Stack

Problem #10: Most Stones Removed with Same Row or Column

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed. Example 1: Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5 Explanation: One way to remove 5 stones is as follows: 1. Remove stone [2,2] because it shares the same row as [2,1]. 2. Remove stone [2,1] because it shares the same column as [0,1]. 3. Remove stone [1,2] because it shares the same row as [1,0]. 4. Remove stone [1,0] because it shares the same column as [0,0]. 5. Remove stone [0,1] because it shares the same row as [0,0]. Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane. Example 2: Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove stone [2,2] because it shares the same row as [2,0]. 2. Remove stone [2,0] because it shares the same column as [0,0]. 3. Remove stone [0,2] because it shares the same row as [0,0]. Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane. Example 3: Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so you cannot remove it. Constraints: 1 <= stones.length <= 1000 0 <= xi, yi <= 104 No two stones are at the same coordinate point.

Topics: Hash Table, Depth-First Search, Union Find, Graph