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/

Write an efficient C program to find the maximum average of contiguous elements inside an array of integers.

Example: [10, 4, -2, 7, 8, -1, -5] Maximum average of continuous elements 7+8=15/2 =7.5

Construct a BST where each node has 3 pointers instead of 2. the structure is struct node { int data; struct node *left; struct node *right; struct node *inordersuccessor; } write a code to add nodes in a binary search tree . inordersuccessor pointing to inorder successor.

Write An Efficient Program to Clone a Graph ?

Given a network of the employees of a company such that edges are between those employees who are friends to each other. Divide the employees into two teams such that no two people who are friends to each other are in the same team

give an algorithm for finding duplicate parenthesis in a expression. (( a + b ) * (( c + d )))

You are Reciving the infinite number of stream , you to retun k random elemnts ,if you query at time t , in those k elements then proababilty of choosing should be 1 e.g. they should have equal probality

Reverse the direction of each pointers of Linked List which haveing next & random pointer with it.

Consider a Linked List with each Node, in addition to having a 'next' pointer also has a 'random' pointer. The 'random' pointer points to some random other Node on the linked list. It may also point to NULL. To simplify things, no two 'random' pointers will point to the same node, but more than 1 Node's random pointer can point to NULL.
Now we are required to reverse the direction of all the pointers (both the 'next' and 'random') of the Linked list. The constraint is the solution MUST be O(1) space complexity (A constant number of new nodes can be created but not proportional to the length of the list)

Find The Largest Binary Search Tree in GIven Tree . Its Should be the Subtree.

Very Faq. Asked Question All Tech Giants :) Will Post The Solution Soon :) Meanwhile You Can Try & Post the approach . 

Prerequisite  : Most Efficient Solution to Check if Given Tree is BST or not ? !st Try it or Search Archives :)

Basic Idea :

Traverse the tree. From each node to the parent, return the following
set of values.
1) If BST, size of the current BST or -1 if the tree is not.
2) Minval & Maxval of the subtree and maxbstsize seen so far (
probably using references)
So in each node check the following:

If( leftmax < node->data && node->data < rightmin)  // Means it is a BST
{
  new size = rightsize+leftsize+1
  update size if greater than max
  return size
}
else
{
  return -1;
} 

 Working Code:

 
/* Largest Binary search tree inside a binary tree -- O(n)*/

#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct node
{
  int data;
  struct node* left;
  struct node* right;
};

struct node* insert_bst(struct node* root, int num){
  if(root == NULL){
    root = (struct node*)malloc(sizeof(struct node));
    root->data = num;
    root->left = NULL;
    root->right = NULL;
    return root;
  }else{
    if(num == root->data){
      return root;
    }

    if(num > root->data){
      root->right=insert_bst(root->right,num);
    }else{
      root->left=insert_bst(root->left,num);
    }
  }
  return root;
}

void inorder_traverse(struct node* root){
  if(root == NULL) return;

  inorder_traverse(root->left);
  printf("%d ",root->data);
  inorder_traverse(root->right);
}

struct node* bst_root = NULL;

int getmaxbst(struct node* root, int& subtreemin, int &subtreemax, int& max)
{
  if(root == NULL) return 0;

  int leftsubtreemin = -32767, rightsubtreemin = -32767;
  int leftsubtreemax = 32767, rightsubtreemax = 32767;
  int x,y;

  x = getmaxbst(root->left, leftsubtreemin, leftsubtreemax, max);
  y = getmaxbst(root->right, rightsubtreemin, rightsubtreemax, max);

  if(x==-1 || y ==-1)
    return -1;
  if(x==0) { leftsubtreemax = root->data; leftsubtreemin = root->data;}
  if(y==0) { rightsubtreemin = root->data; rightsubtreemax = root->data;}

  if(root->data < leftsubtreemax ||
     root->data > rightsubtreemin){
    return -1;
  }

  subtreemin = leftsubtreemin;
  subtreemax = rightsubtreemax;

  if(x+y+1 > max){
    max = x+y+1;
    bst_root = root;
  }

  return x+y+1;

}

int main()
{
  struct node* root=NULL;

  root=insert_bst(root,5);
  root=insert_bst(root,3);
  root=insert_bst(root,9);
  root=insert_bst(root,7);
  root=insert_bst(root,4);
  root=insert_bst(root,1);
  root=insert_bst(root,14);
  root=insert_bst(root,11);

  root->data = 0;

  int a,b,c,max=-32767;
  c = getmaxbst(root,a,b,max);
  printf("\nmax is %d\n",max);

  inorder_traverse(bst_root);
  return 1;
} 

TC O(N)

SC O(1)