Google Interview Question Software Engineers
Country: -
Interview Type: In-Person
public static boolean canMakeWord(String word, char[][] dice) {
HashMap<Character, List<Integer>> diceMap = new HashMap<>();
HashSet<Integer> availableDice = new HashSet<>();
for (int i = 0; i < dice.length; i++) {
for (char c : dice[i]) {
if (!diceMap.containsKey(c))
diceMap.put(c, new ArrayList<>());
diceMap.get(c).add(i);
}
availableDice.add(i);
}
return dfs(word, 0, availableDice, diceMap);
}
private static boolean dfs(String word, int index, HashSet<Integer> availableDice, HashMap<Character, List<Integer>> diceMap) {
if (index == word.length())
return true;
if (!diceMap.containsKey(word.charAt(index)))
return false;
for (int diceIndex : diceMap.get(word.charAt(index))) {
if (availableDice.contains(diceIndex)) {
availableDice.remove(diceIndex);
if (dfs(word, index + 1, availableDice, diceMap))
return true;
availableDice.add(diceIndex);
}
}
return false;
}
object test extends App {
val wordLength = 10 // no of dies
val dice = List("a", "b", "c", "d", "e", "f") // 6 characters
def roll(dice: List[String]): String = {
val r = scala.util.Random
dice(r.nextInt(dice.length))
}
def word(dice: List[String], n: Int): List[String] = {
val word = for (i <- 0 until n) yield roll(dice)
word.toList
}
println(word(dice, wordLength).mkString(""))
println(word(dice, wordLength).mkString(""))
println(word(dice, wordLength).mkString(""))
println(word(dice, wordLength).mkString(""))
println(word(dice, wordLength).mkString(""))
println(word(dice, wordLength).mkString(""))
}
public static boolean canMakeWord(String word, char[][] dice) {
HashMap<Character, List<Integer>> diceMap = new HashMap<>();
HashSet<Integer> availableDice = new HashSet<>();
for (int i = 0; i < dice.length; i++) {
for (char c : dice[i]) {
if (!diceMap.containsKey(c))
diceMap.put(c, new ArrayList<>());
diceMap.get(c).add(i);
}
availableDice.add(i);
}
return dfs(word, 0, availableDice, diceMap);
}
private static boolean dfs(String word, int index, HashSet<Integer> availableDice, HashMap<Character, List<Integer>> diceMap) {
if (index == word.length())
return true;
if (!diceMap.containsKey(word.charAt(index)))
return false;
for (int diceIndex : diceMap.get(word.charAt(index))) {
if (availableDice.contains(diceIndex)) {
availableDice.remove(diceIndex);
if (dfs(word, index + 1, availableDice, diceMap))
return true;
availableDice.add(diceIndex);
}
}
return false;
}
class Program
{
static void Main(string[] args)
{
// Given a six sided dice and an n length word, find out if a given word is constructable or not.
char[] die1 = new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
System.Diagnostics.Debug.Assert(CanMakeWord(die1, "abc"));
System.Diagnostics.Debug.Assert(CanMakeWord(die1, "abcdefg"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, "abcdefgj"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, "scooby"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, ""));
}
private static bool CanMakeWord(char[] dice, string word)
{
if (word == null || word.Length == 0 || word.Length > dice.Length)
return false;
return word.ToCharArray().All(x => dice.Contains(x));
}
class Program
{
static void Main(string[] args)
{
// Given a six sided dice and an n length word, find out if a given word is constructable or not.
char[] die1 = new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
System.Diagnostics.Debug.Assert(CanMakeWord(die1, "abc"));
System.Diagnostics.Debug.Assert(CanMakeWord(die1, "abcdefg"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, "abcdefgj"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, "scooby"));
System.Diagnostics.Debug.Assert(!CanMakeWord(die1, ""));
}
private static bool CanMakeWord(char[] dice, string word)
{
if (word == null || word.Length == 0 || word.Length > dice.Length)
return false;
return word.ToCharArray().All(x => dice.Contains(x));
}
Simple and clean backtracking approach
package Java;
import java.util.*;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 12/04/19
* Description:
*/
public class DiceWordProblem {
public static void main(String args[]) {
String word = "ybdb";
char dices[][] = {{'a', 'b', 'c', 'd', 'x', 'y'},
{'b', 'b', 'c', 'd', 'a', 'b'},
{'c', 'b', 'd', 'd', 'c', 'd'},
{'d', 'b', 'c', 'a', 'a', 'b'}};
System.out.println(isPossible(word, dices));
}
private static boolean isPossible(String word, char[][] dices) {
if (word == null)
return dices == null;
if (dices.length == 0)
return word.isEmpty();
Set<Integer> availableDices = new HashSet<>();
Map<Integer, List<Character>> diceToCharacterMap = new HashMap<>();
int m = dices.length;
int n = dices[0].length;
for (int i = 0; i < m; i++) {
availableDices.add(i);
for (int j = 0; j < n; j++) {
List<Character> chars = diceToCharacterMap.getOrDefault(i, new ArrayList<>(6));
chars.add(dices[i][j]);
diceToCharacterMap.put(i, chars);
}
}
return isPossible(word, availableDices, diceToCharacterMap, "");
}
private static boolean isPossible(String word, Set<Integer> availableDices, Map<Integer, List<Character>> diceToCharacterMap, String temp) {
if (temp.length() > word.length())
return false;
if (temp.equals(word))
return true;
for (Integer i : diceToCharacterMap.keySet()) {
if (availableDices.contains(i)) {
availableDices.remove(i);
for (Character c : diceToCharacterMap.get(i)) {
if (word.contains(String.valueOf(c))) {
temp = temp + c;
if (isPossible(word, availableDices, diceToCharacterMap, temp))
return true;
temp = temp.substring(0, temp.length() - 1);
}
}
availableDices.add(i);
}
}
return false;
}
}
- lesit.jae March 29, 2019struct Dice { Dice(const char* str) { for (int i = 0; i < 6 && *str != '\0'; i++, str++) side[i] = *str; } char side[6]; }; class WordDice { typedef unordered_set<int> _dice_idx; _dice_idx char_dices[26]; int n_dice; public: WordDice() { n_dice = 0; } bool setDices(const vector<Dice>& dices) { for (int idxDice = 0, n = dices.size(); idxDice < n; idxDice++) { const Dice& dice = dices[idxDice]; for (int i = 0; i < 6; i++) { char ch = dice.side[i]; if (!isalpha(ch)) return false; char_dices[tolower(ch) - 'a'].insert(idxDice); } } n_dice = dices.size(); return true; } bool canMakeWord(const string& word) { if (word.size() > n_dice) return false; vector<int> char_idxes(word.size()); for (int i = 0, n = word.size(); i < n;i++) { char ch = word[i]; if (!isalpha(ch)) return false; char_idxes[i] = tolower(ch) - 'a'; } unordered_set<int> used; vector<int> sel_dices(word.size()); if (canMakeWord(char_idxes, 0, used, sel_dices)) { for(int dice:sel_dices) cout<<dice<<", "; cout << endl; } else return false; } protected: bool canMakeWord(const vector<int>& char_idxes, int index, unordered_set<int>& used, vector<int>& sel_dices) { if (index == char_idxes.size()) return true; int ch_idx = char_idxes[index]; for (int dice : char_dices[ch_idx]) { if (used.find(dice) == used.end()) { used.insert(dice); sel_dices[index] = dice; if (canMakeWord(char_idxes, index + 1, used, sel_dices)) return true; used.erase(dice); } } return false; } }; int main() { WordDice wordDice; wordDice.setDices({ {"iqepjw", "lrvqik", "jtejru", "unamsd", "wpqnfy"} }); if(!wordDice.canMakeWord("tape")) cout<<"not matched"; return 0; }