Write an algorithm to remove balls out of a box....

Q : Given a box with n number of balls. Write an algorithm to remove the balls from the box.

Answer :

public class Box
{
Ball[] balls;
int ballCount;
public Box(int ballCount)
{
this.ballCount = ballCount;
balls = new Ball[ballCount];
}
public bool RemoveBall()
{
if(0 < this.ballCount)
{
int deleteThis = Random() % this.ballCount;
for(int index = deleteThis; index < this.ballCount - 1; index++)
{
a[index] = a[index + 1];
}
this.ballCount--;
return true;
}
else
{
return false;
}
}
}

public class Ball
{
int id;
public Ball(int id)
{
this.id = id;
}
public int ID
{
get { return this.id; }
set { this.id = value; }
}
}
static void Main()
{
Box box = new Box(100);
while(true == box.RemoveBall());
}

Note : int rand(void) is the function used in C++ to generate random numbers…..which returns a psuedo-random integral number in the range of 0 to RAND_MAX ( ~ 32767 )
To generate any random number in the range of a to a+x ...
( ( Value % x ) + a ) where value is rand()

Find if a string s2 is a substring of string s1

Let s1 be the string in which we are looking for s2..
boolean Find(char *s1, char *s2) {
// Make a check to see if length of s2 is less than or equal to length of s1.. If not return false…
int i, j=0;
char flag = false;
int len = strlen(s2) - 1;
for(i=0;i{

if(flag = true && s2[j] != s1[i])
{
i--;
j=0;
flag = false;
}
else {

if(s2[j] == s1[i])
{
i++;
j++;
flag = true;
}
else
{
if(flag = false)
i++;
}
}
if(j == len)
{
return true;
}
}
return flag;
}

Zig Zag Traversal of a tree...

Q : Given a binary tree.. Print the elements from the 1st row to the last row (each row corresponding to one set of siblings in the tree) such that

For every odd row : print the elements from left to right
For every even row : print the elements from right to left.

Answer :


Use two stacks. One stack to store the even row pointers and another to store the odd row pointers
Let root be the root element of the tree - lets say the row is even - 0

stack1 - contains the even pointers
stack2 - contains the odd pointers

flag = true;
while( flag !=false)
{
push root into stack1
while( ( s1_current = pop(stack1)) ! = null )
{
print(s1_current->element);
push(s1_current->left) into stack2; //if the element is not null
push(s1_current->right) into stack2; //if the element is not null
}
while( (s2_current = pop(stack2)) != null)
{
print(s2_current->element);
push(s2_current -> right) into stack1; // if the element is not null
push(s2_current -> left) into stack1; // if the element is not null
}
if(top(stack1) != null) // basically to check if stack1 is empty
{
flag = true;
}

}

Time Complexity : O(n)

Space Complexity : The worst case space complexity for this problem would be 2 ^ log(n) since log(n) corresponds to the height of the tree.