GeeksSpot

Given an array of Integers arr, from an element val = arr[i], you can go to element i to i+val. If val is zero, you cannot move forward. find the least selection to reach end of the array. example: 1 3 5 8 9 2 6 7 6 8 9 @index 0, can go to 1 @index 1, can go to 4. if index 3 and 4 choosen, it will reach to end frm there only. Give an algorithm and program. This can be solved with greedy aproach. Assume we are at index i, So For all i ..to i+a[i] index check for the max value value of k+a[k], where i We can prove the correctness of this . If k+a[k] having maximum value then any value except the k in range of i to i+a[i] will be less than range reachable by k. So by choosing k, you still can choose the option available with other indexs.

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

We are having a matrix of size nxn, given rows and column are always sorted order. Need the fastest algorithm to search an given element. I am hoping this can be done in O(log n). Wait for my answer.

Given a circular road and a set of petrol pumps located at distances d1 d2 ... dn away from each other and supplying p1 p2 p3 ... pn amounts of fuel and your vehicle has a mileage of 1km/l. Determine the feasibility of going around the path starting with zero fuel. Find a point from which you can start and complete the cycle given that you have zero initial fuel. This will be O(n) algorithm. Start from a random node say i...check till the last node it reach. Two case: 1: Either it reach to last node. And current node i is result. 2. It stopped at node j. Then start from node j+1. to find where we can reach all the node by above algorithm. No Node from i to j can complete the traversal, because each node will start with 0 petrol. While traversing from i we always reached that node >= 0. So that condition is already checked.

given a string, remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on... Example : string is “abcabeccced” After removing repeated substring of length 1: “abcababceccced” --> “abcababceced” (2 'c' are removed) After removing repeated substring of length 2: “abcababceced” --> “abcabceced” (substring “ab” is removed) and so on... #include using namespace std; bool check ( char *s, int st1, int st2, int size) { for ( int i = 0; i le size; i++) { if ( s[st1+i] != s[st2+i] ) return false; } return true; } int main() { char s[15] = "abcababceccced"; int length = strlen(s); int maxlen = length/2; int match = 0; for ( int len = 1; len < maxlen;len++) { int j = len; int i = 0 ; while ( j < length) { if (check(s,i,j,len)) { j +=len; match++; } else { if ( match) { int temp = i+len; int k = j; while ( k < length ) { s[temp] = s[k];