Given a function bool Zoo(int x) and its called for y times , how you will generate the true with probability x/y times .

lest say if x = 65 & y=100, how will you generate true with probability 65/100. You can represent true by 1 and false by 0.

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}

WAP to Print a Binary tree in level order with a new line after every level.

Data Structure Used Queue

Algorithm Shown Below

printLevelorder(tree)
Initialize the global variable size=0
1) Create an empty queue q
2) temp_node = root /*start from root*/ & initialize the local variable cur_size=0
3) Loop while temp_node is not NULL
A) print temp_node->data.
B) Enqueue temp_node’s children (first left then right children) to q
C) After this check cur_size is equals to zero or not
if(cur_size==0)set cur_size=size of queue(no of elements at that time in queue
D) Dequeue a node from q and assign it’s value to temp_node
E) Decrement the cur_size until it become zero so that we can re-initialize it
again with new size of queue.


#include
#include
#define MAX_Q_SIZE 100

/* 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;
};

/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);

int size=0;

/* Given a binary tree, print its nodes in level order
using array for implementing queue */
void printLevelOrder(struct node* root)
{
int rear, front;
struct node **queue = createQueue(&front, &rear);
struct node *temp_node = root;
int nsize=0;

while(temp_node)
{
printf("%d ", temp_node->data);

/*Enqueue left child */
if(temp_node->left)
enQueue(queue, &rear, temp_node->left);

/*Enqueue right child */
if(temp_node->right)
enQueue(queue, &rear, temp_node->right);
if(nsize==0)
{
nsize=size;
printf( " \n ");
}

/*Dequeue node and make it temp_node*/
temp_node = deQueue(queue, &front);
nsize--;
}
}

/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
struct node **queue =
(struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);

*front = *rear = 0;
return queue;
}

void enQueue(struct node **queue, int *rear, struct node *new_node)
{
queue[*rear] = new_node;
(*rear)++;
size++;
}

struct node *deQueue(struct node **queue, int *front)
{
(*front)++;
size--;
return queue[*front - 1];
}

/* 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);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->left->left = newNode(41);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->right->right = newNode(71);


printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/FLgSI

Device An Algorithm to Find minimal number of moves the to pegs to transform from the initial to final configuration. .

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

• A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
• At anypoint of time, the decreasing radius property of all the pegs must be maintained.

The Social Network (2010) - FaceMash Algorithm

I saw Social Network 2-3 times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie.

You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window:

and

What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor.

As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students went to a page and 2 random images of girls were picked and presented to them. The students then had to click on the hottest girl presented to them and then another set of two girls would be presented asking the students to repeat the same actions they had done. The difference with hotornot was that the girls presented were all Harvard students. In other words, the students were rating girls of Harvard based on their looks (You can imagine why Mark got into trouble).

The algorithm used - The Elo Rating system - insured a fair rating and ranking of the girls. A hot girl A winning over hot girl B girl would gain more points than winning (or being picked) against ugly girl C. Same goes for the following: ugly girl C wins over ugly girl D. ugly girl C gains some points in her general ranking. If ugly girl C wins over hot girl A then ugly girl C gains more points because the ranking of hot girl A is much higher than ugly girl D. The previous scenario is roughly what the algorithm implemented by Mark was doing. It was somewhat insuring a level of fairness despite the misogynistic nature of the product.

In today’s society, the Elo Rating system is used by many rating and ranking system to predict the outcome of matches but also insure a level of fairness between teams of different levels playing against each others. FIFA uses it to rank football teams.

You can read more about the system on wikipedia page(http://en.wikipedia.org/wiki/Elo_rating_system).

Algorithm to Generate the permutations of the array containing number in lexicographical order.

Approach & Description:

Generation in lexicographic order

There are many ways to systematically generate all permutations of a given sequence. One classical algorithm, which is both simple and flexible, is based on finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates the distinct multiset permutations each once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

Final Algorithm:

1) From the end, keep decrementing till A[i] < A[i+1]..
2) Now, find the closest element , greater than equal, to A[i] in 

A[i+1 ... n]. Say, the index of the found element is "j".
3) Swap (A[i], A[j])
4) Reverse array A[i+1 .. n]

Example:

Input 14532

output  15234..

1) 4 is the value where A[i] < A[i+1] when scanned from the end.
2) The closest element grater than equal to 4 in the subarray 532 is 5.
3) Swap (4,5) : 14532 -> 15432
4) Now, as we have identified in step 1 the index of i, we need to
reverse the array from A[i+1, n] i.e. in 15(432) (432) needs to be
reversed and hence we will get 15234...

Working Code

#include < iostream>

#include < algorithm>

#include < time.h>

using namespace std;

  

// Swap function

template < class T>

void swap(T *i, T *j)

{

    T temp = *i;

    *i = *j;

    *j = temp;

}

  

// function to reverse a range of values

template < class T>

void reverse(T *start, T *end)

{

    while(start < end)

    {

        swap(start,end);

        start++;

        end--;

    }

}

// array_end does not point to a valid element of the array

// it is beyond the last element

template < class T>

bool permute(T* array_start,T* array_end)

{

    // array does not contain any element

    if(array_start == array_end)

        return false;

     

    // array contains only 1 element

    if(array_start+1 == array_end)

        return false;

         

    T *i,*i1,*j;

     

    // Make the pointers point to last and the second last elements

    i = array_end - 2;

    i1 = array_end - 1;

     

    // find two elements a,b such that a < b and index of a

    // is less than the index of b

    while(true)

    {

        // If such a pair is found, find an element c such that

        // c > a, then swap them and reverse the list from b till

        // the end

        if(*i < *i1)

        {

            j = array_end -1;

                 

            // worst case is that j == i1

            while(!(*i < *j))

                j--;

                 

            // This step implements the lexicographic order by

            // bringing the larger element in the front

            swap(i,j);

             

            // Reverse the list so that we have a weak decreasing

            // order in the remainder of the list

            reverse(i1,array_end-1);

            return true;

        }

         

        // Now the list is in strictly decreasing order

        // no more permutations are possible, return the

        // list as it was originally received

        if(i == array_start)

        {

            reverse(array_start,array_end-1);

            return false;

        }

         

        // decrement the two pointers

        i--;

        i1--;

    }

     

}

template< class T>

void display(T *array,T *end)

{

    T* i = array;

    while(i < end)

    {

        cout << *i << "-";

        i++;

    }

    cout << endl;

}

  

int main()

{

    srand(time(NULL));

     

    // You can declare any type here of any size

    int size = 4;

    char array[size];

     

    cout << "Enter four numbers" << endl;

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

        cin>>array[i];

     

    // C++ sort function so that the permutation

    // function receives the elements in the sorted order

    // in order to create a lexicographic order

    sort(array,array+4);  

     

    // First permutation

    display(array,array+4);

    int count=1;

     

    // Call the function while you get valid permutations

    while(permute(array,array+4))

    {

        count++;

        display(array,array+4);

    }

     

    cout << "Total permutations are " << count << endl;

     

    system("pause");

    return 0;

}

Run Here http://ideone.com/sK8JH
The complexity of the approach is O(n*n!)

http://en.wikipedia.org/wiki/Permutation
http://marknelson.us/2002/03/01/next-permutation/