Interview Question: Design an Object Oriented System

I was asked this question in a couple of software engineer job interviews recently. After the interviews, I wondered if there is a general way to approach this question for any system X.

What is the question?

The system to design can be of two types:

1. The system manifests as software processes. Examples would be a rule engine, an app store and so on.
An app store selling software runs as processes in a network of computers. Its interfaces with the outside world can be defined by a handful of software interfaces.

2. The system manifests in the world outside computers. Examples would be an elevator, a parking lot, a DVD lending library and so on.
These systems can be viewed in a couple of ways:

2a. Real time software drives pieces of the physical system. Other software coordinates the pieces. As an example, in a parking lot, the system to design could be the software controlling and monitoring the parts of the parking lot. The software interfaces with the actual hardware using some well defined interfaces.

2b. A simulation of the entire physical system as software processes. Consider 2 examples:
i. A card game, where we model decks of cards, timers and game rules as software processes with a graphical user interface to make the game useful to users.
ii. A parking lot, where we simulate the entire system within software processes. The user interface allows the user to get a view into the system, and perhaps vary system parameters. Reasons to do this may be to study the system's characteristics in a cost effective way or create a virtual reality game.

In a type 2b system, we are essentially converting a type 2 system into a type 1 system.

Before attempting design, I think it is better to agree on a point of view with the interviewer.

If it is a physical system, it may be easier to deal with a model which simulates the system in software in its entirety, rather than one which attempts to design pieces of real time systems. Unless designing an embedded software system complements the job you are interviewing for.

Data structures and algorithms

It may appear that OO design questions can be answered while avoiding data structures and algorithms. This is not true. An interface or class may need to use an abstract data type or a well known algorithm in its implementation.
As an example assume the OO system to design is a syntax checker. You may define an interface which checks for balanced parentheses. The interviewer may want to know how you would implement the interface.
Even if you don’t know the answer off the bat, you could ask the interviewer for a hint or think of a naive answer which might lead to a good solution. The key is to know about the stack abstract data type and its operations. If you don’t know anything about stacks, this could become a difficult problem and raise a red flag with the interviewer.

It is good to know how to estimate time and space complexity of algorithms since interviewers may want to know if you can use this knowledge for design trade-offs.

Some ways to improve knowledge of data structures and algorithms:
Books Internet articles
Exercises
Perusing the standard library of your language
Work on projects.

Heuristic

Some approaches to the object oriented job interview question:

1. In my interviews, I wrote down interfaces and base classes which occurred as I described use cases to the interviewers. Then I began writing out the interactions between the objects. I asked questions when I faced ambiguity in my assumptions. This approach allowed me to engage the interviewer in the design process. However I thought it was a vague method when we got into the details and the interviewers started adding and modifying requirements.

2. A more precise way is to write down use cases first. Based on the use cases, come up with the objects. Then use a method like CRC cards to flush out the interactions between the objects. Use a message sequence diagram to refine the interactions. Finally use a deployment diagram to show various processes which host the objects as they run on computers and network elements. While this is a methodical way of doing object oriented design, it may not be the best approach within the constraints of a job interview.

Message Queue

Here is another way. Assume:
- A central priority message queue where any object can send a request for something to be done. The message queue automatically routes the message to the destination object.
- Unless there is a specific need, objects are created automatically and their lifetime is infinite (at least for the time of the interview).

So we assume an event loop, to which objects can send messages. The event loop routes the message to a suitable destination object, creating it if necessary.

Consider part of the design for an elevator bank.

This is not very different from the other methods given in the previous section; it just provides a compressed approach for the interview.

Events, Async Calls and Collections

In case of an asynchronous call or a call to a collection of objects, it helps to introduce a controller object which serializes the async events or helps choose an item from the collection. We did this in the call to the elevator bank controller, which chooses the optimal elevator to send in response to a passenger's request message.

Source Code

The point of the design is to clarify the domain and make good choices while solving the problem. At this point, we should have enough to switch over to code. This helps make the discussion more concrete.

Obviously we want to use the language which we are most comfortable with, unless the system to design is best expressed in a specific language. For example, if the system to design is a widget which is hosted within a web browser, JavaScript would be a good choice, even if Scheme is your favorite language. In this case it is likely the job involves some client side browser programming, and you should expect to use JavaScript at work.

Using higher level constructs like interfaces in the initial design allows for more flexibility while dealing with modified requirements. But remember such constructs usually imply indirection and you have to deal with the added complexity in the discussion with the interviewer.

Object Oriented Concepts

The main objective is to design a system. A well prepared interviewer will introduce additional requirements into the design, and this is a cue for you to leverage OO design concepts. Objected oriented design concepts like inheritance, polymorphism, encapsulation and dynamic dispatch should be used judiciously (and perhaps sparingly) in the design process. In the elevator design example, the interviewer might ask for a service elevator which is somewhat different from normal elevators to be added to the elevator bank. In case of a rule engine, the interviewer might add additional rule types which you may not have considered in the design.

A Builder

If the interview asks how the processes are setup, we can introduce a builder which translates a configuration into the actual objects at startup time.
For example consider an xml configuration for elevators:

<ellevatorbank>
    <ellevator id="1">
        <door id="1">
        </door>
        <allowedfloors>
            <floor id="1">
            </floor>
            <floor id="2">
            </floor>
        </allowedfloors>
    </ellevator>
    <ellevator id="2">
        <!-- etc. -->
    </ellevator>
<!-- etc. -->
</ellevatorbank>

The builder would just read the configuration file at startup and instantiate the corresponding objects required at startup. It may be good to think about a mechanism where the system behavior may be re-configured at runtime too.

Message Queue Again

With the interfaces and objects in place, we now need a way to put things in motion. We can introduce a priority message queue again. So we start an event loop which serializes messages and routes them to their destination. We can draw parallels with the way load balancers, web servers or operating systems deal with events which typically start or end on external actors.

Using a priority queue helps deal with messages which have to be executed ahead of the order in which they arrive. For example, a maintenance message from a technician to the elevator bank should take precedence over a normal call originating from a passenger.

Design Patterns

Making design patterns more important than the design might signal to the interviewer that we want to complicate the design rather than simplify it.

If I chose a design pattern, I would clarify if it is okay with the interviewer. Where possible I would prefer a well known data type or algorithm which may be available as a language library over a design pattern. And when I choose a design pattern, it would be a one I have used before in practice, not just read about in a book.

Generally avoid buzzwords and concepts you are not clear about.

Functional Programming Design? Procedural Programming Design?

I think it is valid to use alternate design methodologies to answer the question. Couple of things to consider:

- Does the group or company you are interviewing with have an environment where solving problems take precedence over the language and technology being used? There may be good reasons for this question to be answered either ways, and you may want to know the answer before hand using the internet and your contacts.
- Confirm with the interviewer if it is okay to approach the problem using an alternate design method.

Some Tips

In the design process, it helps to keep in mind:
1. The system to be designed is most important; any concepts used in the process should be to help in this design.
2. Articulate any design trade-offs you recognize to the interviewer.
3. Avoid buzzwords or terminology which you don’t understand well.
4. If you are faced with ambiguity, discuss a resolution with the interviewer.
5. At some point, reason with code, it can help focus the design process. Choose a language you are comfortable with.
6. Assume that data structures and algorithms cannot be avoided.
7. Assume that the interviewer will modify the constraints and requirements you have assumed in the initial design process.
8. With an open ended question like object oriented design, you have as much as of an opportunity to gauge your future colleagues and work environment as they have to judge you. Use it as an input while deciding if you want to take the job.