[2009-03-01] 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


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

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

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 ---

(Originally posted on Blogspot.)

Other Posts from 2009