interview questions

Building Heaps from an array of keys

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 (value of A[1]) is not the larg...

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

Dynamic Programming – CrazyNumbers

Problem Statement We are interested in finding the count of all N digit crazy numbers. Let us define a crazy number. A crazy number is a number where the magnitude of its consecutive digits differ by 1. For e.g.: Here is a list of all 2 digit crazy numbers: The total number of 2 digit crazy numbers is 17. You can notice that in all the numbers the digits differ only by 1. Similarly for three digit numbers the count reaches 32. For four digit numbers it becomes 61 and very soon it increases exponentially to 924903595810 for a 40 digit number. It might look like the a problem wh...