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

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

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

C program to find fibonacci series using only one variable !!!

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.

Method #2:
The following recursive function would do the job.

Method #3:
The following one works great as well!

Cheers!!
Jack

Google CodeJam 2010 : "Rope Intranet" Problem with solution

Problem

A company is located in two very tall buildings. The company intranet connecting the buildings consists of many wires, each connecting a window on the first building to a window on the second building.
You are looking at those buildings from the side, so that one of the buildings is to the left and one is to the right. The windows on the left building are seen as points on its right wall, and the windows on the right building are seen as points on its left wall. Wires are straight segments connecting a window on the left building to a window on the right building.

You've noticed that no two wires share an endpoint (in other words, there's at most one wire going out of each window). However, from your viewpoint, some of the wires intersect midway. You've also noticed that exactly two wires meet at each intersection point.
On the above picture, the intersection points are the black circles, while the windows are the white circles.
How many intersection points do you see?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing an integer N, denoting the number of wires you see.
The next N lines each describe one wire with two integers A_i and B_i. These describe the windows that this wire connects: A_i is the height of the window on the left building, and B_iis the height of the window on the right building.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of intersection points you see.

Limits

1 ≤ T ≤ 15.
1 ≤ A_i ≤ 10⁴.
1 ≤ B_i ≤ 10⁴.
Within each test case, all A_i are different.
Within each test case, all B_i are different.
No three wires intersect at the same point.

Small dataset

1 ≤ N ≤ 2.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input	Output
2 3 1 10 5 5 7 7 2 1 1 2 2	Case #1: 2 Case #2: 0

Solution

This is one of the simpler problems that I was able to solve in the Codejam round. Following is the source code.

private long solve(int[] a, int[] b) {
  
  PointMesh p = new PointMesh();
  
  for(int i=0;i<a.length;i++){
   p.add(a[i], b[i]);
  }
  
  return p.intersects;
 }

 class PointMesh{
  long intersects;
  List<Line2D> lineList = new ArrayList<Line2D>();
  Line2D line1 = new Line2D.Double();
  Line2D r = new Line2D.Double();  
  
  void add(int a,int b){
   Point2D p1 = new Point2D.Double(0, a);
   Point2D p2 = new Point2D.Double(10, b);
   Line2D newLine = new Line2D.Double(p1,p2);
   
   for(Line2D eachLine:lineList){
    if(eachLine.intersectsLine(newLine))
     intersects++;
   lineList.add(newLine);
  }
 }

Complete source code : here
Practice inputs : here

Cheers!!
Bragaadeesh.

Google CodeJam 2010 : "File Fix-it" Problem with solution

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input	Output
3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b

Solution

To attack this problem we can use the famous TRIE data structure. We have already seen enough about this data structure in steps and this becomes so handy in this particular problem.
A TRIE data structure simply stores the data that becomes easy for retrieval. But lets not bother about the retrieval part in this particular problem. We will simply increase our counter whenever we add a new folder to the existing directory structure. The place where we optimize this problem involves in its running time.  Whenever we see a new directory structure, we simply pass through it in the length times instead which is linear in time jargons. The solution is given below.

private int solve(String[] already, String[] fresh) {
  Trie trieDSA = new Trie();
  
  for(int i=0;i<already.length;i++){
   trieDSA.insert(already[i],false);
  }
  
  for(int i=0;i<fresh.length;i++){
   trieDSA.insert(fresh[i], true);
  }
  
  return trieDSA.counter;
 }

So clean, isnt it? The TRIE and the Node classes are given below. Remember, please go through my TRIE data structure introduction for few minutes, its definitely a knowledgeable one! Trust me :)

class Node {
 String currentPath;
 boolean marker; 
 Collection<Node> child;
 
 public Node(String path){
  child = new HashSet<Node>();
  marker = false;
  currentPath = path;
 }
 
 public Node subNode(String path){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.currentPath.equals(path)){
     return eachChild;
    }
   }
  }
  return null;
 }
}

class Trie{
 private Node root;
 
 public int counter = 0;

 public Trie(){
  root = new Node("");
 }

 public void insert(String pathArray, boolean shouldTrack){
  Node current = root; 
  
  String[] paths = pathArray.substring(1).split("\\/");
  
  if(paths.length==0){
   //DO NOTHING
   current.marker=true;
  }
   
   
  for(int i=0;i<paths.length;i++){
   Node child = current.subNode(paths[i]);
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(paths[i]));
    current = current.subNode(paths[i]);
    if(shouldTrack){
     counter++;
    }
   }
   // Set marker to indicate end of the word
   if(i==paths.length-1)
    current.marker = true;
  } 
 }
}

Complete source code : here
Sample Input : here

Cheers!!
Bragaadeesh.

Google CodeJam : Alien Language Problem with Solution

This is the problem asked in 2009 Google Codejam's qualification round. Lets get into business straightaway.

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input
   
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Output
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

The solution for this problem is relatively simple compared to the other codejam problems that we are going to solve in the future. The solution is implemented in Perl language. It uses the regex pattern matching method.

Input file of large dataset : Download
Output file of large dataset : Download

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.

Find the last person seated around in a circle program/puzzle

This is a programming question asked at one of the class companies. Following is the question

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

Me and my roommate both implemented a solution for the above problem one in Java and the other in C++ respectively. Please see the code and the ouput for the above problem below.

Implementation in Java

package brainteasers;

public class FindWinner {
 public static void main(String[] args) {
  FindWinner finder = new FindWinner();
  char winner = finder.findWinner(10,3);
  System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
 }
 
 private char findWinner(int n, int m){
  char[] people = getPeople(n);
  boolean[] eliminated = new boolean[n];
  //always start from 1st person
  int remainingGuys = n;
  int current = 0;
  
  while(remainingGuys>1){
   int inkiPinki=0;
   
   while( eliminated[current] || ++inkiPinki != m )
       current = (current+1) % n;
   
   eliminated[current] = true;
   printStatus( eliminated, people );
   remainingGuys--;
   
   while(eliminated[(current+1)%n]){
    current++;
   }
   
   current = (current+1)%n;
  }
  
  System.out.println();
  return people[current];
 }

 private void printStatus(boolean[] eliminated, char[] people) {
  System.out.println();
  for(int i=0;i<eliminated.length;i++){
   char output;
   if(eliminated[i]){
    output = people[i];
   }else{
    output = (char)(people[i] - 32);
   }
   System.out.print(output+" ");
  }
 }

 private char[] getPeople(int n) {
  char[] people = new char[n];
  System.out.println("Participants are...");
  for(int i=0;i<n;i++){
   people[i] = (char)(i+97);
   System.out.print((char)(people[i]-32)+" ");
  }
  System.out.println();
  return people;
 }
}
/*
Participants are...
A B C D E F G H I J 

A B c D E F G H I J 
A B c D E f G H I J 
A B c D E f G H i J 
A b c D E f G H i J 
A b c D E f g H i J 
a b c D E f g H i J 
a b c D E f g h i J 
a b c D e f g h i J 
a b c D e f g h i j 

And the winner is D!!
*/

Implementation in C++

//============================================================================
// Name        : puzzle.cpp
// Author      : Prabhu Jayaraman
// Version     : 0.1
// Copyright   : Free
// Description : Find Last man stand
//============================================================================

#include <iostream>
using namespace std;

int FindWinner(int n, int m)
{
 int a[n];
 for(int i=0;i<n;i++)
 {
  a[i] = 1;
 }
 int e = 0;
 int c = 0;
 for(int i=0;;i++)
 {
  if(e == (n-1))
   break;
  if(a[i%n] == 1)
   c++;
  if(c == m)
  {
   a[i%n] = 0;
   e++;
   c = 0;
  }
 }
 for(int i=0;i<n;i++)
 {
  if(a[i] == 1)
   return i+1;
 }
 return -1;
}

int main()
{
 int x = FindWinner(20,19);
 cout << x << endl;
 return 0;
}

Cheers,
Bragaadeesh

Find common parent in a binary search tree in Java

This is a very famous question that many already are aware of. But I wanted to give a comprehensive working program in java to implement this with illustration. Consider the following binary tree which infact is a binary search tree.

The idea is very simple. For the first node traverse up till you reach root, while doing so, put the nodes in a hash set. Then do the same for the second node ie, try to traverse towards the root. Amidst doing that search for the existence of this node in the hash set we already created for the first traversal.

The place where those two nodes matches will be the common node. For any two nodes in a tree, there will be at least one common node which will be the root. I have given two examples below. One having a node other than root as the common parent and the other with root as the common parent.

The green line shows the traversal of first node path. Red shows the second node's path. The intersection or the common parent is shown in a blue circle.

Now for the Java source.

package dsa.tree;

import java.util.HashSet;
import java.util.Set;

public class FindCommonNode {
 private Node n1,n2;
 
 public static void main(String args[]){
  FindCommonNode nodeFinder = new FindCommonNode();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  System.out.println("Common Parent : "+commonParent.data);
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(45);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  Set<Node> firstNodeAddrSet = new HashSet<Node>();
  //Traverse till root
  while(node1!=null){
   firstNodeAddrSet.add(node1);
   node1 = node1.parent;
  }
  while(!firstNodeAddrSet.contains(node2) && node2!=null){
   node2 = node2.parent;
  }
  return node2;
 }
}

The implementations for Tree and BinarySearchTree can be found here.

Cheers,
Bragaadeesh.

Progress software - interview coding problem

This is one of the problems that have been asked in a company called Progress Software, Hyderabad. I have posted the question as well as the working Java code for the same.

Question

Sports Associations in India
-------

The Sports Associations in India (SAI) wants to choose 2 teams of 4 people each
to send to Asain games. There are 13 people who want to be members of
the teams. The SAI tries grouping them in various ways to see which
athletes perform well together. Each grouping gets one test run on the
test track and their time is recorded. Your task is to help the SAI
choose two disjoint teams of 4 such that the sum of their practice times
is minimal.

Input
-----

There will be several input instances. The first line of each instance
gives the total number of practice runs. This will be followed by n lines.
Each of those lines will contain 5 numbers: p1 p2 p3 p4 t
t is the time taken (in milliseconds) by the team consisting of p1, p2, p3 and p4.

The time taken will not be more than 2 minutes.

The end of the input will be indicated by a line with n=0.

Output
------

Output the best total time for the two teams that you choose.
If it is impossible to choose two disjoint teams from the test runs given, output -1.

Sample Input
------------

6
1 2 3 4 30000
10 11 12 13 15000
5 6 7 8 37800
1 5 10 12 20000
5 6 9 11 43000
1 9 12 13 11000
3
1 4 7 9 10000
3 5 7 11 17890
6 7 12 13 20000
0

Sample Output
-------------

45000
-1

Along this you will get a file consisting of an input and they ask you to send the output. I am sharing the solution to this problem.

package main;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

public class Main {

 /**
  * @param args
  */
 public static void main(String[] args) {
  new Main().start();
 }

 private ArrayList<Event> events = null;

 public static final String DIR = "D:/Question2/";

 private String filename = DIR + "input.txt";

 public void start() {
  readInput();
  printInput();
  solve();
  writeToFile();
 }
 
 private void printInput() {
  Event eventRound = null;

  for (int i = 0; i < events.size(); i++) {
   eventRound = events.get(i);
   System.out.println("Round Count: " + eventRound.roundCount);
   System.out.println("Rounds : " + eventRound.toString());
  }
 }
 
 public void readInput() {
  FileRead read = new FileRead(filename);
  events = read.getEvents();
 }

 public void solve() {
  Event eventRound = null;
  for (int i = 0; i < events.size(); i++) {
   eventRound = events.get(i);
   eventRound.findMinTime();
   eventRound.printVal();
  }

 }
 
 private void writeToFile() {
  try {
   BufferedWriter out = new BufferedWriter(new FileWriter(DIR
     + "output.txt"));

   Event eventRound = null;
   for (int i = 0; i < events.size(); i++) {
    eventRound = events.get(i);
    out.write(eventRound.minTime+System.getProperty("line.separator"));
   }
   out.close();
  }catch(IOException e) {
   e.printStackTrace();
  }
 }
}

package main;

import java.util.StringTokenizer;

/**
 * Class to reprsent a round. A round consist of an array of players and time taken 
 * by them on that particular round.
 * @author Bragadeesh
 *
 */
public class Round {
 public int[] players;
 public int time;
 
 /**
  * Represents the player count for the event
  */
 public static final int PLAYER_COUNT = 4;
 
 public Round(String line){
  StringTokenizer tokens = new StringTokenizer(line);
  players = new int[PLAYER_COUNT];
  for(int i=0;i<PLAYER_COUNT;i++){
   players[i] = Integer.parseInt(tokens.nextToken());
  }
  time = Integer.parseInt(tokens.nextToken());
 }
 
 /**
  * Returns the formatized string for a particular Round
  */
 public String toString(){
  String op = "";
  for(int i=0;i<players.length;i++){
   op = op + players[i] + " ";
  }
  
  op = op + time;
  
  return "[" + op + "]";
 }
 
}

package main;


/**
 * Event is a class which is comprises an array of Rounds.
 * @author Bragadeesh
 *
 */
public class Event {
 
 public Round[] rounds;
 public int roundCount;
 private static final int MAX_VAL = 99999999;
 
 public int minTime = -1;
 
 /**
  * Variable used to show the the minimum round1 should there be any
  */
 public Round minRound1;
 
 
 /**
  * Variable used to show the the minimum round2 should there be any
  */
 public Round minRound2;
 
 
 /**
  * Returns the formatized string for a particular Event
  */
 public String toString(){
  
  String op = "";
  
  for(int i=0;i<rounds.length;i++){
   op+=rounds[i].toString();
  }
  
  return "{" + op + "}";
 }
 
 /**
  * Method to calculate the minimum time
  * @return
  */
 public int findMinTime(){
  int min = MAX_VAL;
  Round roundA = null;
  Round roundB = null;
  
  for(int i=0;i<roundCount;i++){
   for(int j=0;j<roundCount&&i!=j;j++){
    roundA = rounds[i];
    roundB = rounds[j];
    
    if(!disjoint(roundA, roundB)){
     if(roundA.time + roundB.time < min){
      minRound1 = roundA;
      minRound2 = roundB;
     }
     min = Math.min(roundA.time + roundB.time, min);
    }
   }
  }
  
  if(min != MAX_VAL){
   minTime = min; 
  }
  
  return minTime;
 }
 
 /**
  * Method to print the Round values and the minimum time for a 
  * given event. Prints -1 if there is no minimum time set.
  */
 public void printVal(){
  if(minRound1!=null){
   System.out.println(minRound1.toString());
   System.out.println(minRound2.toString());
   System.out.println(minTime);
  }else{
   System.out.println("-1");
  }
 }
 
 /**
  * Simple bubble sort that does the sorting of the events based on the round time
  * @return void
  */
 public void sortRounds() {
     for(int i=0;i<roundCount;i++){
      for(int j=i;j<roundCount;j++){
       if(rounds[i].time > rounds[j].time){
        Round temp = rounds[i];
        rounds[i] = rounds[j];
        rounds[j] = temp;
       }
      }
     }
 }

 
 /**
  * Given two arbitrary rounds A and B, returns whether they are disjoint or not
  * @param roundA
  * @param roundB
  * @return boolean value whether given set is disjoint or not
  */
 public boolean disjoint(Round roundA, Round roundB){
  for(int i=0;i<Round.PLAYER_COUNT;i++){
   for(int j=0;j<Round.PLAYER_COUNT;j++){
    if(roundA.players[i] == roundB.players[j]){
     return true;
    }
   }
  }
  return false;
 }
 
}

package main;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class FileRead {
 
 private String filename = null;
 private ArrayList<Event> events;
 
 public FileRead(String filename){
  this.filename = filename;
  events = new ArrayList<Event>();
  load();
 }
 
 private void load(){
  
  FileInputStream fstream = null;
  DataInputStream in = null;
  BufferedReader br = null;
  Event event = null;
  
  
  try {
   fstream = new FileInputStream(filename);
   in = new DataInputStream(fstream);
   br = new BufferedReader(new InputStreamReader(in));
   
   for(;;){
    event = new Event();
    event.roundCount = Integer.parseInt(br.readLine());
    if(event.roundCount == 0){
     break;
    }
    event.rounds = new Round[event.roundCount];
    for(int i=0;i<event.roundCount;i++){
     event.rounds[i] = new Round(br.readLine());
    }
    event.sortRounds();
    events.add(event);
   }
   
   
  } catch (Exception e) {
   System.err.println("Error: " + e.getMessage());
  } finally{
   try {
    in.close();
   } catch (IOException e) {
    e.printStackTrace();
   }
  }
 }
 
 public ArrayList<Event> getEvents(){
  return events;
 }
}

Input file : Input.txt
Output file : Output.txt
Cheers,
Bragaadeesh.

Find common sequence that is out of order between two given strings in Java

Hi,
Recently i faced this question from Amazon. Given two strings, find the longest common sequence that is out of order. Initially it was royally confusing to me what the question meant, but I was able to come up with a solution. Please see the following program implemented in Java. The sample inputs and outputs have been provided at the end.

package dsa.stringmanipulation;

import java.util.LinkedHashMap;
import java.util.Map;

public class Sequence {
 public static void main(String[] args) {
  Sequence seq = new Sequence();
  String str1 = "a111b3455yy";
  String str2 = "byy115789";
  System.out.println("Input1: "+str1);
  System.out.println("Input2: "+str2);
  String solution = seq.findCommonSequnce(str1, str2);
  System.out.println("Output: "+solution);
 }
 
 public String findCommonSequnce(String str1, String str2){
  if(str1==null || str2==null){
   return "";
  }
  if(str1.length() == 0 || str2.length() == 0){
   return "";
  }
  //parse first String store the frequency of characters
  //in a hashmap
  Map<Character,Integer> firstStringMap = frequencyMap(str1);
  
  StringBuilder output = new StringBuilder();
  
  for(int i=0;i<str2.length();i++){
   int count = 0;
   if(firstStringMap.containsKey(str2.charAt(i)) && (count=firstStringMap.get(str2.charAt(i)))>0){
    output.append(str2.charAt(i));
    firstStringMap.put(str2.charAt(i), --count);
   }
  }
  
  return output.toString();
 }

 /**
  * Returns a map with character as the key and its occurence as the value
  * @param str
  * @return
  */
 private Map<Character,Integer> frequencyMap(String str) {
  Map<Character, Integer> freqMap = new LinkedHashMap<Character,Integer>();
  for(int i=0;i<str.length();i++){
   Integer count = freqMap.get(str.charAt(i));
   if(count==null){//means the frequency is yet to stored
    freqMap.put(str.charAt(i), 1);
   }else{
    freqMap.put(str.charAt(i), ++count);
   }
  }
  return freqMap;
 }
}

//SAMPLE OUTPUTS
//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115
//
//Input1: lsjfa9fjdsajf
//Input2: dsklajfdkl99
//Output: dslajf9

Cheers,
Bragaadeesh.

Binary Search Trees in Java

Now that we've seen how a binary tree is structured, lets take a look at one of the most common and powerful implementations - Binary Search Trees.
Binary Search trees are binary trees with some defined rules. Binary search trees can be formed only to nodes which are comparable. By Comparable, i mean which objects in real life that can be compared with each giving outputs as equal, greater or lesser. Numerals are the simplest example of comparables.
The rule of binary search tree follows that all the nodes that are lesser than the root will be on the left and the nodes that are greater than will be on the right. Equal valued nodes can come on either side.
Following is a simple illustration of a binary search tree formed using numerals

The following is a comprehensive Java code on how to construct and then manipulate from a binary tree.

The abstract Data Structure for Tree and the class Node.

package dsa.tree;

public interface Tree {
 public void add(int currentData);
 public Node search(int data);
}

package dsa.tree;

public  class Node {
 Node left;
 Node right;
 Node parent;
 int data;
}

package dsa.tree;

public class BinarySearchTree implements Tree{
 
 private Node root;
 
 public void add(int currentData){
  if(root == null){
   root = new Node();
   root.data = currentData;
   return;
  }
  add(currentData, root);
 }
 
 private void add(int currentData, Node position){
  if(currentData<position.data){
   if(position.left==null){
    position.left = new Node();
    position.left.data = currentData;
    position.left.parent = position;
    return;
   }
   add(currentData, position.left);
  }else{
   if(position.right==null){
    position.right = new Node();
    position.right.data = currentData;
    position.right.parent = position;
    return;
   }
   add(currentData, position.right);
  }
 }
 
 public Node search(int searchData){
  if(root == null){
   return null;
  }
  return search(searchData, root);
 }
 
 /*
  * O(log n) on average case
  */
 private Node search(int searchData, Node node){
  if(node.data == searchData){
   return node;
  }
  if(searchData < node.data){
   return search(searchData, node.left);
  }else{
   return search(searchData, node.right);
  }
 }
 
 public void printOrdered(){
  if(root == null){
   return;
  }
  printOrdered(root);
 }
 
 //DO A IN ORDER TRAVERSAL
 //VISIT LEFT
 //VISIT ROOT
 //VISIT RIGHT
 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left);
  }
  System.out.println(node.data);
  if(node.right!=null){
   printOrdered(node.right);
  }
 }
 
 public void printValues(){
  print(root);
 }
 
 private void print(Node node){
  if(node == null){
   return;
  }else{
   print(node.left);
   print(node.right);
  }
 }
 
 public static void main(String args[]){
  BinarySearchTree bTree = new BinarySearchTree();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println(t);
   bTree.add(t);
  }
  bTree.printValues();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println("For i="+t+": "+bTree.search(t));
  }
  System.out.println();
  bTree.printOrdered();
 }
}

We shall discuss about the various features used in this program in the following post.

Bragaadeesh.

Binary Trees in Java

One of the coolest data structures that is both highly efficient and very simple is a Binary Tree. Binary Tree is a data structure where a there will be a node having at most two child nodes.

Lets briefly define the concepts of a binary tree and lets take look at a working Java program in the future posts. Binary Tree has three pointers, one pointing to the left child, one pointing to the right child and one pointer to the parent. These are the terms we use with respect to a binary tree.

• Root - The uppermost node in a binary tree. The parent node is always null for a root or we can say Root does not have a parent.
• Child - A child is a sub-node to a parent node. A child can be either a left child or a right child
• Leaf - A node which does not have any right or left nodes to it.
• Node - constitutes to an element of a tree which has three pointers one to parent, one to right child and one to left child. And it has a place holder to store the data as well.
  

There are more jargons available with regard to a binary tree but as of now these terms are sufficient.

One of the most common misunderstanding that many have is to tell the definition of a "Binary search tree" when asked for a "Binary tree". They are not the same!!. Although we can say binary search tree is a form of binary tree with some condition. All Binary search trees are Binary trees and not vice versa!!!!

If asked to write a binary tree structure in Java, the following code would be more than sufficient. Note: This is just a raw structure.

public class BinaryTree{
 
 class Node {
  Node left;
  Node right;
  Node parent;
  int data;
 }
 
 private Node root;

}

More trees to come in the following posts.
Cheers,
Bragaadeesh.