## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 10 vote

The current solutions given here are too complex. You can do something simpler and smarter.
Note that we're given 10 integers, each from 0 to 9. If we concatenate the 10 numbers we'll get at most 9,999,999,999 which fits in a 64 bit integer.
Also note that having dominoes (0,2) and (2,0) is the same, as having boxes [(0,2); (9,1); (3,3); (7,4); (5,6)] or [(0,2); (3,3); (5,6); (7,4); (9,1)] is also the same, the order does not matter.

``````#include <algorithm>
#include <vector>
#include <unordered_set> // hashtable in c++11
using namespace std;
typedef pair<int,int> Domino;

class DominoChecker {
unordered_set<long long> hash;
vector<vector<Domino> > boxes;

public:
bool addBox(const vector<int>& box) {
vector<Domino> v;
for (int i = 0; i < 5; i++) {
Domino d(box[2*i], box[2*i+1]);
if (d.first > d.second)
swap(d.first, d.second); // order does not matter
v.push_back(d);
}
sort(v.begin(), v.end());  // order does not matter here as well.
long long hash_value = 0;
for (int i = 0 ; i < 5; i++)
hash_value = hash_value * 100 + v[i].first*10 + v[i].second;
if (hash.find(hash_value) != hash.end())
return false;
hash.insert(hash_value);
boxes.push_back(v); // i suppose we want to store them
return true;
}
};``````

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

+1
Nice solution. Certainly more simpler and elegant than my complex one which uses operator overloading.

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

you can do easier than this by constructing a fingerprint of of sorted pairs
so the array of 10 should be reduced to an array of 5 sort the pair desc
then construct a fingerprint of the box using a simple string which will be the same for the same domino pieces in the box whatever the order

``````#include <iostream>
#include <map>

using namespace std;

int compare(const void * a, const void * b){
return ((*(int*)a)-(*(int*)b));
}

class DominoChecker{
public:
bool AddBox(int dominoBox[],int len){
bool result=false;
string fingerPrint;
int* x=new int[len/2];

for (int i=0,j=0; i<len/2; i++,j+=2) {
x[i]=dominoBox[j]>dominoBox[j+1]?dominoBox[j]*10+dominoBox[j+1]:dominoBox[j]+dominoBox[j+1]*10;
}
std::qsort(x,5,sizeof(int),compare);
for(int i=0 ; i<len/2;i++){
fingerPrint+=std::to_string(x[i]);
}

cout<<fingerPrint<<endl;
if(dominoBoxes[fingerPrint]!= NULL){
result= true;
}
else{
dominoBoxes[fingerPrint]=dominoBox;

}
delete[] x;
return result;
}
private:
std::map<string,int*> dominoBoxes;

};

int main(void){

int a[10]={1,2,3,5,6,6,5,6,0,3};
int b[10]={1,2,6,6,5,3,5,6,0,3};
DominoChecker dc ;
cout<<result<<endl;
cout<<result<<endl;
return 0;``````

}

Comment hidden because of low score. Click to expand.
2
of 4 vote

FUCK. FUCK. FUCK.

I AM TIRED OF PPL JUST POSTING CODE WITHOUT AN EXPLANATION.

ok?

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

+1
Scanned the page from top to bottom, say no pseudocode nor analysis.

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

Java Implementation of DominoChecker....

``````public class DominoChecker {

class Domino {
int first;
int second;

Domino(int first, int second){
this.first = first;
this.second = second;
}
public boolean equals(Object obj){
if(!(obj instanceof Domino)){
return false;
} else{
Domino that = (Domino) obj;
return (this.first == that.first && this.second == that.second);
}
}
public int hashCode(){
return (this.first+this.second)*31;
}
}

class DominoComparator implements Comparator<Domino>{
public int compare(Domino dom1, Domino dom2) {
if(dom1.first < dom2.first){
return -1;
} else if(dom1.first > dom2.first){
return 1;
} else{
if(dom1.second < dom2.second){
return -1;
}
if(dom1.second > dom2.second){
return 1;
}else{
return 0;
}
}
}
}

Set<Long> boxes = null;
public DominoChecker(){
boxes = new HashSet<Long>();
}

public boolean addBox(int[] box) {
Domino[] dominos = new Domino[box.length>>1];
for(int index = 0; index < 5; index++) {
Domino domino = new Domino(box[2*index], box[2*index+1]);
if(domino.first > domino.second){
swapDominoPair(domino);
}
dominos[index] = domino;
}
Arrays.sort(dominos, new DominoComparator());
long hashValue = 0;
for(int index = 0; index < 5; index++) {
hashValue = hashValue * 100 + dominos[index].first*10 + dominos[index].second;
}

if(!boxes.contains(hashValue)){
} else {
return false;
}
return true;
}

private void swapDominoPair(Domino domino){
int temp = domino.first;
domino.first = domino.second;
domino.second = temp;
}

public static void main(String[] args) {
DominoChecker checker = new DominoChecker();
int[] box1 = {0,2,9,1,3,3,7,4,5,6};
int[] box2 = {0,2,3,3,5,6,7,4,9,1};

int[] box3 = {0,1,3,2,5,6,7,4,9,1};

int[] box4 = {3,3,3,1,1,1,7,3,3,1};
int[] box5 = {7,3,1,1,1,3,3,1,3,3};
}
}``````

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

Why not just use HashSet<Domino>?

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

I have done the code almost as below. I just explained about the overriding the hashcode method but not coded. Don't know what will be the result :-(
Could any one explain how to override the hashcode & compare the contents of Box object in Java?

``````class Domino {
int num1;
int num2;
}

class Box {
Domino[] dominos;
public Box(Domino[] dominos) {
this.dominos = dominos;
}
}

Hashtable<Box, Boolean> htable = new Hashtable<Box,Boolean>();
Domino[] domino = new Domino[box.length()/2];
int domino_index = 0;
for(int i=0; i < 10; i=i+2) {
domino[domino_index] = new Domino();
domino[domino_index].num1 = box[i];
domino[domino_index].num2=box[i+1];
domino_index++;
}
Box boxobj = new Box(domino);

if(!htable.contains(boxobj) {
return true;
}
else {
return false;
}

}``````

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

Was the interviewer satisfied?

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

I think, the interviewer was not satisfied. I did two mistakes here
Forgot to add key/value pair in hash table while adding box object in the above code.

It should be htable.add(boxobj, true);

Another thing, I didn't write code for comparing the boxes i.e., to override hashcode() method.

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

Why use Hashtable<Box, Boolean> (you actually mean HashMap) ? You don't need the boolean value because it is exists/don't exist. HashSet is enough.
Or in your pseudo-code, Hashtable<Box>.

You can avoid that kind of hashing. Check my answer below.

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

Here is a solution in CPP. I tested the code and I think it works. The main takeaway of this problem was that the interviewer wanted to see if you understod strict weak ordering and comparator function overloading or not.

``````#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <set>

class Domino
{
public:
Domino()
{
num1 = -1;
num2=  -1;
}
void setPair(int n1,int n2)
{
if(n1>n2)
{
num1 = n2;
num2 = n1;
}
else
{
num1 = n1;
num2 = n2;
}
}

bool operator<(const Domino &obj) const
{
if(num1<obj.num1)
return true;
else if(num1==obj.num1)
return num2<obj.num2;
else
return false;
}

friend std::ostream& operator<<(std::ostream& o,const Domino &d);

int num1;
int num2;

};

std::ostream& operator<<(std::ostream& o,const Domino &d)
{
o << "[" << d.num1 << "," << d.num2 << "]" ;
return o;
}

class DominoBox
{
public:

DominoBox(int arr[])
{
for(int i=0;i<10;i=i+2)
{
boxset[i/2].setPair(arr[i],arr[i+1]);
}
}

friend std::ostream& operator<<(std::ostream& o,const DominoBox &b) ;

bool operator<(const DominoBox &box)const
{
for(int i=0;i<5;i++)
{
if(boxset[i].num1<box.boxset[i].num1 || boxset[i].num2<box.boxset[i].num2)
{
return true;
}
}
return false;
}

void sortInOrder()
{
std::sort(boxset,boxset+5);
}

Domino boxset[5];
};

std::ostream& operator<<(std::ostream& o,const DominoBox &b)
{
int i;
for(i=0;i<5;i++)
o << b.boxset[i];
return o;
}

class DominoChecker
{
public:
{
DominoBox* newBox = new DominoBox(arr);
std::cout <<"Trying to insert:";
newBox->sortInOrder();
std::cout << *newBox << "\n";
std::pair<std::set<DominoBox>::iterator,bool> ret;
ret = set_ds.insert(*newBox);
return ret.second;
}

void print()
{
std::set<DominoBox>::iterator it;
for(it=set_ds.begin();it!=set_ds.end();it++);
std::cout << *it;
}
private:
std::set<DominoBox> set_ds;
};

int main()
{
int x1[] = {7,4,0,2,9,1,3,3,5,6};
int x2[] = {7,4,0,2,3,3,6,5,9,9};
int x3[] = {2,0,9,1,3,3,6,5,4,7};

DominoChecker* myObj = new DominoChecker();
std::cout << "Inserting 1st element.\n";
bool res1 = myObj->addBox(x1);
std::cout << "Insertion successful:" << res1 << "\n";
std::cout << "Inserting 2nd element.\n";
bool res2 = myObj->addBox(x2);
std::cout << "Insertion successful:" << res2 << "\n";
std::cout << "Inserting 3rd element.\n";
bool res3 = myObj->addBox(x3);
std::cout << "Insertion successful:" << res3 << "\n";

return(EXIT_SUCCESS);
}``````

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

This solution is pretty simple. It runs in O(n).
We create two objects - Domino and DominoBox each of which override hashCode. We use the hashCode of the DominoBox as a key in a Map. Once we have the key we can easily tell if the DominoBox already exists in our vast collection of DominoBoxs.

``````package domino;

import java.util.HashMap;
import java.util.Map;

public class DominoChecker {
private Map<Integer, DominoBox> dominoCollection = new HashMap<Integer, DominoBox>();
public boolean addBox(int[] rawDominos){
DominoBox box = new DominoBox(rawDominos);
boolean duplicate = false;
if(dominoCollection.containsKey(box.hashCode())){
duplicate = true;
} else {
dominoCollection.put(box.hashCode(), box);
}
return duplicate;
}
}``````

``````package domino;

public class Domino {
private int _left, _right;
public Domino(int left, int right){
_left = left;
_right = right;
}
@Override
public int hashCode(){
final int prime = 31;
int result = 1;
result = prime * result + _left;
result = prime * result + _right;
return result;
}
}``````

``````package domino;

import java.util.ArrayList;
import java.util.List;

public class DominoBox {
private List<Domino> _dominos;

public DominoBox(int[] rawDominos){
if(rawDominos != null && rawDominos.length > 0){
for(int i = 0; i < rawDominos.length; i = i + 2){
}
}
}

public void addDomino(Domino domino){
if(_dominos == null){
_dominos = new ArrayList<Domino>();
}
}

@Override
public int hashCode(){
final int prime = 31;
int result = 1;
if(_dominos != null && _dominos.size() > 0){
for(Domino domino : _dominos){
result = prime * result + (domino != null ? domino.hashCode() : 0);
}
} else {
result = result * prime;
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
The simplest solution is use Hash, Convert given box into String of 10. Sort each box so that you will get small number first and then bigger number. Then sort whole set of boxes based on 1st number and then create output string by concatenating all box. if this is already present in hash then return false or else put that in hash and return true. {{{ public static boolean isBoxPresent(HashMap<String, Boolean> map, String[] box) { int i; int n = box.length; for(i = 0; i < n; i++) { char [] c = box[i].toCharArray(); Arrays.sort(c); box[i] = new String(c); } Arrays.sort(box); String out = ""; for(i = 0; i < n; i++) { out += box[i]; } if(map.containsKey(out)) { return false; } else { map.put(out, true); return true; } } public static void main(String[] args) { HashMap<String, Boolean> map = new HashMap<String, Boolean>(); String [] box = {"02","91","33","74","56"}; System.out.println(isBoxPresent(map, box)); String [] box1 = {"02","33","56","74","91"}; System.out.println(isBoxPresent(map, box)); } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

The simplest solution is use Hash, Convert given box into String of 10. Sort each box so that you will get small number first and then bigger number. Then sort whole set of boxes based on 1st number and then create output string by concatenating all box. if this is already present in hash then return false or else put that in hash and return true.

``````public static boolean isBoxPresent(HashMap<String, Boolean> map, String[] box) {

int i;
int n = box.length;
for(i = 0; i < n; i++) {
char [] c = box[i].toCharArray();
Arrays.sort(c);
box[i] = new String(c);
}

Arrays.sort(box);

String out = "";
for(i = 0; i < n; i++) {
out += box[i];
}

if(map.containsKey(out)) {
return false;
} else {
map.put(out, true);
return true;
}
}

public static void main(String[] args) {
HashMap<String, Boolean> map = new HashMap<String, Boolean>();
String [] box = {"02","91","33","74","56"};
System.out.println(isBoxPresent(map, box));
String [] box1 = {"02","33","56","74","91"};
System.out.println(isBoxPresent(map, box));
}``````

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.

### 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.