Amazon Interview Question Software Engineer in Tests
generate all combinations of the string and check against a dictionary if a given combination is a valid word and keep a count. Off course the dictionary should be provided and it can be in a hash table format so that the lookup is constant time.
// company_project.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <set>
#include <string>
#include <list>
#include <iostream>
#include <sstream>
#include <map>
// algorithm 1
unsigned int numUniqueElements(std::string &s) {
std::map< std::string, bool > stringPresenceMap;
std::istringstream originalStringStream(s);
std::string word;
unsigned int count = 0;
while (originalStringStream >> word) {
if (stringPresenceMap.find(word) == stringPresenceMap.end()) {
stringPresenceMap[word]= true;
count++;
}
}
return count;
}
// test 1
void test1() {
std::string str1("This is goog goog good good");
std::cout << str1 << std::endl << numUniqueElements(str1);
str1.assign("donkey donkey donkey");
std::cout << str1 << std::endl << numUniqueElements(str1);
str1.assign("");
std::cout << str1 << std::endl << numUniqueElements(str1);
str1.assign("yahoo google yahoo google microsoft microsoft");
std::cout << str1 << std::endl << numUniqueElements(str1);
}
int _tmain(int argc, _TCHAR* argv[])
{
test1();
return 0;
}
answers from Anonymous and hugh are just BS.
the first 2 answers sounds simple and pragmatic..
The question is asking for the number of unique words, but your answer seems that you already know these words "use a Hashset and add all words". How did you identify these unique words from the given string?
HashSet cannot have duplicate elements. Therefore when you add all the words in the string(could be duplicate), only unique words will be inserted. Hence size of the HashSet will be the answer.
int uniqueWords(String input)
{
Set<String> hs = new HashSet<String>();
String[] strings = input.split("");
for(String x: strings){
hs.add(x);
}
return hs.size();
}
String in = "this is not madness this is sparta";
StringTokenizer st = new StringTokenizer(in);
Hashtable<String, Integer> h = new Hashtable<String, Integer>();
int count = 1;
while(st.hasMoreTokens()){
String s = st.nextToken();
if(!h.contains(s)){
h.put(s, count);
}
}
System.out.println(h.size());
- knap August 12, 2009