4 program design interview questions

Question

I was preparing for technical interviews and would like to know how could I go about briefly explaining an interviewer about the approach to designing the following programs without going into unnecessary details

1. Program that lets people play tic tac toe with each other over the internet?               
2. A suitable data structure for a photo editor or text editor? Why?
3. Implementing code to operate the elevators?
4. Implementing the rendering engine of a web browser?

I could come up with the following:

1. There are primarily 2 parts to the program. One deals with the rendering of the board display. The other is the actual engine containing methods to find the winning move, AI, game completion, etc. Then, there will be the code related to the network.

2. A linked list of strings seems appropriate for the text editor, since the primary element is text and related manipulations. Does a linked list of objects seem right for the photo editor?

3. This again involves a display rendering of the elevators along with resource synchronization.

4. Don't have much clue about how to approach this one.

Are the sufficient enough? Am I missing some important details in approaching these problems.

Answer 1

The photo editor is an interesting one.

You need to consider the requirements of a photo editor:

• rapid selection, decode and display of part of a multi-megabyte data structure (16M?+)
• responsive display of user operation of paint tools - the brush should not lag, even if brushing over the whole image
• can you efficiently operate paint tools when zoomed out?
• save to common formats efficiently
• consider impact of all this data on CPU cache and bandwidth - note that accessing main memory can take 100s of times longer than accessing cache. How do you make most operations happen in the cache?
• what common features do existing editors have - undo, layers, effects, real-time blend modes, gamma conversion at the final display pass

I suggest holding multiple zoom levels with lower resolution and bit-depth (like mipmaps) in memory at once to allow efficient operation at different zoom levels, encoding changes as patches to the base image, not directly editing the base (i.e. layer every change separately). The patches could be encoded as a grid with only painted squares having memory allocated to them. Edits can be encoded as actions (e.g. tool, mouse down, movement, mouse up) before they are rendered into pixels - this allows a cheap paint to be done as patches at the current mipmap level and quickly displayed, while a background thread creates patches at the other mipmap levels.

Answer 2

Hi

Elevator scheduling is achieved by SCAN algorithm. Its also used for disk scheduling.

I hope this helps.

cheers