Competitive Programming

Hope you have solved yesterday's and today's questions, below is the solutions. Question 47: Minimum Path Sum in CPP Solution: https://www.prodevelopertutorial.com/minimum-path-sum-in-cpp/ Question 48: Simplify Path CPP Solution: https://www.prodevelopertutorial.com/simplify-path-cpp/ Please comment with your answers in the comment section of the above post. Feedbacks are greatly appreciated.

Day 48 Question: Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo". Difficulty: Medium

Day 47 Question: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. Difficulty: Medium Companies Asked: Amazon

Hope you have solved today's questions, below is the solutions. Question: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. Now consider if some obstacles are added to the grids. How many unique paths would there be? Solution: https://www.prodevelopertutorial.com/unique-paths-ii-in-c/ Please comment with your answers in the comment section of the above post.

Day 46 Question: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. Note: m and n will be at most 100. Example 1: Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right Difficulty: Medium Companies Asked: Paytm, Microsoft, Walmart

Hope you have solved previous questions, below are the solutions. Please update your answers in the appropriate links. ========================================= Day 39th Question: Merge Intervals Solution: https://www.prodevelopertutorial.com/merge-intervals-in-c/ ========================================= Day 40th Question: Reverse Linked List iterative and recursive in C++ Solution: https://www.prodevelopertutorial.com/reverse-linked-list-iterative-and-recursive-in-c/ ========================================= Day 41st Question: Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order in C++ Solution: https://www.prodevelopertutorial.com/given-a-positive-integer-n-generate-a-square-matrix-filled-with-elements-from-1-to-n2-in-spiral-order-in-c/ ========================================= Day 42nd Question: Wildcard Matching in C++ Solution: https://www.prodevelopertutorial.com/wildcard-matching-in-c/ ========================================= Day 43rd Question: Find Intersection of Two Linked Lists in c++ Solution: https://www.prodevelopertutorial.com/find-intersection-of-two-linked-lists-in-c/ ========================================= Day 44th Question: Rotate linked list by k nodes in C++ Solution: https://www.prodevelopertutorial.com/rotate-linked-list-by-k-nodes-in-c/ ========================================= Day 45th Question: Unique Paths Solution in C++ Solution: https://www.prodevelopertutorial.com/unique-paths-solution-in-c/

Day 45 Question: A robot is located at the top-left corner of a m x n grid . The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid ]. How many possible unique paths are there? Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right Example 2: Input: m = 7, n = 3 Output: 28 Difficulty: Medium Companies Asked: Paytm, Microsoft, Amazon, Walmart

Day 28th Question: Merge k sorted linked lists and return it as one sorted list. Solution: https://www.prodevelopertutorial.com/merge-k-sorted-linked-lists-and-return-it-as-one-sorted-list/ ========================================= Day 37th Question: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Solution: https://www.prodevelopertutorial.com/given-a-matrix-of-m-x-n-elements-m-rows-n-columns-return-all-elements-of-the-matrix-in-spiral-order-in-cpp/ ========================================= Day 38th Question: Given an array of non-negative integers determine if you are able to reach the last index in C++ Solution: https://www.prodevelopertutorial.com/given-an-array-of-non-negative-integers-determine-if-you-are-able-to-reach-the-last-index-in-c/

Day 44 Question: Given a linked list, rotate the list to the right by k places, where k is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL Difficulty: Medium

Hope you have solved previous questions, below are the solutions Day 32nd Question: Given a collection of numbers that might contain duplicates, return all possible unique permutations. Solution: https://www.prodevelopertutorial.com/given-a-collection-of-distinct-integers-return-all-possible-permutations-2/ ========================================= Day 33rd Question: Given an n x n 2D matrix rotate it by 90 degrees (clockwise) in C++ in place Solution: https://www.prodevelopertutorial.com/given-an-n-x-n-2d-matrix-rotate-it-by-90-degrees-clockwise-in-c-in-place/ ========================================= Day 34th Question: Group Anagrams in C++ Solution: https://www.prodevelopertutorial.com/group-anagrams-in-c/ ========================================= Day 35th Question: Rain water trapping in C++ Solution: https://www.prodevelopertutorial.com/rain-water-trapping-in-c/ ========================================= Day 36th Question: Implement pow(x, n), which calculates x raised to the power n (xn) in C++ Solution: https://www.prodevelopertutorial.com/implement-powx-n-which-calculates-x-raised-to-the-power-n-xn-in-c/

Day 43 Question: Write a program to find the node at which the intersection of two singly linked lists Sorted and Unsorted. For example, the following two linked lists: A: a1 → a2 ↘️ c1 → c2 → c3 ↗️ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. Difficulty: Easy Companies Asked: Accolite, Microsoft, Amazon, D-E-Shaw, Goldman Sachs, MakeMyTrip, Qualcomm, Zopper

Day 42 Question: Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *. Example 1: Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence. Example 3: Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'. Example 4: Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce". Example 5: Input: s = "acdcb" p = "a*c?b" Output: false Difficulty: Hard Companies Asked: Microsoft, Amazon, Ola Cabs, Walmart, InMobi, United Health Group

Day 41 Question: Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Difficulty: Medium Companies Asked: Microsoft JP Morgan Amazon

Day 40 Question: Reverse Linked List Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? Difficulty: Easy Quote: Be like a duck, paddling and working hard in the water, but what everyone sees is a smiling, calm face.

Day 39 Question: Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considerred overlapping. Difficulty: Medium Company asked: Google, Amazon

Hope you have solved Day 31st question. Day 31st Question: Given a collection of distinct integers, return all possible permutations. Solution: https://www.prodevelopertutorial.com/given-a-collection-of-distinct-integers-return-all-possible-permutations/ Please comment with your answers in the comment section of the above post.

Day 38 Question: Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. Difficulty: Medium Company asked: Moonfrog Labs, Amazon, Housing.com, Walmart Quote: The difference between ordinary and extraordinary is that little extra

Day 37 Question: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2: Input: [ [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] Difficulty: Medium Company asked: Paytm, Microsoft, Morgan Stanley, D-E-Shaw, Oracle, Snapdeal, MAQ Software, MakeMyTrip Quote: There is no substitute for hard work.

Day 36 Question: Implement pow(x, n), which calculates x raised to the power n (xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Note: -100.0 < x < 100.0 n is a 32-bit signed integer, within the range [−231, 231 − 1] Difficulty: Medium Companies Asked: Microsoft MakeMyTrip Quote: Opportunities are usually disguised as hard work, so most people don't recognize them.

Day 35 Question: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Examples: Input: arr[] = {2, 0, 2} Output: 2 Structure is like below | | |_| We can trap 2 units of water in the middle gap. Input: arr[] = {3, 0, 0, 2, 0, 4} Output: 10 Structure is like below | | | | | | |__|_| We can trap "3*2 units" of water between 3 an 2, "1 unit" on top of bar 2 and "3 units" between 2 and 4. See below diagram also. Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 | | || | _|_||_|||||| Trap "1 unit" between first 1 and 2, "4 units" between first 2 and 3 and "1 unit" between second last 1 and last 2 Difficulty: HARD Companies Asked: Accolite Microsoft Amazon D-E-Shaw Payu Adobe Try with below Constraints: Time Complexity: O(n) Auxiliary Space: O(n) Motivational quote for the day: Once you have commitment, you need the discipline and hard work to get you there.