While travelling in a cycle race, there are several pit stops. A cyclist can travel upto 50 km without stopping at any pit stop, where he can have a health drink and refill his energy. Given a start point ’t’ and let ’k’ be the distance needed to be travelled by the cyclist, find an efficient algorithm to reach the destination ’d’ so as to have minimum pit stops and prove your algorithm is the most optimal one.

You have given n numbers from 1 to n. You have to sort numbers with increasing number of set bits.

for ex: n=5.
output: 1,2,4,3,5
Note: If you have two number with equal number of set bits, then number with lowest value come first in the output.

Write a function to convert Hexadecimal number (String) to Decimal Number (Int)

Maximum Sum Subsequence in an unsorted array of size n

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are  possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to  by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let  denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

 (for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over  for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array  where  would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes  time and  space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all  values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes  time and  space.

Remove all two zeros in the given string. Example: a3409jd00dk000d Output: a3409jddk000d Note: If there are less/more than two zeros consecutive, it should not be replaced.

#include<iostream>
#include <string.h>
using namespace std;
 
void removeDoubleZeros(char* src)
{
int len = strlen(src);
 
 
int idxSrc = 0;
int idxDest = 0;
while (idxSrc + 1 < len)
{
if(src[idxSrc]=='0'&& src[idxSrc+1]== '0')
{
 if(
 ((idxSrc - 1 >= 0 && src[idxSrc - 1]!= '0') 
   || idxSrc - 1 < 0) &&
 ((idxSrc + 2 < len && src[idxSrc + 2]!= '0')
  || idxSrc + 2 >= len)
)
 
{
idxSrc += 2;
}
else
src[idxDest++] = src[idxSrc++];
}
else
{
src[idxDest++] = src[idxSrc++];
}
}
 
 
src[idxDest++] = src[idxSrc];
src[idxDest] = 0;
};
 
 
int main()
{
char src[] = "a3409jd00dk000d";
 
 
removeDoubleZeros(src);
printf("%s", src);
 
return 0;
}
 
Time Complexity O(N) where N is length 
of string
Space Complexity O(1)
Run Here http://ideone.com/1p3Sb

You have a book will billion pages. Each Page P has L lines and each lines has W number of words. Design a search algorithm which gives me best match search results. Best match is when all the words given by user exactly matches.

Given two string, check whether the other is permutation of first one or not. Eg: abc cba Ans: True Eg: abca abbc: Ans: False

1.take an array of 256 size,(for ascii characters),initialize with 0.
2.iterate through the both string,increment the value of array1 by 1,on position pointed by ascii value of char obtained and simultaneously decrement the value of array2 by 1,on position pointed by ascii value of char /: 
3.finally check if at any index in array its value is not zero if its true then return false else return true.

#include<iostream>
#include <string.h>
using namespace std;
 
int ifPermutation(const char* a, const char* b)
{
if (strlen(a) != strlen(b))
return 0;
 
 
char arr[256];
memset(arr, 0, sizeof(arr));
 
 
for (int i = 0; i < strlen(a); i++)
{
arr[a[i]]++;
arr[b[i]]--;
}
 
 
for (int i = 0; i < 256; i++)
{
if (arr[i] != 0)
return 0;
}
 
 
return 1;
};
 
 
int main()
{
char* a = "abca";
char* b = "cbaa";
 
 
int res = ifPermutation(a, b);
printf("%d",res);
 
 
}

 
time complexity o(n)
space complexity o(1)

Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution. input output

 ex1: (a+(b)+c) a+b+c ex2: (a*b)+c a*b+c

Given n find all possible representations of n in Fibonacci binary number system.

Consider the Fibonacci Seies 1, 2, 3, 5, 8, 13.....
Now consider a Fibonacci binary number system of numbers where numbers are considered as sum of Fibonacci numbers
Ex. 10 can be written as 8+2=>10010 and 17 can be written as 13+3+1 => 100101. This representation is similar to binary representation. Instead of powers of 2, Fibonacci numbers are used.
The question was, given n find all possible representations of n in Fibonacci binary number system.
as 10=8+2=>10010
also 10=5+3+2=>1110 

#include <stdio.h>
#include <string.h>
 
void printSol(int* sol, int size)
{
        int i;
 
        for( i = 0; i <= size; ++i )
                printf("%d",sol[i]);
        printf("\n");
}
 
void binaryFiboUtil(int* sol, int depth, int num,int* arr, int size)
{
        if(depth < 0 || num == 0){
                if(num == 0)
                   printSol(sol,size);
               return ;
        }
        else
        {
                if(arr[depth] <= num)
                {
                        sol[depth] = 1;
                        binaryFiboUtil(sol,depth-1,num-arr[depth],arr,size);
                        //sol[depth] = 0;
                }
                else
                {
                  sol[depth]=0;
                  binaryFiboUtil(sol,depth-1,num,arr,size);
                }
        }
}
 
void binaryFibo(int num)
{
        if(num <= 0 )
                return;
 
        int a, b, c, arr[100], top = -1;
 
        a = 0;
        b = 1;
        c = a+b;
 
        while( c <= num )
        {
                arr[++top] = c;
                a = b;
                b = c;
                c = a+b;
        }
        int sol[top+1];
 
        memset(sol,0,sizeof(sol));
        binaryFiboUtil(sol,top,num,arr,top);
}
 
int main()
{
        int num;
 
        scanf("%d", &num);
 
        binaryFibo(num);
 
        return 0;
} 
 
Thanks to a reader named "coder" for posting the code.
  

Find the kth smallest element in a (MxN) matrix.

PS:Think how efficiently u can do same for an array .

Write an algorithm that prints an unordered sets of k elements chosen from a set of size n.

Example, let the size of the give set be n and set = {0, 1, 2, 3, 4} and we need to find all the subsets of size 3, then there will be a total of 10 such subsets given as:

{0, 1, 2}
{0, 1, 3}
{0, 1, 4}
{0, 2, 3}
{0, 2, 4}
{0, 3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}

give an algorithm for finding duplicate parenthesis in a expression. (( a + b ) * (( c + d )))

Find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Given Table of Cities , Find Minimum Number of Hopes Required to Fly From One to Other City

There is a very Primitive Database and it has a table say "Travel". The content of table is as follows:

Source | Dest
--------------


Sea | LA
LA | FL
LA | MA
FL | Sea
Sea | FL

The ask is to find out all routes between (Sea) to (FL) with mininum hop.
the Result would be:
1. Sea -> FL
2. Sea -> LA - > FL

You have to write a Middle tier function to achieve above result. You can assume there is DBAPI that return the Destination city if you provide the source city.

Count the number of islands in an ocean where ocean is represented as a grid. Cells, having a part of any island, are marked as 'x' otherwise 'o'.

Coin Denomination Problem

Let us say we have an amount we have to pay someone: say $97. The given currency has notes worth $1, $5, $10 and $50. Now, what is the minimum number of currency notes with which the amount can be made? In this case, its eight: two $1 notes, a $5 note, four $10 notes and a $50 notes - eight in all.

If a computer had to solve the same problem, how would it do it? Let us see below. ‘Denomination’ refers to the list of available currency notes: $1, $5, $10 and $50 in this case - each note is a denomination.

In General

Problem: We are given a set of denominations d1,d2,d3,...,dn in increasing order. (Without loss of generality) we assume also that d1=1 (that is, there is always a $1 note, and that is the first denomination) so that it is always possible to produce all amounts from the given denominations. We are also given an amount of money amt. We must use a minimum number of coins (or currency notes) of the given denominations to produce amt.

Great Info http://www.seeingwithc.org/topic1html.html

Find The Number of Unique Path in Maze Where Robot is Sitting at Top-Left Corner & Can Move According to Given Constraints

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . marked ‘end' in the diagram below.How many possible unique paths are there?

I posted the solution with post because i was aware of such problem earlier :)

Basic Solution,Approach,Algoriothms Using BackTracing

Start form top left corner (say we are at position 1,1 in starting deonted by row=r,column=c (e.g. r=1, c=1 initially) & then will will keep moving untill reach when r=m and c=n e.g. bottom-left corner) writing code for this is simple.

int backtrack(int r, int c, int m, int n) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}

but as normal backtracking problems it inovolves repeated calculations
so is very inefficient in the sense that it recalculates the same solutio n over patah again & again. so we need to use a dynamic programming (DP) technique called memoization akso called top down approach.

const int M_MAX = 10;
const int N_MAX = 10;

int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

if (mat[r+1][c] == -1)
mat[r+1][c] = backtrack(r+1, c, m, n, mat);
if (mat[r][c+1] == -1)
mat[r][c+1] = backtrack(r, c+1, m, n, mat);

return mat[r+1][c] + mat[r][c+1];
}

int bt(int m, int n) {
int mat[M_MAX][N_MAX];
memset(mat, -1, sizeof(mat));
return backtrack(1, 1, m, n, mat);
}

Time Complexity O(M+N)
Space Complexity O(M*N)



Bottom-Up Dynamic Programming More Efficient

As we know The total unique paths at above matrix (r,c) is equal to the sum of total unique paths from matrix to the right (r,c+1) and the matrix below (r+1,c).

(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:

X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on

Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):

(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..

const int M_MAX = 100;
const int N_MAX = 100;

int dp(int m, int n) {
int mat[M_MAX][N_MAX] = {0};
mat[m][n+1] = 1;

for (int r = m; r >= 1; r--)
for (int c = n; c >= 1; c--)
mat[r][c] = mat[r+1][c] + mat[r][c+1];

return mat[1][1];
}

Lets Assume you have M×N sample matrix or grid. so it doen't matter how you traverse the grids, you always traverse a total of M steps. To be more exact, you always have to choose M-N steps to the right (R) and N steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose M-N R‘s and N B‘s in these M+N-2 steps. The answer is C(M,N) (or C(M,M-N)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1) & this is our answer.

Time Complexity O(M*N)
Space Complexity O(M*N)


Follow Up: Using Above We Have Only Calculated the number of paths can we print those path as well if yes what will be time complexity.

How to Count Number of Set Bits e.g. Number of 1's efficiently ?

This Question is asked in almost all core s/w companies & most of we know logarithmic solution of this problem but there exist a constant time solution using bit manipulations stuck !!!!:) See 2nd Method to solve the same problem in O(1)

1st Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

#include

/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}

/* Program to test function countSetBits */
int main()
{
int i = 16;
printf("%d", countSetBits(i));
getchar();
return 0;
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/2y2KJ

2nd Method is Most Efficient One !!!!!!

Assuming that the integer is 32 bits, this is pretty good:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

where
0x55555555 = 01010101 01010101 01010101 01010101
0x33333333 = 00110011 00110011 00110011 00110011
0x0F0F0F0F = 00001111 00001111 00001111 00001111
0x00FF00FF = 00000000 11111111 00000000 11111111
0x0000FFFF = 00000000 00000000 11111111 11111111


Notice that the hex constants are respectively alternate bits,
alternate pairs of bits, alternate groups of four bits, alternate
bytes, and the low-order half of the int.

The first statement determines the number of one-bits in each pair of
bits. The second statement adds adjacent pairs of bits to get the
number of bits in each group of four bits. Then these are added to get
the number of bits in each byte, short int, and finally in the whole
int.

but it works at low level ??

Suppose that the first four bits of x from the left are abcd. Lets separate the bits into pairs with a comma: ab,cd. The first four bits of the hex constant0x55... are 0101, or separated into pairs: 01,01. The logical product of x with this constant is 0b,0d. The first four bits of x>>1 are 0abc, or separated into pairs are 0a,bc. The logical product of this with the constant is 0a,0c. The sum 0b,0d + 0a,0c is a+b,c+d, where a+b = 00, 01, or 10, and b+c = 00, 01, or 10. Thus we have replaced each pair of bits in x with the sum of the two bits originally in the pair.

The next statement uses the constant 0x333.... The first four bits of this are 0011, split into pairs as 00,11. The logical product of the first four bits of x with this constant gives 00,c+d. Furthermore (a+b,c+d)>>2 = 00,a+b. Then 00,c+d + 00,a+b gives the four-bit quantity a+b+c+d, i.e., the number of one bits set in the first four bits of the original x.

The next statements continue to double the number of bits included in each sum.
& so on

#include
using namespace std;

int main()
{
int x=0x00000016;
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

cout<> 2) & 0x33333333);

cout<> 4) & 0x0F0F0F0F);

cout<> 8) & 0x00FF00FF);

cout<> 16) & 0x0000FFFF);

cout< return 0;

}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/uDKGK
More Info http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Write a program to merge two BST efficiently in O(n)

There are two methods to do this :-

1st
1)convert both tree into doubly linked list
2) merge both these doubly linked list
3) then create a tree from these merge linked list by taking median of this list as root and traverse left from root to make left subtree and traverse right from root to make right sub tree
this has complexity O(n1+n2) and space complexity O(1)

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}



1)Find the inorder traversal of both the trees
2)Merge them into one (Giving one sorted tree)
3)Find the median of this sorted array(O(1))
Call this procedure recursively

struct tree
{
int data ;
tree * left , *right ;
};
void insert(int * array , int left , int right)
{
if (left<=right){ int mid=(left+right)/2; tree * root= malloc(sizeof (tree)); root->data=array[mid];
root->left=insert(array , left , mid-1);
root->right=insert(array , mid+1 , right);
return root;
}
}

Time Complexity O(N)

Wap to Replace all the instances of ’%’ with this string s,offered that the length of the array

Given an array of dimension n with very first l positions crammed with characters and a string s ,replace all the instances of ’%’ with this string s,offered that the length of the array is enough to deal with these substitutions.

input output

eg: abcdef%ghi%—— and “ppp” abcdefpppghippp



Although program is Simple but i am posting here as i found on one forum that it is asked by MS:)

Data Structure:Array

Algorithm:
1.count number of % character
2.increase size of array by lenth + 2* number op & chars.
3. scan through new array & replace all % occurance with "ppp"


class test
{
public static void ReplaceFun(char[] str, int length) {
int percentCount= 0, newLength, i = 0;
for (i = 0; i < length; i++)
{
         if (str[i] == '%')
        {
            percentCount++;
        }
}

newLength = length + percentCount* 2; str[newLength] = '\0';

for (i = length - 1; i >= 0; i--)
{
if (str[i] == '%')
{
str[newLength - 1] = 'p';
str[newLength - 2] = 'p';
str[newLength - 3] = 'p';
newLength = newLength - 3;
}
else
{
str[newLength - 1] = str[i];
newLength = newLength - 1;
}

}
System.out.println(str);
}
public static void main(String a[])
{
ReplaceFun(new char[]{'s','h','%','a','%','%','s','h','a','n','%','%','%','k'},15);

}
}