Google Interview Question: There are a set of dictionary... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate)

There are a set of dictionary words and a set of license

  plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the characters in the license plate, irrespective of the order of characters. Ex: RC101 is the license plate number. The shortest word that can be found in the dictionary is CAR which has characters 'R' and 'C' in the license plate.

Interview Answer

1 Answer


bool my_function(const std::string & s1 , const std::string & s2)
  return s1.length() find_matching_words(char* text, int i, int j , int max_len, std:\
:vector & dictionary)
  if(i==max_len) return dictionary;
  std::cout tempVec;
  for(std::vector:: iterator vIt = dictionary.begin();
      vIt !=dictionary.end();++vIt)
      if(vIt->find(text[i]) != std::string::npos)
          //count the matched characters
  //no match so return
  if(i==max_len && j == 0) return tempVec;
   if(tempVec.size() == 0) return find_matching_words(text,i,j,max_len,dictionary);
     return find_matching_words(text,i,j,max_len,tempVec);

int main()
 std::vector dictionary;
  std::vector words = find_matching_words("rc101", 0,0,5,dictionary);
  if(words.size()>0) std::cout<<" Matched Word "<

Dead_right on May 19, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.