My software development journey
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 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…
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…
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 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…
In some applications like card games, we need to shuffle an array of objects. In this post we will consider the problem of shuffling an array of numbers so that the same algorithm would be applicable for any type of arrays. We use the random number generator in this algorithm. Let us consider an array…