Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
Hey, I have worked around this problem to some extent and below is the code.
I am reading the strings from the files.
comment in your questions with respect to the code.
#include <iostream>
#include <list>
#include <map>
#include<algorithm>
#include<sstream>
#include<fstream>
using namespace std;
string Hash(string);
int main()
{
list<string> words;
map<string,int> dictionary;
//Hash("candy");
//dictionary has values of hash strings assigned to 0;
dictionary["c3y"] =0;
dictionary["d3y"] = 0;
dictionary["a5y"] = 0;
ifstream inputfile;
inputfile.open("inputStringList.txt");
string str;
while(getline(inputfile,str))
{
string hashvalue = Hash(str);
if(dictionary.find(hashvalue) != dictionary.end()){
cout<<str<<" is not a unique string"<<endl;
dictionary.find(hashvalue)->second++;
}else{
cout<<str<<" is a unique string"<<endl;
dictionary[hashvalue] =0;
}
}
inputfile.close();
return 0;
}
string Hash(string str)
{
int len = str.length();
int hashLen = len-2;
string hashValue ="";
hashValue+= str[0];
ostringstream convert;
convert<<hashLen;
hashValue+=convert.str();
hashValue+=str[len-1];
return hashValue;
}
I guess that's it:
public class WordDict{
private HashMap<String, List<String>> dict;
public WordDict(){
this.dict = new HashMap<>();
}
public static void main(String[] args){
WordDict wordDict = new WordDict();
wordDict.load(new String[]{"candy", "carry", "dummy"});
}
public void load(String[] words){
for(String word : words){
String key = generateKey(word);
if(!dict.containsKey(key)){
dict.put(key, new ArrayList<>());
}
dict.get(key).add(word);
}
}
private String generateKey(String word){
return word.substring(0, 1) + (word.length() - 2) + word.substring(word.length() - 1, word.length());
}
public Boolean isUnique(String word){
Boolean unique = false;
String key = generateKey(word);
if(!dict.containsKey(key)){
System.out.println("word not found in dictionary");
}
else{
unique = dict.get(key).size() > 1;
}
return unique;
}
}
Solution in Objective-C
@interface WordDict:NSObject {
NSMutableDictionary *wordDict;
}
-(void) loadWithWords:(NSArray *) words;
-(NSString *) hashedWord:(NSString *) word;
-(BOOL) isUnique:(NSString *) word;
-(void) printDict;
@end
@implementation WordDict
-(id) init {
if (self = [super init]) {
wordDict = [NSMutableDictionary new];
}
return self;
}
-(void) loadWithWords:(NSArray *) words {
for (NSString *s in words) {
NSString *key = [self hashedWord:s];
NSMutableArray *similarWords = [wordDict objectForKey:key];
if (similarWords) {
[similarWords addObject:s];
} else {
NSMutableArray *sameHashWords = [NSMutableArray new];
[sameHashWords addObject:s];
[wordDict setObject:sameHashWords forKey:key];
}
}
}
-(NSString *) hashedWord:(NSString *) word {
if (word && word.length > 3) {
return [NSString stringWithFormat:@"%@%lu%@", [word substringWithRange:NSMakeRange(0, 1)], word.length - 2,
[word substringWithRange:NSMakeRange(word.length-1, 1)]];
}
return @"[Not Valid Entry]";
}
-(void) printDict {
for (NSString *word in wordDict) {
NSLog(@"word = (%@", word);
for (NSString *entry in [wordDict objectForKey:word]) {
NSLog(@" %@,", entry);
}
NSLog(@")");
}
}
-(BOOL) isUnique:(NSString *) word {
NSArray *similarWords = [wordDict objectForKey:[self hashedWord:word]];
if (similarWords == nil) {
NSLog(@"word not found");
return NO;
} else {
return (similarWords.count == 1);
}
}
@end
int main (int argc, const char * argv[])
{
@autoreleasepool {
NSArray<NSString*> *words = @[@"candy", @"carry", @"dummy"];
WordDict *wordDict = [WordDict new];
[wordDict loadWithWords:words];
// [wordDict printDict];
NSLog(@"cattering is unique %i", [wordDict isUnique:@"cattering"]);
NSLog(@"candy is unique %i", [wordDict isUnique:@"candy"]);
NSLog(@"dummy is unique %i", [wordDict isUnique:@"dummy"]);
}
}
}
Objective-C solution:
@interface WordDict:NSObject {
NSMutableDictionary *wordDict;
}
-(void) loadWithWords:(NSArray *) words;
-(NSString *) hashedWord:(NSString *) word;
-(BOOL) isUnique:(NSString *) word;
-(void) printDict;
@end
@implementation WordDict
-(id) init {
if (self = [super init]) {
wordDict = [NSMutableDictionary new];
}
return self;
}
-(void) loadWithWords:(NSArray *) words {
for (NSString *s in words) {
NSString *key = [self hashedWord:s];
NSMutableArray *similarWords = [wordDict objectForKey:key];
if (similarWords) {
[similarWords addObject:s];
} else {
NSMutableArray *sameHashWords = [NSMutableArray new];
[sameHashWords addObject:s];
[wordDict setObject:sameHashWords forKey:key];
}
}
}
-(NSString *) hashedWord:(NSString *) word {
if (word && word.length > 3) {
return [NSString stringWithFormat:@"%@%lu%@", [word substringWithRange:NSMakeRange(0, 1)], word.length - 2,
[word substringWithRange:NSMakeRange(word.length-1, 1)]];
}
return @"[Not Valid Entry]";
}
-(void) printDict {
for (NSString *word in wordDict) {
NSLog(@"word = (%@", word);
for (NSString *entry in [wordDict objectForKey:word]) {
NSLog(@" %@,", entry);
}
NSLog(@")");
}
}
-(BOOL) isUnique:(NSString *) word {
NSArray *similarWords = [wordDict objectForKey:[self hashedWord:word]];
if (similarWords == nil) {
NSLog(@"word not found");
return NO;
} else {
return (similarWords.count == 1);
}
}
@end
int main (int argc, const char * argv[])
{
@autoreleasepool {
NSArray<NSString*> *words = @[@"candy", @"carry", @"dummy"];
WordDict *wordDict = [WordDict new];
[wordDict loadWithWords:words];
// [wordDict printDict];
NSLog(@"cattering is unique %i", [wordDict isUnique:@"cattering"]);
NSLog(@"candy is unique %i", [wordDict isUnique:@"candy"]);
NSLog(@"dummy is unique %i", [wordDict isUnique:@"dummy"]);
}
}
Here is another Java implementation:
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Properties;
// Insertion is O(1) per word or O(n) where n is the number of words to add to dict
// Lookup is O(1) per word or O(n) for n words
// Conversion is O(1) per word or O(n) where n is the number of words to convert
// Loads the strings from a dictionary.properties file
// TODO: use a set here for cleaner code. Used a Map since I am rusty with Java and trying to code this from memory
public class Dict {
Properties map = new Properties();
static boolean DEBUG = true;
public static final String PROPERTIES_FILE_NAME = "dictionary.properties";
// Main method used to test Dict.
// - Adds carry, candy, dummy to the PROPERTIES_FILE_NAME file,
// - then loads the file
// - then calls isUniqueDictionaryWord() on a few test words
public static void main(String[] args) throws IOException {
Dict dict = new Dict();
// If there are no values, create some for testing
if(DEBUG) {
dict.add("carry");
dict.add("candy");
dict.add("dummy");
dict.store(PROPERTIES_FILE_NAME);
}
// Load initial values
dict.load(PROPERTIES_FILE_NAME);
for(String word: new String[] {"dandy", "diddly", "dancing", "domes"}) {
System.out.printf("%s is %sin dict\n",word, dict.isUniqueDictionaryWord(word) ? "" : "not ");
}
}
public void load(String fileName) throws FileNotFoundException, IOException {
map.load(new FileReader(fileName));
}
public void store(String fileName) throws IOException {
map.store(new FileWriter(fileName), "Dictionary for Dict.java");
}
// Convert words 3 or longer to CxC => first character+ (length-2) +last character
private String getConvertedWord(String word) {
String newWord = "";
if(word == null || word.length() == 0)
newWord = "";
else if(word.length() < 3)
newWord = word;
else
newWord = ""+word.charAt(0) + (word.length() - 2) + word.charAt(word.length() - 1);
if(DEBUG)
System.out.printf("Converted %s to %s\n", word, newWord);
return newWord;
}
public void add(String word) {
map.put(getConvertedWord(word), "");
}
public boolean isUniqueDictionaryWord(String word) {
String newWord = getConvertedWord(word);
return map.containsKey(newWord);
}
}
// add the strings at the key place of hash table so code will throw exception when the key is duplicate
static void Main(string[] args)
{
List<string> words = new List<string>();
words.Add("Samah");
words.Add("Ali");
words.Add("Mohamed");
words.Add("rose");
words.Add("samah");
bool checkunique = checkIfUniqueValue(words, "samah");
}
public static bool checkIfUniqueValue(List<string> words, string uniqueWordToCheck)
{
Hashtable hT = new Hashtable();
foreach (string word in words)
{
try
{
hT.Add(word.ToUpper (), words.IndexOf(word));
}
catch
{
if (word.ToUpper () == uniqueWordToCheck.ToUpper () )
{
return false;
}
}
}
return true;
}
I guess you asked some follow up questions right? For example, in the first version of the problem, are the strings in a list? a dictionary? Could you please share them as well?
- Jorge April 15, 2016