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.
Answer

Interview Answer

1 Answer

0

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)
        {
          tempVec.push_back(*vIt);
          //count the matched characters
          j++;
        }
    }
  i++;
  //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;
  dictionary.push_back("cccaar");
  dictionary.push_back("car");
  dictionary.push_back("bus");
  dictionary.push_back("baby");
  dictionary.push_back("cat");
  std::vector words = find_matching_words("rc101", 0,0,5,dictionary);
  std::sort(words.begin(),words.end(),my_function);
  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.