My software development journey
Given an array A of size N, We want to perform several iterations as described below. Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right Similarly move right, and fill each element which is one greater than it’s…
Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below. If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1. 1 / \ 2 3 / \ / \ 4 5 6 7 Given two nodes from…
This problem is from Codechef. I am re-wording it for more clarity. A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free. However we can divide the items into multiple orders to save more.…
Given an array A of distinct numbers, how to count the number of pairs (i,j) such that A[i] < A[j] For example, let us consider A = [2, 1, 3] the pairs are (1,2), (1,3), (2,3). So there are 3 pairs. Similarly for A = [10, 6, 9, 2], there are 6 pairs This problem…
Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R]. How to find out the position of a number after these operations are applied? For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2. Reverse elements between 1, and…
Given two numbers A, B, What is the maximum value of A’ XOR B’, where A’, B’ are obtained by permuting the binary representations of A, B respectively. For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A’ =…
Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]The algorithm here is simple. Let us assume two…
Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.Similarly a rectangle of size 3 x 7, can only be divided…
Given a permutation of numbers from 1 to N, We can represent it in two ways. For example, let us consider a permutation from 1 to 5 P = [2 4 1 5 3] This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on. Alternatively, this…
Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal. For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make…