My software development journey
How to implement a Queue data structure using Stack? We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.…
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…
Given some text and a word. How do we find the frequency of the word?In this post we will see a Java program which finds it with just a few lines of code using regular expression matching. Java provides utilities for matching the regular expressions using java.util.regex package. In our program we utilize two of…
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 a single linked list, how do you find the middle of the list?One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance…
In simple words, Recursion is nothing but a function calling itself. How can we solve this problem using recursion? Initially pass the entire string as input to the function. Basically a pointer to the first character is passed. This function examines the next character; if it is not null, it calls itself by advancing the pointer…
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…