My software development journey
The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the…
Given an integer, how do we count the number of set (1) bits?For example the number 37 has 3 set bits in it’s binary representation (0010 0101) Method#1: Simple In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1…
We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.For example if the input array is [2,0,1,2,1,0,0,2], the output should be[0,0,0,1,1,2,2,2].As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that…
Given an array of 0s and 1s, how do we sort them? After sorting all the 0s appear before all the 1s.For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.Method#1:We can take two counts…
Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop…
Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is…
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…
Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique. We discuss three different implementations of this function with various time and space complexities. Method-1: Naive approach This approach checks every possible pair in…