My software development journey
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 a number, how do we generate a smallest number which is greater than the given number and is a palindrome?Consider the following examplesInput Output3 49 1113 22767 777594 595898 909999 1001Here is the solution approach. This problem has multiple cases to be considered.Case 1: If all the digits in the number are ‘9’, the output…
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 two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid. The word can be formed in any of the 8 possible directions as shown below. Here is how I solved this problem. Write a function which takes the string to…
Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed. For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.The solution is based on the following observation,…
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 a parenthesis expression, We have to find the maximum nesting depth. For example: the expression ()((()))(()) has a maximum nesting depth of 3. The expression ((()())) has a maximum nesting depth of 3. Let us output -1 for an unbalanced expressions such as (())) or ()( This is a simple problem that can be…
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 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…
This problem is from Codechef January challenge. Click on the link to try this problem on your own. The problem statement is as follows. Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R].…