HELP You are a software engineer at Pear, a mobile phone company. You\'ve been a
ID: 3709567 • Letter: H
Question
HELP
You are a software engineer at Pear, a mobile phone company. You've been asked to implement the "autocomplete" feature of PearOS. Autocomplete suggests how a partially typed word might be completed into a word from a list, e.g. a dictionary. Because the data might depend upon the user and what words they use most commonly, adding words to the list must be permitted. To keep up with your users’ typing, your code must give suggestions extremely fast (?(log n) time). However, changing the list via adding words is allowed to be slow (?(n) time). A dynamic array of sorted words that uses binary search to find suggestions would work.
Create a new C++ souce filed name autocompleter.cpp that implements the class declared in autocompleter.h, so that autocompleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file autocompleter.cpp.
The following files have been given to you:
HEADER FILE - AUTOCOMPLETER.H
SOURCE FILE - MAIN.CPP
TEXT FILE - WORDS.TXT
///// AUTOCOMPLETER.H /////
///// MAIN.CPP /////
///// WORDS.TXT /////
the of and to a in for is on that by this with I you it not or be are from at as your all have new more an was we will home can us about if page my has search free but our one other do no information time they site he up may what which their news out use any there see only so his when contact here business who web also now help work last most products music buy data make them should product system post her city t add policy number such please available copyright support message after best software then jan good video well d where info rights public books high school through m each links she review years order very privacy book items company r read group sex need many user said de does set under general research university january mail full map reviews program life know games way days management must store travel comments made development report off member details line terms before hotels did send right type because local those using results office education national car design take posted internet address community within states area want phone dvd shipping reserved subject between forum family l long based w code show o even black check special prices website index being women much sign file link open today technology south case project same pages uk version section own found sports house related security both g county american photo game members power while care network paxil spine trout enclosed feat temporarily ntsc cooked thriller transmit apnic fatty pressed frequencies scanned reflections hunger mariah sic municipality usps joyce detective surgeon cement experiencing fireplace endorsement bg planners disputes textiles missile intranet closes seq psychiatry persistent conf marco assists summaries glow gabriel auditor wma aquarium violin prophet cir bracket oxide oaks magnificent erik colleague naples promptly modems adaptation hu harmful paintball prozac sexually enclosure acm dividend newark kw paso glucose phantom norm playback supervisors turtle ips distances absorption treasures dsc warned neural ware fossil mia hometown badly transcripts apollo wan disappointed persian continually communist collectible handmade greene entrepreneurs robots grenada creations jade scoop acquisitions foul keno gtk earning mailman sanyo nested biodiversity excitement somalia movers verbal blink presently seas carlo workflow mysterious novelty impose organisms sega telescope viewers asbestos enters pod savage advancement wu harassment willow resumes bolt gage throwing existed generators lu wagon barbie dat soa knock urge smtp generates potatoes thorough replication inexpensive kurt receptors peers optimum neon interventions quilt huntington creature ours mounts syracuse internship lone refresh snowboard webcast michel evanescence subtle coordinated notre shipments maldives stripes firmware cope shepherd lm cradle chancellor mambo lime kirk flour controversy legendary bool sympathy choir avoiding beautifully blond expects cho jumping fabrics antibodies polymer hygiene wit poultry virtue burst examinations surgeons bouquet immunology promotes mandate wiley departmental bbs spas ind corpus terminology gentleman fibre reproduce convicted shades jets indices roommates adware qui intl threatening daisy mating compute redhead arrives translator automobiles tractor allah continent ob unwrap fares longitude resist challenged hoped pike safer insertion instrumentation constraint groundwater touched strengthening cologne gzip wishing ranger smallest insulation newman marsh ricky ctrl scared theta infringement bent subjective monsters asylum stake cocktail outlets varieties arbor mediawiki configurations poison
This text file actually has 10,000 words in the English dictionary. I'll only put 500 to not be so obnoxious with this questions. Please leave any comments if possible. TIA!!!
Explanation / Answer
#include <iostream>
#include <string>
#include "autocompleter.h"
using namespace std;
int binarySearch(string* arr, int l, int r, string x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
void getLexicographicOrder(string* arr)
{
string temp;
for (int i = 0; i < 9; ++i)
{
for (int j = i + 1; j < 10; ++j)
{
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int Autocompleter::index_of(string x, string* A, int n)
{
int found = binarySearch(A, 0, count, x);
if (found != -1)
{
return found;
}
else
{
return count;
}
}
Autocompleter::Autocompleter()
{
string arr[10000];
A = arr;
count = 0;
capacity = 0;
}
void Autocompleter::insert(string x)
{
for (int i = 0; i < Autocompleter::size(); i++)
{
if (x == A[i])
{
return;
}
}
A[count] = x;
count++;
}
int Autocompleter::size()
{
return count;
}
int Autocompleter::completion_count(string x)
{
int total_found = 0;
for (int j = 0; j < count; j++)
{
if (A[j].find(x) == 0)
{
total_found++;
}
}
return total_found;
}
void Autocompleter::completions(string x, string* suggestions)
{
int total_found = 0;
getLexicographicOrder(A);
for (int j = 0; j < count; j++)
{
if (A[j].find(x) == 0)
{
suggestions[total_found] = A[j];
total_found++;
if (total_found == 5)
{
break;
}
}
}
if (total_found < 5)
{
for (int i = total_found; i < 5; i++)
{
suggestions[i] = "";
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.