My software development journey
Given two strings, how to check one is a rotation of the other? For example consider the strings “abcd”, “cdab”. If we rotate any string twice, you will get the other string. A simple way of solving this problem is to rotate one string, and see if it matches the other string. But we don’t know…
Given an array numbers, we have to join them in such a way that it forms the biggest number. For example consider the simple three element array [10,3,2], they can be joined in following ways 1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number. To solve this problem we definitely…
Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}. For example consider N = 4, K = 3, the possible combinations are [ [1, 2, 3] [1, 2, 4] [2, 3, 4] [1, 3, 4] ] Let us look how to solve this combination problem.…
Given the base and exponent, how do we implement the pow(base,exp) function efficiently? For example pow(2.0,5) = 32 pow(0.4,2) = 0.16 pow(2.0,-2) = 0.25 For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the…
Given a string, how do you find the minimum number of characters to insert to make it a palindrome? For example given a string “abbc”, the number of characters to insert is 2, and the resulting palindrome is “cabbac” Take another example “abc”, we need to insert two characters at a minimum to make it…
This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki. Given a set of strings, how do we find the longest common sub-sequence(LCS) among them? For example, LCS{“ATDACG”,”CTDACGA”} is “TAG”. In this post, we will look at the algorithm…
Given ‘N’ zeros and ‘M’ ones, In how many ways can we arrange them to form a string of length (N+M)? For example if we have 2 zeros and 2 ones, we can arrange them in 6 ways 0011, 1100, 0101, 1010, 1001, 0110 If there are N symbols to arrange, The number of ways…
Given a number, we have to find out the number ways to express it in the form of sum of two integer squares.For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)24 cannot be written as a sum of any two squares.Mathematically this problem is to find the…
Given an array of distinct numbers, how do we count the number of triplets with given sum? For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14, There are 3 triplets with the given sum(2,5,7)(2,4,8)(3,4,7) A brute-force algorithm will take O(n3) time. But this problem can also be…
Given an array of numbers, Count the number of pairs with sum less than or equal to K For example consider the array {5, 1, 12, 3, 6}, pairs with sum <= 10 are {(1,3), (1,5), (1,6), (3,5), (3,6)}. So there are 5 pairs with the given constraint. In one of the previous posts, we…