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

WAP to Convert it to a sorted array with minimum cost. You are given an array of positive integers.

You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element
For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3


we can make the DP more efficient You don't need to scan the whole previous column when calculating costs of decrementing. Rather there are only two
possibilities.

Algorithm Given By Gene

DP is better for this problem.
Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
sequence with the last element being no more than m. And we always
draw m from the set V of values in a.
So here is the new DP:
C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
C(n, m) = min (
a[n] + C(n - 1, m), // delete
(a[n] <= m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
)
In case you don't follow, the "//delete" line is saying that we
already know the cost of making everything up to element n-1 non-
decreasing and no more than m. This, by recursive assumption, is just
C(n-1,m). The additional cost of deleting a[n] is a[n].
The "//decrement" line is similar, but there are 2 cases. If a[n] is
more than m, we must decrement it. The cost here consists of making
everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
In the other case, a[n] is m or less. So there's no need to
decrement, but we must get the elements a[1..n-1] to be no more than
a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
least cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.
So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and "m" means that a
decrement was based on the value of m rather than a[n].
We take the answer from C(6,5) = 5.
Implementing this is a little tricky because m values are drawn from
V. You could use a hash table for the m-axis. But it's more
efficient to store V in an array and convert all the values of m in
the DP into indices of V. Because all the indices lie in [ 1 .. |
V| ], we can use simple arrays rather than hash tables to represent
the rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.
For C, we also need to convert all the indices to origin 0.
So here's the final O(n^2) code. I think this is a correct
implementation. If anyone has an example that breaks it, I'd like to
see.
#include
#define NMAX 10000
int cost(int *a, int N)
{
int i, j, max, Nv;
int V[NMAX], A[NMAX], B[NMAX];
int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
// Compute set V with no duplicates.
// Remember where max element is.
Nv = max = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < Nv; j++)
if (a[i] == V[j])
break;
if (j == Nv) {
V[Nv++] = a[i];
if (V[j] > V[max])
max = j;
}
a[i] = j; // Convert a to indices.
}
// Fill in first row of C.
for (i = 0; i < Nv; i++)
Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0;
// Fill in the rest of the rows of C.
for (i = 1; i < N; i++) {
for (j = 0; j < Nv; j++) {
int del = Cm[j] + V[a[i]];
int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
Cn[j] = (del < dec) ? del : dec;
}
// Swap row buffers so current becomes previous.
int *tmp = Cn; Cn = Cm; Cm = tmp;
}
return Cm[max];
}

int main(void)
{
static int a[] = { 5, 1, 1, 1, 3, 1 };
printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0]));
return 0;
}
TC O(N^2)
Sc O(n)
Run Here https://ideone.com/VdsC0

WAP to Find a Word in Dictionary at ith Position Efficiently

If you have a dictionary (sorted list of words) of unknown size and given a function which returns the word in the dictionary at a specified 'i'th location. Suggest an algorithm for finding a word.

We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.

WAP a Program By Choosing Best Data structure which is supposed to log number of user requests per second.

Make a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds. It can be at any time for example he will say at 71st second that tell me how many hits for past 30 seconds or something, but this window can go maximum upto 60 seconds to in the previous example 11 to 71.

WAP to Generate The Series of Ugly or Lucky Number

Question:Generate The Series of Lucky/Ugly Number or Find the First K Ugly/Lucky Number



eg. 1 2 4 8 10 16 20 25 32 64 100 125 128

Algorithm

Answer: Consider an array of first 10 ugly numbers: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, , , , }

Next ugly number can be calculated by just multiplying one of all these numbers with 2 or 3 or 5.

The least number whose double is not present in the list is 8 (any number before this has its double present in the list). So one of the candidates for next ugly number is 8*2=16

The least number whose multiple by 3 is not present in the list is 5 (any number before this has its multiplied by 3 present in the list). So other candidate for next ugly number is 5*3 = 15.

The least number whose multiple by 5 is not present in the list is 3 (any number before this has its multiplied by 5 present in the list). So other candidate for next ugly number is 3*5 = 15.

Least of these three numbers (15) is our next ugly number.

Now how to choose next ugly number is pretty simple. Since our ugly number is 15 it means now 3*5 and 5*3 are present in the list. So next numbers whose multiple by 3 and 5 respectively are not present in the list are 6 and 4 respectively. The least number whose double is not present in the list remains unchanged at 8. So next candidates are 8*2, 6*3 and 4*5. We will continue in this manner for further list.
Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.


Algorithm: Keep 3 pointers with you and keep track whose multiple by 2,3 and 5 are present and whose are not. Choose the least number of next candidates and increase the pointer by 1 for the chosen one. If 2 candidates are same, and we chose that number, increment both the pointers as in example above.


#include
#include
using namespace std;
#define k 20 //modify it

int Lucky[k], ptr2, ptr3, ptr5;

int minimum(int x,int y,int z)
{
if (x return (y}

int nextLucky(int num)
{
int num2,num3,num5;
if(num==0)
{
Lucky[num]=1;
ptr2=ptr3=ptr5=0;
return Lucky[num];
}

num2=Lucky[ptr2]*2;
num3=Lucky[ptr3]*3;
num5=Lucky[ptr5]*5;

Lucky[num]=minimum(num2,num3,num5);

if(Lucky[num]==num2) ptr2++;
if(Lucky[num]==num3) ptr3++;
if(Lucky[num]==num5) ptr5++;

return Lucky[num];
}

int main()
{
int i;

for(i=0; i printf("Lucky number no. %d is %d\n", i+1,nextLucky(i));
}

Dynamic Programming
TC O(n)
SC O(n)
Run Here https://ideone.com/B8rCN


Variation
Google Interview Question in different Way:
Given expression E=(2^i * 5^j), increment i and j to ensure the output is sorted.
so above logic will remain same except we need multiples of 2's & 5's thats it

TC O(n)
SC O(n)
Run Here https://ideone.com/M2Bmz

Given integer n decide if it is possible to represent it.SPOJ Prob. 91 as a sum of two squares of integers.

In number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
x^2+y^2=c
with x and y integers, if and only if

For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:

On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares.

More Info http://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares


I used Above Fact to Solve the Question(to Solve SPOJ problem You have to Modify the program )

#include
#include

int isSquare(int c)
{
int a=0;int b=sqrt(c);
if(c%4==1)//remove this to solve spoj probelm
{
while(a<=sqrt(c))
{ int pows=pow(a,2)+pow(b,2);
if(a!=b && pows==c ) //a!=b means 1^1+1^1=2 not allowed
{ printf(" yes Possible \t %d %d ", a,b);
return 1;
}
else if(pows a++;
else b--;

printf( " %d %d %d \n", a,b,pows);
}

}
else
{ printf( "not Possible");
return 0;
}
return 0;
}

int main()
{
printf(" %d ", isSquare(29));
}


TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/nLGDs

WAP to design an efficient algorithm to find whether String s3 is formed from the interleaving of String s1 and String s2

Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not.
s1= aabccabc
s2= dbbabc
s3= aabdbbccababcc

If I am Correct a Similer Iterative Approahc can be written as

bool test(A,B,C)
{
i=j=k=0;
while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); } Similer Recursive Apparoahc in Which Interviewer Show More Interest bool interleaved(char *s1, char *s2, char *s3) { // Base case, all strings are empty return (!s1[0] && !s2[0] && !s3[0]) || // First character of s1 is next in s3 (s1[0] && (s1[0] == s3[0]) && interleaved(s1+1,s2,s3+1)) || // First character of s2 is next in s3 (s2[0] && (s2[0] == s3[0]) && interleaved(s1,s2+1,s3+1)); } No Doubt This Problem Requires DP (Top-Down memozation will be Best )Approach & I had Solved It Using the Same. Below is one of The Possible Approach. I found A Good Discussion Here AlgoGeek


TC O(N) length of Bigger String thats S3 Need to Check
SC O(1)
Run Here http://ideone.com/n6RLc

WAP to Check That Binary Representation of Given Number is Palindrome of NOt

Here i Found an Algorithm for This

Algorithm
take two varible i -0 & j=N (number)
keep storing bits of number from lsb in reverse order (e.g. shift i left & do or operation with j&1 (mind shud click this the way to extract right most set bit from number :)
keep shifting j right while j is not equals to 0

Explaintion

The first while loop reverses the rightmost bits of the number, stopping after the leftmost 1-bit. It does this by anding out the low-order bit of the number j and oring it into a new number, i. Then j is shifted right. E.g., the number j = 01101 becomes 01011. If the number j matches the input number, then the input number is a palindrome, and the procedure returns TRUE. If the reversed number is less than the input number, it may be that the input number has trailing zeros. E.g., 0110 has reversal 0011. Since this is less than the input number, we shift it left until it is no longer less, giving 0110. Since this equals the input number, we call the number a palindrome. If you don't want to consider the leading zeros, then you leave out the second while loop and say that the number 0110 is not a palindrome.


#include

bool isPalindrome(int N)
{
int i = 0, j = N;
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}

int main()
{
printf( " %d ", isPalindrome(9));

}


TC O(logn) as You Know that n=logk(base 2)
Sc O(1)
Run Here http://ideone.com/ddovS


Most Optimized Way can Be Find Here http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable in O(1) :)

WAP Search An Element in N-Ary Tree Efficiently

Given an n-ary tree , you have to search for an element in the tree without using recursion.
int FindNum(node *head, int num)
{

}

Note: Review Needed...??

Using BFS is Absolutely Efficient Way to Solve it..kep in Mind Recursion(DFS) is not good because it needs memory stack.

#include
#include
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node *child[];
   
};
 
/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
 
/* Given a binary tree, print its nodes in level order
   using array for implementing queue */
void printLevelOrder(struct node* root,int val)
{
  int rear, front;
  struct node **queue = createQueue(&front, &rear);
  struct node *temp_node = root;
  int i=0;
  while(temp_node)
  {
     if(temp_node->data==val)
printf("item found");
else
printf(" Item DNE");

  i=0;
    /*Enqueue left child */
if(temp_node->child[i])
{
     while(temp_node->child[i)
{
       enQueue(queue, &rear, temp_node->left);
i++;
}
 
    
 
    /*Dequeue node and make it temp_node*/
    temp_node = deQueue(queue, &front);
  }
}
 
/*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)++;
}    
 
struct node *deQueue(struct node **queue, int *front)
{
  (*front)++;
  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(11);
int i=0,j=0;int k=1;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
   root->child[i]= newNode(k);
k++;
}
k++;
root=root->child[i];
}
  
  printf("Level Order traversal of binary tree is \n");
  printLevelOrder(root);
 
  getchar();
  return 0;
}

TC O(nlogn)
SC O(1)
Run Here

WAP to convert a given string to its palindrome string by appending min chars at the right side of string.

Example
e.g. i/p is abc , o/p should be abcba
i/p is aaba , o/p should be aabaa.

aaba is not a palindrome

aaaa is a palindorme (so it does not require anything)

aabaa is also a palindrome (so it does not require anything)

Example 1:
-------------
str = abcbad;
revStr = dabcba;
output = abcbadabcba

Example 2:
----------------
str = abcb;
revStr = bcba;
output = abcba;

Ecample 3
str = rrrr
revstr=rrrr
output=rrrr

You have a note to write by cutting and pasting necessary letters from the book, write an algorithm to see if you can write the note.

import java.util.*;
import java.io.*;

public class NoteChecker
{

private final File noteFile;
private final File bookFile;

private int noteTotalLength = 0;

private void checkIfFileExists(File file)
{
if( ! file.exists() )
{
throw new IllegalArgumentException("File doesn't exists '" + file.getPath() + "'");
}
}

public NoteChecker(String noteFilePath, String bookFilePath){
super();

noteFile = new File(noteFilePath);
checkIfFileExists(noteFile);

bookFile = new File(bookFilePath);
checkIfFileExists(bookFile);
}

private int[] getRequiredLetters()
{

final int[] requiredLetters = new int[128];

Scanner noteSc = null;

try{

noteSc = new Scanner(noteFile);

while( noteSc.hasNextLine() ){
String line = noteSc.nextLine();

for(int i =0; i < line.length(); i++ ){
char ch = line.charAt(i);
++requiredLetters[ch];
++noteTotalLength;
}
}
}
catch(Exception ex ){
ex.printStackTrace();
return requiredLetters;
}
finally {
if( noteSc != null ){
noteSc.close();
}
}

return requiredLetters;
}

public boolean canCreateNote()
{

final int[] requiredLetters = getRequiredLetters();

Scanner bookSc = null;

try
{

bookSc = new Scanner(bookFile);

while( bookSc.hasNextLine() )
{
String line = bookSc.nextLine();

for(int i =0; i < line.length() && noteTotalLength > 0; i++ )
{
char ch = line.charAt(i);

if( requiredLetters[ch] > 0 )
{
--requiredLetters[ch];
--noteTotalLength;
}
}
}
}
catch(Exception ex)
{

ex.printStackTrace();
return false;
}
finally
{
if( bookSc != null )
{
bookSc.close();
}
}
return noteTotalLength == 0 ? true : false;
}



public static void main(String a[])
{

NoteChecker ob=new NoteChecker("E:/ubuntu/note.txt","E:/ubuntu/Input.txt");
System.out.println(ob.canCreateNote());


}
}
Above Solution is provided By Max

TC O(m+n)
SC O(1)

WAP to Find Maximum and minimum of an array using minimum number of comparisons

Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.

First of all, how do we return multiple values from a C function? We can do it either using structures or pointers.

We have created a structure named pair (which contains min and max) to return multiple values.

?
struct pair
{
int min;
int max;
};
And the function declaration becomes: struct pair getMinMax(int arr[], int n) where arr[] is the array of size n whose minimum and maximum are needed.


Method 1

Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element)

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;

/*If there is only one element then return it as min and max both*/
if(n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}

/* If there are more than one elements, then initialize min
and max*/
if(arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[0];
minmax.min = arr[1];
}

for(i = 2; i {
if(arr[i] > minmax.max)
minmax.max = arr[i];

else if(arr[i] < minmax.min)
minmax.min = arr[i];
}

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

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

In this method, total number of comparisons is 1 + 2(n-2) in worst case and 1 + n – 2 in best case.
In the above implementation, worst case occurs when elements are sorted in descending order and best case occurs when elements are sorted in ascending order.



METHOD 2 (Tournament Method) (Efficient)

Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.

Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Implementation

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;

/* If there is only on element */
if(low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}

/* If there are two elements */
if(high == low + 1)
{
if(arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);

/* compare minimums of two parts*/
if(mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;

/* compare maximums of two parts*/
if(mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Number of Instruction Executed less
Time Complexity: O(n)
Space Complexity
Run Here https://ideone.com/jB3tu

Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
If n is a power of 2, then we can write T(n) as:

T(n) = 2T(n/2) + 2
After solving above recursion, we get

T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.

WAP to generate the Dyck Word from given string.??

A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's

It Can Be Solved by Catalan Number Cn=2nCn/(n+1)=2n!/n!*n+1!

Cn is the number of Dyck words of length 2n. A For example, the following are the Dyck words of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.


class DyckWord
{
public static void printDyckWord(int xnum, int ynum, char[] str, int count)
{
if (xnum < 0 || ynum < xnum) return; // invalid state
if (xnum == 0 && ynum == 0)
{
System.out.println(str); // found one, so print it
}
else
{
if (xnum > 0) { // try a left paren, if there are some available
str[count] = 'X';
printDyckWord(xnum - 1, ynum, str, count + 1);
}
if (ynum > xnum) { // try a right paren, if there’s a matching left
str[count] = 'Y';
printDyckWord(xnum, ynum - 1, str, count + 1);
}
}
}

public static void printDyckWord(int count)
{
char[] str = new char[count*2];//As DyckWord is 2n length nX + nY
printDyckWord(count, count, str, 0);
}
public static void main(String a[])
{
printDyckWord(3);
}
}

Time Complexity O(n)
Space Complexity O(1)
Run Here http://www.ideone.com/pBgGO

WAP to Calculate the next Smallest Prime Number From Given Number Efficiently

Given a number n, compute the smallest prime that is bigger than n. For example, n=8, then the smallest prime that bigger than 8 is 11. n=23 o/p is 29 & so on

#include

int power(int x, int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


double sqrt(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}

int next_prime(int n)
{
int i=n+1;


/*The largest known Mersenne prime (243,112,609 − 1) is also the largest known prime
number,else // no such prime exist explain above
int pow=power(2,243112609)−1;
if(n>pow)
return 0; this line wont execute overflow*/

while(true)
{

if(is_prime(i))
break;
i++;

}
return i;
}
int main()
{
printf( " %d ", next_prime(23));
return 0;

}


TC of isprime is O(sqrt(n))
TC of sqrt is log(n)
TC of pow function is O(logn)
TC of next prime O(k*sqrt(n) where k is number of iteration used to find next smallest prime so k is constant & so overall time complexity of this algo is O(sqrt(n))

TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/5ViQe

Feel Free to Comment or Optimize the solution or if any issue with time complexity

WAP find Minimum Distance Between two Nodes In Binary Tree

Algorithm

Assume each node has parent pointer:
let distance d=0;
1. Start from the node 1 and find the distance of the node from root by traversing up. let it be d1.
2. start from node 2 and do the same. let this distance be d2.
3.if(d1>d2) then traverse d1-d2 nodes up from the node2. add d=d+(d1-d2)
4.now traverse up from each node from that place until both point to same node. while traversing up make d=d+2;
5. when both reaches to same node, it represents the common ancestor. so substract 1 from d.
6. now d represents the distance between two nodes.

Algo Suggested By sreenivas putta then I Coded It.

Efficiency Level:- Not Efficient (cause Parent Pointer Overhead)

#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;
struct node* parent;
};

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

int distance(struct node* root, struct node* n1,struct node* n2)
{
int d=0,d1=0,d2=0;
struct node* temp=n1;

while(temp->parent!=NULL)
{
temp=temp->parent;
d1++;

}
temp=n2;

while(temp->parent!=NULL)
{
temp=temp->parent;
d2++;

}
if(d1>d2)
{

d=d1-d2;
while((d1-d2)>0)
{

n1=n1->parent;
d1--;
}

}
else
{
d=d2-d1;
while((d2-d1)>0)
{
n2=n2->parent;
d2--;
}

}
while(n1!=n2)
{

n1=n1->parent;
n2=n2->parent;
d+=2;

}
return d;

}

/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;

/* first print data of node */
printf("%d ", node->data);

/* then recur on left sutree */
printPreorder(node->left);

/* now recur on right subtree */
printPreorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->parent=NULL;

root->left = newNode(2);
root->right = newNode(3);
root->left->parent=root;
root->right->parent=root;

root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->parent=root->left;
root->left->right->parent=root->left;

root->left->left->left = newNode(6);
root->left->left->right = newNode(7);
root->left->left->left->parent= root->left->left;
root->left->left->right->parent= root->left->left;

root->left->right->left = newNode(8);
root->left->right->right = newNode(9);
root->left->right->left->parent= root->left->right;
root->left->right->right->parent= root->left->right;

root->right->left = newNode(10);
root->right->right = newNode(11);
root->right->left->parent=root->right;
root->right->right->parent=root->right;


root->right->left->left = newNode(12);
root->right->left->right = newNode(13);
root->right->left->left->parent=root->right->left;
root->right->left->right->parent=root->right->left;

root->right->right->left = newNode(14);
root->right->right->right = newNode(15);
root->right->right->left->parent=root->right->right;
root->right->right->right->parent=root->right->right;

//printf("\n Preorder traversal of binary tree is \n");
//printPreorder(root);

printf( " %d ", distance(root, root->left->left->left , root->right->right->right));

getchar();
return 0;
}

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

Design The Data Structure & Algorithm to Show That Their Exist a Path (Connection Between Two Person on Facebook)

How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection,
or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).


Approach:
Forget that we’re dealing with millions of users at first. Design this for the simple case.
We can construct a graph by assuming every person is a node and if there is an edge between
two nodes, then the two people are friends with each other.
class Person {
Person[] friends;
// Other info
}
If I want to find the connection between two people, I would start with one person and do a simple breadth first search.
But... oh no! Millions of users!
When we deal with a service the size of Orkut or Facebook, we cannot possibly keep all of our data on one machine. That means that our simple Person data structure from above doesn’t quite work—our friends may not live on the same machine as us. Instead, we can replace our list of friends with a list of their IDs, and traverse as follows:
1. For each friend ID: int machine_index = lookupMachineForUserID(id);
2. Go to machine machine_index
3. Person friend = lookupFriend(machine_index);
There are more optimizations and follow up questions here than we could possibly discuss, but here are just a few thoughts.
Optimization: Reduce Machine Jumps
Jumping from one machine to another is expensive. Instead of randomly jumping from machine
to machine with each friend, try to batch these jumps—e.g., if 5 of my friends live on one machine, I should look them up all at once.
Optimization: Smart Division of People and Machines
People are much more likely to be friends with people who live in the same country as them. Rather than randomly dividing people up across machines, try to divvy them up by country, city, state, etc. This will reduce the number of jumps.
Question: Breadth First Search usually requires “marking” a node as visited. How do you do that in

this case?
Usually, in BFS, we mark a node as visited by setting a flag visited in its node class. Here, we don’t want to do that (there could be multiple searches going on at the same time, so it’s bad to just edit our data). In this case, we could mimic the marking of nodes with a hash table to lookup a node id and whether or not it’s been visited.
Other Follow-Up Questions:
»»In the real world, servers fail. How does this affect you?
»»How could you take advantage of caching?
»»Do you search until the end of the graph (infinite)? How do you decide when to give up?
»»In real life, some people have more friends of friends than others, and are therefore more likely to make a path between you and someone else. How could you use this data to pick where you start traversing?
The following code demonstrates our algorithm:

import java.util.*;

public class Server
{
ArrayList machines = new ArrayList();
}

public class Machine {
public ArrayList persons = new ArrayList();
public int machineID;
}

public class Person {
private ArrayList friends;
private int ID;
private int machineID;
private String info;
private Server server = new Server();

public String getInfo() { return info; }
public void setInfo(String info) {
this.info = info;
}

public int[] getFriends() {
int[] temp = new int[friends.size()];
for (int i = 0; i < temp.length; i++) {
temp[i] = friends.get(i);
}
return temp;
}
public int getID() { return ID; }
public int getMachineID() { return machineID; }
public void addFriend(int id) { friends.add(id); }

// Look up a person given their ID and Machine ID
public Person lookUpFriend(int machineID, int ID)
{
for (Machine m : server.machines)
{
if (m.machineID == machineID)
{
(Person p : m.persons)
{
if (p.ID == ID){
return p;
}
}
}
}
return null;
}

// Look up a machine given the machine ID
public Machine lookUpMachine(int machineID)
{
for (Machine m:server.machines)
{
if (m.machineID == machineID)
return m;
}
return null;
}

public Person(int iD, int machineID)
{
ID = iD;
this.machineID = machineID;
}

}

Algorithm & Solution Given By Galye

WAP to Find Maximum Difference between two Index of array such that value at 1st index is less then value at 2nd Index, Efficiently

WAP to find out maximum j-i such that a[i]
Method 1

Algorithm
Use two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
struct maxdif
{
int i;
int j;
int maxDiff;

};
struct maxdif maxIndexDiff(int a[],int n)
{
struct maxdif maxdif;
maxdif.maxDiff=-1;
int i=0,j=0;
for(i=0;i {
for(j=n-1;j>0;j--)
{
if(a[i] {
maxdif.i=i;
maxdif.j=j;
maxdif.maxDiff=j-i;
}
}
}
return maxdif;
}

int main()
{ int ar[]={9,2,3,4,5,6,7,8,20,1};
int n=sizeof(ar)/sizeof(int);
struct maxdif max_diff=maxIndexDiff(ar,n);
printf(" j=%d i=%d maximum difference=%d", max_diff.j,max_diff.i,max_diff.maxDiff);
return 0;
}

Worst Case O(n^2)
Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Best Case O(n)
Input: {6, 5, 4, 3, 2, 1}
Output: -1

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

Method 2 (Algorithm Given By Celicom


Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(jwhile(B[i] < C[j] && jmax_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}

so To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.


#include
 
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}
 
int min(int x, int y)
{
    return x < y? x : y;
}
 
/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);
 
   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);
 
    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);
 
    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {9,2,3,4,5,6,7,8,20,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}


Time Complexity O(n)
Space Complexity O(n)
Ryun Here https://ideone.com/vQOMi