My software development journey
Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it. For example in the array [1, 2, 3], the pivot element is 2, as all…
Given an array of numbers A, which might contain duplicate elements, How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k? Look at the following examples.1. A = [9, 5, 6, 9, 3, 0, 1], K =3The answer is…
Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum? For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements. The straight forward approach is to check the sum of all possible arrays and find out…
Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N] That means each entry in the product array should contain product off all the elements except the one at that particular index. For example let us consider the array [4, 2, 10, 5], the…
Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.You can read the problem from this link. I will try to give the abridged problem statement below. There are…
Given an array of integers where each element has a difference of atmost 1 with it’s neighbors, we need to find the given element. For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5. This is just…
Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row. For example consider the following matrix. 0 0 1 10 0 0 10 1 1 10 0 0 0 The maximum…
Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?For example, the input arrays can look like {1, 3, 5, 4, 2} , {11, 17, 25, 36, 24, 6}. Basically we need to find…
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…
Given an array of of size N, How do we find the longest sub-array with all non-zero elements? For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}. This problem is from Codechef. Follow this link to solve this problem…