06 February 2010

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.

4 comments:

JP Arun said...

adengappa! veriya aazha varuvae Braga! :)

ahmed said...

thanks for sharing the question.

is it necessary to implement it in java or can it be implemented in any programming language.

please post any other problems if u know for progress software

BragBoy said...

@ahmed - it is not necessary to do in Java. You can do it any language of your choice. All that matters is the end solution.
And I don't have any other problems from them.

Venky said...

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class GetTeams {

void readInput()
{

try {
FileInputStream fis = new FileInputStream("input.txt");
BufferedReader breader= new BufferedReader(new InputStreamReader(fis));
String line1=breader.readLine();
while(line1!=null && !line1.trim().equals("0"))
{
line1=initialize(breader, line1);

line1=breader.readLine();

}


} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}



}



/**
* @param breader
* @param line1
* @throws NumberFormatException
* @throws IOException
*/
public String initialize(BufferedReader breader, String line1)
throws NumberFormatException, IOException {
Integer initCount= Integer.parseInt(line1.trim());
int a [][]= new int [initCount][14];
int b[][]=new int [initCount][5];
int i=0;

while(i sum)
{


for(int x=0;x<13;x++)
{
if(a[m][x]+a[n][x]==2)
{

flag=false;

}

}

if(flag)
{
minTime=sum;
minTimeI=m;
minTImeJ=n;
}

}

}
}

System.out.println( minTime);





return line1;
}



public static void main(String[] args) {

GetTeams a = new GetTeams();
a.readInput();


}


}