Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
can the question be clarified? what exactly is the input, an array of strings? and what is the expected out, an array of strings?
This is the question from the interviewer, verbatim. I agree it is unclear and poorly worded. Presumably the interviewer was looking for clarifying questions which I, unfortunately, did not ask much of. I assumed this was simply testing for length and looking it up in a HashSet which was apparently wrong. So part of this question involves interpreting the requirements.
prolly implementation of a hashmap is wat the interviewer was getting at acc to the operations insert and get...
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<fstream>
#include<map>
using namespace std;
// Use quick sort to sort the strings.
void quicksort(string& str, int low, int high) {
char pivot = str[(low+high)/2];
int i = low;
int j = high;
while (i <= j) {
while (str[j] > pivot)
j--;
while(str[i] < pivot)
i++;
if(i <= j) {
char temp;
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}
if (j > low)
quicksort(str, low, j);
if (i < high)
quicksort(str,i,high);
}
// Longest match algotithm.
void longestmatch(map<string,string>& mymap) {
string matcher("aeffgirq");
vector<string> final_list;
map<string,string>::iterator it;
for (it = mymap.begin(); it != mymap.end(); ++it) {
string str = it->second;
int i = 0;
int j = 0;
bool is_match = false;
while(true) {
if((i == matcher.length()) && (j < str.length()))
break;
if (matcher[i] == str[j]) {
i++;
j++;
} else {
i++;
}
if (j == str.length()) {
is_match = true;
break;
}
}
if (is_match) {
string first = it->first;
final_list.push_back(first);
}
}
// Iterator over the final list of all the words that
// match our criterion and then print the one with
// highest length
vector<string>::iterator it1;
int maxlength = 0;
string final_string;
for(it1 = final_list.begin();it1 != final_list.end();++it1) {
string tmp = *it1;
int length = tmp.length();
if (length > maxlength) {
final_string.replace(final_string.begin(), final_string.end(), tmp);
}
}
cout << "The longest string:" << final_string << '\n';
}
int main() {
vector<string> list;
ifstream in_stream;
string line;
in_stream.open("file.txt");
map<string,string> my_map;
// Read the words into a vector
while(in_stream.is_open())
{
while (in_stream.good()) {
getline(in_stream, line);
list.push_back(line);
}
in_stream.close();
}
// Sort the words in the vector and put the sorted
// words in a map with their keys as original words.
vector<string>::iterator it;
for (it=list.begin();it!=list.end(); ++it) {
string str = *it;
string sorted_str = *it;
int length = str.length();
quicksort(sorted_str,0,length-1);
my_map[str] = sorted_str;
}
// Clear this memory. No use now.
list.clear();
// Get the longest match.
longestmatch(my_map);
// clear the map
my_map.clear();
}
Write a method to get the next string in the alphabetic order from the current string:
From here it is simple, start with first 6-letters string "aaaaaa" and then keep generating strings using the above method and check if they are valid using isValid(s). If yes, print them, else do not print.
- HauntedGhost March 10, 2013