My software development journey
Given two strings, how do we check if their edit distance is 1?Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string.For example let us consider two strings “java”, “lava” they both differ by just one character. we can…
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 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 a set of n strings, we have to write a program to find out the number of characters appearing in all the strings.For example consider the following strings{“India”, “China”, “United states”}, the letters {a,i,n} appear in all the strings.Let us think of the following solution. We first add all the characters in the first…
Given two strings, how do we find the number of characters to be deleted from both the strings in order to make them anagrams. Two words are said to be anagrams if one word can be formed by re-arranging the letters of another word. For example the words “TAN” and “ANT” are anagrams. Given two…
Given a string consisting of only 0s and 1s, How do we write a program to find the longest sub string with equal number of 0s and 1s in it? For example consider the string “01001”, the longest string with equal number of 0s and 1s is “1001”. Let us look at the solution approaches.Considering…
Given a string, how do we write a program to find the length of longest sub-string without any characters repeating in it. Let us call it a unique sub string. For example consider the string “program” the maximum length of a unique sub-string is 5 for the sub string “ogram”. A method by checking all…
Given a list of strings, how do we find the longest common prefix of all the strings?For example consider { “Anomaly”, “Anatomy”, “Analog”, “Angry” } the longest common prefix is “An”.This is a simple algorithm. Assume the first string as the longest common prefix, and try to match with the other strings and modify the…
Given an integer N, we have to generate the nth sequence of the following pattern. “1” “11” as the previous item contains one instance of 1. “21” as the previous entry contains two 1’s. “1211” as the previous entry contains one 2 and one 1. Following is the program which generates such a sequence. It…