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\$
6
  • 1
    \$\begingroup\$ What version of C++ are you using? I'm not familiar with the included statement. \$\endgroup\$
    – Kevin
    Aug 15, 2012 at 18:17
  • 2
    \$\begingroup\$ One problem I see is: what happens if your input string is just 'A'? \$\endgroup\$
    – rpsml
    Aug 15, 2012 at 18:19
  • \$\begingroup\$ "a" & 'a' are different, 'a' is a single character whereas "a" is a string i.e. 'a','\0' \$\endgroup\$ Aug 15, 2012 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, 2012 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\$ Aug 15, 2012 at 19:01

5 Answers 5

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
  • 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\$ Jul 24, 2018 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\$
3
  • \$\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, 2012 at 19:01
  • 2
    \$\begingroup\$ Unfortunately this fails if there is punctuation in the input stream. \$\endgroup\$ Aug 15, 2012 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, 2012 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\$
3
  • \$\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, 2012 at 18:41
  • \$\begingroup\$ @GManNickG: White board sure. In sample code sent for interview not so much. It must compile. \$\endgroup\$ Aug 15, 2012 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\$ Aug 16, 2012 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\$
4
  • \$\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\$ Aug 16, 2012 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, 2012 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\$ Aug 25, 2012 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\$ Aug 27, 2012 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\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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