Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

Write a method to get the next string in the alphabetic order from the current string:

string next(string s){
    int idx = s.size()-1;
    s[idx]++;
    
    while(s[idx] > 'z'){
        s[idx] = 'a';
        idx--;
        
        if(idx == -1)
            return 'a' + s;
        else 
            s[idx]++;
    }
    return s;
}

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i am not sure about this but i think that the input gives you the list of words..why do you want to generate words?

- alex March 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can the question be clarified? what exactly is the input, an array of strings? and what is the expected out, an array of strings?

- Anonymous March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- DJ March 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

DJ!!! ALWAYS... ASK... QUESTIONS

Good luck on your next job interview.

- Barry Fruitman March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

yes, the question is in't clear. Plz elaborate.

- LAP March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

prolly implementation of a hashmap is wat the interviewer was getting at acc to the operations insert and get...

- bbarodia March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This Question is not clear, what he expecting ?

- Shrikant March 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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();
}

- NBob March 21, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More