Tag Archives: interview questions

Binary Search Trees from keys 1 to n

Construct Binary Search Trees from keys 1 to n Problem statement to construct a Binary Search Tree(BST) from keys 1 to n. We are given a list of consecutive numbers from 1 to . Determine the number of binary trees that can be constructed from these numbers. Example for building a Binary Search Tree from keys… Read More »

Remove duplicates in a Binary Search Tree

Remove duplicate nodes in a Binary Search Tree (BST). Problem statement to remove redundant nodes in a Binary Search Tree. Given a binary search tree (BST), remove the redundant nodes to obtain a tree without the duplicate elements. Example: INPUT: array: 1,5,8,10,10,12,15,20,20,20 OUTUT: 10(2) / \ 5 15 / \ / \ 1 8 12 20(3)… Read More »

Sorted Linked List to balanced Binary Search Tree

Sorted Linked List to balanced Binary Search Tree (BST). Problem statement to create a Binary Search Tree from a sorted linked list. Given a singly linked list in a sorted order, create a balanced binary search tree (BST). Example: INPUT: Linked List: 1->5->8->10->12->15->20 OUTUT: 10 / \ 5 15 / \ / \ 1 8 12 20 Create… Read More »

Print common nodes in two Binary Search Trees

Print common nodes in two Binary Search Trees Problem statement to print common nodes in two Binary Search Trees (BST). Given two binary search trees, print all the elements that are common in both the trees. Example: INPUT:Tree 1 10 / \ 5 15 / \ / \ 1 8 12 20 Tree 2 7… Read More »

Turn an image by 90 degrees

Turn an image by 90 degrees Turn an image by 90 degrees Problem Statement: An image can be treated as 2D matrix which can be stored in a buffer. We are given the matrix dimensions and it’s base address. Write a program to turn it by 90 degrees. Turn an image by 90 degrees Example:… Read More »

Create a BST such that sum of all greater keys is added to its every key

Create a BST such  that sum of all greater keys is added to its every key. Problem statement to construct a Binary Search Tree (BST) such  that sum of all greater keys is added to its every key: Given a balanced binary search tree (BST), build a binary search tree such that all nodes in original… Read More »

Find a Triplet in the Given Array that sums to a Given Value

Find a Triplet in the Given Array that sums to a Given Value This post deals with the problem of finding a triplet in the given array ,the sum of whose elements are equal to a given value. Find a Triplet in the Given Array that sums to a Given Value Problem Statement: Given an… Read More »

Find the maximum j – i such that arr[j] greater than arr[i]

Find the maximum j – i such that arr[j] greater than arr[i] Find the maximum j – i such that arr[j] greater than arr[i] Problem Statement: Given an array find the maximum difference j – i such that arr[j] > arr[i]. Find the maximum j – i such that arr[j] greater than arr[i] Example: arr[] = {2, 8, 1, 9, 0}… Read More »

Maximum Length Bitonic Subarray

Maximum Length Bitonic Subarray This post deals with the problem of finding maximum length bitonic subarray from a given input array. Maximum Length Bitonic Subarray Problem Statement: Given an array arr[] containing n positive integers, we need to find a bitonic subarray which is of maximum length from the input array arr[]. A sequence is… Read More »

k largest elements in an array using heaps

k largest elements in an array using heaps We suggest that you go through this post first: Building a max heap. k largest elements in an array using heaps Problem Statement: Write a program for printing k largest elements in a given array. Make use of heaps for an efficient program. k largest elements in an… Read More »