My software development journey
Given the base and exponent, how do we implement the pow(base,exp) function efficiently? For example pow(2.0,5) = 32 pow(0.4,2) = 0.16 pow(2.0,-2) = 0.25 For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the…
Given an array of numbers, how do we count the number of inversions in it? Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] . For example consider the array {3, 2, 1,…
Given a base and it’s exponent, how do we efficiently evaluate it? In other way, how do implement a pow() function which is typically provided by a library. For example 210 = 1024. The simplest method that comes to our mind is multiply the base with 1 in a loop for exponent times. double result…
Given a circularly sorted array, how to search for an element efficiently? For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3. Since the array is sorted but rotated, we can expect it to be solved using the binary search technique. We can design an…
Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations? For example the array [4, 5, 1, 2, 3] is (right) rotated twice. Before proceeding to find a solution, let’s note some observations. To find the number of rotations, we have to find the smallest element in the…
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…