License Plate & Dictionary

来源：Meetqun,一亩三分地, Google Phone Interview

原帖：http://www.meetqun.com/thread-2802-1-1.html
            http://www.meetqun.com/forum.php?mod=viewthread&tid=4901&ctid=41

题目：

“AC1234R” => CAR, ARC | CART, CARED not the shortest

“OR4567S” => SORT, SORE | SORTED valid, not the shortest | OR is not valid, missing S

Google电面题目: 04/13/2015

1 <= letters <= 7

O(100) license plate lookups

O(4M) words in the dictionary

d1 = abc   000....111

d2 = bcd   000…..110

s1 = ac1234r  00001...101

s1 & d1 == s1 d1

s1 & d2 != s1

代码：

 int convert2Num(string s) {   
     int res = 0;   
     for (int i = 0; i < s.size(); ++i) {   
         if (!isdigit(s[i]) {   
             res |= 1 << (s[i] - ‘a’);    
         }   
     }   
     return res;   
 }   
   
 string find_shortest_word(string license, vector<string> words) {   
     int lis_num = convert2Num(license);   
     string res;    
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]); // conversion;    
         if (lis_num & word_num == lis_num) {   
             if (res.empty() || res.size() > words[i].size())   
                 res = words[i]; // brute force; 可以sorting来减少比较次数   
         }   
     }   
     return res;   
 }  

<key, conversion number》

<words, save shortest length of words>

abc, abccc,   <000...111, abc>   

Follow up:
dictionary = { “BAZ”, “FIZZ”, “BUZZ” } | BAZ only has one Z

vector<int> map(26, 0);

a -> 0,   z -> 25;

map[s-’a’]++;

need[26];

need[i] < map[i]

代码：

 bool compare(const string& s1, const string& s2) {   
     return s1.size() < s2.size();   
 }    
   
 string find_shortest_string(string license, vector<string> words) {   
     sort(word.begin(), word.end(), compare);   
     int lic_num = convert2Num(license);   
     vector<int> map(26, 0);   
     for (auto i : license) {   
         if (!isdigit(i)) map[i-’a’]++;   
     }   
   
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]);   
         // First check that it has all the letters, then check the counts   
         if (lic_num & word_num != lic_num) continue;   
   
         vector<int> word_map(26, 0);   
         for (auto k : words[i]) {   
             if (!isdigit(k)) map[k-’a’]++;   
         }    
         int j = 0;   
         for (; j < 26; ++j) {   
             if (word_map[‘a’+j] < map[‘a’+j]) break;   
         }   
         if (j == 26) return words[i];   
     }   
 }    

Follow up:

find_shortest_word(“12345ZZ”, dictionary) 50% => “FIZZ” | 50% => “BUZZ”

vector<string> s = {};

s[rand() % 2];

reservoir sampling;

FIZZ: s = words;

count = 1;

BUZZ: count++; count = 2;

rand() % count == 0 : s = BUZZ;