I am a beginner in C++ and learning from textbook. I find it hard to jump into oops concepts as I have used C a lot. Here is an interview question I came across:
Problem Statement
Our marketing department has just negotiated a deal with several local merchants that will allow us to offer exclusive discounts on various products to our top customers every day. The catch is that we can only offer each product to one customer and we may only offer one product to each customer.
Each day we will get the list of products that are eligible for these special discounts. We then have to decide which products to offer to which of our customers. Fortunately, our team of highly skilled statisticians has developed an amazing mathematical model for determining how likely a given customer is to buy an offered product by calculating what we call the "suitability score" (SS). The top-secret algorithm to calculate the SS between a customer and a product is this:
- If the number of letters in the product's name is even then the SS is the number of vowels (a, e, i, o, u, y) in the customer's name multiplied by 1.5.
- If the number of letters in the product's name is odd then the SS is the number of consonants in the customer's name.
- If the number of letters in the product's name shares any common factors (besides 1) with the number of letters in the customer's name then the SS is multiplied by 1.5.
Your task is to implement a program that assigns each customer a product to be offered in a way that maximizes the combined total SS across all of the chosen offers. Note that there may be a different number of products and customers. You may include code from external libraries as long as you cite the source. INPUT SAMPLE:
Your program should accept as its only argument a path to a file. Each line in this file is one test case. Each test case will be a comma delimited set of customer names followed by a semicolon and then a comma delimited set of product names. Assume the input file is ASCII encoded. For example (NOTE: The example below has 3 test cases):
Jack Abraham,John Evans,Ted Dziuba;iPad 2 - 4-pack,Girl Scouts Thin Mints,Nerf Crossbow
Jeffery Lebowski,Walter Sobchak,Theodore Donald Kerabatsos,Peter Gibbons,Michael Bolton,Samir Nagheenanajar;Half & Half,Colt M1911A1,16lb bowling ball,Red Swingline Stapler,Printer paper,Vibe Magazine Subscriptions - 40 pack
Jareau Wade,Rob Eroh,Mahmoud Abdelkader,Wenyi Cai,Justin Van Winkle,Gabriel Sinkin,Aaron Adelson;Batman No. 1,Football - Official Size,Bass Amplifying Headphones,Elephant food - 1024 lbs,Three Wolf One Moon T-shirt,Dom Perignon 2000 Vintage
Known Bug
- I don't know how to handle the last input sample. It has 7 customer names and 6 products. I'm confused on how to handle that. What would be a good approach?
- I know this code can be easily done in Python or other languages, but I am trying to learn C++ here.
Questions
- Is vector a good way to deal with this data? If not, what else works and why?
- I am using too many "for" loops which is a bad thing (I guess). Any other approach to eliminating them?
General code review/ suggestions/ creative criticism would be cool.
#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>
#define DEBUG false
//=================================
MAIN ROUTINE AT END
//=================================
int getGCD(int a, int b)
{
if(b == 0)
return a;
else
return getGCD( b , a % b );
}
double find_common(int a, int b) // basically a GCD finder
{
int gcd;
gcd = getGCD ( a , b );
if (gcd > 1)
return 1.5;
else
return 1.0;
}
void find_let_vow_con(std::string s, int& l, int& v, int& c)
{
char chars[] = "aAeEiIoOuUyY";
v = 0;
//Y is a vowel and a consonant (looked up in the dicitionary :)
l = s.size();
for(int i = 0; i< sizeof(chars); i++)
{
for(int j = 0; j < l; j++ )
{
if(s[i]== chars[j])
v++;
}
}
c = l - v; //consonants = num_letters in string - num_vowels
std::cout << "string = " << s << std::endl;
std::cout << "num_letters = " << l << std::endl;
std::cout << "num_vowels = " << v << std::endl;
std::cout << "num_consonants = " << c << std::endl;
}
void strip_string(std::string& s)
{
char chars[] = "\n\r.-_1234567890 ";
for (unsigned int i = 0; i < sizeof(chars); ++i)
{
// you need include <algorithm> to use general algorithms like std::remove()
s.erase (std::remove(s.begin(), s.end(), chars[i]), s.end());
}
}
void comma_seprate(std::string s, std::vector < std::vector<std::string> >& a , int i)
{
std::istringstream ss(s);
std::string token;
//s.resize(i);
std::vector<std::string> n;
int j = 0;
while(std::getline(ss, token, ','))
{
//n.push_back(token);
a.push_back(std::vector<std::string>());
a[i].push_back(token);
std::cout << token << std::endl;
j++;
}
}
void split_string( std::string s, std::vector<std::string>& v, std::vector<std::string>& u )
{
std::string delimiter = ";";
v.push_back (s.substr(0, s.find(delimiter)));
u.push_back (s.substr(s.find(delimiter)+1,s.size()));
}
int main ( int argc, char** argv )
{
//variable for file name
std::string filename;
//error handling for invalid argument size
if ( argc > 2 || argc < 2 )
{
std::cerr <<"filename missing! Usage: " << argv[0] << " <input_filename>"<< std::endl;
return EXIT_FAILURE;
}
//=========================================================================
//Using C style debugging : Any other way to do this in c++?
#ifdef DEBUG
std::cout << "filename :"<<filename << "\t num_arguments: " << argc << std::endl;
#endif
//=========================================================================
//opening the file for reading
std::ifstream in(argv[1]);
std::vector<std::string> line_vec;
std::string temp_line;
int line_count = 0;
while(std::getline(in,temp_line))
{
line_count++;
//Ignores any empty lines in the input file
if(temp_line.empty())
continue;
line_vec.push_back(temp_line);
}
//=========================================================================
#ifdef DEBUG
std::cout <<"\nPrinting out contents of the line_vec" <<std::endl;
for (int i=0; i<line_vec.size();i++){
std::cout << line_vec[i] << std::endl;
}
std::cout << "The size of the line_vector is : " << line_vec.size() << std::endl;
#endif
//=========================================================================
//Now splitting line by semicolon for customer names and product name seperation
std::vector<std::string> customer_list;
std::vector<std::string> product_list;
for (int i=0; i<line_vec.size();i++)
{
split_string(line_vec[i], customer_list, product_list);
}
#ifdef DEBUG
std::cout <<"=======================================================================" <<std::endl;
std::cout <<"\nPrinting out contents of the customer_list " <<std::endl;
std::cout <<"=======================================================================" <<std::endl;
for (int i=0; i<customer_list.size();i++){
std::cout << customer_list[i] << "\n\n" << std::endl;
}
std::cout << "The size of the customer_list vector is : " << customer_list.size() << std::endl;
std::cout <<"=======================================================================" <<std::endl;
std::cout <<"\nPrinting out contents of the product_list " <<std::endl;
std::cout <<"=======================================================================" <<std::endl;
for (int i=0; i<product_list.size();i++){
std::cout << product_list[i] << "\n\n" << std::endl;
}
std::cout << "The size of the line_vector vector is : " << product_list.size() << std::endl;
#endif
//comma seprating the string to get a list of customer names and product names
std::vector < std::vector < std::string > > customer_name;
std::vector < std::vector < std::string > > product_name;
for(int i =0; i< customer_list.size(); i++)
{
comma_seprate(customer_list[i],customer_name,i);
comma_seprate(product_list[i],product_name,i);
}
//
#ifdef DEBUG
std::cout << customer_name[0][0]<<std::endl;
std::cout << product_name[0][0]<<std::endl;
#endif
//strip strings with special characters so only letters remain
std::string strip_this;
for(int i =0; i<customer_name.size();i++)
{
for(int j = 0;j<customer_name[i].size();j++)
{
strip_this = customer_name[i][j];
strip_string(strip_this);
customer_name[i][j] = strip_this;
#ifdef DEBUG
std::cout << strip_this << std::endl;
#endif
}
}
for(int i =0; i<product_name.size();i++)
{
for(int j = 0;j<product_name[i].size();j++)
{
strip_this = product_name[i][j];
strip_string(strip_this);
product_name[i][j] = strip_this;
#ifdef DEBUG
std::cout << strip_this << std::endl;
#endif
}
}
double ss = 0,multiplier;
//Odd or Even
/*
1. If the number of letters in the product's name is even then
the SS is the number of vowels (a, e, i, o, u, y) in the
customer's name multiplied by 1.5.
2. If the number of letters in the product's name is odd then
the SS is the number of consonants in the customer's name.
3. If the number of letters in the product's name shares any
common factors (besides 1) with the number of letters in
the customer's name then the SS is multiplied by 1.5.
*/
int cnum_letters,cnum_vowels,cnum_consonants; //number of letters in customer name, vowels and consonants
int pnum_letters,pnum_vowels,pnum_consonants; //number of letters in product name, vowels and consonants
for(int i =0; i<customer_name.size();i++)
{
for(int j = 0;j<customer_name[i].size();j++)
{
find_let_vow_con(customer_name[i][j],cnum_letters,cnum_vowels,cnum_consonants);
find_let_vow_con(product_name[i][j],pnum_letters,pnum_vowels,pnum_consonants);
multiplier = find_common( cnum_letters, product_name[i][j].size() );
if( pnum_letters % 2 == 1) //odd
{
ss += cnum_vowels * 1.5;
}
else //even
{
ss += cnum_consonants;
}
ss = ss * multiplier;
}
std::cout << ss << std::endl;
ss = 0.0;
}
/* for(int i =0; i<product_name.size();i++)
{
for(int j = 0;j<product_name[i].size();j++)
{
find_let_vow_con(product_name[i][j],pnum_letters,pnum_vowels,pnum_consonants);
}
}
*/
}