Amazon Interview Question SDE1s
Country: United States
class List
{
DominoTile *Head;
DominoTile *Tail;
public:
List()
{
Head = NULL;
Tail = NULL;
}
~List()
{
delete Head;
delete Tail;
}
DominoTile* GetHead()
{
return Head;
}
DominoTile* GetTail()
{
return Tail;
}
void Append(DominoTile *Cnode)
{
if (Head == NULL)
{
Head = Cnode;
Tail = Cnode;
}
else
{
Tail->Pnext = Cnode;
Tail = Tail->Pnext;
}
}
};
class DominoTile
{
int Ftile;
int Etile;
public:
DominoTile *Pnext;
DominoTile()
{
Ftile = -1;
Etile = -1;
Pnext = NULL;
}
DominoTile(int FValue, int Evalue)
{
Ftile = FValue;
Etile = Evalue;
Pnext = NULL;
}
~DominoTile()
{
delete Pnext;
}
void setFtile(int Value)
{
Ftile = Value;
}
void setEtile(int Value)
{
Etile = Value;
}
int getFtile()
{
return Ftile;
}
int getEtile()
{
return Etile;
}
DominoTile operator= (DominoTile V)
{
V.Ftile = Ftile;
V.Etile = Etile;
V.Pnext = Pnext;
}
};
void main()
{
List Tiles;
int Fvalue;
int EValue;
for (int i = 0; i < 28; i++)
{
cout << "Please Enter Tiles";
cin >> Fvalue;
cin >> EValue;
DominoTile *Tile = new DominoTile(Fvalue, EValue);
if (Fvalue == -1 && EValue == -1)
{
break;
}
Tiles.Append(Tile);
}
DominoTile *Ptrav= new DominoTile();
DominoTile *Ptrav2 = new DominoTile();
Ptrav = Tiles.GetHead();
Ptrav2 = Ptrav->Pnext;
int LOOPFlag = 0;
while (Ptrav2->Pnext!=NULL)
{
if (Ptrav->getEtile() == Ptrav2->getFtile())
{
LOOPFlag = 1;
}
else
{
LOOPFlag = -1;
break;
}
Ptrav = Ptrav2;
Ptrav2 = Ptrav2->Pnext;
}
if (Tiles.GetHead()->getFtile() == Tiles.GetTail()->getEtile())
{
LOOPFlag += 1;
}
cout << LOOPFlag;
}
Dominoes can be presented as a graph with vertices 0, 1, ..., N, where edges stand for edges connecting vertices of the corresponding number. The degree of each vertex is N+2 (N edges connecting each vertex with other vertices and one loop edge, which increases degree by 2). Building the full dominoes loop is equivalent to finding Eulerian cycle in the graph. And the latter is possible if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. That means that we just need to check if N is even. In this case N+2 is also even which means that there's a Eulerian cycle in the graph.
Your answer is correct if a tile is allowed to be visited more than twice. The provided example isn't making this very clear. If you think about a traditional domino game, tiles can't be connected to more than two tiles so "inner loops" aren't allowed. This then turns into the Hamiltonian cycle problem, which is NP-complete. It's possible that this specific question solution is not NP-complete as some graphs (e.g. a complete graph) can be determined to have a Hamiltonian cycle without exhaustive search.
- Farida December 02, 2014class List { DominoTile *Head; DominoTile *Tail; public: List() { Head = NULL; Tail = NULL; } ~List() { delete Head; delete Tail; } DominoTile* GetHead() { return Head; } DominoTile* GetTail() { return Tail; } void Append(DominoTile *Cnode) { if (Head == NULL) { Head = Cnode; Tail = Cnode; } else { Tail->Pnext = Cnode; Tail = Tail->Pnext; } } }; class DominoTile { int Ftile; int Etile; public: DominoTile *Pnext; DominoTile() { Ftile = -1; Etile = -1; Pnext = NULL; } DominoTile(int FValue, int Evalue) { Ftile = FValue; Etile = Evalue; Pnext = NULL; } ~DominoTile() { delete Pnext; } void setFtile(int Value) { Ftile = Value; } void setEtile(int Value) { Etile = Value; } int getFtile() { return Ftile; } int getEtile() { return Etile; } DominoTile operator= (DominoTile V) { V.Ftile = Ftile; V.Etile = Etile; V.Pnext = Pnext; } }; void main() { List Tiles; int Fvalue; int EValue; for (int i = 0; i < 28; i++) { cout << "Please Enter Tiles"; cin >> Fvalue; cin >> EValue; DominoTile *Tile = new DominoTile(Fvalue, EValue); if (Fvalue == -1 && EValue == -1) { break; } Tiles.Append(Tile); } DominoTile *Ptrav= new DominoTile(); DominoTile *Ptrav2 = new DominoTile(); Ptrav = Tiles.GetHead(); Ptrav2 = Ptrav->Pnext; int LOOPFlag = 0; while (Ptrav2->Pnext!=NULL) { if (Ptrav->getEtile() == Ptrav2->getFtile()) { LOOPFlag = 1; } else { LOOPFlag = -1; break; } Ptrav = Ptrav2; Ptrav2 = Ptrav2->Pnext; } if (Tiles.GetHead()->getFtile() == Tiles.GetTail()->getEtile()) { LOOPFlag += 1; } cout << LOOPFlag; }