Infibeam Interview Question
SDE-2sCountry: India
can you please tell that how test cases are executing?
you can reply me on kashifaliquazi@gmail.com
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
class RomanBase
{
private:
int _factor;
protected:
virtual const char *_One() = 0;
virtual const char *_Four() = 0;
virtual const char *_Five() = 0;
virtual const char *_Nine() = 0;
public:
RomanBase(int factor) { _factor = factor; }
virtual ~RomanBase() {}
virtual int ToDecimal(char *input)
{
int decimal = 0;
int chars_done = 0;
if (!strlen(input)) // nothing to parse
return 0;
if (!strncmp(input, _Four(), 2))
{
decimal = 4 * _factor;
chars_done = 2;
}
else if (!strncmp(input, _Nine(), 2))
{
decimal = 9 * _factor;
chars_done = 2;
}
else
{
if (!strncmp(input, _Five(), 1))
{
decimal = 5 * _factor;
chars_done = 1;
}
// takes care of all remaining ones (1,2,3,6,7,8)
for (int max_repeat = chars_done + 3; chars_done < max_repeat; chars_done++) {
if (!strncmp((input+chars_done), _One(), 1))
decimal += 1 * _factor;
else
break;
}
}
// remove the chars_done
strcpy(input, (input + chars_done));
return decimal;
}
};
class RomanThousand: public RomanBase
{
protected:
const char *_One() { return "M"; }
const char *_Four() { return ""; }
const char *_Five() { return ""; }
const char *_Nine() { return ""; }
public:
RomanThousand(): RomanBase(1000) {}
~RomanThousand() {}
};
class RomanHundred: public RomanBase
{
protected:
const char *_One() { return "C"; }
const char *_Four() { return "CD"; }
const char *_Five() { return "D"; }
const char *_Nine() { return "CM"; }
public:
RomanHundred(): RomanBase(100) {}
~RomanHundred() {}
};
class RomanTen: public RomanBase
{
protected:
const char *_One() { return "X"; }
const char *_Four() { return "XL"; }
const char *_Five() { return "L"; }
const char *_Nine() { return "XC"; }
public:
RomanTen(): RomanBase(10) {}
~RomanTen() {}
};
class RomanOne: public Roman
{
protected:
const char *_One() { return "I"; }
const char *_Four() { return "IV"; }
const char *_Five() { return "V"; }
const char *_Nine() { return "IX"; }
public:
RomanOne(): Roman(1) {}
~RomanOne() {}
};
class RomanNumber {
private:
char * _string;
RomanBase * _array[4]; // max roman number 3999!
public:
RomanNumber(): _string(NULL) {
for (int i = 0; i<4; i++)
_array[i] = NULL;
}
~RomanNumber() {
for (int i = 0; i<4; i++)
delete _array[i]; // clean it up
}
int ToDecimal(const char * roman) {
_string = strdup(roman);
if (!_array[0]) _array[0] = new RomanThousand();
if (!_array[1]) _array[1] = new RomanHundred();
if (!_array[2]) _array[2] = new RomanTen();
if (!_array[3]) _array[3] = new RomanOne();
int decimal = 0;
for (int i = 0; i<4; i++)
decimal += _array[i]->ToDecimal(_string);
if (strlen(_string) != 0)
decimal = -1; // invalid roman number
free(_string);
return decimal;
}
};
// in main() just use:
RomanNumber roman;
int decimal = roman.ToDecimal(roman_str);
#include "Roman.h"
#include <boost/regex.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/tokenizer.hpp>
#include <boost/lexical_cast.hpp>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
using namespace boost::algorithm;
void Roman::intergalaxy_transaction(string& request)
{
//print the input
cout<<"INPUT: "<<request<<endl;
//Read the file and get the list of input string
vector<string> input_list = get_input_list();
//This credit list will store the key/value of Gold/Silver/Iron credit values
map<string,float> credit_list = get_credit_list(input_list);
//Generate output
string output_str = get_output(request,credit_list);
//print result
cout<<"OUTPUT: "<<output_str<<endl;
cout<<"============================================="<<endl;
}
map<string,float> Roman::get_credit_list(vector<string> &input_list)
{
//This base list will store key/value of glob=I,prok=V,pish=X and tegj=L
//map<string,string> base_list;
//Final list
map<string,float> credit_list;
//Apply rules
static const boost::regex rule1("^(glob|prok|pish|tegj){1}.* is{1} (I|V|X|L){1}$");
static const boost::regex rule2("^(glob|prok|pish|tegj){1}.* (glob|prok|pish|tegj){1}.* (Silver|Gold|Iron){1} .* Credits$");
//Build dict
for(int index=0;index<input_list.size();index++)
{
string input_str =input_list.at(index);
if ( true == regex_match(input_str,rule1))
{
string key= input_str.substr(0,4);
string value = input_str.substr(input_str.size()-1,input_str.size());
base_list[key] = value;
}
else if(true == regex_match(input_str, rule2))
{
float credit_value = 0.0;
if(input_str.find("Gold") != -1)
{
credit_value = get_credit_value(base_list,input_str);
credit_list["Gold"] = credit_value;
}
else if(input_str.find("Silver") != -1)
{
credit_value = get_credit_value(base_list,input_str);
credit_list["Silver"] = credit_value;
}
else if(input_str.find("Iron") != -1)
{
credit_value = get_credit_value(base_list,input_str);
credit_list["Iron"] = credit_value;
}
else
{
cout<<"Gold/Silver/Iron only currently allowed"<<endl;
}
}
else
{
cout<<"String Not Matched For Input, Please refer the format \""<<input_str<<"\""<<endl;
}
}
return credit_list;
}
string Roman::get_output(string &request,map<string,float> &credit_list)
{
//Output Format Rules
static const boost::regex rule1("^((how much is)?) ((pish|tegj|glob|prok|\\?)\\s?){0,}$");
static const boost::regex rule2("^((how many Credits is)?) ((pish|tegj|glob|prok)\\s?){0,}((Silver|Gold|Iron)\\s?){1}\\?$");
string final_output;
if ( true == regex_match(request,rule1))
{
string output_str = get_result(request);
final_output = output_str + "is " + boost::lexical_cast<std::string>(process_tokens(output_str));
}
else if(true == regex_match(request,rule2))
{
string output_str = get_result(request);
float credit_val = credit_list[find_credit_name(output_str)] * process_tokens(output_str);
final_output = output_str + " is " + boost::lexical_cast<std::string>(credit_val) + " Credits";
}
else
{
final_output = "I have no idea what you are talking about";
}
return final_output;
}
string Roman::find_credit_name(string &credit_name)
{
trim(credit_name);
int found = credit_name.find_last_of(" ");
return credit_name.substr(found+1);
}
int Roman::process_tokens(string &string_tokens)
{
typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
boost::char_separator<char> sep(" ");
tokenizer tok(string_tokens,sep);
string temp_str;
for(tokenizer::iterator beg=tok.begin(); beg!=tok.end();++beg)
{
string t = string(*beg);
temp_str += base_list[t];
}
return convert_roman_to_number(temp_str);
}
string Roman::get_result(string &request)
{
int start = request.find(" is ");
int end = request.find("?");
string output_str = request.substr(start+3,(end-(start+3)));
return output_str;
}
float Roman::get_credit_value(map<string,string> &base_list,string &input_str)
{
string roman_value = base_list[input_str.substr(0,4)] + base_list[input_str.substr(5,4)];
int decimal_value = convert_roman_to_number(roman_value);
int start = input_str.find(" is ");
int end = input_str.find(" Credits");
string credit_value_str = input_str.substr(start+3,(end-(start+3)));
return (atof(credit_value_str.c_str())/decimal_value);
}
int Roman::convert_roman_to_number(string& input_str)
{
//Init the map
map<char,int> maplist = init_map();
//Trim the input;
trim(input_str);
//Check the given Rules
apply_rules(input_str);
//Convert Roman to number
return romanToNumber(input_str,maplist);
}
map<char,int> Roman::init_map()
{
map<char,int> mlist;
mlist['I'] =1;
mlist['V'] =5;
mlist['X'] =10;
mlist['L'] =50;
mlist['C'] =100;
mlist['D'] =500;
mlist['M'] =1000;
return mlist;
}
bool Roman::apply_rules(const string& str)
{
//Rule1: "I", "X", "C", and "M" 3 times allowed
//Rule2: "D", "L", and "V" shouldnt be repeated
static const boost::regex e("^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$");
if ( false == regex_match(str, e))
{
throw "Invalid Roman Input";
}
}
int Roman::romanToNumber(const string& input_str,map<char,int> &maplist)
{
int output_num = 0;
for(int i=0,j=1;j<=input_str.length();i++,j++)
{
if(maplist[input_str[i]] >= maplist[input_str[j]])
{
output_num += maplist[input_str[i]];
}
else if(maplist[input_str[i]]<maplist[input_str[j]])
{
output_num += maplist[input_str[j]] - maplist[input_str[i]];
i++;j++;
}
}
return output_num;
}
vector<string> Roman::get_input_list()
{
vector<string> list;
ifstream file("InputFile.txt");
string line;
while(getline(file, line))
{
list.push_back(line);
}
file.close();
return list;
}
O/P:
INPUT: how much is pish tegj glob glob ?
OUTPUT: pish tegj glob glob is 42
=============================================
INPUT: how many Credits is glob prok Silver ?
OUTPUT: glob prok Silver is 68 Credits
=============================================
INPUT: how many Credits is glob prok Gold ?
OUTPUT: glob prok Gold is 57800 Credits
=============================================
INPUT: how many Credits is glob prok Iron ?
OUTPUT: glob prok Iron is 782 Credits
=============================================
INPUT: how much wood could a woodchuck chuck if a woodchuck could chuck wood ?
OUTPUT: I have no idea what you are talking about
Hi
Below is the Java Implementation:
/////////////////////////Handling the use cases stated in the question/////////////
import java.util.HashMap;
public class GalaxyGuide {
/**
* Creating symbol table for parsing roman numeral values to decimal
* nums: key value entry to keep track of inputs given
* goods: key value entry to decode the message and store the Credit value corresponding to the good stuff.
**/
private HashMap<Character, Integer> symbol_table = new HashMap<Character, Integer>();
private HashMap<String, String> nums = new HashMap<String, String>();
private HashMap<String, String> goods = new HashMap<String, String>();
private String key;
private String val;
private String message_symbols;
private String message_txt;
private int num_values;
private double good_values;
private int decimal;
private String good_name;
//insert roman symbol values in symbol table
private void insertSymbolValues(){
symbol_table.put('I', 1);
symbol_table.put('V', 5);
symbol_table.put('X', 10);
symbol_table.put('L', 50);
symbol_table.put('C', 100);
symbol_table.put('D', 500);
symbol_table.put('M', 1000);
}
/**
* parsing the roman numeral value into decimal value
**/
private int parse(String symbols){
if(symbols == null)
return 0;
if(symbols.length() == 1){
return symbol_table.get(symbols.charAt(0));
}
decimal = 0;
// boolean flag = true;
for(int i = 0; i < symbols.length(); i++){
if( i+1 < symbols.length()){
if(symbol_table.get(symbols.charAt(i)) >= symbol_table.get(symbols.charAt(i+1))){
decimal = decimal + symbol_table.get(symbols.charAt(i));
}
else{
//subtracting the decimal value of the roman numeral as it is smaller than it's next one.
decimal = decimal + (symbol_table.get(symbols.charAt(i+1)) - symbol_table.get(symbols.charAt(i)));
i++;
}
}
else {
decimal = decimal + symbol_table.get(symbols.charAt(i));
}
}
return decimal;
}
/**
* To Decode the message and conclude accordingly.
* it may be a hidden data entry to goods.
* it may be a question whose output is required.
**/
void processMessage(String[] message, int words){
//handling "glob is I" type of input message
if(words == 3 && message[1].equalsIgnoreCase("is")){
key = null;
val = null;
try{
key = message[0];
val = message[words - 1];
//to check whether a valid roman numeral
if(parse(val)/1 == 1){}
}
catch(NumberFormatException e){
System.out.println(message[words - 2] + "is not a valid numeric value.");
}
catch(Exception e){
System.out.println("I've no idea what you are talking about");
}
nums.put(key, val);
return;
}
//handling "glob glob silver is 34 credits" type of input messages
if(words > 4 && message[words-1].equalsIgnoreCase("credits") && message[words-3].equalsIgnoreCase("is") ){
message_symbols = "";
key = null;
val = null;
try{
key = message[words - 4];
val = message[words - 2];
}
catch(Exception e){
System.out.println(message[words - 2] + " is not a valid numeric value.");
}
//getting the part of message to be parsed
for(int i = 0; i< words - 4; i++){
if(nums.get(message[i]) != null)
message_symbols = message_symbols + nums.get(message[i]);
else{
System.out.println(message[i] + " is not a valid symbol.");
return;
}
}
num_values = -1;
num_values = parse(message_symbols);
if(num_values > 0)
//making entry to the goods
goods.put(key, String.valueOf(((double)(Double.valueOf(val)/num_values))));
else
System.out.println(val + " is not a valid Galactic number.");
return;
}
//handling "how many credits is glob prok silver ?" type of input questions
if(words > 4 && message[0].equalsIgnoreCase("how") && message[1].equalsIgnoreCase("many")
&& message[2].equalsIgnoreCase("credits") && message[3].equalsIgnoreCase("is")){
message_symbols = "";
good_name = null;
message_txt = "";
if(message[words-1].equals("?"))
words--;
good_name = message[words-1];
//getting the part of message to be parsed
for(int i = 4; i < words -1; i++){
if(nums.get(message[i]) != null){
message_symbols = message_symbols + nums.get(message[i]);
message_txt = message_txt + message[i] + " ";
}
else{
System.out.println(message[i] + " is not a valid symbol.");
return;
}
}
num_values = -1;
num_values = parse(message_symbols);
if(num_values > 0){
good_values = Double.valueOf((goods.get(good_name)));
if(good_values != 0){
System.out.println(good_name + " is not a valid Galactic number.");
System.out.println(message_txt + " " + good_name + " is " + num_values * good_values + " credits");
}
else{
System.out.println(good_name + " is not a valid Galactic number.");
}
}
else
System.out.println(message_symbols + " is not a valid Galactic number.");
return;
}
//handling "how much is pish tegj glob glob ?" type of input questions
if(words > 4 && message[0].equalsIgnoreCase("how") && message[1].equalsIgnoreCase("much") && message[2].equalsIgnoreCase("is")){
message_symbols = "";
message_txt = "";
if(message[words-1].equals("?"))
words--;
//getting the part of message to be parsed
for(int i =3; i < words; i++){
if(nums.get(message[i]) != null){
message_symbols = message_symbols + nums.get(message[i]);
message_txt = message_txt + message[i] + " ";
}
else{
System.out.println(message[i] + " is not a valid symbol.");
return;
}
}
num_values = -1;
num_values = parse(message_symbols);
if(num_values > 0){
System.out.println(message_txt + " is " + num_values + " credits");
}
else
System.out.println(message_symbols + " is not a valid Galactic number.");
return;
}
System.out.println("I've no idea what you are talking about");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GalaxyGuide guide = new GalaxyGuide();
//initializing symbol table
guide.insertSymbolValues();
//Declaring message strings to save and create string array to process
String[] galactic_message = new String[100];
String[] input_message = new String[10];
int i = 0, j = 0, start_index = 0, words = 0;
String temp = null;
//Initilizing input messages
galactic_message[0] = "glob is I";
galactic_message[1] = "prok is V";
galactic_message[2] = "pish is X";
galactic_message[3] = "tegj is L";
galactic_message[4] = "glob glob silver is 34 credits";
galactic_message[5] = "glob prok gold is 57800 credits";
galactic_message[6] = "pish pish iron is 3910 credits";
galactic_message[7] = "how much is pish tegj glob glob ?";
galactic_message[8] = "how many credits is glob prok silver ?";
galactic_message[9] = "how many credits is glob prok iron ?";
galactic_message[10] = "asd";
//iterating over the input messages and passing it to process
while(galactic_message[j] != null && j < galactic_message.length){
temp = galactic_message[j];
start_index = 0;
words = 0;
//Building input string array from input message string.
for(i = 0; i < temp.length(); i++){
if(temp.charAt(i) == ' ' || i == temp.length()-1 ){
if(i == temp.length() - 1)
i++;
input_message[words] = temp.substring(start_index, i);
start_index = i + 1;
words++;
}
}
j++;
//Send input message string for processing.
guide.processMessage(input_message, words);
}
}
}
That's a bit of a rote, isn't it?
That code doesn't bother to enforce all laws about Roman numerals and the pattern matching for the sentences is rather strict. It falls flat, when there is no space before the question mark, for example.But it's a start, I guess.
- Anonymous April 30, 2014