Given two sorted positive integer rrays A(n) and B(n). We define a set S = {(a,b) such that a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm.

Write a program that converts a given tree to its Double tree. To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node.

e.g below tree

1
/ \
2 3
/ \
4 5
is changed to

1
/ \
1 3
/ /
2 3
/ \
2 5
/ /
4 5
/
4

Algorithm:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);

/* Function to convert a tree to double tree */
void doubleTree(struct node* node)
{
struct node* oldLeft;

if (node==NULL) return;

/* do the subtrees */
doubleTree(node->left);
doubleTree(node->right);

/* duplicate this node to its left */
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}

/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Inorder traversal of the original tree is \n");
printInorder(root);

doubleTree(root);

printf("\n Inorder traversal of the double tree is \n");
printInorder(root);

getchar();
return 0;
}
Time Complexity: O(n) where n is the number of nodes in the tree.

An array of size n+1 has integers only from 1 to n. The integers 1 to n can be present 0 or more times in the array. Find the first repeating element in the array. Restrictions: O(n) algo required. Cannot use extra space(not even O(1)) but how you will do if we have to find the all repeating number in given constraints?

Question Seems to bit easy in 1st look but 1st typical Google interview question from their predefined set .in 1st try you won't be able to solve it , i am sure no one can cover the all the test cases in 1st attempt but after trying different test cases we can solve it easily :)

Data Structure Used: Array

Algorithm:(Simple & Straight Forward )

traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Working Code

#include
#include

void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { if(arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}

int main()
{
int arr[] = {1, 2, 3, 1, 3, 0, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}


Its Not Perfect we Need to care of when 0 or any other element occurs more then 2 ?? what happens when it comes multiple times ?? What Happens when array may contains -ive elements ??

suppose you have this array 1 0 2 0 3 0 1 6 4 3 then above algo fail so we need to cover all these case as well isn't it ?? check test case here http://ideone.com/wdxRJ for negative number i will check in last!!!!!!!!

Modified Algorithm(Optimized As Well)
1.While Looping Down from Array Calculate the index of each array element ist clear as all elements will in range of 1 to n so no over flow or underflow conditions.? so index=a[i]%size;
2. then check if value at this index is zero or not if its zero then set its as INT_MIN or -size as you wants. a[index]=-size
3.if above condition fails then check if value at given index is in given range or
not if its in range then multiply the value at given index with -1.
4. if number is less then zero this means its already occurs so print it , multiply with -1 to reset & set value to this index to a[index]=value+size due to time complexity constraints & problem statement i used this when if a number occur say k times algorithm wont fail.
5.

#include
#include
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { index=abs(arr[i])%size; if(arr[index] == 0) arr[index]=-size; else if(arr[index]>0 && arr[index] arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;// try to dry run for each number you will get it !!! :)
}
}
//restore previous array
for(i=0;i arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {2,2,1,1,1,2,2,3,0,0,0,1,1,2,0,7,5};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/i7n7V

further Thoughts: How we will solve if number is between -n to n e.g. total 2n+1 time in unsorted array .Yes As I have already explained the algorithm above will also work here , above we range from 0 to n & here we have -n to n but logic will remain the same why ?? because range is known to us ..i Will suggest to my read to to try out this & do notify it it will fail

Feel Free to Comment :)

Double Square Problem

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32 + 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.

Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100

Output
For each value of X, you should output the number of ways to write X as the sum of two squares.

Peg Game problem

At the arcade, you can play a simple game where a ball is dropped into the top of the game, from a position of your choosing. There are a number of pegs that the ball will bounce off of as it drops through the game. Whenever the ball hits a peg, it will bounce to the left with probability 0.5 and to the right with probability 0.5. The one exception to this is when it hits a peg on the far left or right side, in which case it always bounces towards the middle.

When the game was first made, the pegs where arranged in a regular grid. However, it’s an old game, and now some of the pegs are missing. Your goal in the game is to get the ball to fall out of the bottom of the game in a specific location. Your task is, given the arrangement of the game, to determine the optimal place to drop the ball, such that the probability of getting it to this specific location is maximized.

The image below shows an example of a game with five rows of five columns. Notice that the top row has five pegs, the next row has four pegs, the next five, and so on. With five columns, there are four choices to drop the ball into (indexed from 0). Note that in this example, there are three pegs missing. The top row is row 0, and the leftmost peg is column 0, so the coordinates of the missing pegs are (1,1), (2,1) and (3,2). In this example, the best place to drop the ball is on the far left, in column 0, which gives a 50% chance that it will end in the goal.

x.x.x.x.x
x...x.x
x...x.x.x
x.x...x
x.x.x.x.x
G
‘x’ indicates a peg, ‘.’ indicates empty space.

Input
You should first read an integer N, the number of test cases. Each of the next N lines will then contain a single test case. Each test case will start with integers R and C, the number of rows and columns (R will be odd). Next, an integer K will specify the target column. Finally, an integer M will be followed by M pairs of integer ri and ci, giving the locations of the missing pegs.

Constraints
1 ≤ N ≤ 100
3 ≤ R,C ≤ 100

The top and bottom rows will not have any missing pegs.
Other parameters will all be valid, given R and C

Output
For each test case, you should output an integer, the location to drop the ball into, followed by the probability that the ball will end in columns K, formatted with exactly six digits after the decimal point (round the last digit, don’t truncate).

Notes
The input will be designed such that minor rounding errors will not impact the output (i.e. there will be no ties or near — up to 1E-9 — ties, and the direction of rounding for the output will not be impacted by small errors).

Studious Student Problem

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.

Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

given n ranges (xi, yi) such that xi <= yi for all i from 1 through n and given a number say d, we have to find the number of ranges that this number falls in.

Given an array A of integers, find the maximum difference between two indexes j-i such that A[i] < A[j].

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Algorithm:
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;

for (i = 0; i < n; ++i) { for (j = n-1; j > i; --j)
{
if(arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; } Time Complexity: O(n^2) Space Complexity O(1) Method 2 Given by celicom

Algorithm

we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

You Know Ultimate Things we have to found out is maximum distance between minimum element from Lmin array to Maximum element in RMax Array isn't it :)

Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(j

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x < y? x : y; } /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;

int *LMin = (int *)malloc(sizeof(int)*n);
int *RMax = (int *)malloc(sizeof(int)*n);

/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i-1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n-1] = arr[n-1]; for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);

/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j-i); j = j + 1; } else i = i+1; } return maxDiff; } /* Driver program to test above functions */ int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(2n)..........................!!!!!!!!! Optimization in 2nd Method we can do it without using lmin array #include
#include

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x < y? x : y; } int maxIndexDiff(int arr[], int n) { int maxDiff; int i, j; int LMin; int *RMax = (int *)malloc(sizeof(int)*n); LMin = arr[0]; /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n-1] = arr[n-1]; for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);

/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LMin < RMax[j])
{
maxDiff = max(maxDiff, j-i);
j = j + 1;
}
else
{
LMin = min(LMin,arr[i+1]);
i = i+1;
}
}

return maxDiff;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {2, 9, 3, 4, 5, 6, 7, 8, 18, 8,0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)..........................!!!!!!!!!
Run Here http://ideone.com/tNF7Q

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other. Input: { a, b, b }, distance = 2 Output: { b, a, b }

Question Asked in Google Telephonic Round!!!!!!!!!!!

Here we find 2 ranges for which all the integers in these ranges are present in the array.

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. Have to do it in linear time. May use extra memory. But Hashing is not the correct solution.
eg. arr = {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15}

Here we find 2 ranges for which all the integers in these ranges are present in the array.
namely: [2,8] and [10,12]
out of these [2,8] is the longer one. So we need to output that.


Basic Solution

First sort the array.
Have 3 integers - start, end and len. Initialize to 0. Have another variable "first" to point to the first element in the current set.

Loop the sorted array from start to end. Assign "first" to first element. Keep looping as long as the next element is contiguous. As soon as continuity breaks, subtract current number with "first". If it is more than "len", store "first" and current number in "start" and "end" respectively. Store the length calculated in "len". Continue this process.

You'll finally have the largest range in "start" and "end".

But Constraints is O(N)???