Google Interview Question for Software Engineers


Country: -
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont see any other way but a backtracking and trying all combinations.

- codeReviewer March 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct 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;
}

- lesit.jae March 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(""))

}

- anandhus March 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- GG March 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- GG March 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- kogkoge March 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
        }

- Anonymous March 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

- incoming71 March 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- nitinguptaiit April 12, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More