Design a new programming language GOOGELY.

The programming language consists of two global character registers X and Y. Both X and Y is initialized with A initially.

It consists of two instructions
next: It increments the contents of x. Resets it to ‘A’ if it was ‘Z’.
Print: Prints the value of X and swaps the value of X and Y.

Sample input for the program: A string say “CBC”
Sample output: Sequence of instruction needed to execute, to obtain the input string.
In this case this output would be “next next print next print print“.

Given a array, find the largest contiguous sub-array having its sum equal to 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.

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Example 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

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 Preorder can you make BST from it then print the sorted output from BST

#include<iostream>
#include<stdlib.h>
using namespace std;
 
typedef struct tree{
int val;
struct tree *left;
struct tree *right;
}tree;
 
tree* insert(tree* root, int val)
{
if(root == NULL)
{
tree* temp = (tree*) malloc(sizeof(tree));
temp->val = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
 
tree* node = (tree*) malloc(sizeof(tree));
if(root->val < val)
root->right = insert(root->right, val);
else
root->left = insert(root->left, val);
return root;
}
 
tree* buildBST(int preOrder[], int length)
{
tree* root;
if(length != 0)
{
root = (tree*) malloc(sizeof(tree));
root->val = preOrder[0];
root->left = NULL;
root->right = NULL;
}
else
return NULL;
 
for(int i = 1; i < length; i++)
{
root = insert(root, preOrder[i]);
}
 
return root;
}
 
void printInOrder(tree* BST)
{
if(BST == NULL) return;
printInOrder(BST->left);
cout << BST->val << " ";
printInOrder(BST->right);
}
 
void printPreOrder(tree* BST)
{
if(BST == NULL) return;
cout << BST->val << " ";
printPreOrder(BST->left);
printPreOrder(BST->right);
}
 
int main(void)
{
int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12};
tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int));
printInOrder(BST);
cout << endl;
printPreOrder(BST);
cout << endl;
}

 Time Complexity O(N^2) in Case of Skewed Tree
 Space Complexity O(1)
Run Here http://ideone.com/KVDrB

Given a array of intervals, check if that have any gape efficiently

u will be given pairs.. u need to see whether they have any gaps..
u can think pairs are like intervals..


ex1: max no:20 pairs: 11-15, 0-5, 18-20, 14-19, 6-13 

the above has no gaps..because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)
 

ex2: 11-15, 0-5, 18-20, 14-16, 6-13

this have gap as the intervals miss a number from 0 to 20 i.e.,17

Find Maximum length palindrome in a from a ascii text file

Given an array of length n, print all sub arrays of length r

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.
  

Fill next with node pointers which represent Inorder Successor of every node in BSTin BST

You are given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.
In a binary tree, inorder successor of a node is the next node in inorder traversal of the binary tree. Inorder successor is NULL for the last node in inorder traversal.

PS: In BST, inorder successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.

you have to print all possible combination of a given length let's say 'k' of a string in lexicographic order.

for Example:- input String=az k=2;
output
aa

az

za

zz..

 

Write an algorothm to find the position of rightmost set bit in binary representation of number

Example

Number 19,   Binary Representation 010011
Answer Position of right most set bit 1

Here is an order of log(X) algorithm. We can conclude from 2's complement form that "a number can be converted to 2's complement form by complementing each bit from right most set bit". For example, -7 can be obtained in the following way (assuming 8 bit size)

8 = 00001000
-8 = 11111000

If we perform ANDing between x and -x we left with right most set bit. All this takes O(1) time. Now use binary search [ O(log(x)) ] to figure out which bit is set. Given below is code.





int getPosition(unsigned x)

{

    // ASSUMPTION: x will not be zero



    // left, right and mid position

    int l = 0, r = 33, mid = 0;

    // temp value

    unsigned temp;



    // Iterate till we find the bit position

    while(l < r)

    {

        // ((r - l) >> 1) + l - Is more effective??

        mid = (l + r) >> 1;



        // Set the most possible significant bit

        temp = (1 << (mid - 1));



        if(temp == x)

        {

            break;

        }

        else if(temp < x)

        {

            // Bit is in the higher half

            l = mid;

        }

        else

        {

            // Bit is in the lower half

            r = mid;

        }

    }



    // Return mid itself if bits

    // are positioned from 1 to 32

    return (mid-1);

}



int getRightMostSetBit(unsigned x)

{

    // Return 0 if x is zero

    int position = 0;



    // Avoid multiple return statements

    if(x != 0)

    {

        // Make the integer passes as least power of 2

        // Call the position locator

        position = getPosition(x & -(signed)x);

    }



    return position;

}



Source Heard from My Friend Venki