My software development journey
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…
The following problem is from the Google code jam 2014 qualification round. Head-over there to read the complete problem description. The problem description is as follows. A magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from…
In the last post, the basic use of STL sort() method is explained. In this post, I will discuss some more options available with this method. We have seen in the previous post that sort takes the beginning and ending of the array as arguments. sort( array.begin(), array.end() ); In addition to those parameters, it…
Sorting is one of the most widely used algorithmic primitive in programming. C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits. It’s performance would surely be better than your own implementation. It’s…
In this post, we will write a program to generate a pascal triangle of given height. For example, Pascal triangle of height 5 is shown below 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 The idea behind Pascal triangle is that each element in a row is the…
Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array. For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A…
Given an array of arbitrary numbers and a given value, how do we write a program to delete all instances of the given value? For example, if the input array is [23, 9, 18, 9, 6, 47, 3, 6] and the element to be deleted is 9. The result array should be [23, 18, 6,…
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…
Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.If there no such element in the array…