# 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 ...

## 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...

## 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? ...

## 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...

## 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...