Design a Camel Cards hand evaluator and find best and worst completions

Camel Cards is played with hands of exactly five cards. Every hand belongs to exactly one of seven hand types, and each type has a fixed weight. From strongest to weakest: 1. Five of a kind: all five cards have the same label. 2. Four of a kind: four cards share a label. 3. Full house: three cards share one label and the other two share another. 4. Three of a kind: three cards share a label, and the other two differ from it and from each other. 5. Two pair: two cards share one label, two others share a second label, and the fifth card is different. 6. One pair: exactly two cards share a label, and the other three are all different. 7. High card: all five labels are different. There is no limit on how many cards of one label a hand may hold, so five of a kind is possible. You will design classes for hands and hand types, implement a comparison between two hands, and then handle hands with missing cards. ### Constraints and Clarifications - A complete hand always has exactly five cards. - A stronger hand type always beats a weaker one, whatever the labels. - In Part 2 the interviewer accepted a brute-force solution, and a careful time-complexity analysis is part of the expected answer. ### Clarifying Questions - What is the full set of card labels, and in what order do they rank? The example in Part 2 uses digit labels and includes `1`, so confirm which label is lowest. - When two hands have the same type, how is the tie broken: card by card in the order the cards were dealt, or by comparing the largest group first (for example, the three-of-a-kind label of a full house before its pair)? - What should `evaluate` return: the stronger hand, or a negative, zero or positive comparison result? Can two hands rank exactly equal? - How should malformed input, such as four cards or an unknown label, be reported? ### Part 1 — Model hands and compare two of them Create an abstract class `HandType` and a class `Hand`. Decide which fields each holds and which methods each exposes, then implement `evaluate(hand_1, hand_2)`, which decides which of two hands is stronger. Explain the design before writing code, and state the complexity of building a hand and of one comparison. ```hint Count once All seven types can be recognized from how many cards share each label. Decide which object computes those counts, and when, so that classification and comparison do not repeat the work. ``` #### What This Part Should Cover - What `HandType` abstracts (a name, a weight and a matching rule) and how the seven concrete types plug into it - How `Hand` stores its cards and determines its type once - A comparison by type weight first and a stated tie-break rule second - Input validation, and the cost of building and comparing hands ### Part 2 — Best and worst completions of a partial hand Some of a hand's cards are missing. Given the known cards, return `best_hand`, the strongest complete five-card hand that contains all of them, and `worst_hand`, the weakest. For example, if only `99` is known, the best hand is `99999` and the worst is `99321`. The interviewer said a brute-force approach is fine. Implement it, and break its time complexity down step by step. ```hint Count the candidates Work out how many ways the missing cards can be filled, then multiply by the cost of building and comparing one candidate. Express the result in terms of the number of labels and the number of missing cards. ``` #### Clarifying Questions for this Part - Do known cards keep fixed positions in the hand, or is a hand just a collection of cards whose order does not matter? - Can no cards be known at all, and what should happen if more than five are given? - If several completions tie for best or worst, which one should be returned? #### What This Part Should Cover - A brute-force enumeration that reuses the Part 1 classes and comparison - A step-by-step complexity breakdown, and the reason it is polynomial for a fixed hand size - How the answer depends on the tie-break rule and on whether positions are fixed - Whether a direct construction can replace enumeration, and what it would need to prove ### What a Strong Answer Covers - An object model in which adding, removing or reordering a hand type touches one place - Correct classification at the boundaries: full house versus three of a kind, and two pair versus one pair - A tie-break rule that is confirmed up front and applied the same way in both parts - Complexity analysis that keeps the fixed hand size separate from the number of labels - A clear explanation of the design before any code is written ### Follow-up Questions - Add a wildcard label that counts as any label when the type is determined but ranks lowest in tie-breaks. What changes in type matching and in Part 2? - Sort 1,000 hands from weakest to strongest. How do you reuse `evaluate`, and what does the whole sort cost? - If a hand had `H` cards instead of five, how would the brute force in Part 2 grow with `H`, and would it still be polynomial?