WAP to find Kth Maximum or Largest in Binar Search Tree (BST)

class BST  

{
 private static Node root;
  
 public static void main(String [] args) {
  int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};
  root = buildBST(root, A);
  System.out.println("inorder: ");
  printBSTInorder(root);
  System.out.println();
  int sizeBST = sizeOfBST(root);
  System.out.println("Size of BST: " + sizeBST);
   
  for (int i=1; i<=sizeBST; i++) {
   Node node = nthLargestNode(root, i);
   System.out.println(i + " largest node: " + node.data);
  }
 }
  
 public static Node nthLargestNode(Node node, int N) {
   if (null == node) 
  {
   return null;
  }
    
  int R = sizeOfBST(node.right) + 1;
  if (N == R) 
  {
   return node;
  }
  if(N < R) 
  {
   return nthLargestNode(node.right, N);
  } 
  else 
  {
   return nthLargestNode(node.right, N-R);
  }
  }
 
  
 public static int sizeOfBST(Node node) {
  if (null == node) { return 0; }
  return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right));
 }
  
 public static Node buildBST(Node node, int [] A) {
  if (A == null) { return null; }
  int len = A.length;
  for (int i=0; i<len; i++) {
   node = insertIntoBST(node, A[i]);
  }
  return node;
 }
  
 private static Node insertIntoBST(Node node, int value) {
  if (null == node) {
   return new Node(value);
  }
  if (value <= node.data) {
   node.left = insertIntoBST(node.left, value);
  } else {
   node.right = insertIntoBST(node.right, value);
  }
  return node;
 }
  
 public static void printBSTInorder(Node node) {
  if (null == node) {  return ; }
  if (null != node.left) {
   printBSTInorder(node.left);
  }
  System.out.print(node.data + " ");
  if (null != node.right) {
   printBSTInorder(node.right);
  }
 }
}
 
class Node {
 Integer data;
 Node left;
 Node right;
  
 public Node(Integer data) {
  this.data = data;
  this.left = null;
  this.right = null;
 }
}

 Run Here http://ideone.com/rUQbn

 Time Complexity O(N^2) N is number of nodes in BST

 Space Complexity O(1)   Ping me if anything wrong here  

You have to count how many binary strings are possible of length "K". Constraint: Every 0 has a 1 in its immediate left. 111011 <-- valid 0111 <--- invalid 111100 <-- invalid

Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers

#define ARR_SIZE 100
#include<stdio.h>


void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}


/* The function prints all combinations of numbers 1, 2, ...n
that sum up to n. i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n,int m ,int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= m; k++)
{
arr[i]= k;
printCompositions(n-k,m, i+1);
}
}
}


/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 , 3 , 4 and 5  %d are\n", n);
printCompositions(n,n, 0);
getchar();
return 0;
}

Time Complexity O(n^m) Exponential
Space Complexity O(m)
Run Here http://ideone.com/clone/ETZTv

You are getting a stream of characters and at any time you can be asked to find out if the string received yet is palindrome or not. There can be multiple queries.He insisted to do it in better than O(n) and No extra space.

Given a BST, convert it so that each node has value equal to sum of all the nodes (including itself) which are greater than that node in the whole tree.

You are given a positive integer A. The goal is to construct the shortest possible sequence of integers ending with A, using the following rules

the first element of the sequence is 1,each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible),
each element is larger than all the preceding elements; that is, the sequence is increasing.

For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].

Given a string. Tell its rank among all its permutations sorted lexicographically

Given a number. And one permutation of that number. Find out in how many steps can you get back to the original number from the permutation if you use the same mapping again and again. If its not possible, then state so.

Example: 2315 -> 5213
So in this example Mapping is number at     1st index -> 2nd index
2nd index -> 4th index
3rd index -> 3rd index
4th index -> 1st index
So using same mapping can we come back to 2315. If yes then in how many steps?

GIven a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction.

For Example 

Input:

4

2 3 4 5

1 6 7 8

4 2 1 9

5 3 2 4

Output:

1 2 3 4 

4 7 1 5 

5 6 2 8 

3 2 4 9 

WAP to Count Tottal number of Characters, Words and Lines in File Efficiently

Guys Think its Funny & Can be solved Easily..but when interviewer ask how u counts no of words when u have more then 1 spaces or tabs,line feeds or new lines , i mean white spaces ?? Its Asked Recently from one of the my friend in Amazon & Adobe Both

here is the solution i have taken car of such Scenario

import java.io.FileReader;

class WordCount {
public static void main(String args[]) throws Exception {
int words = 0;
int lines = 0;
int chars = 0;

FileReader fr = new FileReader("E:/ubuntu/tests.txt");
int c = 0;
boolean lastWhite = true;
String whiteSpace = " \t\n\r";
char sp=' ';
char tab=' ';
char lin='\n';
char ret='\r';

System.out.println(" " +(int)sp + " " + (int)tab + " " + (int)lin + " " + (int)ret);

while ((c = fr.read()) != -1)
{
chars++;

System.out.println(c);

if (c == '\n')
{
lines++;
}

int index = whiteSpace.indexOf(c);
//icrement word count when 1st time index of any spaces occurs -1 so set next
//using boolena value lastwhite time it to false

if (index == -1)
{
if (lastWhite == true)
{
++words;
}
lastWhite = false;
}
else
{
lastWhite = true;
}

System.out.println("chars" + chars + " words" + words + " lines " + lines);
}

/*if (chars != 0)
{
++lines;
}*/


}
}

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

Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Transpose Algorithm 

Basically, we are converting rows into columns. E.g. a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should be changed to a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

a1 b1 c1 (i=1)

a2 b2 c2 (i=2)

a3 b3 c3 (i=3)

a4 b4 c4 (i= 4)

So we should write the array as a1 a2 a3 a4 b1 b2 b3 b4........, only this time, we are writiing column wise.

The program is recursive. The variable i is the number of groups

#include

#define SIZE 12 //multiple of 3

void arrange(int arr[], int n, int i)

{

if(i == 1)

{

arr[1] = arr[n];

arr[2] = arr[n <<1]

return;

}

int a = arr[i - 1];

int b = arr[n + i - 1];

int c = arr[2*n + i - 1];

arrange(arr, n, i - 1);

int x = 3 * (i - 1);

arr[x] = a;

arr[x + 1] = b;

arr[x + 2] = c;

}

int main()

{

int n = SIZE;

int a[SIZE], i;

printf("\nEnter %d numbers", SIZE);

for(i = 0; i <>

scanf("%d", a + i);

if(n != 0 && n % 3 == 0)arrange(a, n/3, n/3);

for(i = 0; i <n;i++)
printf(a[i]);

printf("\n");

}

Given a root and a node of a BST tree, write a function which print all the nodes which are a 'k' distance from the given nodes in sorted order. (distance can be upwards and downwards)

Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.

Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.

We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.

Suppose, Amazon have a Logging system Like This:
They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days.
We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”

Write a program to display numbers placed in this way.

Example:-

(1) One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

first point from where a truck will be able to complete the circle.

Given a circle. You have five points on that circle. Each
point corresponds to a petrol pump. You are given two sets of data.

1. The amount of petrol that petrol pump will give.
2. Distance from that petrol pump tp the next petrol pump.

(Assume for 1 lit Petrol the truck will go 1 km)

Now calculate the first point from where a truck will be able to
complete the circle.
(The truck will stop at each petrol pump and it has infinite
capacity).
Give o(n) solution. You may use o(n) extra space.

Problem: You are given a two dimensional bit array(elements are 0 or 1). Find number of islands in this array. One island is defined as all elemnts which are 1, including neighbours(with or without diagonals). Or Array Islands problem.