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