My software development journey
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…
Median of an array is defined as the middle element when it is sorted. The middle element is the one which divides the array into two equal halves if the array is of odd length. If the length is even, the average of two middle elements is median.For example the median of [4,3,2,5,1] is 3…
Insertion sort is also a comparison based sorting. It is also an in-place sorting algorithm i.e it does not require extra space. We can re-arrange the elements within the array itself.The algorithm works as follows. The array is divided into two parts one sorted and one un-sorted. Initially the sorted part will be empty and…
Given an array of numbers, how do you search for a number? The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in…
Fibonacci number in mathematics is defined as the sum of the two previous elements in the series. Formally this is represented as f(n) = f(n-1) + f(n-2) where f(1) = 1 and f(2) = 1. In this post we will see how to generate nth fibonacci number. The algorithm is self-explanatory from the program itself. So…