 # medium-problems

## Shortest path in an unweighted graph

Problem Statement Given the directed, connected and unweighted graph G, a Source and a Destination and the task to find the shortest path possible between two given vertices in the graph. Note: The path does not contain any cycle which means path have finite number of vertices. Example Input Expected Output Path : 0 3 Implementation in …

## Nodes are on same path in a tree or Not

Problem Statement Given a tree and two nodes of tree and the task to check whether these two nodes are on the same path from root to the bottom or not. Example Input Node1 = 1 Node2 = 5 Expected Output Yes Approach The idea is to apply Depth First Search on every node. And …

## Construct binary tree from inorder and postorder traversal

Problem Statement Given inorder and postorder traversal of a tree, construct the binary tree. Note:You may assume that duplicates do not exist in the tree. Sample Test Case Problem Solution Postorder traversal starts at the left subtree then right subtree and then goes to the root. Inorder traversal starts at the left subtree, then goes …

## Construct tree from in-order and pre-order traversal

Problem Statement Given preorder and inorder traversal of a tree, construct the binary tree. Note:You may assume that duplicates do not exist in the tree. Sample Test Case Problem Solution Preorder traversal starts at the root, goes to the left subtree and then to the right subtree. Inorder traversal starts at the left subtree, then …

## Inorder Successor in Binary Search Tree

Problem Statement Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Sample Test Case Problem Solution A node’s inorder successor is node with least value in its right subtree i.e. its right subtree’s left most child. If right subtree of the node doesn’t exists, …

## Maximum XOR of Two Numbers in an Array

Problem Statement Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Sample Test Cases Problem Solution The Approach is that instead of finding the maximum XOR of two numbers in an array, we can find two numbers in an …

## Minimum Area Rectangle

Problem Statement Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes. If there isn’t any rectangle, return 0. Sample Test Case Problem Solution Our Approach will be to sort the given points on the basis of …

## Prison Cells After N Days

Problem Statement There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules: If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied. Otherwise, it becomes vacant. …

## Shortest Distance to Target Color

Problem Statement You are given an array colors, in which there are three colors: 1, 2 and 3. You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1. Sample Test Cases Problem Solution The difficulty of this question is, how do we …

## Binary Search Tree to Greater Sum Tree

Problem Statement Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val. As a reminder, a binary search tree is a tree that satisfies these constraints: The left subtree of a node …

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]