Software Design

Besides testing your Algorithms proficiency, many interviews also test your Software Design abilities. In many software projects, you won't need to create your own complex algorithms, but good design is always important.

Software design is more subjective than algorithms, which makes it harder to practice. Algorithms can be checked for correctness and efficiency, but there's no simple tests for good design. This page will provide a brief review of important design concepts, but you should also get feedback from experienced developers on your own software designs.

Interviewers will usually care more about your design process than the final design you create. Make sure you can demonstrate your software design techniques, such as clarifying requirements, breaking down problems into smaller pieces and planning out your architecture.

System Design

This page reviews designing classes, but some interviews may ask questions related to systems design or web architecture. Make sure you review the fundamentals of any framework you have on your resume. For example, you may want to review the Model-View-Controller and Active Record patterns. Some interviewers may also ask you about common Design Patterns, though you probably won't need to implement them.

Higher-level interviews may ask questions about scalability and performance, so review different topics like storing and retrieving data, caching and concurrency.

Class Design

Here is a standard process for creating an object-oriented program (OOP) design. There are alternative design processes you could use (such as Test-Driven-Development), but its important to be familiar with at least one design process.

1. Gather the requirements. Ask questions from the "user" (or interviewer) to find out the actual use cases of the software.
2. Once you have a clear description of the application, select the nouns mentioned for potential classes, and the verbs for potential methods.
3. Apply OOP-principles to this list to get your list of classes. Remove redundant or unimportant nouns and see where inheritance would fit in or where "conceptual" classes are needed.
4. Create a diagram or list of your classes, their relationships and their important methods.

When designing your classes, keep in mind these basic heuristics of good design (From Chapter 5 of Code Complete):

• Find Real-World Objects - Identify the objects, their attributes and actions
• Form Consistent Abstractions - Look at the Object from a high-level
• Encapsulate Implementation Details - Don't look at the details of the object
• Inherit When Possible - to keep the design simpler
• Hide Secrets (Information Hiding) - e.g. use methods to access variables
• Identify Areas Likely to Change - isolate them so they'll be easier to change in the future
• Keep Coupling Loose - don't let classes become too entangled with each other
• Look for Common Design Patterns - be familiar with standard designs for solving problems

Card Game

Here's a short dialog where you figure out the classes needed for a Card Game program.

User: I need a simple program for playing card games. Can you create it for me?

You: Sure. What is this program going to do?

User: Well it should be able to be extended to be used in various card games.

You: Can you describe how these card games generally work?

User: Well, in most card games, there is a deck of 52 cards used for dealing a set of cards, known as "hand", to each player. Each turn, players can play cards, and sometimes win new cards from other players or the deck.

Once you have your classes, think about the methods you would put in each class. What are the different actions each class will need to perform?

Once you have a basic design plan, you can begin creating the actual code. In the challenge, create a program for running an actual card game.

(For more help with creating your general card game classes, see these Java Notes.)

Goofspiel Challenge

You can create many different card games that use your Deck of Cards classes. In this challenge, create a program for running the game Goofspiel. Goofspiel is a 2-player card game without any randomness.

Setup
The deck of cards are sorted by suit. Both players get one suit of cards, another suit is used for the pile or deck, and one suit is left out of play. (In this game, the specific suits do not matter.)

Play
Each turn, the top card in the pile is turned over for bidding. In this challenge, the first card turned over should be 1, the next card should be 2, all the way up to 13. Each player bids on the face-up card by placing their own card face-down. Both players then lose the card that they bid, but the higher bidder wins the face-up card. Cards that are won can be used for future bids.

Example Turn
The first card turned over is 1. player1 plays a 1, player2 plays a 2. Both players lose the cards they bid, but player2 wins the 1 from the pile. (Each player is down 1 point overall.)

Ties
If the 2 bids are the same, the players take back their cards and bid again.

Winning
The game ends when all 13 cards from the pile have been bid on. The winner is the player with the most points.

Input
The first line of input contains the number of games t. t lines follow, with each line consisting of a complete game:
Each line will contain the integer values of all the cards played in order:

player1 player2 player1 player2...

(Since the suit does not matter in this game, the input just contains integers for the card value.)

Output
On each line, print the score of player1 followed by the score of player2 for that game.

Sample Input/Output

Input:

1
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1

Here's the gameplay:

Card	Player1	Player2
1	1	2
2	2	3
3	3	4
4	4	5
5	5	6
6	6	7
7	7	8
8	8	9
9	9	10
10	10	11
11	11	12
12	12	13
13	13	1

Each round, player1 bids at the card's value while player2 bids 1 above it. player1 loses all his cards and only wins the final card (13), while player2 loses all her cards and wins all the cards from 1 to 12 (a total of 78).

Output:

13 78