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


Engaged Employer


Add an Interview

Interview Question

Software Engineer Interview



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


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

Anonymous on


//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( == S.end() &&e.sides.find(st[indx]) != e.sides.end()) { S.insert(; if (IsWordConstructableFromDice(st, indx + 1, S, dice)) return true; S.erase(; } } 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.