Question

Language C++

// For an input string of words, find the most frequently occuring word. In case of ties, report any one of them.

// Your algorithm should be O(n) time where n is the number of words in the string

#include <iostream>

#include <vector>

#include <sstream>

using namespace std;

string findWord(vector<string>& tokens);

int main() {

string line = "Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the Galaxy lies a small unregarded yellow sun. Orbiting this at a distance of roughly ninety two million miles is an utterly insignificant little blue green planet whose ape descended life forms are so amazingly primitive that they still think digital watches are a pretty neat idea.";

// Convert string to a vector of words

char delimiter = ' ';

string token;

istringstream tokenStream(line);

vector<string> tokens;

while (getline(tokenStream, token, delimiter)) {

tokens.push_back(token);

}

cout << "The most frequently occuring word is: " << findWord(tokens) << endl;

}

string findWord(vector<string>& tokens) {

// Your code here

}

Answer 1

Please see the code below.

Explanation:

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>


using namespace std;

string findWord(vector<string>& tokens);
int main()
{
string line = "Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the Galaxy lies a small unregarded yellow sun. Orbiting this at a distance of roughly ninety two million miles is an utterly insignificant little blue green planet whose ape descended life forms are so amazingly primitive that they still think digital war\tches are a pretty neat idea";
  
//converting string to a vector of words
char delimiter = ' ';
string token;
istringstream tokenStream(line);
vector<string> tokens;
while(getline(tokenStream, token, delimiter)){
tokens.push_back(token);
}

cout<<"The most frequently occuring word is: "<< findWord(tokens)<<endl;

return 0;
}

string findWord(vector<string>& tokens){
  
// Declare two vectors
// one to store unique tokens and second to store tokens count
vector<string> uniqueTokens;
vector<int> tokensCount;

// Iterate through all the tokens
for (int i = 0; i < tokens.size(); i++) {
auto it = std::find(uniqueTokens.begin(), uniqueTokens.end(), tokens[i]);
// if the token not found in uniqueTokens
if (it == uniqueTokens.end()){
// Add the current token to uniqueTokens and add count as 1
uniqueTokens.push_back(tokens[i]);
tokensCount.push_back(1);
} else{
// token already exists, increase the count by 1
auto index = std::distance(uniqueTokens.begin(), it);
tokensCount[index] = tokensCount[index] + 1;
}
}

// find the most repeated words using count
int maxIndex = 0;
for (int i = 0; i < tokensCount.size(); i++) {
if(tokensCount[maxIndex] < tokensCount[i]){
maxIndex = i;
}
}

// return the corresponding word
return uniqueTokens[maxIndex];
}

sample output: