Google Interview Question
Software EngineersCountry: -
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, 2019