"Design a Rubik\'s Cube then write a method that solves it, printing each step of the process"\n\nI was recently asked this in a virtual onsite for an HFT firm. I\'m pretty this is the question that prevented me from getting an offer.\n\nFirst off, I have no idea how to solve a Rubik\'s cube. I was also given about 20 minutes to answer this.\n\nBroadly speaking, my answer was to have a "cube" class with 6 "side" classes which are just 3x3 arrays consisting of "square" classes which consist of a squareID (let\'s say it\'s on the bottom side and it\'s the first square on the top left, the squareID is something like "B1") and a color. The cube class has a method to check if it is solved. Each side class has a "rotate" method which takes three booleans: RowOrColumn (decide if you want to rotate a row or column), direction(decide clockwise or counterclockwise), and FirstOrLast (decide if you want to rotate the first or last row/column). The rotate method would swap colors between squares on the effected sides. I did not need to code the logic for this.\n\nI thought this sounded somewhat reasonable, but solving the Rubik\'s cube is where I panicked. Ultimately I decided to construct a decision tree (or a trie I guess) with each branch representing a rotation. This means there will be 2^3 branches for each node. The nodes in the tree are unique strings consisting of all the squareIDs and their color in a specific order. The root node is the string constructed from the inputted Rubik\'s cube class instance. Basically the string would be a unique identifier for that Rubik\'s cube\'s specific configuration. As you construct the decision tree, you\'d check if it is solved and make sure to check for cycles along the way (using a set). Once you have a string representing a solved Rubik\'s cube, work back up to the root node to get the whole path.\n\nObviously the solution sucks since I\'m basically generating every permutation. I couldn\'t come up with some sort of heuristic on the spot to reduce the search space since, well, I have no idea how to even solve a Rubik\'s cube. Couldn\'t really find a good answer to this online.\n\nDoes my solution sound reasonable? How would you answer this question?

"Design a Rubik\'s Cube then write a method that solves it, printing each step of the process"\n\nI was recently asked this in a virtual onsite for an HFT firm.