9
\$\begingroup\$

I was selected for the third round of MS internships for third years. We were surprisingly asked a very easy question: “Make a program that counts the number of times the WORD "a" or "A" occurs”. I wrote the code below and was rejected from attending the final interview.

What is wrong with my code? Please tell me how to improve it. People who used Char[] instead of string and those who didn't check for first and last words to be "A" were all selected. The condition for commas before and after 'a' was also ignored. What is the error? Is str.at(i) not good enough...? I know even if we use str[i] it is interpreted as str.operator[](i), so I'm preventing the overhead conversion, right?

#include<iostream> 
#include<ctype.h>
#include<string>

using namespace std;

int main()
{

    string str;

    getline(cin,str);

    int i;
    int count=0;
    int l=str.length();

    for(i=1;i<l-1;i++)
    {
        if(toupper(str.at(i))=='A')
            if(str.at(i-1)==' ' && str.at(i+1)==' ')
                    count++;
    }

    if(toupper(str.at(0))=='A' && str.at(1)==' ')
        count++;

    if(toupper(str.at(l-1))=='A' && str.at(l-2)==' ')
        count++;

    cout<<"Count is "<<count<<endl;
    return 0;

}
\$\endgroup\$
  • 1
    \$\begingroup\$ What version of C++ are you using? I'm not familiar with the included statement. \$\endgroup\$ – Kevin Aug 15 '12 at 18:17
  • 2
    \$\begingroup\$ One problem I see is: what happens if your input string is just 'A'? \$\endgroup\$ – rpsml Aug 15 '12 at 18:19
  • \$\begingroup\$ "a" & 'a' are different, 'a' is a single character whereas "a" is a string i.e. 'a','\0' \$\endgroup\$ – another.anon.coward Aug 15 '12 at 18:20
  • 1
    \$\begingroup\$ What I would have done is use a std::stringstream. I think that is the easiest possible way. \$\endgroup\$ – StackUnderflow Aug 15 '12 at 18:21
  • 1
    \$\begingroup\$ I would have tried a state machine. It is probably quite simple to implement and have a single forwarding loop over the input. \$\endgroup\$ – David Rodríguez - dribeas Aug 15 '12 at 19:01
11
\$\begingroup\$

First of all, these interview questions are often a trick. It doesn't really matter if your code works for all cases (everybody makes mistakes). What does matter is how you write the code.

Even if they ask specifically for 'a' or 'A', you are not supposed to hardcode these values. They are a parameter. Understanding what is the input to your program is always the first task. If they ask you "Make a program that counts the number of times the letter 'a' occurs in 'Example'", the correct answer won't be return 1;. They also ask for words, you shouldn't assume that the program should search only for words withs 1 letter.

Second - words are not usually delimited only by a space. You should consider all whitespace and punctuation characters. Or just declare a function isWordDelimiter(char) and don't implement it.

Third - your code is not easily readable. An if inside another if in a for? Use functions. Example (pseudocode - I am not C++ programmer and I forgot STL):

while ((word = getNextWord(input)) != NULL) {
    if (word is in set of searched words) {  //replace this with STL set
        count++
    }
}

Summary: Even on a very simple program, they can see how much experienced you are. Good developer won't just write something that works. He has to think how the problem will evolve in the future (different parameters), how the program will be maintained (write readable code). Good developers also write programs from top to bottom - first define the structure using high level functions, then write the implementation of the functions.

\$\endgroup\$
  • 1
    \$\begingroup\$ I wouldn't call such questions a "trick" - instead, they are seemingly-simple questions that can be attempted by anybody, but can also be ramped up to exercise even outstanding candidates ("How do you identify word boundaries? In Japanese?"). Also, in an interview (unlike a written test), they give the candidate an opportunity to show how they gather requirements ("What size input are you giving me? Do I need to case-fold in a specific locale?"). \$\endgroup\$ – Toby Speight Jul 24 '18 at 9:50
7
\$\begingroup\$

You should do this by using the standard library to its fullest:

std::istringstream ss(str);
auto count = std::count_if(std::istream_iterator<std::string>(ss), std::istream_iterator<std::string>(), 
             [](const std::string& s){ return s == "a" || s == "A"; });
\$\endgroup\$
  • \$\begingroup\$ @David Rodríguez - dribeas You're both wrong. It works. Try it or read it more carefully. ideone.com/qq3Bd \$\endgroup\$ – David Aug 15 '12 at 19:01
  • 2
    \$\begingroup\$ Unfortunately this fails if there is punctuation in the input stream. \$\endgroup\$ – Martin York Aug 15 '12 at 19:56
  • \$\begingroup\$ More accurately it fails to detect 'a' or 'A' as a word if an adjacent character is punctuation. But, this just replaces the OPs code - it doesn't add extra functionality. \$\endgroup\$ – David Aug 17 '12 at 1:50
5
\$\begingroup\$
included <iostream> <ctype.h> <string>

If this is the actual code you sent, I probably wouldn't have read past this line. It's not valid C++ or anything. It suggests you didn't even try to compile and run this.

using namespace std;

int main()
{

    string str;

    getline(cin,str);

    int i;

Why are you declaring this here instead of the for loop

    int count=0;
    int l=str.length();

    for(i=1;i<l-1;i++)
    {
        if(toupper(str.at(i))=='A')
            if(str.at(i-1)==' ' && str.at(i+1)==' ')
                    count++;

I wouldn't have nested braceless blocks like this. It can making things harder to read. }

    if(toupper(str.at(0))=='A' && str.at(1)==' ')
        count++;

    if(toupper(str.at(l-1))=='A' && str.at(l-2)==' ')
        count++;

This is an ugly solution. It'd be better if you worked this into the loop.

    cout<<"Count is "<<count<<endl;
    return 0;

}
\$\endgroup\$
  • \$\begingroup\$ I would hope the interviewer knows what the first line means. If this was on a whiteboard, I'd do the same. \$\endgroup\$ – GManNickG Aug 15 '12 at 18:41
  • \$\begingroup\$ @GManNickG: White board sure. In sample code sent for interview not so much. It must compile. \$\endgroup\$ – Martin York Aug 15 '12 at 20:21
  • \$\begingroup\$ Guys..It was a written test...and I included it ..you mean I should put those limit checking constraints into the loop..why to execute it again and again if it doesn't depend on the index i...? You guys think i complicated things using str.at(i)...? After that round I discovered that a loop iterating from 1 to n-1 and using char[] without converting to toupper was selected for next round.....Is it advantageous to use char[]...??? \$\endgroup\$ – Sekharan Natarajan Aug 16 '12 at 12:31
5
\$\begingroup\$

Not an answer

don't vote.

Extended comment.

My first pass at this would be:

int main()
{
    std::cout << "Count of word 'a' or 'A': "
              << std::count_if(std::istream_iterator<std::string>(std::cin),
                               std::istream_iterator<std::string>(),
                               [](std::string const& word)
                               {
                                    return word == "a" || word == "A";
                               }
                              );
}

But the problem with this is that this only breaks up words based on space. What happens if there is punctuation in the input?

Well just imbue the stream with a facet that tells the stream functors that all non word characters are space and then the stream operators will work.

class OnlyLettersNotSpaceFacet: public std::ctype<char>
{
    public:
        typedef std::ctype<char>   base;
        typedef base::char_type    char_type;

        OnlyLettersNotSpaceFacet(std::locale const& l) : base(table)
        {
            // Get the ctype facet of the current locale
            std::ctype<char> const&  defaultCType = std::use_facet<std::ctype<char> >(l);

            // Copy the default flags for each character from the current facet
            static char data[256];
            for(int loop = 0; loop < 256; ++loop) {data[loop] = loop;}
            defaultCType.is(data, data+256, table);

            for(int loop = 0; loop < 256; ++loop)
            {
                if (!std::isalpha(loop))
                {   table[loop] |= base::space;  // anything that is not alpha
                }                                // is now considered a space.
            }
        }
    private:
        base::mask table[256];
};

Now we can write the code just like we did first time (after imbuing the stream).

int main()
{
    // Create a local and imbue the stream with it.
    const std::locale olns(std::cin.getloc(), new OnlyLettersNotSpaceFacet(std::cin.getloc()));
    std::cin.imbue(olns);


    std::cout << "Count of word 'a' or 'A': "
              << std::count_if(std::istream_iterator<std::string>(std::cin),
                               std::istream_iterator<std::string>(),
                               [](std::string const& word)
                               {
                                    return word == "a" || word == "A";
                               }
                              );
}
// Note some systems have a bug in the standard where imbue on std::cin
// silently fails. If this is the case then convert the code to read from a file.
// Note you need to imbue the filestream `before` opening it.
\$\endgroup\$
  • \$\begingroup\$ In the previous round there was a question on merging two sorted arrays...If I had used STL then it takes 1 or two lines...but..i felt they are actually trying to test the concepts... \$\endgroup\$ – Sekharan Natarajan Aug 16 '12 at 12:36
  • \$\begingroup\$ @SekharanNatarajan Then you should have asked if you could use STL. Personally I'm more impressed by proper library usage than ability to write a trivial low level algorithm (which, with c++11, is becoming an increasingly rare task in the real world) \$\endgroup\$ – David Aug 17 '12 at 12:50
  • \$\begingroup\$ True...but writing algorithm is what I believe they wanted to test on..Using an inbuilt algo is such cases makes the prob too easy rite???? \$\endgroup\$ – Sekharan Natarajan Aug 25 '12 at 10:36
  • \$\begingroup\$ @SekharanNatarajan: I doubt it. This problem is designed to see if you understand how the formatted input operators work. operator>> reads a word. Can you use it with algorithms (the built in ones) can you spot the inherent problem (punctuation). What are some simple solutions to those problems (strip punctuation manually or use a locale to strip automatically). \$\endgroup\$ – Martin York Aug 27 '12 at 6:14
3
\$\begingroup\$

... and those who didn't check for first and last words to be "A" were all selected

maybe they wrote a loop that didn't need to special case the first & last characters, and that was considered cleaner?

Is str.at(i) not good enough...?

std::basic_string::at does bounds checking. You either need this, in which case you've arguably written your loop condition poorly and should be prepared to handle a std::out_of_range exception, or you wrote the loop safely, don't need the bounds checking, and needn't pay for it.

Because you might fail the bounds checking here, but don't handle the exception, your program will just terminate for some valid input strings.

I know even if we use str[i] it is interpreted as str.operator, so I'm preventing the overhead conversion, right?

what conversion? this is syntactic sugar resolved at compile time. You're either calling

str.at[i] => std::basic_string<char>::at(int i)

or

str[i]    => std::basic_string<char>::operator[](int i)

the fact that one has a fancy-looking syntax doesn't affect the cost of calling it.

Actually, as I mentioned above, operator[] is cheaper because it doesn't do the bounds checking (which you don't handle correctly anyway).


Oh, and for completeness, a sample (untested) one-pass state machine that doesn't require special cases for the first and last characters:

class CountA
{
    int count_;
    enum { NewWord, PossibleMatch, NonMatch } state_;

    void next(char c)
    {
        if (isalnum(c)) { // assuming words are alphanumeric strings only
            switch (state_) {
            case NewWord: // first char of a new word
                state_ = (toupper(c) == 'A') ? PossibleMatch : NonMatch;
                break;
            case PossibleMatch:   // had "A", got "Ax"
                state_ = NonMatch;
            case NonMatch:      ; // just a non-match getting longer
            }
        } else {
            if (state_ == PossibleMatch) ++count_; // complete match!
            state_ = NewWord;
        }
    }
public:
    CountA() : count_(0), state_(NewWord) {}
    int count() const { return count_; }

    void scan(std::string const &str)
    {
        char const *p = str.c_str();
        do {
            next(*p);
        } while(*p++);
    }
};
\$\endgroup\$

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.