Hotel Automation Controller - Interview coding problem

This is one of the problems I got via a friend who recently faced a company called Sahaj Software a clone company to Thoughtworks.

Problem Statement:

Hotel Automation Controller Problem  Statement

A very prestigious chain of Hotels is facing a problem managing their electronic equipments. Their equipments, like lights, ACs, etc are currently controlled manually, by the hotel staff, using switches. They want to optimise the usage of Power and also ensure that there is no inconvenience caused to the guests and staff.

So the Hotel Management has installed sensors, like Motion Sensors, etc at appropriate places and have approached you to program a Controller which takes inputs from these sensors and controls the various equipments.

The way the hotel equipments are organised and the requirements for the Controller is below:

• A Hotel can have multiple floors
• Each floor can have multiple main corridors and sub corridors
• Both main corridor and sub corridor have one light each
• Both main and sub corridor lights consume 5 units of power when ON
• Both main and sub corridor have independently controllable ACs
• Both main and sub corridor ACs consume 10 units of power when ON
• All the lights in all the main corridors need to be switched ON between 6PM to 6AM, which is the Night time slot
• When a motion is detected in one of the sub corridors the corresponding lights need to be switched ON between 6PM to 6AM (Night time slot)
• When there is no motion for more than a minute the sub corridor lights should be switched OFF
• The total power consumption of all the ACs and lights combined should not exceed (Number of Main corridors * 15) + (Number of sub corridors * 10) units of per floor. Sub corridor AC could be switched OFF to ensure that the power consumption is not more than the specified maximum value
• When the power consumption goes below the specified maximum value the ACs that were switched OFF previously must be switched ON

Motion in sub corridors is input to the controller. Controller need to keep track and optimise the power consumption.

Write a program that takes input values for Floors, Main corridors, Sub corridors and takes different external inputs for motion in sub corridors and for each input prints out the state of all the lights and ACs in the hotel. For simplicity, assume that the controller is operating at the night time. Sample input and output below.

Initial input to the controller: Number of floors: 2

Main corridors per floor: 1

Sub corridors per floor: 2

Since the hotel management is trying this for the first time, they would be changing the requirements around which electronic equipments are controlled and the criteria based on which they are controlled, so the solution design should be flexible enough to absorb these requirement changes without significant change to the system.

The solution to this problem involves approaching in an object oriented manner. Also we need to see here that we should use a Command/Strategy Pattern given there could be changes in the behavior based on external factors. I have not included the timings from the problem but from on here it should be easily extensible.

Code below:

Cheers!
Braga

Write a program to find the number corresponding to a alphabet and vice-versa with the given rule

Problem:
A = 1
B = A*2 + 2
C = B*2 + 3...
1. Write a program to find the number corresponding to a alphabet and vice-versa.
2. Given a series like GREP find the total in numbers. Given a number like 283883, find the shortest alphabetical series corresponding to it.
Compute above recursively when required and do not pre-compute and store beforehand.

Solution:
The solution is straightest-forward. Java code given below.

Cheers!
Braga

Write a program to build a small knowledge base about top "N" movies listed at IMDB

This was an interesting problem that I came across with. This problem is like an open book exam and race against time. The problem had to be solved within an allocated amount of time with a technology stack that is limited only to Ruby/Python/Node.js/Perl.

Few googling here and there and with some knowledge about Ruby I was able to solve this problem within an hour.

Problem Statement:

Build a small knowledge base about top "N" movies listed at http://www.imdb.com/chart/top. Each movie should mention the cast written on the individual page of the movie.
Given the name of a cast member, you should be able to return the movies out of the top "N" movies he/she has acted in. "N" will be passed by the user.
The knowledge base should be built during the runtime and stored in a data structure of your choice.
Q1. For example, if N=3, then you should parse the first 3 movies' individual pages from that page (http://www.imdb.com/chart/top) and build the knowledge base of the cast (there are about 15-20 on every page). Upon querying for "Morgan Freeman", you should return "The Shawshank Redemption". Do not use any external api for this.
Use only Ruby/Python/Node.js/Perl.

Solution:


Cheers!
Braga

Novel finder Program

This was one of the problems that I had faced during one of my interviews. The problem sounded interesting and I was given 1 hour to solve it which I did quite comfortably.

Problem:

The K-doublets of a string of characters are the ordered pairs of characters that are K distance from each other. A string is K-singular if all its K- doublets are different. A string is Novel String if it is K-singular for all possible K distances.

For e.g. take the string FLBL, its 0-doublets are FL, LB and BL. Since all these are different, FLBL is 0-singular. Similarly, its 1-doublets are FB and LL, since they are different FLBL is 1-singular as well. Lastly, the only 2-doublet of FLBL is FL, so FLBL is 2-singular. Hence, FLBL is a Novel String.

Note that the fact that FL is both a 0-doublet and 2-doublet is insignificant as zero and two are different distances.

Input:

The input is one or more non-empty strings of at most 100 capital letters, each string on a line by itself, followed by a line containing only two dollars ($$) signaling the end of the input.

Output:

For each input line, output whether or not it is a Novel string using the exact output format shown below.

Sample Input: (Input File: novel.in)

FLBL

FFLL

ORDINARY

R

QYQRQYY

$$

Sample Output: (Output File: novel.out)

FLBL is a Novel string

FFLL is not a Novel string

ORDINARY is a Novel string

R is a Novel string

QYQRQYY is not a Novel string

Solution:

To attack this problem, you first have to find all the doublets for each distance starting from 0 to the maximum distance which would string's length minus one. Then keep pushing them into a hash set. Whenever the add() method of the Set returns false, it means we are adding a duplicate hence, its not a Novel text. Here is the Java source code.


Cheers!
Braga

Reconstruct a binary tree given its Inorder and Preorder traversals in Java

This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.

This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.

Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.

Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I

I tweaked a bit from this source for UI.

The Node structure

The code for UI

Hope you learnt something today along with me.

Cheers!
Braga

Given a sorted array, find k in least possible time in Java

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

Leave some comments if you have anything to say.

Cheers!
Braga

Find middle element in a circularly sorted array

Given a circularly sorted array, find its middle element in best possible time.

A circularly sorted array is an array that is obtained by shifting an array k times. For example, the following is a circularly sorted array,

[5, 6, 7, 8, 9, 1, 2, 3, 4]

If you sort this array and find the middle element it will be 5. But then, sorting is a painful operation which will take O(nlogn) timing. So it is out of the equation right away. If you closely observe this problem, it is enough to find the shifting index, the place where the sorting varies. For example, the shifting index in the above example is 5.  Once that is found, then it is a matter of applying the bias over the length.

This program can be attacked in a recursive manner. Take the first and last elements in the array and compare them. If they are sorted, then the last element is greater than the first element. If this condition is not met, we will have to divide this array into two halves and try applying the same logic. If you do this, at some point you will arrive at a situation where you are left with only two elements or lesser. The end value is the shift index. Once the shift index is found, it is easy to find the middle element(s) for odd and even cases. Java code is below.

Leave comments if something is unclear.

Cheers!
Braga

Queue using Stack in Java

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.



And a test class for this with output


Cheers!
Braga

Program to check whether a tree is a BST

Write a program to check whether a given tree is a binary search tree.

We all know that a binary search tree follows the rule : for any given node with value N, all the values in the left of that node is lesser than N and all the values in the right of that node will be greater than or equal to N. For example,

This is a tricky question. We may try to immediately run through all the nodes checking only the immediate left and right nodes and coming to a conclusion that it is a binary search tree. But this program may not work for this scenario.

The simplest solution to this problem is to do an inorder traversal through the entire tree and find whether it is sorted or not. Typically we can do that by pushing into any array. Even better is to calculate the minimum value at each step. Program is as follows. Please leave some comments if something is confusing. I will get back immediately.

Cheers!
Braga

Conway's Game of Life in Java!!

I recently met with Conway's Game of Life problem given as a programming assignment by one of the famous MNCs to clear level 1 in interview process. It was so mouth watering that I want to develop an UI for it and publish it in my blog. Spent 3 hours and came up with this.

Quick gist about the game from wikipedia

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

Following is the screenshot and an applet for the same. The Code is free to share and distribute. Visit my github link for this game for the bleeding edge copy.

 

Cheers!!
Braga

How to find angle between hour and minute hands in an analog clock?

Given a simple clock, we have to find the angle between the hour and minute hands. Since this is a deliberate question, we should obviously be ignoring the thickness of the hands in the clock.

We need to understand the following things before we arrive at our solution.

• The hour hand moves at the rate of 0.5 degrees per minute.
• The minute hand moves at the rate of 6 degrees per minute.

The reason for the above statements are obvious if you think a layer deep. Now, for the code (works both for C++ and Java)


Cheers!!
Jack.

What is the difference between memcpy and memmove?

Answer:

With memcpy, the destination cannot overlap the source at all. With memmove copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap. This means that memmove might be very slightly slower than memcpy, as it cannot make the same assumptions.

Cheers!!
Jack

Linked List : Given a pointer to any node, delete the node pointed by the pointer

Given a linked list like this,

Given a pointer to any node, delete the node pointed by the pointer. Note: no head pointer is given.

Solution:

Assume a pointer to p3, lets call it to 'p'. Since only pointer to current node is provided, there is no way to delete the current node from the list. But instead of deleting the current node, we can just move the next node data to current node and delete the next node. The algorithm can be explained simply as,

Cheers!!
Jack

Interview Puzzle - Equal heads

Puzzle:

There are 50 coins on the table out of which 43 are tail-face up and 7 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 50 coins in two sets (not necessarily equal) such that both have equal number of coins with heads face up.

Solution:

Divide the 50 coins into two sets - once set with 43 coins and the other set with 7 coins. Thus, the first set will contain 'x' heads and '43-x' tails and the second set will contain '7-x' heads and 'x' tails. The possibilities can be tabulated as shown in the left table.

Now, flip the coins in the second set, so that both will contain 'x' heads. The result after flipping can be seen on the right table. You can see that both sets have equal number of heads whatever be the distribution.

Cheers!!
Jack

Print a Matrix in diagonal zig zag order

Problem:
Given a square matrix, write a program to print the items in zig zag diagonal order.

Following is an example,

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic. I have provided the solution in C++ below, you may also try to solve the same in the language of your choice!!


Cheers!!
Jack

Trie data structure - In C++

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.

Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.


Demonstration of trie operations

Cheers!!
Jack.

Print Matrix in a circular path (Interview question)

Hi friends,

This is one of the interview questions I faced recently and thought I would share it.

Question:
Given a matrix print all its value in a circular fashion like shown in the image below.

Solution:
To attack this problem we definitely want to have a left-right, top-bottom, right-left and bottom-top spans. For attaining this, we obviously want to have 4 loops. The C++ code is given below.

//============================================================================
// Name        : circular_matrix_read.cpp
// Author      : c++
// Description : output given matrix elements circularly
//============================================================================

#include <iostream>
using namespace std;

#define HEIGHT 6
#define WIDTH  3

int main()
{
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5},{16,17,18,19,6},{15,24,25,20,7},{14,23,22,21,8},{13,12,11,10,9}};
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5,6},{14,15,16,17,18,7},{13,12,11,10,9,8}};
 int array[HEIGHT][WIDTH] = {{1,2,3},{14,15,4},{13,16,5},{12,17,6},{11,18,7},{10,9,8}};
 int maxh = HEIGHT-1, maxw = WIDTH-1;
 int minh = 0, minw = 0;
 while(1)
 {
  if(minh > maxh || minw > maxw)
   break;

  //top-left to top-right
  for(int i=minh,j=minw;j<=maxw;j++)
   cout << array[i][j] << endl;
  minh++;

  if(minh > maxh || minw > maxw)
   break;

  //top-right to bottom-right
  for(int i=minh,j=maxw;i<=maxh;i++)
   cout << array[i][j] << endl;
  maxw--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-right to bottom-left
  for(int i=maxh,j=maxw;j>=minw;j--)
   cout << array[i][j] << endl;
  maxh--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-left to top-left
  for(int i=maxh,j=minw;i>=minh;i--)
   cout << array[i][j] << endl;
  minw++;
 }
 return 0;
}
//1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Cheers!
Bragaadeesh.

Find three numbers in an array which forms a maximum product (for signed integers)

This is a problem that we had already seen. But it gives more kick if the input has negative elements and zero!!!

Question:
Given an array of integers (signed integers), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].

int[] MaxProduct(int[] input, int size)

The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product. Handling all these scenarios with comprehensive test cases, please find the code below for the problem implemented in C++

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman
// Version     : v2
// Copyright   : open
// Description : To find three signed numbers in an array with max product
//========================================================a====================

#include <iostream>
using namespace std;

#define MAX 10

int* MaxProduct(const int input[], const int size)
{
 int* output = new int[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};

 for(int i=0;i<size;i++)
 {
  // find two smallest negative numbers
  if(input[i] <= 0)
  {
   if(input[i] < min[0])
   {
    min[1] = min[0];
    min[0] = input[i];
   }
   else if(input[i] < min[1])
   {
    min[1] = input[i];
   }
   negative++;
  }

  // find three largest positive numbers
  if(input[i] > output[0])
  {
   output[2] = output[1];
   output[1] = output[0];
   output[0] = input[i];
  }
  else if(input[i] > output[1])
  {
   output[2] = output[1];
   output[1] = input[i];
  }
  else if(input[i] > output[2])
  {
   output[2] = input[i];
  }
 }

 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) || (min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }

 return output;
}

int main()
{
 const int input[MAX] = {-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result = 0;
 result = MaxProduct(input,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result[i] << endl;
 }

 const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
 int* result1 = 0;
 result1 = MaxProduct(input1,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result1[i] << endl;
 }

 const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result2 = 0;
 result2 = MaxProduct(input2,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result2[i] << endl;
 }

 const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
 int* result3 = 0;
 result3 = MaxProduct(input3,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result3[i] << endl;
 }

 return 0;
}

Cheers!
Bragaadeesh.

Given a sorted array find the pair that forms the sum in O(n) time

This problem is quite frequently asked and we had already seen a solution in O(n) time but using a hash table here. However in this posting we shall see how to attack this problem when the input data is sorted.

For example for the input,

[-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24] and the sum bein 0, the matching pair is -12 and 12

The solution for this problem relies upon the knowledge of the input data : sorted. We will be having two pointers, one from the start of the Array called as min and the other from the end of the array called as max. We always calculate the sum with the values present in the minimum and maximum indexes. If the sum is greater than what is needed, we will be decrementing the max pointer and for the other case, we will be incrementing the min pointer. This happens till min exceeds max.

Following the solution in C++

//============================================================================
// Name        : array_find_sum.cpp
// Author      : Prabhu Jayaraman
// Version     : v1
// Copyright   : Free
// Description : Find elements in the array that equals to given sum
//============================================================================

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Cheers!
Bragaadeesh

Compact a given array coding problem

This problem may look very simple and indeed it is because the solution can be arrived at very easily. But to arrive at a clean and an efficient may take sometime. This question is asked to test the cleanliness and simplicity in providing solutions. Enough hype, here is the question.

Given an array of random numbers and -1 placed in-between, compact that array ie., all the -1s are to be removed and the final output should be the last valid index with the fresh array. For example.

You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.

The solution to this problem is seemingly simple and the same has been implemented in Java below.


Cheers!
Bragaadeesh.