Infibeam Interview Question for SDE-2s


Country: India




Comment hidden because of low score. Click to expand.
0
of 0 vote

That's a bit of a rote, isn't it?

#!/usr/bin/python

import sys

digits = {
    "i": 1,
    "v": 5,
    "x": 10,
    "l": 50,
    "c": 100,
    "d": 500,
    "m": 1000
}

num = {}
goods = {}



def msg(s):
    """Return-and-print frontend"""
    print s

    

def parse(word):
    """Parse a Galactic/Roman number"""
    
    n = 0
    try:
        dig = [num[i] for i in word]
    except:
        return -1
        
    while dig:
        d = dig.pop(0)
        if dig and dig[0] > d:
            n -= d
        else:
            n += d
            
    return n

         

def process(line):
    """Read a sentence."""
    
    word = line.lower().split(None)
    
    if not word:
        return
        
    if len(word) == 3 and word[1] == "is":
        key = word[0]
        val = word[2]
        
        if not val in digits:
            return msg("'%s' is not a valid digit." % val)
        num[key] = digits[val]
        return
        
    if len(word) > 4 and word[-1] == "credits" and word[-3] == "is":
        word.pop()
        try:
            val = float(word[-1])
        except:
            return msg("'%s' is not a valid numeric value" % word[-1])
            
        word.pop()
        word.pop()
        g = word.pop()
        n = parse(word)
        
        if n < 0:
            return msg("That's not a valid Galactic number")
        
        goods[g] = val / n
        return
        
    if word[0:3] == ["how", "much", "is"]:
        word = word[3:]
        if word[-1] == "?":
            word.pop()
            
        n = parse(word)
        if n < 0:
            return msg("'%s' is not a valid Galactic number" % " ".join(word))
            
        print " ".join(word), "is", n
        return
        
    if word[0:4] == ["how", "many", "credits", "is"]:
        word = word[4:]
        if word[-1] == "?":
            word.pop()
            
        g = word.pop()
        if not g in goods:
            return msg("I don't know of the trading good %s" % g)
            
        n = parse(word)
        if n < 0:
            return msg("'%s' is not a valid Galactic number" % " ".join(word))
            
        print " ".join(word), g.title(), "is", int(n * goods[g]), "Credits"
        return
        
    return msg("I've no idea what you are talking about")



for line in sys.stdin:
    process(line)

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please tell that how test cases are executing?

you can reply me on kashifaliquazi@gmail.com

- ashish August 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please tell that how test cases are executing?

you can reply me on sd.junaidali@gmail.com

- Anonymous September 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);

- Anonymous May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

- Sivasakthi Jayarman May 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

}

- Vikram Singh Chouhan June 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I got the question but i am not understanting how the test cases are executing?
what I have understand from the problem is how to convert roman to decimal and vice versa can any one please tell me how test cases are executed?
thanks in advance

- ashish sharma August 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check out the solution on github repo
user: rohinp
repository: merchantguide
Some how pasting links on careercup is not allowed so specifying the user and repo name.
Feedback is welcomed.

- Rohin Patel April 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{Check the solution on the github repo
user: rohinp
repo: merchantguide

Feedback is welcomed.
PS. careercup doesn't allow to paste links in comments thats very annoying how can someone code entire stuff for a complicated problem like this.}}

- rohin April 03, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More