Design an algorithm and write code to serialize and deserialize a binary tree.

Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘de-serialization’.

First, we are able to save the binary tree to a file and restore it at a later time. We are also able to transmit the binary tree representation via network and load it into another computer. Without doubt, serialization/deserialization of a binary tree is important and an algorithm to represent a binary tree in a compact way is very desirable.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

The pre-order traversal code below does all the job to serialize a binary tree, believe it or not!
Source :http://www.brilliantsheep.com/serializing-and-deserializing-a-binary-tree-in-java Time Complexity O(N)
Space Complexity O(N) to Store BST in File

Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.

Question need to be understand clearly .We Have to Transfer the Whole BST/BT across the network this is where he asked to implement the serialization on Tree & the transfer to another host on recipient side we use deserialization . to implement serialization on tree we need to save it in file & restoring the exact tree on receiving side .important question arises that which traversal we have to use here pre,in or post ?? only one is best are u able to think of it ???

let me explain lets we have tree is
_30_
/ \
20 40
/ / \
10 35 50

In-order traversal
If we do an in-order traversal, we will output 10 20 30 35 40 50. There is no way of telling how the original BST structure looks like, as the following unbalanced BST is one of the possible BST sets from the output 10 20 30 35 40 50.

_50
/
40
/
35
/
30
/
20
/
10

Post-order traversal:
If we do a post-order traversal, we will output the leaf nodes before its parent node. Specifically, we will output 10 20 35 50 40 30 using post-order traversal. Imagine we’re reading the nodes to construct the tree back. See the problem that we are reading the leaf nodes before its parent? There’s too much trouble to create the child nodes before its parent. Remember that the BST insertion algorithm works by traversing the tree from the root to the correct leaf to insert.

Pre-order traversal:
Pre-order traversal is the perfect algorithm for making a copy of a BST. The output of a pre-order traversal of the BST above is 30 20 10 40 35 50. Please note the following important observation:
A node’s parent is always output before itself.

Therefore, when we read the BST back from the file, we are always able to create the parent node before creating its child nodes. The code for writing a BST to a file is exactly the same as pre-order traversal.

Ps: we can solve this problem with any traversal if we need to given an array to store in array instead of file isn't it think ?? why

on receiving side Reading a BST from a file:
The question now is, how would you reconstruct a BST back from the file? Assume that we have the following pre-order traversal output of the BST earlier: 30 20 10 40 35 50.
so answer is
When we encounter a new node to insert, we should always place it into the first empty space which it will fit using a pre-order traversal. How do we determine the first empty space which a node will fit in? We can use the ordinary BST insertion algorithm, but the run-time complexity will be O(n lg n), since inserting a node takes O(lg n) time. Not efficient enough! so we need some more efficient algorithm
yes we can do it using what we used to solve "Determine if a Binary Tree is a Binary Search Tree (BST)?"

so what will be the efficent algo then here it is
We use the same idea here. We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.

void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) { int val = insertVal; p = new BinaryTree(val); if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}

void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}

Time Complexity O(N)
Space Complexity O(1)

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