Cover image for Google
Logo
See All Photos
Best Places to Work 2022

Google

Engaged Employer

Google

Add an Interview

Interview Question

Software Engineer Interview

-

Google

Given a word of length n, and n six-sided dice with a character in each side, find out if this word is constructible by the set of given dice

Interview Answers

2 Answers

0

A recursive problem, np-hard, maintain a set of parameters for each subproblem.

Anonymous on

0

//recursive with backtracking might work struct dice { int id; setsides; dice(int i, sets) :id(i), sides(s) {} }; bool IsWordConstructableFromDice(string st, int indx, unordered_setS,const vector&dice) { if (indx >= st.length()) return true; for (auto e : dice) { if (S.find(e.id) == S.end() &&e.sides.find(st[indx]) != e.sides.end()) { S.insert(e.id); if (IsWordConstructableFromDice(st, indx + 1, S, dice)) return true; S.erase(e.id); } } return false; } bool IsWordConstructableFromDice(string st, vectordice) { return IsWordConstructableFromDice(st, 0, unordered_set{}, dice); } int _tmain(int argc, _TCHAR* argv[]) { bool bOk = IsWordConstructableFromDice("ABCDEF", vector {dice(0, set{'A', 'X', 'Y', 'Z', 'W', 'M'}), dice(2, set{'F', 'C', 'Y', 'Z', 'W', 'M'}), dice(4, set{'A', 'X', 'D', 'Z', 'W', 'M'}), dice(1, set{'B', 'X', 'Y', 'Z', 'W', 'M'}), dice(5, set{'E', 'F', 'Y', 'Z', 'W', 'M'}), dice(3, set{'A', 'X', 'F', 'Z', 'W', 'M'})}); }

Abe on

Add Answers or Comments

To comment on this, Sign In or Sign Up.

Google Careers

Cover image for Google

We strive to provide Googlers and their loved ones with a world-class benefits experience, focused on supporting their physical, financial,...More

  • Where we work
  • Building belonging
  • Flexibility at Google
  • Build your future
This is the employer's chance to tell you why you should work for them. The information provided is from their perspective.