My software development journey
Anagram of a word is nothing but rearrangement of it’s letters to form another word.For example ‘listen’ is an anagram of ‘silent’ and ‘enlist’.We have to write a function to check if two given strings are anagrams are not. We can solve this problem in two different ways. The first way is to sort the…
Given an array, and a value K as input, we have to find a pair of elements such that their sum is K. There are multiple ways of solving this problem. We will discuss some of them in this post. Let us implement the function which prints the two values such that array[i] + array[j]…
Let us consider an array of size N contains numbers in the range [1,N]. We have to find if it has duplicates in linear time – O(n) and by using only constant extra space – O(1). Let us also have a restriction that we should traverse the array only once. Take a look at the following…
In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack. The trick here is to use another stack which stores the minimum values of the original stack. The top of Min-stack always contains the…
Merge sort follows the divide and conquer approach. This is also a comparison based sorting algorithm like Bubble sort, selection sort and insertion sort etc. In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just…
How do you implement a stack using Queue? This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack. This can be done using two queues. One queue acts as the…
Given a string as input, how do we find the first non-repeating character? We have to do this in linear time – O(n) and constant extra space- O(1) Assuming that the character set is ASCII, the number of characters possible are 256. This will differ if the string contains non-ASCII characters like Unicode. First we…
This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.We discuss a recursive algorithm as it is simple to understand and implement. Let us…
A Magic square is a two dimensional arrangement of numbers ( from 1 to n2 ) in an n x n matrix such that adding all the numbers from any row, column or principal diagonal gives the same result.for example the following matrix is a magic square of size 3 X 38 1 63 5 …
Given an array of numbers, we have to find the longest sub sequence of that array which is strictly increasing.For example in the following array [8 1 4 2 7 9 5] {8,9}{1,4,7,9}{1,2,7,9}{1,2,5}{1,2,7}{1,2,9} are some of the increasing sub-sequences. The second and third are the longest increasing sub sequences with length 4. Our job is…