5
\$\begingroup\$

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:

  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.

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

  1. 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?
  2. I know this code can be easily done in Python or other languages, but I am trying to learn C++ here.

Questions

  1. Is vector a good way to deal with this data? If not, what else works and why?
  2. 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);
                }
            }
*/

    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Sadly, you asked near the end of the day when I am all out of votes... :/ \$\endgroup\$ – syb0rg Mar 25 '14 at 22:01
  • \$\begingroup\$ @syb0rg Ah! no problem mate :) ther's always another day :) @Jamal♦ Thank you for the edit once again :) \$\endgroup\$ – Dexobox Mar 25 '14 at 22:30
3
\$\begingroup\$

Reading a unit test:

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

// Utility class that reads ',' seprated words from a stream.
// Also automatically converts to std::string when needed.
struct ItemInList
{
    std::string itemValue;
    operator std::string {return itemValue;}
    friend std::istream& operator>>(std::istream& s, ItemInList& value)
    {
        return std::getline(s, value.itemValue, ',');
    }
};

///// STUFF

std::ifstream  file(<fileName>);

std::string   allCustomers;
std::getline(file, allCustomers, ';');          // Reads upto ';' puts the content into `allCustomers`
std::stringstream allCustomersStr(allCustomers);// Convert the string into a stream

// Iterate over the stream. Copy the values into the vector.
std::vector<std::string>  customerVec(std::istream_iterator<ItemInList>(allCustomersStr),
                                      std::istream_iterator<ItemInList>());



std::string   allProducts;
std::getline(file, allProducts);
std::stringstream  allProductsStr(allProducts);
std::vector<std::string>  productVec(std::istream_iterator<ItemInList>(allProductsStr),
                                      std::istream_iterator<ItemInList>());

EDIT 1:

Same thing applies to stripping things

struct Strip
{
     // Defining the method `operator()` means that objects of this type
     // Can be called like functions.
     //
     //  Strip  stripper;
     //  std::cout << stripper("String with 56686868 Bad char") << "\n";
     //
     // This is called a functor (a function like object).
     std::string operator()(std::string value) const
     {
          // remove bad characters.
          // 
          return value;
     }

     // So why do this over a function.
     // It turns out this is much easier for the compiler to optimize.
     //
     // But this technique is really a closure in disguise.
     // A closure is a function with captured state. Now this particular
     // one does not capture state but by adding some member variables
     // you can save information each time it is called and that 
     // information can be used on subsequent calls.
};

std::transform(std::begin(product_name), std::end(product_name), // Src
               std::begin(product_name),                         // Dst (same as src
               Strip());   // Action create strip object.

Of course this can be done in a single line with C++11 and lambdas.

std::transform(std::begin(product_name), std::end(product_name), // Src
               std::begin(product_name),                         // Dst (same as src
               [](std::string value){
    // remove bad characters.        The lambda declaration
    //                               Basically creates an anonymous functor
    return value;                //  behind the scenes.

});

Which technique to use is still a matter of debate. If the operation is common (by common I mean easy to understand and you can tell what it does by its name without looking it up) and you think it can be re-used then I would use a functor. If it is a on-off and short i would use a lambda. Everything else will depnd on how easy it is to read in the context.

Edit 2

Copying arrays/vectors to the output:

            for (int i=0; i<product_list.size();i++){
                std::cout << product_list[i] << "\n\n" << std::endl;

Can be greatly simplified. using the above techniques.

std::copy(std::begin(product_list), std::end(product_list),
          std::ostream_iterator<std::string>(std::cout, "\n\n\n"));
                             // ^^^^^^^^^^^

Here simply printing the string. But by changing std::string here I can modify how the output is printed. Thus encapsulating and changing the printing behavior.

\$\endgroup\$
  • \$\begingroup\$ Very peculiar way to use a structure .. haven’t come across anything like this before, confuses me a bit \$\endgroup\$ – Dexobox Mar 25 '14 at 22:53
  • 1
    \$\begingroup\$ You should read my other answers then. This is very common technique in C++. You define some small piece of functionality in a class (same as a struct) then use that as the control over a generic function. Though in C++11 lambdas are becoming very popular (this allows the code to be defined inline (but this is a technique I am still learning)). \$\endgroup\$ – Martin York Mar 26 '14 at 14:58
  • 1
    \$\begingroup\$ Anyway. If you see a loop. See if you can eliminate it with an algorithm that uses an iterator. For streams this means using istream_iterator or ostream_iterator for other containers std::begin() and std::end() \$\endgroup\$ – Martin York Mar 26 '14 at 15:02
  • \$\begingroup\$ Wow! gr8 info Edit2 method is so much more readable and way cooler than a for loop :P . I am still unclear (one Edit 0 & 1)as to how operator overloading(that's what i assume that is , if i am wrong please correct me ) works and i need to read on that i guess to understand the structs you have created. Also how would you handle the last case where (number_of_customers) != (number_of_products) .. i.e. Aron Adelson has no product pair. Program generates a seg-fault if the pairs are not complete. ignore the last one customer ? \$\endgroup\$ – Dexobox Mar 26 '14 at 20:49
  • 1
    \$\begingroup\$ Technically it would be operator overloading. But you will get better search results if you search for functor. \$\endgroup\$ – Martin York Mar 26 '14 at 22:08
3
\$\begingroup\$
#define DEBUG false

This strikes me as a poor idea. Your code depends only on whether DEBUG is defined or not. As it stands, it looks rather like you're trying to say: "Don't include the debugging code", but in fact the opposite is actually true. I'd either define DEBUG to true (or 1), or not define it at all.

//=================================
      MAIN ROUTINE AT END 
//=================================

I'm a bit uncertain how you managed to get this to compile at all. It shouldn't, since the MAIN ROUTINE AT END part isn't in a comment (or maybe it's something you edited in while posting--hard to be sure).

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

I think I'd count the vowels using something like std::count_if:

static const std::string vowels = "aAeEiIoOuUyY";

int num_vowels = std::count_if(s.begin(), s.end(), 
     [](char ch) { return vowels.find(ch) != std::string::npos; });

That may or may not be noticeably faster, but (IMO) it's a lot more convenient and readable.

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

I'm not sure, but I suspect this isn't doing what you intended. You're adding strings to a[i], but incrementing j (and never using it). At a guess, you may have intended to do something like a[j].push_back(token);?

In any case, I think @Loki's suggestion is much better; instead of trying to fix the details here, I'd try to start with something simpler and cleaner.

\$\endgroup\$
  • \$\begingroup\$ I gathered the debug method was poorly written. Also i dont know why i put the "false" after the debug. Yes! i commented stuff while posting which might have broken things :( . count_if that is very COOL .. definitely something new to learn. Actually the j was for something else .. now i just use it to gather a count. The motive here was to push a empty vector first so i could created 2nd dimension members of the 2D vectr and assign strings. @Jerry what do you think was vector a good choice for this program, in terms of data structures that can be used for this problem? \$\endgroup\$ – Dexobox Mar 26 '14 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.