Adap.tv Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
suggestion:
1. build a tries on the dictionary
2. create a small map . Key: int, values char[] eg: (2,new char[]{'a','b','c'})
3. do a search on tries based on the input number
I do like this: making a map array, which record all the alphas and digits relations. Then open file, and process every word with length of the length of given number, ignore others which can save a lot of time. below is my codes, time complexity is O(N), if the length of word can be taken as O(1), space complexity is O(1).
#include<iostream>
#include<string>
using namespace std;
int map[26];
void init_map() {
int i;
int value = 2;
for(i = 0; i < 15; i += 3) {
map[i] = map[i + 1] = map[i + 2] = value;
value++;
}
map[15] = map[16] = map[17] = map[18] = value++;
map[19] = map[20] = map[21] = value++;
map[22] = map[23] = map[24] = map[25] = value;
}
bool process_word(char *word, char *number) {
while(*word) {
if(map[*word - 'a'] != (*number - '0')) {
return false;
}
word++;
number++;
}
return true;
}
void find_all_valid_words(char *file_path, char *number) {
char buffer[20];
int len_num = strlen(number);
FILE *input = fopen(file_path, "r");
init_map();
while(fscanf(input, "%s", buffer) != EOF) {
if(strlen(buffer) == len_num) {
if(process_word(buffer, number)) {
cout << buffer << endl;
}
}
}
}
void main() {
char number[] = "228";
char file_path[] = "words.txt";
find_all_valid_words(file_path, number);
getchar();
}
and here the test case:
bat cat act bus cut just take make bad pass typical
HI,
I am apperaing for adaptv. Could you please provide some questions that were asked in the interviews?
Regards
hi pandu,
am to appearing for adap.tv can you please give me little context on what type of questions they are asking( it is even grateful if you list out other questions asked thanks)
- Anonymous January 22, 2013