My software development journey
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 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…
How to check if the given number is a Fibonacci number? A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers. Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,… If a number is given, a straight forward way to check if…
Given an array of numbers, find an index such that the sum of numbers to the left is equal to the sum of elements to it’s right. If there are no elements to the left or right, the sum is considered to be zero.This problem is from Hackerrank. Click here to solve this problem on…
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…
A binary sequence contains 0 and 1 only S.No Binary sequence——————–1 02 13 004 015 10…Given a number k, we have to design an algorithm to print kth binary sequence. Initial approach (not efficient): Starting from the sequence 0, this algorithm iterates k times. To get the next sequence, in each iteration we do the following. check the last…
Given an array of numbers, how do we count the number of inversions in it? Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] . For example consider the array {3, 2, 1,…
Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time. For example let us consider the following intervals. { (0,2), (3, 7), (4,6), (7,8), (1,5) } The maximum number of intervals overlapped is 3 during (4,5). This can be asked in many forms in a…