Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
+1
Nice solution. Certainly more simpler and elegant than my complex one which uses operator overloading.
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 ;
bool result=dc.AddBox(a,10);
cout<<result<<endl;
result=dc.AddBox(b,10);
cout<<result<<endl;
return 0;
}
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)){
boxes.add(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};
System.out.println(checker.addBox(box1));
System.out.println(checker.addBox(box2));
int[] box3 = {0,1,3,2,5,6,7,4,9,1};
System.out.println(checker.addBox(box3));
int[] box4 = {3,3,3,1,1,1,7,3,3,1};
int[] box5 = {7,3,1,1,1,3,3,1,3,3};
System.out.println(checker.addBox(box4));
System.out.println(checker.addBox(box5));
}
}
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>();
addBox(int[] box) {
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) {
htable.add(boxobj)
return true;
}
else {
return false;
}
}
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.
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:
bool addBox(int arr[])
{
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);
}
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){
addDomino(new Domino(rawDominos[i], rawDominos[i+1]));
}
}
}
public void addDomino(Domino domino){
if(_dominos == null){
_dominos = new ArrayList<Domino>();
}
_dominos.add(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;
}
}
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));
}
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.
- Miguel Oliveira September 28, 2013#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; } };