WAP to Calculate The Maximum Width of Binary Tree With & Without Recursion

Given a binary tree, write a function to get the maximum width of the given tree. Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.

So the maximum width of the tree is 3.



Algortihm:
There are basically two functions. One is to count nodes at a given level (getWidth), and other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from root.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
width = getWidth(tree, i);
if(width > maxWdth)
maxWdth = width
return width
/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;
else if level greater than 1, then
return getWidth(tree->left, level-1) +
getWidth(tree->right, level-1);


#include
#include

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

/*Function protoypes*/
int getWidth(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to get the maximum width of a binary tree*/
int getMaxWidth(struct node* root)
{
int maxWidth = 0;
int width;
int h = height(root);
int i;

/* Get width of each level and compare
the width with maximum width so far */
for(i=1; i<=h; i++)
{
width = getWidth(root, i);
if(width > maxWidth)
maxWidth = width;
}

return maxWidth;
}

/* Get width of a given level */
int getWidth(struct node* root, int level)
{

if(root == NULL)
return 0;

if(level == 1)
return 1;

else if (level > 1)
return getWidth(root->left, level-1) +
getWidth(root->right, level-1);
}

/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lHeight = height(node->left);
int rHeight = height(node->right);
/* use the larger one */

return (lHeight > rHeight)? (lHeight+1): (rHeight+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->right = newNode(5);
root->right->right = newNode(8);
root->right->right->left = newNode(6);
root->right->right->right = newNode(7);

/*
Constructed bunary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
printf("Maximum width is %d \n", getMaxWidth(root));
getchar();
return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here https://ideone.com/rTjk2


Optimization(Iterative Algorithm)

#include
#include
#include

typedef struct TreeNode {
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns maximum width of a binary tree without recursion

We are using level order traversal
*/

int Width(Tree t) {

int width = -1;

if(t != NULL) {

std::list q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

int cur = 0;

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, compare width with cur width and push NULL if q not empty

if(width < cur)
width = cur;

cur = 0;

if(!q.empty())
q.push_back(NULL);

}
else {

cur++;

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}
}

}

return width;
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data) {

TreeNode *n = (TreeNode *)calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}


int main() {

/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->left->left->right = makeTreeNode(70);
t->left->right->left = makeTreeNode(70);
t->left->right->right = makeTreeNode(70);
t->right->left->left = makeTreeNode(60);
t->right->left->right = makeTreeNode(160);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*level 4*/
t->left->left->left->left = makeTreeNode(70);

printf("%d\n", Width(t));

return 0;
}


Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/rs3tO


Algorithm is Proposed By My Friend Sambasiva He also Runs on Blog On Application of data Structure & Algorithm

WAP to Find Diameter of Binary Tree

Its Really Good Question Because i have found this can be asked in number of ways to make candidate confused. see the number of possible way below.


Find Number of Nodes on the Longest Path in Binary Tree so one thing is sure that this path comprises on two leaves with maximum distance in BT..isn't it

Finding The Longest Path in Binary Tree will use the algorithms used by Diameter of Tree

PS:Don't confused with finding the maximum distance between two nodes in Binary Tree
its completely different algorithm & it has also been solved so u can search in blog.

Algorithm Used to Calculate Diameter/ finding two nodes which are separated by maximum difference.

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with same 7 as a diameter but different orientation. (also note that there is more than one path in each tree of length nine, but no path longer than nine nodes).



Diameter 7



Diameter 7

The diameter of a tree T is the largest of the following quantities:

1 the diameter of T’s left subtree
2 the diameter of T’s right subtree
3 the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

#include
#include

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

/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);

/* returns max of two integers */
int max(int a, int b);

/* The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}

/* Function to get diameter of a binary tree */
int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == 0)
return 0;

/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);

/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}

/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */



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

/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1 D=4 lh=2,rh=1
/ \
D=3,rh=1 2 3
lh=1 / \
4 5 D=1,lh=rh=0
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Diameter of the given binary tree is %d\n", diameter(root));

getchar();
return 0;
}

Time Complexity (N^2)
Space Complexity O(1)
Run Here https://ideone.com/s9OdR

Optimization(2nd Method)
The above implementation can be optimized by calculating the height in the same recursion rather than calling a height() separately. This optimization reduces time complexity to O(n).


#include
#include

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

/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);

/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */

/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:

int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;

if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;

return max(lh + rh + 1, max(ldiameter, rdiameter));
}


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

/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

int height=0;
printf("Diameter of the given binary tree is %d\n", diameter(root,&height));

getchar();
return 0;
}

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

More Info http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

WAP to Find Number of Divisor & sum of All Proper Devisor of Number Efficiently

Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.
Output

One integer each line: the divisor summation of the integer given respectively.
Example

Sample Input:
3
2
10
20

Sample Output:
1
8
22


Writing the O(N) code is not the big deal for this..question but writing quality code O(sqrt(n)) is efficient way to solve it.Thats why great companies used to ask such question because the wants quality code.

#include
#include
using namespace std;

int main()
{
int n;
int sum=1;
while(cin>>)
{
int numOfDiv=0;
int loop=(int)sqrt(n);

for (int i=2;i<=loop;i++)
{
if(n%i == 0)
{
numOfDiv += 2;
sum += i + n/i;
}

}

if(loop*loop==n)
{
numOfDiv--;
sum -= loop;
cout<}

cout<<"\nnumber of div are :"<cout<<"sum of proper divisors"<}


return 0;
}

TC o(sqrt(n))
SC O(1)
Run Here For Getting Sum of Divisor http://ideone.com/ElSVQ

Given an array find all the groups that make the sum equal to an integer given n.

Example

100,10,30,20,90,70,55,80,15,60,0
Sum=100

Possible ways are 100+0, 20+80,10+20+70,60+30+10,55+15+10+20...and so on..


Source http://max.cs.kzoo.edu/cs215/lectures/w5-graph-coloring.pdf
http://max.cs.kzoo.edu/cs215/lectures/w5-graph-coloring.pdf

WAP to Finding The Minimum Window In An Array Which Contains All Given Elements (Need Not to be Contiguous)

Question: Given a set CHARS of characters and a string INPUT, find the minimum window in INPUT which will contain all the characters in CHARS in complexity O(n).

Ex:
INPUT = "ABBACBAA"
CHARS = "AAB"

Minimum window is "BAA".

For example
Test length
[A B B A] C B A A 4
A B B [A C B A] A 4
[A B B A] C [B A A] 3 answer


lgorithm
Input is the given array and chars is the array of character need to be found.

1) Make an integer array shouldfind[] of len 256 . i-th element of this array will have a the count how many times we need to find element of ASCII value i.
2) Make another array hasfound of 256 elements, which will have the count of required element found till now.
3) Count <= 0
4) While input[i]
. a. If input[i] element is not to be found -> continue
. b. If input[i] element is required => increase count by 1.
. c. If count is length of chars[] array, slide the window as much right as possible.
. d. If current window length is less than min length found till now. Update min length.
5) end



#include
#include
#include
#include
using namespace std;

#define MAX 256

void minlengthwindow(char input[], char chars[], int start, int finish)
{
int shouldfind[MAX] = {0,};
int hasfound[MAX] = {0,};
int cnt = 0;
int minwindow = INT_MAX;

int charlen = strlen(chars);
for (int i=0; i< charlen; i++)
shouldfind[chars[i]] += 1;

int iplen = strlen(input);
start = 0;
finish = iplen;
int j = 0;

for (int i=0; i< iplen; i++)
{
if (!shouldfind[input[i]])
continue;
hasfound[input[i]] += 1;

if (shouldfind[input[i]] >= hasfound[input[i]])
cnt++;

if (cnt == charlen)
{
while (shouldfind[input[j]] == 0 || hasfound[input[j]] > shouldfind[input[j]])
{
if (hasfound[input[j]] > shouldfind[input[j]])
hasfound[input[j]]--;
j++;
}
if (minwindow > (i - j +1))
{
minwindow = i - j +1;
finish = i;
start = j;
}
}
}
cout << start << " " << finish << endl;
}


int main()
{
char a[]="ABBACBAA";
int size=sizeof(a)/sizeof(int);
char chars[]="AAB";
minlengthwindow(a,chars,0,size);


}


TC O(N) If you walk through the code, i and j can traverse at most N steps (where N is input size size) in the worst case, adding to a total of 2N times. Therefore, time complexity is O(N).

SC O(1)
Run Here http://ideone.com/kJwMS

Suppose Your Are Writing a Message to Your Friends , Assume Simple Mobile of Old Time Where You Don't Had Seperate buttons for chars , so you have to type some digit and that show you number of possible chars , now suppose you press some random keys on mobile & send some fake message to your friendsCan You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed.

e.g. if numbers pressed 9876124305 then output should be same as in this file https://ideone.com/VtoBo

Can You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed. What Will Be Time and Space Complexity .

Follow Up:

Can You Output only those strings that are in a given dictionary. (and length of the dictionary is small.) What Will Be Complexity of Problem , Explain Clearly .

Algorithm:

Data Structure used : Array

Problem Solving Paradigm Used: Recursion

class Number2Text
{       // Mapping From 0-9 Number in to Corresponding Strings  
        // when you press 1 only 1 is showed , when you press 0 , 0 is showed 
        //those assume simple mobile else 1 used to show many chars then we can store 
       //chars in string and can pass thi string at 1st string in below array.
       //e.g. lest 1 may support 1 -> , . ! ~ @ # $ % ^ & * ( ) { } [ ] / ? : ; " ' etc.
       //so we can write String one=" ,.!~@#$%^&*(){}[]/?:;"' "; can pass one string 
       //to below 
         
         private static String[] mapping = {"0","1","ABC", "DEF", "GHI", "JKL", "MNO",
                        "PQRS", "TUV", "WXYZ"};
 
 
public static void combinations(int[] number, char[] buf, int numIndex) 
{
 
          for (int i = 0; i < mapping[number[numIndex]].length(); i++) 
         {
                        buf[numIndex] = mapping[number[numIndex]].charAt(i);
                        if (numIndex < number.length - 1) 
                        {
                                combinations(number, buf, numIndex + 1);
                        } 
                        else
                                System.out.println(buf);
         }
}
 
 
 
public static void main(String[] args)  
{
                int num[] ={9,8,7,6,1,2,4,3,0,5};// { 5, 8, 5, 5, 0, 3, 3, 4, 4, 7 };
                Number2Text.combinations(num, new char[num.length], 0); 
} 
 
}

Time Complexity O(4*T(n-1)) //Worst Case

Space Complexity O(N)

Run Here Small Input https://ideone.com/9T6yb

              Average Size Input https://ideone.com/T07Qy

              Large Input https://ideone.com/l4sbz

Aplplication : Frequently Used in Mobile Phone  , When You Type Message , it Show you Different Combinations. Its Great Code :) .

Feel Free to Comment on anything you like such that how we can improve complexity , other way to solve same problem or if anything wrong here , Thanks for visiting.

WAP a function to determine the number of bits required to convert integer A to integer B.

Write a function to determine the number of bits required to convert integer A to integer B.
Input: 31, 14
Output: 2

class digit_prob
{

public static int bitSwapRequired(int a, int b)
{
int count = 0;
for (int c = a ^ b; c != 0; c = c >> 1) {
count += c & 1;
}
return count;
}

public static void main(String a[])
{
System.out.println(bitSwapRequired(10,9));

}

}


TC O(n)
Sc O(1)
Run Here https://ideone.com/VaBTS

WAP to Print Binary Representation of Decimal Number Thats Passed as String to Function

Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”

Note: Review Needed

First, let’s start off by asking ourselves what a non-integer number in binary looks like. By analogy to a decimal number, the number n = 0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3).
Printing the int part of n is straight-forward (see below). To print the decimal part, we can multiply by 2 and check if the 2*n is greater than or equal to one. This is essentially “shifting” the fractional sum. That is:
r = 2*n = 2*0.101 = 1*(1 / 2^0) + 0*(1 / 2^1) + 1*(1 / 2^2) = 1.01
If r >= 1, then we know that n had a 1 right after the decimal point. By doing this continuously,we can check every digit.

class digit_prob
{

public static String printBinary(String n)
{

int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
double decPart = Double.parseDouble(
n.substring(n.indexOf('.'), n.length()));
String int_string ="";
while (intPart > 0) {
int r = intPart % 2;
intPart >>= 1;
int_string = r + int_string;
}
StringBuffer dec_string = new StringBuffer();
while (decPart > 0) {
if (dec_string.length() > 32) return "ERROR";
if (decPart == 1) {
dec_string.append((int)decPart);
break;
}
double r = decPart * 2;
if (r >= 1) {
dec_string.append(1);
decPart = r - 1;
} else {
dec_string.append(0);
decPart = r;
}
}
return int_string + "." + dec_string.toString();
}
public static void main(String a[])
{
System.out.println(printBinary("3.5"));

}

}

TC O(K) k= length of number e.g digits in number
SC O(1)
Run Here https://ideone.com/7yjsH

WAP to Find a String in Sorted Array of String " Containing Large number of empty Strings in it Efficiently....Think of O(logn) ??

Given a sorted array of strings which is interspersed with empty strings, write a method
to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

class stringSearch
{
 

public static int search(String[] strings, String str,

 int first, int last) 
 {
        while (first <= last) 
        {
                // Ensure there is something at the end
          while (first <= last && strings[last] =="") 
                {
                        --last;
                }
                
                if (last < first) 
                {
                        return -1;  

// this block was empty, so fail
                }
                 int mid = (last + first) >> 1;
                
                 while (strings[mid] =="") 
                {
                         ++mid;  

// will always find one
                }
                
                 int r = strings[mid].compareTo(str);
                 if (r == 0) return mid;
                 
                 if (r < 0) 
                 {
                         first = mid + 1;
                 }
                 else 
                {
                         last = mid - 1;
                 }
         }
 return -1;
 }
 
 public static int search(String[] strings, String str) 
 {
         if (strings == null || str == null) return -1;
         if (str =="") 
         {
              for (int i = 0; i < strings.length; i++) 
                {
                      if (strings[i] == "") return i;
                }
                 return -1;
         }
         return search(strings, str, 0, strings.length - 1);
 }
 
   public static void main(String a[])
  {
  String str_arr[]=new String[]{"at", "", "", "",  

"ball", "", "", "car", "", "", "dad", "", ""};
     String str="ball";
     System.out.println(search(str_arr,str));
  
  }
}

TC O(n) when all array having empty string the 1st inner loop will run n time
SC O(1)
Run Here https://ideone.com/f9FcL

WAP to Calculate nth Prime Number Efficiently

java program

class nth
{

public static void main(String a[])
{
nthfindPrime(5);
}
static void nthfindPrime(int n)
{
int i=0,count=2;
if(n==1)
{
System.out.println("1st prime =2");
return;
}
if(n==2)
{
System.out.println("2nd prime =3");
return;
}

while(true)
{
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
System.out.println(n+"th prime ="+i);
break;
}
i++;
}
}
}

Time Complexity O(n)
Space Complexity O(1)

Run Here https://ideone.com/OHmO9


A More Efficient Version

#include
#include
using namespace std;

int main()
{
int i=0,count=2;int n=60;
if(n==1)
{
cout << "1st Prime Number = 2\n";
return 1;
}
if(n==2)
{
cout << "2nd Prime Number = 3\n";
return 2;
}
i=5;
float root2 = sqrt(2);
int limit;
while(true)
{
limit = (int)(i/root2);
for(int j=2;j<=limit;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
cout << n << "th Prime No. : " << i << endl;
break;
}
i++;
}
}

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

But number of Instruction Reduced
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/ncfzh