interview questions

Build Balanced Binary Search Tree from Array

Introduction This post describes the algorithm to build binary search tree from array of sorted elements. However, this technique can be used to build balanced binary search tree from array. A balanced binary tree is a binary tree which has minimum height. To know more about various aspects of a binary search tree, please visit my previous posts. What does balanced means? In this post as we are trying to build a BST, we will assume the input to be a sorted array. In case, we are just building a binary tree, we can take any array as an input. Let me explain the process with the help of a ...
Read More

Print all paths of robot through the grid

Introduction This is a supplement to the previous post where we were interested in just one path of a robot from top left corner to the bottom right corner. In this post we will print all paths of robot moving through a given grid containing few blocked cells. The algorithm for this solution remains the same, we just need few tricks to get that right. Here, I will explain the idea behind printing all paths of robot through the grid. Approach Here, let us discuss what different we need to do to print all the paths. As we can recall from the previous post, the moment we reached the destina...
Read More

Find the maximum possible profit

Problem Statement Given an array of stock prices per share for a given share over a time period. Calculate the maximum possible profit per share one could have made . Here we do not consider short selling as an option. The trader must have purchased the stocks before selling it. The problem statement is a real world definition of the problem called maximum positive difference. For the above two arrays, here are the maximum profit per share one could have made: A : 18.0 (difference between 21 and 3) B : 13.0 (difference between 19 and 6) What is Maximum Positive Difference? ...
Read More

Maximum Element Sliding Window

A very interesting problem indeed! Often asked in Interviews in various forms and we will discuss one of these forms here in this post. Problem Statement - Maximum Element Sliding Window Given a stream or array of elements (preferably integers). Find the elements with maximum value in a window of length K where the window slides by one step to the right every time. What is a Sliding Window? Given an array A, a sliding window of length K is a range of fixed size K in the array such that the range slides to the right by one index. Here is a diagram to explain how sliding window will look...
Read More

Count Triangles formed by the elements of array

Problem Statement Given a sorted array of distinct integers, each of these integers can represent a length. The task at hand is to count the number of possible triangles which can be made through these lengths. Of course, if you chose one length to be one side of the triangle, you cannot use that length again in the same triangle. This means, no triangle contains the same length more than once. Important Note: For given sides of lengths a, b and c. A triangle can only be formed if sum of any two sides is greater than the third side. This is called the triangle inequality. The sum of any...
Read More

Building Heaps from an array of keys

[nextpage title="Introduction"] In the last post we learnt the basics of the heap data structure, its array and tree representations. We also learnt about the heap property and its significance. In the process of learning we understood that a given node can be disturbed and the heap property needs to be restored using the Heapify operation. Here in this post, we will try building heaps from an array of keys. Building Heaps Let us think about the easiest way to build a heap. Assume we are given the below array A: This clearly is not satisfying the max heap property because the root ...
Read More

Cursed Trees – Interview Question

Problem Statement This is an awesome interview question which tests our ability to extensively use data structures. We are given an array of trees with different heights. The trees have a curse upon them, they do not grow any more and for a given pair of trees, if a tree is taller than the one to its left then the tree will die in a year. The task at hand is to find out, the number of years after which no trees will die. Explanation Year 1 : At the end of the first year the trees with height 6 , 14 and 10 will die. All of these trees have a smaller tree to their left and the r...
Read More