Sample ADT design problem

One of the midquarter assessment tasks will be a data design problem. The problem statement will describe a system in need of a data structure, along with a few operations desired for the system. You are to propose a design for the data structure and describe how to implement the requested operations. The problem statement may also ask you to analyze the Big O runtime of a particular operation or design an operation to meet a particular Big O runtime.

Unless otherwise restricted in the problem statement, you will have access to the full range of C++ primitive data types (bool, char, int, double, string) and Stanford collections (Vector, Grid/GridLocation, Stack, Queue, Set, Map). Your design can mix and match, use more than one type, and/or create nested structures as befitting the needs of the system.

When presenting your proposed design, you should provide precise, valid C++ type declarations for the components and a rough diagram/list of the contents of a tiny system.

When describing an operation, your answer can be presented as a "code sketch". Think of this as somewhat elevated pseudocode. Your code should contain sufficient detail to demonstrate your understanding of the correct access to the data, but will not require the full precision of entirely valid C++.

What we are assessing with this task is your knowledge of the appropriate use of each data structure and understanding of the tradeoffs in choosing among them when designing a system. During the discussion portion of the assessment, you will offer the rationale for the choices you made, the alternatives you considered, and your evaluation of how your design meets the needs of the system.

Sample problem statement

The CS106B Paperless system allows you to re-submit as often as you like, a newer submission replaces any previous submission. (Pro Tip: submit your code as soon as it is partially working, and resubmit it as it improves. This way you always have a “safety” if catastrophe strikes)

The Paperless system is to be re-designed to track of each student’s submissions in a way that allows the student to revert to an earlier version. The new system should support the three operations below:

Your task is to design the data storage for the new Paperless system and give a code sketch for the operations. Here are the deliverables for your answer:

Solution

Data structure

  • Store submissions in Vector< Map<string, Stack<string> >> data
  • Vector has one element, a map containing two entries, (key = Student A, value = Stack of 2 submissions) and (key = Student B, value = Stack of 1 submission). No entry in Map for Student C (no submission yet)

submit

  • Add code onto stack of submissions for sunet
  • data[assignNum][sunet].push(code)

discard

  • Handle error (no submit), pop top from stack, remove student from map if discarded only submit 
      if (!data[assignNum].containsKey(sunet)) error(...)
  data[assignNum][sunet].pop()
  if (data[assignNum][sunet].isEmpty()) data[assignNum].remove(sunet)

count

  • We do not store empty stack for non-submitting student, so count of students submitting is equal to size of map
  • return data[assignNum].size()
  • runs in O(1)

Other problems to consider

Here are a few other ADT design tasks to consider.