My software development journey
Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination. For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities…
Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum? For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements. The straight forward approach is to check the sum of all possible arrays and find out…
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 an array of positive and negative numbers, find the maximum sum of any sub sequence such that no two elements are contiguous.For example consider the array {3,-2, 1, 7}, maximum sum is 10 for {3,7}For {3,-2, 1, 0, -4, 2} it is 6 for {3,1,2}This problem can be efficiently solved in O(n) time using…
Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it. The depth of a tree is defined as the maximum length of the path from root to any leaf node. For example the following tree has a depth of 2 (for the path 0-2-4) It…
Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount? Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations {1,1,4} {1,1,1,3} {3,3}…
Given two strings as input, write a program to find the edit distance between them. The edit distance is defined as the minimum number of modifications to do on one string to transform it into the other string. A modification can be inserting a character, deleting a character, or replacing an existing character. For example,…
Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value. For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t…
Given an array of positive and negative values. We have to find the maximum sum a sub-array can have. For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}. To solve this problem, we take two variables to keep…