Author Archives: Crazyadmin

Longest Increasing Subsequence

Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example : {10, 25, 9, 30, 21, 55, 40, 60, 75} Here Length of LIS Read More →

Root to leaf path with sum equal to given sum

Given a binary tree and a number,Write a function to find out whether there is a path from root to leaf with sum equal to given Number. In above tree, root to leaf paths exists for following sum. 7=> 1->2->4 9=> 1->3->5 10=>1->3->6 Implementation :

Mirror image of a binary tree

mirrorImage

Write a program to create a mirror copy of a binary tree i.e. left nodes become right and right nodes become left. Solution 1 : Following program will create a new mirror tree. Solution 2: This program will convert tree into it’s mirror tree.

Check if a binary tree is subtree of another tree

Given two binary trees T1 and T2, Find whether T2 is a subtree of T1.T1 has millions of nodes and T2 has hundreds of nodes. Solution: Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.

Prisoners and Hats Puzzle

hatpuzzle

Problem: Four prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed. The jailer puts three of the men Read More →

Find Majority Element in an array in O(n)

The majority element is the element that occurs more than half of the size of the array. Algorithm below loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then Read More →

Find largest BST in a binary tree

Given a Binary tree, Find largest Binary Search tree in it. A tree is a BST if: 1. Both left and right subtrees of a node are BSTs. 2. The node’s value is greater than its left subtree’s maximum value. 3. The node’s value is less than its right subtree’s minimum value. Top-Down approach : Read More →

Heap Data Structure

heapArray

Heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest , which is filled from the left up to a point. There are two Read More →

Print all root to leaf paths in a tree

Binary Tree

Given a binary tree,Print all root to leaf paths in it. root to leaf paths in above tree. [1 2 4] [1 3 5] [1 3 6] We start with the root and while traversing the tree we keep storing node data in array.We print the array when we reach a leaf node. Time Complexity Read More →

Mysql Query – Set 4

Given an Employee table with following structure EmpId EmpName Department ManagerId Part 1: Write a sql to retrieve all Manager’s Name with 5 or more subordinates. Note : ManagerId is also an Employee Id. Part 2 : Write a sql to retrieve ManagerId who have 5 or more subordinates in one column and comma separated Read More →

Diameter of a Tree

tree-diameter

Definition : Diameter of a tree is the longest path between two leaf nodes in a tree. We can see in the picture below that Diameter of the tree would be maximum of these: i. Diameter of left subtree. ii. Diameter of right subtree. iii. Path that goes through the root i.e. height of left Read More →

Replace node with sum of left and right subtree

Given a Binary tree , Replace each node with sum of values in left and right subtree. leaf nodes value will be changed to 0. Solution : i) Traverse the tree recursively. ii) Store the old value of the current node, recursively call for left and right subtrees and change the value of current node Read More →