My software development journey
Problem: Given a set of coordinates in a two dimensional plane, How do we find the area of a minimum square which includes all the points. The points can exist on the border also. For example consider two points (0,0), (1,2) we need a minimum 2*2 square to cover these points. Hence the area is…
This is a problem from Codeforces. Please follow this link to solve this problem on your own. The abridged problem statement is as follows. You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that…
Given a number, how do we find the next greater number with the same digits? For example if the given number is 123, the next greater number with the same digits is 132. Similarly for 23876, the output is 26378. If all the digits of the number are in decreasing order (Eg. 54321), there…
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…