# Arrays

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

## Save the largest area

Problem Statement In the historic city of Technisia there are rectangular monuments made of stones. The monuments are placed on the ground in such a way that they all lie in one row. The width of each monument is one unit and the length may vary.  The population of the city is growing and people need empty spaces to build houses and markets. The mayor decides to demolish the monuments and presents a demolition schedule. You being a monument lover, would like to preserve the most of what can be preserved, hence you start finding a solution to save the largest area. Upon your request the may...

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

## Minimum Range over K arrays

Introduction This is one interesting problem with a non-trivial solution, this has been asked in couple of good interviews. Here goes the problem statement. "Given K positive integer arrays, each of which contains elements in sorted order. Find a range of integers such that it must contain at least one element from each array and the range is minimum." May be a diagram can make this more clear. Here you go! Understanding the Minimum Range over K arrays problem. In the above diagram we have 3 arrays each containing elements in increasing order. Now, let us identify a range which cont...

## Student Enrollment Interview Question

Introduction This is another interview question which I find interesting. The problem statement goes as follow: "Its the beginning of a new academic year and I am a teacher of Data Structures and Algorithm subject. Many students with distinct roll numbers want to enroll for the class. After sometime few students wanted to opt out from the enrollment because they found some other subject much more interesting. Now, I also have a teaching assistant who can ask me the roll number of a student who is still enrolled into my class. It is not mandatory to tell him a different roll number every ti...