## Friday, September 4, 2015

### Problem

Given a BST with 2 nodes swapped fix it.

Example
Consider the BST:
Following is the correct BST
10
/  \
5    20
/ \
2   8

Now we swap  8 and 20, and BST is changed.

Input Tree:
10
/  \
5    8
/ \
2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.


In the previous post, we saw how many pairs in the input tree violate the BST property. Here we will fix it.

1. The swapped nodes are not adjacent in the inorder traversal of the BST.
 For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 25 7 8 10 15 20 5

If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.
2. The swapped nodes are adjacent in the inorder traversal of BST.
  For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25 
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.

How to Solve? We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.

code:
 private void swap(Node a, Node b) {
if (n1 == null || n2 == null)  return;
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}

public void recoverTree(Node root) {
Node cur = root, pre = null, first = null, second = null;
// in order travesal should return a sorted list
Stack stack = new Stack();
while (cur != null) { // find the left most child
stack.push(cur);
cur = cur.left;
}
while (!stack.isEmpty()) {
cur = stack.pop();

// is it wrong?
if (pre != null && cur.val < pre.val) {
if (first == null) {
// the first wrong item should be the bigger one
first = pre;
second = cur; // there is a chance that the two were swapped
} else {
// the second wrong item should be the smaller one
second = cur;
break;
}
}

// go to right child and repeat
pre = cur;
cur = cur.right;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
}

swap(first, second);
}


References

### Problem

Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post.

Example
Consider the BST:
Following is the correct BST
10
/  \
5    20
/ \
2   8

Now we swap  8 and 20, and BST is changed.

Input Tree:
10
/  \
5    8
/ \
2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.


Now number of pairs not following BST property are 3. The reason is :
• 10-20
• 10-8
• 20-8

### Solution

Method 1 - Using in-order traversal
We can have following solution:
1. Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8
2. Find the number of inversions in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8.
Time complexity - O(n logn) as O(n) time for inorder traversal and O(nlogn) for number of inversions in the sorted array.

### For a Given node of a binary tree, print the K distance nodes.

Problem
You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.

Example
start node = 18, k = 2 , then output = 2, 19, 25
start node = 18, k = 3,  then output = -4, 3

### Solution

We have already seen a similar problem, where we have to find k distance from the root and k distance from the leaf. Find the distance from root is easy. In the second case of printing from bottom to top (k distance from leaves), we know the direction, i.e. we have to go up. But here we have to find the k elements even going upwards.

Note :- Parent pointer is not given.

Method 1 - Using the recursion

(Printing nodes at a disance of K  downwards  is easy). Its a simple recursive function.So moving to nodes which are in upwards direction.

There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 18 and k is 2, then such nodes are 19 and 25.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 18 and k is 2, the node 2 comes in this category.

Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown().

How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.
// Recursive function to print all the nodes at distance k in the
// tree (or subtree) rooted with given root. See
void printkdistanceNodeDown(Node root, int k)
{
// Base Case
if (root == null || k < 0)  return;

// If we reach a k distant node, print it
if (k==0)
{
System.out.println(root.data);
return;
}

// Recur for left and right subtrees
printkdistanceNodeDown(root.left, k-1);
printkdistanceNodeDown(root.right, k-1);
}

// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward.  This function
// Returns distance of root from target node, it returns -1 if target
// node is not present in tree rooted with root.
int printkdistanceNode(Node root, Node target , int k)
{
// Base Case 1: If tree is empty, return -1
if (root == null) return -1;

// If target is same as root.  Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (root == target)
{
printkdistanceNodeDown(root, k);
return 0;
}

// Recur for left subtree
int dl = printkdistanceNode(root.left, target, k);

// Check if target node was found in left subtree
if (dl != -1)
{
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from target
if (dl + 1 == k)
System.out.println(root.data) endl;

// Else go to right subtree and print all k-dl-2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(root.right, k-dl-2);

// Add 1 to the distance and return value for parent calls
return 1 + dl;
}

// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left subtree
int dr = printkdistanceNode(root.right, target, k);
if (dr != -1)
{
if (dr + 1 == k)
System.out.println(root.data) endl;
else
printkdistanceNodeDown(root.left, k-dr-2);
return 1 + dr;
}

// If target was neither present in left nor in right subtree
return -1;
}


Method 2 - Using the queue

Use a queue of size K to store the root to node path.
Now since, the queue is of size K.As soon as we find the NODE  in tree, the node at front of queue is at a distance K from NODE. It can be the case that the front node is less than K distant from NODE.
So, maintain a counter.

Now start popping a node from queue which is at distant  i from NODE, and print all downwards nodes at distance K-i  in its other subtree.We only need to print the nodes in other  subtree to avoid Error.

Note :- Since we need to print the nodes in sorted order, we can maintain a priority queue to store the nodes and after processing the nodes, we can print it.

References

### Problem

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

Example
(Please ignore the empty node, and consider it null)

k = 1, Answer = 2, 19 , 21
k = 2, Answer = 5, 18 , 19

### Solution

The idea is to traverse the tree. Keep storing all ancestors till we hit a leaf node. When we reach a leaf node, we print the ancestor at distance k. We also need to keep track of nodes that are already printed as output. For that we use a boolean array visited[].

// This function prints all nodes that are distance k from a leaf node
//   path[] - Store ancestors of a node
//   visited[] - Stores true if a node is printed as output.  A node may be k
//                 distance away from many leaves, we want to print it once
void kDistantFromLeafUtil(Node node, int path[], bool visited[],
int pathLen, int k)
{
// Base case
if (node==null) return;

// append this Node to the path array
path[pathLen] = node.data;
visited[pathLen] = false;
pathLen++;

// it's a leaf, so print the ancestor at distance k only
// if the ancestor is not already printed
if (node.left == null && node.right == null &&
pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
{
System.out.print(path[pathLen-k-1] + " ");
visited[pathLen-k-1] = true;
return;
}

// If not leaf node, recur for left and right subtrees
kDistantFromLeafUtil(node.left, path, visited, pathLen, k);
kDistantFromLeafUtil(node.right, path, visited, pathLen, k);
}

// Given a binary tree and a nuber k, print all nodes that are k
//   distant from a leaf
void printKDistantfromLeaf(Node node, int k)
{
int[] path = new int[MAX_HEIGHT];
boolean[] visited = new boolean[MAX_HEIGHT];
//all the elements false in visited
Arrays.fill(visited, false);
kDistantFromLeafUtil(node, path, visited, 0, k);
}


References

### Problem

Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.

Example
Dist(-4,3) = 2,
Dist (-4,19) = 4
Dist(21,-4) = 3
Dist(2,-4) = 1

### Solution

The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula.

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)
'n1' and 'n2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of n1 and n2
Dist(n1, n2) is the distance between n1 and n2.


Example take the case of Dist(-4,3)
LCA(-4,3) = 2
Dist(-4,3) = Dist(5,-4)+Dist(5,3) - 2 * (5,2) = 3 + 3 - 2 * 2 = 2

Now lets do the coding.

Code

// Returns level of key k if it is present in tree, otherwise returns -1
int findLevel(Node root, int k, int level)
{
// Base Case
if (root == null)
return -1;

// If key is present at root, or in left subtree or right subtree,
// return true;
if (root.key == k)
return level;

int l = findLevel(root.left, k, level+1);
return (l != -1)? l : findLevel(root.right, k, level+1);
}

// This function returns pointer to LCA of two given values n1 and n2.
// It also sets d1, d2 and dist if one key is not ancestor of other
// Note that we set the value in findDistUtil for d1,d2 and dist
// d1 -. To store distance of n1 from root
// d2 -. To store distance of n2 from root
// lvl -. Level (or distance from root) of current node
// dist -. To store distance between n1 and n2
Node findDistUtil(Node root, int n1, int n2, Integer d1, Integer d2,
Integer dist, int lvl)
{
// Base case
if (root == null) return null;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (root.key == n1)
{
d1 = lvl;
return root;
}
if (root.key == n2)
{
d2 = lvl;
return root;
}

// Look for n1 and n2 in left and right subtrees
Node left_lca  = findDistUtil(root.left, n1, n2, d1, d2, dist, lvl+1);
Node right_lca = findDistUtil(root.right, n1, n2, d1, d2, dist, lvl+1);

// If both of the above calls return Non-null, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
{
dist = d1 + d2 - 2*lvl;
return root;
}

// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null)? left_lca: right_lca;
}

// The main function that returns distance between n1 and n2
// This function returns -1 if either n1 or n2 is not present in
// Binary Tree.
int findDistance(Node root, int n1, int n2)
{
// Initialize d1 (distance of n1 from root), d2 (distance of n2
// from root) and dist(distance between n1 and n2)
Integer d1 = -1, d2 = -1, dist;
Node lca = findDistUtil(root, n1, n2, d1, d2, dist, 1);

// If both n1 and n2 were present in Binary Tree, return dist
if (d1 != -1 && d2 != -1)
return dist;

// If n1 is ancestor of n2, consider n1 as root and find level
// of n2 in subtree rooted with n1
if (d1 != -1)
{
dist = findLevel(lca, n2, 0);
return dist;
}

// If n2 is ancestor of n1, consider n2 as root and find level
// of n1 in subtree rooted with n2
if (d2 != -1)
{
dist = findLevel(lca, n1, 0);
return dist;
}

return -1;
}


findDistance() is the main function which calculates the distance, which calls findDistUtil which calculates distance as well as find the LCA in case n1 is not the ancestor of n2 or vice versa.
If n1 is ancestor of n2 or vice versa, we use findLevel to simply find the difference between 2 levels.

Time Complexity - O(n) as we do single traversal on the tree

Note that in java we dont have out parameters in function, like we have in c#. Hence I have used Integer Object, so that I can set the value in d1,d2 and dist as we have pass by value for primitive types in java, but we needed pass by reference.

References

### Problem

Count leaf nodes in a binary tree

### Solution

Method 1 - Recursive
Here is the logic:
1. If node is NULL then return 0.
2. Else If left and right child nodes are NULL return 1.
3. Else recursively calculate leaf count of the tree using below formula.
Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree

Here is the recursive solution:
int countLeaves(Node node){
if( node == null )
return 0;
if( node.left == null && node.right == null ) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}


Time complexity - O(n)

Method 2 - Iterative
Here we can use Queue. Idea is to use Level Order traversal.

int countLeaves(Node root)
{
int count=0;
if(root==null)
return 0;

Queue<Node> myqueue = new Queue<Node>();
myqueue.push(root);

while(!myqueue.empty())
{
Node temp;
temp=myqueue.pop();//take the top element from the queue
if(temp.left==null && temp.right==null)
count++;
if(temp.left!=null)
myqueue.push(temp.left);
if(temp.right!=null)
myqueue.push(temp.right);
}
return count;
}


Time complexity - O(n)
Space Complexity - O(n)  for queue

Referenes

## Friday, June 26, 2015

### Problem

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends.
You are given a N×Nmatrix M which consists of characters Y or N. If M[i][j]=Y, then ith and jth students are friends with each other, otherwise not. You have to print the total number of friend circles in the class.
Input Format
First line of the input contains an integer N - (size of the matrix), followed by N lines each having N characters.
Output Format
Print the maximum number of friend circles.
Constraints
1N300
Each element of matrix friends will be Y or N.
Number of rows and columns will be equal in the matrix.
M[i][i]=Y, where 0i<N
M[i][j] = M[j][i], where 0i<j<N

Here is the code

Thanks

## Wednesday, June 10, 2015

### Lazy Caterer's sequence

Problem
Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that.

Solution
The solution to this is very simple, if you know mathematics. :P

Number of pieces p
p = ( n^2+n+2)/2
p = C(n+1,2) + 1


More on wikipedia - http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence.

Proof
When a circle is cut n times to produce the maximum number of pieces, represented as p = ƒ(n), the nth cut must be considered; the number of pieces before the last cut is ƒ(n − 1), while the number of pieces added by the last cut is n.
To obtain the maximum number of pieces, the nth cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the nth line itself is cut in n − 1 places, and into n line segments. Each segment divides one piece of the (n − 1)-cut pancake into 2 parts, adding exactly n to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.
Thus, the total number of pieces after n cuts is

f(n) = n + f(n-1)
This recurrence relation can be solved. If ƒ(n − 1) is expanded one term the relation becomes
f(n) = n + n-1 + f(n-2)
Expansion of the term ƒ(n − 2) can continue until the last term is reduced to ƒ(0), thus,
f(n) = n + n-1 + n-2 ..... + 1 + f(0)
But f(0) = 1 , because there is one piece before any cuts are made, this can be rewritten as
f(n) = 1 + (1+2+3 + .... n)
This can be simplified, using the formula for the sum of an arithmetic progression:
f(n) = 1+ n*(n+1)/2 = ( n^2+n+2)/2

## Tuesday, June 2, 2015

### Lego Blocks Problem

Problem statement - https://www.hackerrank.com/challenges/lego-blocks
solution - http://stackoverflow.com/questions/15424945/lego-blocks-dynamic-programming
http://stackoverflow.com/questions/913566/has-anyone-seen-a-programming-puzzle-similar-to-this

Code -

Thanks.

## Monday, May 25, 2015

### K reverse a linked list with increasing K

Problem
Reverse k elements in the linked list such that k goes on increasing

Example
Eg.        1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7

### Solution

You can take this problem here. Here we are just increasing k.

   public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {

ListNode<Integer> startNode = null;
ListNode<Integer> endNode = null;

int k = 2;
while (nextNode != null) {

startNode = nextNode;
endNode = nextNode;

for (int i = 1; i < k; i++) {
endNode = endNode.next;
if (endNode == null) {
break;
}
}

if (endNode != null) {
// Save the node next to endNode
nextNode = endNode.next;
endNode.next = null;
// Reverse the list starting from startNode

startNode = reverseListIterative(startNode);
k++;
} else {
nextNode = null;
//              // Save the node next to endNode
//              nextNode = endNode.next;
//              endNode.next = null;
// Reverse the list starting from startNode

startNode = reverseListIterative(startNode);
}

} else {
ListNode<Integer> temp = startNode;
while(temp!=null){
if(temp.next==null){
break;
}
temp = temp.next;
}
}
}

}

public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
ListNode<Integer> prevNode = null;
ListNode<Integer> nextNode = null;

while (currNode != null) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}

return prevNode;
}



Time complexity - O(n)

## Saturday, May 16, 2015

### Convert Binary Tree to Doubly linked list in level order

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.
For traversing the tree, we'll use level / order traversal a.k.a breadth first search.

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
{
if (root == NULL)
return NULL;
queue nodeQueue;
struct Node* listIT = NULL; //current node being processed
struct Node* prevNode = NULL; //previous node processed
//initialize the stack
nodeQueue.push(root);
while (!nodeQueue.empty())
{
//process next node in stack
prevNode = listIT;
listIT = nodeQueue.front();

nodeQueue.pop();
if (listIT->left != NULL)
nodeQueue.push(listIT->left);
if (listIT->right != NULL)
nodeQueue.push(listIT->right);
if (prevNode != NULL)
prevNode->right = listIT;
listIT->left = prevNode;
}

//connect end node of list to null
listIT->right = NULL;
}


Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:
1. If the root node is null, we return null because the tree is empty.
2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:

prevNode = listIT gets reference to the last processed node because we are about to process a new node

listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.

nodeQueue.pop() removes the top node out of the queue.

We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.

Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.

6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

## Sunday, May 3, 2015

### Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

Problem
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.

Example
Example 1
Input
s1 = abcd
s2 = bacd

Output
Ans = 1
Reason, just move b forward and we get it.

Example 2
Input
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Output
Ans =7
Explanation
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Characters b,e,g are in the order, rest characters have to brought first.

### Solution

This is a DP problem,  LCS of the 2 strings is adf, and rest of the character are moved forward, and rest of the characters will be moved forward.

### Maximize the number of magical gems by passing through array of house

Problem
There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.

Example
Gem array = 1 2 0 4 5 6 2 3
color array = 0 0 1 1 1 0 0 1 (r=1,b=0)
o/p = 20 (4*5)

### Solution

This is similar to maximum product subarray, but there is another condition of red color.

Here is the code below:
int maximumMoney(int n, int[] colour, int[] gems) {
int max = 1;
int red = 0;
int start = 0, end = 0;
int actualMax=1;
for(int i=0;i<gems.length;i++){
if(gems[i]>0)
{
max = max*gems[i];
end++;
if(colour[i] == 1)
red++;

}else{
if(actualMax < max){
if(red%2==0)
{
actualMax = max;

}else{
int temp = max;
int startRed = -1, endRed = -1;
for(int i=start;i<end;i++){
if(colour[i]==1 && startRed==-1){
startRed = i;
endRed = i;
}else if(colour[i]==1)
endRed = i;
}
int tempProdStart = 1; tempEndProd = 1;
for(int i=start;i<=startRed;i++){
tempProdStart = a[i]*tempProdStart ;

}

for(int i=endRed;i<=end;i++){
tempEndProd= a[i]*tempEndProd;

}
int minProd = Math.min(tempProdStart, tempEndProd);

max = temp/minProd;
if(max > actualMax){
actualMax = max;
}

}

}

start = end+1;
end = end + 1;

}
}
}


Time complexity - O(n)

### Find the least wastage in cutting the Trees?

Problem
You are given n Trees with their heights in an array. and you are given a value k units , that much wood you need to collect. You can have an axe of any height you want but you can use only 1 axe when you choose.

Assume height to be integral value.

### Solution

So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k.

It is always possible to choose an axe height such that chopping all trees above this height will result in zero waste.
To see this, just sort the trees in descending order of height, and consider moving the axe height gradually down from the top of the tallest tree.

Suppose the tallest tree has height h. Notice that the function:

f(x) = total amount of wood cut by using an axe of height h - x to
chop all trees of at least this height


• Sort the trees by their height in descending order
•  starts at 0 when x = 0, and is an increasing piecewise linear function of x, with no discontinuities. Every time x increases past the point when one or more trees just start to become choppable, the rate of change of f(x) increases, but this doesn't cause problems.
• So for any desired level of wood y, just (conceptually) intersect a horizontal line of height y with the graph f(x), and drop a vertical line from this point down to the x axis to find its value. (How to actually do this in a program I leave as an exercise, but here's a hint: consider trees in decreasing height order to find the pair of adjacent x values x1, x2 such that chopping at h - x1 produces too little wood, and h - x2 produces too much.)

Reference

### Problem

Give logic for implementing "diff" command in Linux.
Consider various test cases and explain what will happen in each. The two files are source code and are huge..
For e.g.
File 1: 1-2-3-4
File 2: 1-3-4-2

### Solution

The operation of diff is based on solving the longest common sub-sequence problem.
In this problem, you have two sequences of items:
a b c d f g h j q z
a b c d e f g i j k r x y z
and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is
a b c d f g j z
From a longest common subsequence it's only a small step to get diff-like output: if an item is absent in the subsequence but present in the original, it must have been deleted. (The '–' marks, below.) If it is absent in the subsequence but present in the second sequence, it must have been added in. (The '+' marks.)
e h i q k r x y
+ - + - + + + +

Resource