Interview Question

Rotating an Array by a fixed distance

Problem Statement Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array. Here is an example of input and output. The problem seems very easy until s...
Read More

Median of a Stream of Integers

[nextpage title="Problem Statement"] Here is a very interesting problem which has been asked in many interviews and coding competitions. The problem statement goes as follows: Given a never ending stream of number, at any point in time, find the median of all the numbers received till that point. This means, we need to recalculate the new median whenever there is a number available in the input stream. This problems seems to be a very practical one, imagine a lot of sensors in manufacturing plants are pushing data about temperature, pressure and other physical parameters. It is very importa...
Read More

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

Linked List Batch Reversing

Introduction As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList. Understanding the problem statement Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same. For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed. Approach We need to use our reverse linked list func...
Read More

Spiral Traversal

Spiral Traversal or Zigzag Traversal in a Tree. This is the fourth article in the Tree Traversals - Online Classes. Recently I wrote an article on Level Order Tree Traversal. Another problem on the same lines is to traverse the tree in a zigzag manner. That is also termed as spiral traversal. This question has been asked in many companies during the interview process. Although it is not very specific problem, if you understand the idea behind traversing a tree in breadth first manner, then you can easily solve this. Please read further for more understanding. Defining the problem L...
Read More