Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Meesho. 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: Number of Ways to Form a Target String Given a Dictionary

You are given a list of strings of the same length words and a string target. Your task is to form target using the given words under the following rules: target should be formed from left to right. To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k]. Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string. Repeat the process until you form the string target. Notice that you can use multiple characters from the same string in words provided the conditions above are met. Return the number of ways to form target from words. Since the answer may be too large, return it modulo 109 + 7. Example 1: Input: words = ["acca","bbbb","caca"], target = "aba" Output: 6 Explanation: There are 6 ways to form target. "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca") Example 2: Input: words = ["abba","baab"], target = "bab" Output: 4 Explanation: There are 4 ways to form target. "bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba") "bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab") "bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab") "bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab") Constraints: 1 <= words.length <= 1000 1 <= words[i].length <= 1000 All strings in words have the same length. 1 <= target.length <= 1000 words[i] and target contain only lowercase English letters.

Topics: Array, String, Dynamic Programming

Problem #2: Minimum Edge Reversals So Every Node Is Reachable

There is a simple directed graph with n nodes labeled from 0 to n - 1. The graph would form a tree if its edges were bi-directional. You are given an integer n and a 2D integer array edges, where edges[i] = [ui, vi] represents a directed edge going from node ui to node vi. An edge reversal changes the direction of an edge, i.e., a directed edge going from node ui to node vi becomes a directed edge going from node vi to node ui. For every node i in the range [0, n - 1], your task is to independently calculate the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges. Return an integer array answer, where answer[i] is the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges. Example 1: Input: n = 4, edges = [[2,0],[2,1],[1,3]] Output: [1,1,0,2] Explanation: The image above shows the graph formed by the edges. For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0. So, answer[0] = 1. For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1. So, answer[1] = 1. For node 2: it is already possible to reach any other node starting from node 2. So, answer[2] = 0. For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3. So, answer[3] = 2. Example 2: Input: n = 3, edges = [[1,2],[2,0]] Output: [2,0,1] Explanation: The image above shows the graph formed by the edges. For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0. So, answer[0] = 2. For node 1: it is already possible to reach any other node starting from node 1. So, answer[1] = 0. For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2. So, answer[2] = 1. Constraints: 2 <= n <= 105 edges.length == n - 1 edges[i].length == 2 0 <= ui == edges[i][0] < n 0 <= vi == edges[i][1] < n ui != vi The input is generated such that if the edges were bi-directional, the graph would be a tree.

Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph

Problem #3: Count Subarrays With Fixed Bounds

You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray of nums is a subarray that satisfies the following conditions: The minimum value in the subarray is equal to minK. The maximum value in the subarray is equal to maxK. Return the number of fixed-bound subarrays. A subarray is a contiguous part of an array. Example 1: Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5 Output: 2 Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2]. Example 2: Input: nums = [1,1,1,1], minK = 1, maxK = 1 Output: 10 Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays. Constraints: 2 <= nums.length <= 105 1 <= nums[i], minK, maxK <= 106

Topics: Array, Queue, Sliding Window, Monotonic Queue

Problem #4: Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip. Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus. You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips. Example 1: Input: time = [1,2,3], totalTrips = 5 Output: 3 Explanation: - At time t = 1, the number of trips completed by each bus are [1,0,0]. The total number of trips completed is 1 + 0 + 0 = 1. - At time t = 2, the number of trips completed by each bus are [2,1,0]. The total number of trips completed is 2 + 1 + 0 = 3. - At time t = 3, the number of trips completed by each bus are [3,1,1]. The total number of trips completed is 3 + 1 + 1 = 5. So the minimum time needed for all buses to complete at least 5 trips is 3. Example 2: Input: time = [2], totalTrips = 1 Output: 2 Explanation: There is only one bus, and it will complete its first trip at t = 2. So the minimum time needed to complete 1 trip is 2. Constraints: 1 <= time.length <= 105 1 <= time[i], totalTrips <= 107

Topics: Array, Binary Search

Problem #5: Minimum Number of Taps to Open to Water a Garden

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e., the length of the garden is n). There are n + 1 taps located at points [0, 1, ..., n] in the garden. Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open. Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1. Example 1: Input: n = 5, ranges = [3,4,1,1,0,0] Output: 1 Explanation: The tap at point 0 can cover the interval [-3,3] The tap at point 1 can cover the interval [-3,5] The tap at point 2 can cover the interval [1,3] The tap at point 3 can cover the interval [2,4] The tap at point 4 can cover the interval [4,4] The tap at point 5 can cover the interval [5,5] Opening Only the second tap will water the whole garden [0,5] Example 2: Input: n = 3, ranges = [0,0,0,0] Output: -1 Explanation: Even if you activate all the four taps you cannot water the whole garden. Constraints: 1 <= n <= 104 ranges.length == n + 1 0 <= ranges[i] <= 100

Topics: Array, Dynamic Programming, Greedy

Problem #6: Number of Visible People in a Queue

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person. A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]). Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue. Example 1: Input: heights = [10,6,8,5,11,9] Output: [3,1,2,1,1,0] Explanation: Person 0 can see person 1, 2, and 4. Person 1 can see person 2. Person 2 can see person 3 and 4. Person 3 can see person 4. Person 4 can see person 5. Person 5 can see no one since nobody is to the right of them. Example 2: Input: heights = [5,1,2,3,10] Output: [4,1,1,1,0] Constraints: n == heights.length 1 <= n <= 105 1 <= heights[i] <= 105 All the values of heights are unique.

Topics: Array, Stack, Monotonic Stack