The Tormentor

About ten years ago, I was assigned as a mentor for the "Data Structures and Algorithms" course in a boot camp for freshers who had joined the company that I was working for at the time. My task was to answer any queries that the students might have had about the concepts taught in the course and then to test their understanding by giving them a related assignment. Looking back at one of these assignments, I can understand why I was nicknamed the "tor-mentor".

For some reason, Manju has preserved one of these assignments that I am now reproducing below. The students were expected to finish this assignment in the post-lunch half of the day and were divided into groups of three to four for this task. At least two groups chose the problem in Section B (Manju was in one of them, as was Sriki) and demonstrated a working implementation within the assigned time.

                      Data Structures and Algorithms
                      ==============================

Instructions:
-------------

    1) Solve either the three problems in Section A or the
       single problem in Section B. You must implement your
       algorithms as working programs in the C language.

    2) Try to keep your programs as simple as possible.
       Take care of proper program layout and embellish it
       with useful comments at the appropriate places.

    3) Make your programs as robust as possible. All borderline
       cases should be handled properly and the program should
       exit gracefully under all circumstances.



Section A
=========

Problem A1: Prime Number Generation
-----------------------------------

Given a positive number N, generate all the prime numbers
from 2 to N. The primary emphasis in the solution to this
problem should be on speed. In addition, you must not consume
an inordinate amount of memory.


Problem A2: Arbitrary Precision Arithmetic
------------------------------------------

Implement an arbitrary precision arithmetic calculator.
You should implement addition, subtraction, multiplication
and division in the respective order. Try to make your
program as fast as possible and keep memory usage to the
bare minimum.


Problem A3: Sub-string Search
-----------------------------

Given two strings S1 and S2, determine whether S2 occurs
as a substring in S1 and if so, find the first occurrence
of S2 in S1. Your program should be extremely fast. Try
to come up with a linear solution to the problem.



Section B
=========

Problem B1: Simple File-system Implementation
---------------------------------------------

Implement a simple filesystem within a normal file on the
hard disk, i.e. treat the file as a virtual disk and
implement the filesystem by manipulating records within the
file.

You are free to devise your own scheme for the file system
but it should minimally support the following operations:

   1) Create - Create a virtual hard disk on a file of the
      specified size and "format" it. Formatting would
      essentially involve initialising disk allocation
      structures and whatever else you need to do before
      you can have a valid filesystem.

   2) Open, Read, Write, Close - All the normal file operations
      to use the files.

   3) Delete, Rename - Remove unwanted files or rename existing
      files.

Do not place artificial restrictions on file names, sizes, etc.

In addition, if you can, provide support for folders (also known
as directories) which can be arbitrarily nested. Provide all
the common operations for folders.

You should implement this as a library of routines that can be
used by anyone wanting to treat a file as a filesystem.
Demonstrate the correctness of your routines by writing a demo
program that lets one manipulate files interactively.

                             --- X ---

Tweet