My software development journey
In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time. Here is the strategy for linked list insertion…
Given an array of sorted numbers, we have to find the right most occurrence of a number.For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index). This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).Similar to the…
Given an array of integers which might contain both positive and negative integers, how do you modify the array such that all the positive and all the negative elements appear together. For example consider the following array. [36, -2, -18, 24, 42, -3, 6] This should be transformed to some thing like [-2, -18, -3,…
Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit. For example 2-bit gray code is shown below. 00 01 11 10 Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray…
Given an integer N, we have to generate the nth sequence of the following pattern. “1” “11” as the previous item contains one instance of 1. “21” as the previous entry contains two 1’s. “1211” as the previous entry contains one 2 and one 1. Following is the program which generates such a sequence. It…
How do we implement a function to find the integer square root of a number? For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root) A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >=…
Given a matrix of size m * n, write a program to fill zero in ith row and jth column if matrix[i][j] is zero. For example let us consider the following matrix. [ 6 0 2 1 3 4 5 9 0 ] It should transform to the following. [ 0…
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 range of numbers, how do we count the number of perfect squares? This problem is posted on Hackerrank as part of 20/20 Hack March 2014. If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know…
Given a sorted array of numbers, how to delete the duplicate numbers in it? We have to write a function to modify the existing array without using any extra space and return the new length. The solution to this problem is similar to that of “Deleting all instances of a particular number from a given…