Machine Graded Programming Tests

While doing my post-graduation in C-DAC — this was the 6 month full time PGDST (Post Graduate Diploma in Software Technology) course at E-city — we found that we'd pass the course only if we passed the minimum number of Machine Graded Programming Tests (MGPT's). These tests were similar to Google Code Jam, where you'd have to submit your program to a software program which will supply various inputs to your program and you pass the test only if each and every one of those inputs give the desired output.

It's a test that makes students very nervous, because let's say you're writing a program to accept a string and print whether it's a palindrome or not, some programmers won't consider the possibility that the program might receive an empty string as an input. The software which supplies such boundary conditions to your program, was called the "Parikshak" program, in C-DAC. We'd be given our questions and had 45 minutes to write our program on paper. Then, we could go to the lab where we had 45 minutes to type our program, correct it and keep feeding it into Parikshak. We used to wait in trepidation each time we submitted the program to Parikshak, and Parikshak would evaluate the program by supplying inputs to it and we'd see if the outputs were correct, by (if I remember correctly), "X" symbols for every correct output and "-" for every wrong output. If we got even a single "-", we got zero marks for the question, and had to correct our program and re-submit.

The challenge eased:
I decided to put this nervousness to rest by requesting the course coordinator to allow us to create our own questions for Parikshak, so that our classmates could attempt solving it and thereby be prepared for the real MGPT's. Nobody had ever attempted to do this in C-DAC, and our generous course coordinator was happy to allow us (two other programmer enthusiast classmates of mine, joined in) to volunteer. We called ourselves the "Mock MGPT team" (play rock music now for some effect). A few months later a third classmate joined the team. We became the B.RA.I.N.S team.
B - Binish
RA - RAghvendra
I - Ipe 

N - Navin
S - Shiv

So we set out on this new journey with the blessings of both our teachers and our classmates. For me, it was a creative journey too. These are some of the questions I created (just came across them today in an old email and thought I'd post it online):

Question 1:

PROBLEM STATEMENT:
A software error in a data entry software caused the string "MGPT" to get added to some institution names in a list of instutitions in Bangalore. When word got out, the principals of those institutions thought it a pretty good idea to introduce MGPT in their colleges. The students however, are worried, and have pleaded with you to remove MGPT from the list before the principals return from their tea break and take a final decision on the matter.

Your job is to write a program which will locate the "MGPT" string in the institution names and remove the string from the institution name.
If an institution name is CDAC (upper case, lower case or both), you are to leave the MGPT string in that institution name intact.
If the "MGPT" string occurs in any institution name, it will not occur more than once.
All institution names will begin with an alphabet.
Institution names may contain only alphabets, spaces and/or full stops.
The list of institution names have to be sorted alphabetically before being output.
The default priority for alphabetical sorting is: 1.Spaces, 2.Full stops, 3.Upper case letters 4.Lower case letters. (This is the same priority followed by the Java string handling functions)
The "MGPT" string may either consist of upper case or lower case letters.

INPUT:
The first input will be a number N, indicating the number of institution names that will follow.
N number of institution names will be provided, each on a new line.

OUTPUT:
The list of institution names, sorted alphabetically. Each on a new line.


SAMPLE INPUT:
7
Ammgptbc Institute of Technology
Z P College of EngineeringmGpt and Technology
Ghost ColMGptlege of Engineering
MGPTJanaloka Education Institute
JSM College of EngineeringmgpT
cmgPtDac
M. R. College of Engineering

SAMPLE OUTPUT:
Ambc Institute of Technology
Ghost College of Engineering
JSM College of Engineering
Janaloka Education Institute
M. R. College of Engineering
Z P College of Engineering and Technology
cmgPtDac


PROGRAM:
import ncst.pgdst.*;

class m
{

 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();
  int n=Integer.parseInt(s.readLine());
  String[] word=new String[n];//stores the original strings
  String[] big=new String[n];//strings converted to upper case
  String[] removed=new String[n];//strings with 'mgpt' removed
  for(int i=0;i  {
   word[i]=s.readLine();
   big[i]=word[i].toUpperCase();//convert it to upper case for ease of use
   removed[i]="";
  }//for

  for(int i=0;i  {
   int start=0,end=0;
   String w="";
   start=big[i].indexOf("MGPT");
   if (start>=0)//found the mgpt string
   {
    end=start+4;
    w=word[i].substring(0,start)+word[i].substring(end,word[i].length());
    String temp=w.toUpperCase();
    if (temp.compareTo("CDAC")==0) {w=word[i];}
   }//if
   else w=word[i];
   removed[i]=w;
  }//for

  //sort alphabetically
  for(int i=0;i  {
   for(int j=0;j   {
    if (removed[j].compareTo(removed[j+1])>0)
    {
     String temp=removed[j+1];
     removed[j+1]=removed[j];removed[j]=temp;
    }
   }//for
  }//for

  for(int i=0;i  {
   System.out.println(removed[i]);
  }
 }//main
}//class

-----------------------

Question 2 for Mock MGPT (classmates found this one very amusing)

When Tarzan came swinging to the CDAC campus, he heard of forests and trees being discussed in the classes. The CDAC'ians offered Tarzan three binary search trees to start swinging on, but Tarzan was afraid that if he tried to swing on a leaf node, he'd fall down.
A bunch of monkeys decided to help him with this. The monkeys would climb up onto the trees, according to their ages, in the same way that numbers are inserted into a binary search tree.
Any node which is not null is a node containing a monkey.

Tarzan doesn't like crash-landing on monkeys and he can't swing on the leaf of a tree, so he will swing only on VALID branches of the trees.
He differentiates between VALID branches and leaves (ie:leaf's) this way (this is a little different from conventional terminology)
A VALID branch is a node which is null and has a sibling node which contains a monkey.
A node is a leaf node if it is null and its sibling node is also null.

We will specify a swinging height for Tarzan (one swinging height will apply for all trees) so that he doesn't crash into the CDAC building. The swinging height is always greater than zero. Even if there is a single VALID branch at the specified height on a tree, Tarzan can swing on that tree.
Tarzan will be jumping from the CDAC building, onto the first tree, then to the second tree and then to the third tree, in that order. He doesn't jump after he reaches the third tree. Each time he jumps, he yells "OOOEEOOOYEEEOOOHH". If a tree doesn't have any VALID branches at the specified height, Tarzan falls down and yells "OOH AAH OUCH". Once he falls down, he doesn't attempt to jump onto any more trees.

You have to write a program to create three binary search trees and insert monkeys (age of the monkeys) into the trees. You should output the words that Tarzan yells when he attempts to jump onto the first tree, the second tree and the third tree. Assume the root node to be at a height of zero.


INPUT SPECIFICATION:
Three lines of numbers, each on a new line. The first number N of each line specifies that N numbers (these are the ages of the monkeys) follow it on the same line. The first line of monkey ages are for insertion into the first binary tree, the second line for the second tree and so on.
One number on a new line, specifying the swinging height.

OUTPUT SPECIFICATION:
"OOOEEOOOYEEEOOOHH" (without quotes) if Tarzan can jump onto a tree with VALID nodes.
"OOH AAH OUCH" (without quotes) if he cannot land on a tree because it doesn't have VALID nodes at the specified height.

SAMPLE INPUT/OUTPUT:
Input1:
3 4 2 3
6 10 9 60 5 11 61
6 8 6 21 4 7 30
1

Output1:
OOOEEOOOYEEEOOOHH
OOH AAH OUCH

Input2:
3 4 2 3
6 10 9 60 5 11 61
6 8 6 21 4 7 30
2

Output2:
OOOEEOOOYEEEOOOHH
OOOEEOOOYEEEOOOHH
OOOEEOOOYEEEOOOHH

Input3:
4 4 2 3 5
6 10 9 60 5 11 61
6 8 6 21 4 7 30
1

Output3:
OOH AAH OUCH


PROGRAM:

import ncst.pgdst.*;

class t
{
 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();

  Node r1=new Node();
  int t=Integer.parseInt(s.readWord());
  for(int i=0;i
  Node r2=new Node();
  t=Integer.parseInt(s.readWord());
  for(int i=0;i
  Node r3=new Node();
  t=Integer.parseInt(s.readWord());
  for(int i=0;i
  int sHeight=Integer.parseInt(s.readWord());
  boolean fell=false;
      //check if first tree has VALID nodes
  if (r1.search(sHeight))
     System.out.println("OOOEEOOOYEEEOOOHH");
  else {System.out.println("OOH AAH OUCH");fell=true;}

  if (!fell)
     {//check if second tree has VALID nodes
      if (r2.search(sHeight))
         System.out.println("OOOEEOOOYEEEOOOHH");
      else {System.out.println("OOH AAH OUCH");fell=true;}
     }
  if (!fell)
     {//check if third tree has VALID nodes
      if (r3.search(sHeight))
         System.out.println("OOOEEOOOYEEEOOOHH");
      else {System.out.println("OOH AAH OUCH");fell=true;}
     }
 }//main
}//class

class Node
{
 Node left,right;
 int value;
 int height;

 Node() {left=null;right=null;value=0;height=0;}
 Node(int v, int h) {left=null;right=null;value=v;height=h;}

 public boolean search(int searchHeight)
 {
  boolean b=false,bv=false;
  if (height==searchHeight-1)
  {
   if ((right!=null && left==null) || (right==null && left!=null)) bv=true;
  }
  else
  {
   if (right!=null) {b=right.search(searchHeight);if (b) bv=true;}
   if (left!=null) {b=left.search(searchHeight);if (b) bv=true;}
  }
  return bv;
 }//search

 public void insert(int v)
 {
  if (value==0) value=v;
  else
  {
   if (v>value)
      {
       if (right==null) {Node n=new Node(v,height+1);right=n;} else right.insert(v);
      }
   else
      {
       if (left==null) {Node n=new Node(v,height+1);left=n;} else left.insert(v);
      }
  }//else
 }//insert

}//Node

--------------------

Question 3:

Students complained that bugs, which accidentally entered the Brinjal curry in the canteen food which they ate, were turning up as bugs in their software programs, which highly inconvenienced them while writing bug-free code during MGPT's.
Following these complaints, the canteen decided to install a device, capable of detecting and driving out bugs from the food with a K.N machine that emits special, patented Keeda-Naashak rays.

The food on a plate consists of many layers of food. Each layer is uniform in constitution, and is represented here with 5 characters. The character representation meaning is given below:
'P' is for a layer of Paapad. 'C' is for a layer of curry. 'R' is for a layer of rice.
'K' is a bug that can be present in any layer of food.
When a bug is present in a layer of food, the layer of food is represented with 4 food characters and one bug character.

The K.N machine emits rays laterally into a plate of food for 2 seconds. This irritates the bug, which immediately crawls up the layers of food and flies away when it reaches the surface.
The bug takes one second to crawl through a layer of food. The exception to this rule is that the bug takes 2 seconds to crawl through the curry layer.
If in the beginning the bug is in a layer of curry or if the bug passes through a layer of curry while crawling up, the bug always takes 2 seconds to crawl through ANY layer of food. Curry layers are not additive. ie: if a bug passes through two layers of curry, it won't take 2+(2+2) seconds to cross the layer. The time taken to cross the two layers of curry will be 2+2=4 seconds.

At the end of the 2 seconds for which the machine scans the food, if the bug is still in the food, the machine displays "KEEDA ALERT" (without quotes) on its screen. If there is no bug or if the bug has managed to reach the surface within the two seconds, the machine displays "CLEAN" (without quotes) on its screen.
You have to write a program to find out if at the end of the 2 seconds of scanning, would the food be bug-free or not. Your output will be the same as what is displayed on the screen of the K.N machine.

Assumptions:
1. The bug always crawls upward perpendicularly.
2. Assume that the number of layers of food will always be: number of layers >= 3 and number of layers <= 5
3. All inputs will be in upper-case characters
4. Assume that there can be only one or no bugs in a plate of food

INPUT:
One integer M, representing the number of plates to be scanned
M number of plate inputs will follow.
A plate input consists of:
One integer N on a new line, representing the number of layers of food in a plate.

N layers of food will follow, each on a new line.

OUTPUT:
"KEEDA ALERT" (without quotes) is displayed for a plate if it has a bug at the end of the two second scan.
"CLEAN" (without quotes) is displayed for a plate if it has no bug in it at the end of the two second scan.


SAMPLE INPUT:
5
4
PPPPP
PPPPP
CCCKC
RRRRR
3
PPPPP
CCCCC
KRRRR
3
PPPPP
RRRRR
KRRRR
5
PPPPP
PPPPP
RRRRR
RRRRK
CCCCC
3
CCCCC
PPPPP
RRRRR

SAMPLE OUTPUT:
KEEDA ALERT
KEEDA ALERT
CLEAN
KEEDA ALERT
CLEAN

CODE:

import ncst.pgdst.*;
class keeda
{
 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();
  int plates=Integer.parseInt(s.readWord());
  for(int j=0;j<plates;j++)
  {
   int n=Integer.parseInt(s.readWord()),foundInLayer=999;
   boolean alert=false,curry=false;
   for(int i=0;i<n;i++)
   {
    String layer=s.readWord();
    if (layer.indexOf("K")!=-1 && i>1) {foundInLayer=i;alert=true;}
    if (i<3 && layer.indexOf("C")!=-1) curry=true;
    if (foundInLayer==2) alert=curry;
   }//for i
   if (alert) System.out.println("KEEDA ALERT"); else System.out.println("CLEAN");
  }//for j
 }//main
}//class

And these were some of the questions my classmates created:

 

Problem 1:

 

Print the Fibonacci series which is prime number.
Fibonacci-series: A sequence of numbers in which each number equals the sum of the two preceding numbers.
For example: 2 3 5 8 13 21 34 55
Prime Numbers: A number which is divided only by 1 or itself.
(Note: 2 is a prime number).
For example: 3,5,13 etc.
You have to generate Fibonacci series and choose prime number among them and print it.

Input specification:
The first line of input will be two integers, a and b, separated by a space, specifying the first numbers in Fibonacci series.
The second line is also an integer, specifying the number of elements to be generated to check prime numbers.

Output specification:
The output contains only one line, containing each elements in Fibonacci series which should be prime number having single space between them.

Sample Input/Output:

Input:
2 3
5
Output:
2 3 5 13

 

 

 

Problem 2: LUCKY-5-PRIME

The objective of the program is to count the number of lucky-5-prime numbers occurring within a given range of integers. Lucky-5-prime numbers are those prime numbers the sum of whose digits add up to integer value 5. If the sum of digits of a number generates a two digit number add it's digits again to generate a single integer value.
For eg, 345=3+4+5=12
12=1+2=3

INPUT SPECIFICATION:
Input line contains two integers M and N which is the range of numbers
OUTPUT SPECIFICATION:
If number is found print LUCKY followed by the number of lucky 5 prime numbers after a space, terminated by a newline
If number is not found in the given range print NO LUCK terminated by a newline

Sample Input/Output:

Input
1 50
Output
LUCKY 3

 

 

Problem 3: Maximal Subsequence Problem:
Consider a series of numbers:
Eg: -2, 11, -4, 13,-5,-2
What is its maximal subsequence, i.e., a contiguous part of this series whose sum is maximum of all such subsequence?
Total sum is: 11
Subsequence <11,-4,13>= 20.(Maximum).
You have to write a program to find the maximal subsequence and print it with starting and last address. Assume position start with 1 and if there is more than one duplicate maximum then should be preferred first set of numbers.

Input specification:
The input will be single line containing an integer N, followed by N integers.
Output specification:
Only 3 values separated by single space
1st is maximum value.
2nd is position of first value.
3rd is position of second value.

Sample Input/Output:

Input:
8 -2 -3 45 25 -90 50 20 -1 -2
Output:
70 3 4

Input:
8 23 34 -90 34 5 6 7 98
Output:
150 4 8

Problem 4:
Create a stack consisting of the following elements : {32,29,24,20,12}. Observe that the stack created is arranged in
descending order from bottom to "top"(Top is the
upper bound of the stack from where insertions and deletions take place.) Given an ITEM to be pushed, insert into the
stack without disturbing the order of elements,
i.e stack should be in descending order even after insertion of ITEM and also without disturbing the property of stack.
Input Specification:
One line of input consisting of an integer value ITEM, which is to be pushed into existing stack.
Output specification:
Print the steps involved in pushing the new item into the stack i.e to push an item print PUSH <item> and for popping out
an item print POP <item>.
The popped item is reinserted into the stack according to it's value. Terminate each step with a newline.

For eg.
Input
22
Output
POP 12
POP 20
PUSH 22
PUSH 20
PUSH 12

Input
24
Output
POP 12
POP 20
PUSH 24
PUSH 20
PUSH 12

Problem 5
Consider a fees payment counter. Students waiting for service form a queue. At the start, the queue is empty and time is zero. The service per student is 5 minute. The input to the program consists of an integer N followed by a sequence of integer and float values indicating the arrival time (in
minutes) and amount paid respectively by the student. The times are given as offset from the start of simulation. So that an input 50 means 50 minutes
from the start of the simulation.If value of N is equal to the value of the arrival time of the student you have to consider that the student had paid his
amount.

The sequence of input numbers is terminated by number-1.
A program must simulate the queue and print the following.
1. The number of students processed until N minutes from the start of the
simulation.
2. The total amount of fees submitted from the students at time=N minutes.

In the output, each value must be separated by a space. Terminate your output with a newline character. For doing the computation, you can assume that
if the counter is expected to be vacant at time T, the first student in the queue will be scheduled for service before counting is done for time T.

Assumptions:-

1.The given arrival times will be already in sorted order.
2.The no of students will always be less than 200.
3.The input will terminated by -1.

Input:-
17 3 200.0 7 110.0 8 6.3 8 20.9 10 300.0 -1

output:-
3 316.3

Few interested classmates regularly attempted the mock MGPT's. Some of them were the only ones to crack the real MGPT's too. The sessions were helpful in taking a bit of the tension away from our minds. If I may humbly mention, I was the first one in my class to crack the real MGPT's and eventually was the only one to pass my PGDST course in the first attempt, because I was the only one in a class of 38 (comprising of CS engineers and MCA grads), to clear the necessary number of MGPT's.

The FPGDST (one year course) students had it easy. Their MGPT's were extremely simple. We PGDST (half year course) students had it very tough. Clearing it was not only a challenge, it was satisfying to have given my best shot at something and winning!