My software development journey
Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern. Quick sort works as follows. A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All 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…
Given two strings, How do we delete all the characters in the first string which are present in the second string? Find the character set of the string. Create a Boolean array of size equal to the character set size. If the character set is ASCII, the size is 256. This array will be indexed…
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…
In selection sort, a list is sorted in the following way. Initially there will be an empty sorted list and the un-sorted list. We select the first element(According to the sort order) from the unsorted list and add it to the sorted list. We select the second element and append it to the sorted list…
Pattern matching algorithms are very important in computer science. In this post we will discuss the simplest algorithm for pattern matching. Given some text and a pattern, we have to find where in the text, the pattern is found. In this brute-force algorithm, we start matching the pattern from the beginning of the text. If…
Given an array of positive integers, all numbers occur even number of times, except one which occurs odd number of times. How do you find the number in O(n) time and O(1) space? You can find a similar question in interviews which is infact a specific problem of the above category. An array contains 2n+1…