Searching and Sorting: Get the fixed point in an array
Problem Statement: You are given an sorted ascending array, you need to find the fixed point. A fixed point is an element in the array, such that index i and arr[i] are same. Example Input: {-7, -4, 0, 3, 6} Output: 3 Because arr[3] == 3 Solution There are multiple ways to solve this problem: […]
Strings: Recursively print all sentences that can be formed from list of word lists
Problem Statement: You are given list of words, you need to print all the combinations of phrases that can be formed by picking one word from each list. Example s[][] = {{“I”, “You”}, {“love”},{“programming”}} OUTPUT “I love programing” “You love programming” Solution We need to take the idea of depth first traversal. We start from […]
Strings: Find minimum operations required to transform a string into another string
Problem Statement: You are given 2 strings, you need to convert str1 to str2 by only moving a character from str1 to front. If the string can be transformed, then return the min number of operations required. Example Str 1 = ADCB Str 2 = ABCD Output: 3 Move C to the front -> CADB […]
Strings: Remove all consecutive duplicates from the string
Problem Statement: You are given a string S, you have to remove all the consecutive string. Example Input: aabb Output: ab Solution The solution is very simple and can be solved using recursion. Base case will be, if the string is empty return. else compare the adj character and the present character. If they are […]
Strings: Minimum Window Substring
Problem Statement: You are given 2 strings s1 and s2. You need to find the smallest substring in s1 that has all the characters of s2. Example Input: s = "ARTYUIBANC", t = "ABC" Output: "BANC" Solution This problem can be solved by number of methods. Method 1: Brute Force Approach In this approach, generate […]
Minimum characters to be added at beginning to make string palindrome
Problem Statement: You are given a string, you need to tell minimum characters to be added at the beginning to make the string palindrome. Example Input : str = “ABC” Output : 2 Because we can make the string “ABC” palindrome by adding “CB” at the beginning of the string. Solution This problem can be […]
Strings: Check if it is possible to re-arrange characters in a string, such a way that no two adjacent are same
Problem Statement: You are given a string, you need to check if ti is possible to rearrange the string such that no two adjacent characters are same. Example Input: aab Output: Yes Why? You can swap the string to “aba”. So no 2 adjacent characters are same. Solution The solution is very simple. We need […]
Strings: Smallest distinct window
Problem Statement: You are given a string ‘s’. You need to find the smallest window length that contains all the characters of the string. Example Input : "aaab" Output : 2 Sub string : "ab" Solution We can solve this problem using Sliding Window Approach. For that we need 2 pointers start and end. Start […]
Strings: Find the longest common subsequence between two strings.
Problem Statement: You are given 2 strings you need to return the longest common subsequence between two strings. Example str1 = ABC str2 = AC Output: 2 The LCS of the 2 strings is "AC" hence 2. Solution The solution is similar to LCS, but here we have 2 different strings. So here we have […]
Strings: Minimum swaps required for bracket balancing
Problem Statement: You are given a string with 2N characters consisting of equally “[” and “]” brackets. They are unbalanced, you need to find the minimum swaps required for them to make balanced. Example Input : []][][ Output : 2 Swap position 3 and 4 [][]][ Then swap position 5 and 6 [][][] Solution The […]