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) 

Find all the "maximal independent sets" in a given graph

Find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.