5
\$\begingroup\$

It is a 1.5 hour coding test, started the moment when the question was sent by email. My solution was done under the strict condition. I was not told anything before the test.

The question is about counting word occurrence in natural language processing. Paraphrased, it asks:

Given an input document and a range k (with 1 ≤ k ≤ 5), calculate all cooccurrence probabilities for various pairs of words A and B:

$$ p(A, B, k) = \frac{\textit{cooccurrence(A, B, k)}}{\textit{count}(A)} $$

In other words, out of every time the word A appears, what is the probability that B appears within ±k words?

My solution in C++ is below. I think I could do better in my attempt. What are the areas that I should prepare & learn? I failed to come up with a better data structure under the exam condition.

During the test, I briefly tried stack but later found out I couldn't iterate all elements without changing the data structure. That wasted my time and I wonder if a stack can be used?

#include <set>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <boost/algorithm/string/predicate.hpp>

int main(int argc, char* argv[])
{
    const auto file = argv[0];
    const auto K = atoi(argv[1]);

    std::string line;

    // Mapping for coocurrence
    std::map<std::pair<std::string, std::string>, unsigned> coo;

    std::map<std::string, unsigned> count;

    // History of the last K words
    std::vector<std::string> hist;

    std::ifstream ss(file);

    while (std::getline(ss, line))
    {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

        for (auto &tok : toks)
        {
            boost::replace_all(tok, ",", "");
            boost::replace_all(tok, ".", "");
            boost::replace_all(tok, "!", "");
            std::transform(tok.begin(), tok.end(), tok.begin(), ::tolower);

            if (tok == "\t" || tok == "," || tok == "")
            {
                continue;
            }

            // Required for dennominator
            count[tok]++;

            std::set<std::string> known;

            // Checking the last K history
            for (auto &i : hist)
            {
                if (!known.count(i))
                {
                    coo[std::pair<std::string, std::string>(tok, i)]++;
                    //coo[std::pair<std::string, std::string>(i, tok)]++;
                }

                known.insert(i);
            }

            if (hist.size() != K)
            {
                hist.push_back(tok);
            }
            else
            {
                /*
                 * Reconstruct the history of recent words
                 */

                for (auto i = 0; i < hist.size()-1; i++)
                {
                    hist[i] = hist[i+1];
                }

                hist[hist.size()-1] = tok;
            }
        }
    }

    std::vector<std::string> toks;
    boost::split(toks, line, boost::is_any_of(" "));

    for (std::string line; std::getline(std::cin, line);)
    {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

        std::string x1 = toks[0];
        std::string y1 = toks[1];
        std::transform(x1.begin(), x1.end(), x1.begin(), ::tolower);
        std::transform(y1.begin(), y1.end(), y1.begin(), ::tolower);

        if (!count.count(x1))
        {
            return 0;
        }

        const auto den = count.at(x1);
        auto num1 = coo.count(std::pair<std::string, std::string>(x1, y1)) ? coo.at(std::pair<std::string, std::string>(x1, y1)) : 0;
        auto num2 = coo.count(std::pair<std::string, std::string>(y1, x1)) ? coo.at(std::pair<std::string, std::string>(y1, x1)) : 0;

        if (x1 == y1)
        {
            num1++;
            num2++;
        }

        std::cout << (double)(std::max(num1, num2)) / den << std::endl;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The task quoted said various pairs of words A and B, you seem to be handling each and every pair. (I'd probably claim the task insufficiently specified, associate ordinals with "each" word and wait for queries…) \$\endgroup\$ – greybeard Sep 7 '16 at 7:14
  • \$\begingroup\$ @greybeard I think the question is asking about each and every pair within the K distance. \$\endgroup\$ – SmallChess Sep 7 '16 at 7:14
1
\$\begingroup\$

You have used a std::vector<std::string> for hist, a history of the last K words. To limit that vector to size K, you shift the words over like this:

    if (hist.size() != K)
    {
        hist.push_back(tok);
    }
    else
    {
        /*
         * Reconstruct the history of recent words
         */

        for (auto i = 0; i < hist.size()-1; i++)
        {
            hist[i] = hist[i+1];
        }

        hist[hist.size()-1] = tok;
    }

But that loop is essentially doing erase() on the first element — and, as you can see, it's an inefficient O(K) operation on a vector.

A std::deque would be an improvement:

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. … As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

That non-contiguous caveat is a bit of a disappointment, though. Since you want a bounded-size buffer where adding an entry at the end causes the first entry to drop out, the data structure that you really want is a . As luck would have it, Boost has a circular buffer.

\$\endgroup\$
1
\$\begingroup\$
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <boost/algorithm/string/predicate.hpp>

Each file should be self-sufficient by including the specific header a symbol relies on. You forgot to remove the <sstream> and <stack> artifacts. You are missing:

#include <algorithm>  // std::transform
#include <cstdlib>    // std::atoi
#include <string>     // std::string<>
#include <utility>    // std::pair<>

Prefer to organize your headers in logical groups. A common logical ordering would be by ascending hardiness. Code that isn't as rigorously tested is processed before other libraries that are better tested.

When searching a list of includes, binary search is faster than linear search. so prefer to order lexicographically.

#include "class.h"            // Prototype/Interface

#include "range/algorithm.h"  // Project-Level libraries
#include "utils/string.h"

#include <boost/algorithm/string.hpp>  // Third-Party Libraries
#include <boost/algorithm/string/predicate.hpp>

#include <algorithm>          // Standard Library
#include <cstdlib>
// ...
#include <vector>

int main(int argc, char* argv[]) {
    const auto file = argv[0];
    const auto K = atoi(argv[1]);

Always check argc before accessing argv. argc is only guaranteed by the standard to be non-negative, not non-zero. argv[0] is also special.

3.6.1 Main function [basic.start.main]

\$^2\$ ... If argc is nonzero these arguments shall be supplied in argv[0] through argv[argc-1] as pointers to the initial characters of null-terminated multibyte strings (NTMBSs) (17.5.2.1.4.2) and argv[0] shall be the pointer to the initial character of a NTMBS that represents the name used to invoke the program or "".


    // Mapping for coocurrence
    std::map<std::pair<std::string, std::string>, unsigned> coo;

Don't say in comments what can be stated in code. Keep code-related comments minimal and crisp. When something is important and not obvious (unusual/obscure code), clarify through a comment.

Don't pay for what you don't use. Unless you require that keys be sorted at all times, prefer using std::unordered_[map|set].


    std::ifstream ss(file);

Give variables appropriate names. ss doesn't give the reader an idea of what the variable is holding.


    while (std::getline(ss, line)) {
        std::vector<std::string> toks;
        boost::split(toks, line, boost::is_any_of(" "));

std::string::operator>> already delimits on whitespace.


        boost::replace_all(tok, ",", "");
        boost::replace_all(tok, ".", "");
        boost::replace_all(tok, "!", "");

This is probably not the intended purpose of boost::replace_all as copies and buffers are used in the background to handle resizing. You could just use the erase-remove idiom.

        auto is_nonalpha = std::not1(std::fun_ptr(std::isalpha));
        tok.erase(std::remove_if(tok.begin(), tok.end(), is_nonalpha), tok.end());

C++17 will introduce uniform container erasure.

        std::erase_if(tok, is_nonalpha);

            for (auto i = 0; i < hist.size()-1; i++) {
                hist[i] = hist[i+1];
            }

            hist[hist.size()-1] = tok;

Prefer to use standard algorithms as they may afford you optimizations.

            std::copy(std::next(hist.begin()), hist.end(), hist.begin());
            hist.back() = tok;

Rather than paying the cost of cycling, consider using a Circular container adaptor.


    if (!count.count(x1)) {
        return 0;
    }

Are you sure you want to exit if a word doesn't appear in the corpus? This doesn't seem like a case where termination is necessary.


    std::cout << (double)(std::max(num1, num2)) / den << std::endl;

std::endl outputs '\n' and flushes the stream. If you did not intend to flush the stream, just output '\n'.


My solution in C++ is below. I think I could do better in my attempt. What are the areas that I should prepare & learn? I failed to come up with a better data structure under the exam condition.

Seems like you already know where you should be looking.

During the test, I briefly tried stack but later found out I couldn't iterate all elements without changing the data structure. That wasted my time and I wonder if a stack can be used?

You can write a non-owning read-only adaptor. The underlying container is a protected data member of the Standard Library container adaptors.

\$\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.