Test example for Autotester

Task 1 (18 р)

To write a flow-chart, which realizes the following algorithm:

There is an input file INF with serial access (file open and close operations, end-off file check, current record reading and transition to the next record are permitted). File contains records of the same structure sorted in increasing order of integer key field values. In file INF there can be records with the same key values. You have to create an output file OUTF, which is formed from the input file INF under the following rules:

• If for some key value record with this key field value is missing in INF, then this record can't be in file OUTF.
• If for some key value in file INF there is only one record with this key field value, then this record has to be copied to file OUTF.
• If for some key value in file INF there is some odd number of records with this key value then you should copy the record from the set that is physically allocated the first among all records with this key value in file INF.
• If for some key value in file INF there is some even number of records with this key value then you should copy the record from the set that is physically allocated the last among all records with this key value in file INF.

For example:
INF: k2, k3, k4a, k4b, k4c, k8, k99a, k99b, k100a, k100b, k100c, k100d
OUTF: k2, k3, k4a, k8, k99b, k100d.

Task 2 (15 р).

To write a function
    char* superSort (char*)
which takes a line of words divided with word spaces. Each word can consist of Roman letters of lower case and figures. The returned result must be a line of got words sorted in alphabetical order and divided with word spaces. During sorting when comparing words, figures must be ignored as if there were no figures at all. For example, for input line
    ma79ma 9n8e7 mila r1a2m3u
the result of function work has to be
    ma79ma mila 9n8e7 r1a2m3u

Task 3 (15 р).

A publishing house ordered you a program, Automaic Workplace of editor, which has to facilitate work with different editions (versions) of books. Each book can contain chapters, subchapters, subsubchapters, subsubsubchapters, ordinary text, lists of homogeneous text elements (you can meet them in dictionaries, catalogues etc.). The book author can be either a group or a person. Various editions of the same book may differ from each other by the contents and even the authors' list, but not by name. You have to design hierarchy of classes for the described system and write the appropriate non-detailed class diagram. Near the diagram you have to describe in details the used notation (preferably using UML).

Task 4 (8 р).

To describe in words the idea of function realization
    int printSubSets (char *)
which takes a line of words divided with word spaces, and prints all non-empty subsets of words (each subset in separate line). For example, for the input line     lazy brown fox
this function has to give the following results:
    lazy brown fox
    lazy brown
    brown fox
    lazy fox
    lazy
    brown
    fox
Offer the returned value. Your text description of the algorithm has to be brief, clear to the coder who has a lower level of qualification than you.

Task 5 (35 р).

To write a function
    int printMinQuantity (unsigned int input_value)
which takes integer input_value and prints on the screen the line of prime numbers divided with word spaces. The sum of these prime numbers is specified value input_value. The number of prime numbers must be minimal so that one can't select shorter series of prime numbers, which make in sum input_value.
For example, for number 6 variants "5 1" and "3 3" are considered as correct, variants "3 2 1", "2 2 2", "1 1 1 1 1 1" are considered as incorrect and so on. You have to find not every correct variant, but only one of them.
When writing a function pay attention to the algorithm efficiency and to the warranty of the fact that your algorithm finds the shortest of the possible series of prime numbers.

Suggest a value variant, which is returned by function.

Task 6 (35 р).

Write a program, which takes one argument of the command line. This argument is supposed to have the file name, which this system will work with. Input file contains code in C++, which is written according to C++ standard including commentaries. If in the command line parameter there is no extension, it means that the extension is .cpp. Your program has to create two new files from the source one. These new files must have the original extension changed to .src and .rem correspondingly.

File with the extension .src must contain only code from input file, and all commentaries must be changed to word spaces. File with the extension .rem must contain only commentaries, and the whole program code must be changed to word spaces.

The program must correctly handle the code, which contains:

• commentaries "nested" into each other (for example, /*   //   */ );
• different text lines (including those containing "//", "/*" etc);
• line continuation symbols (inverse slash at the end of the line);
• trigraphs;

etc.

Rules of writing a test.

When writing a test one is allowed to ask questions only a person who holds the interview. Any communication between the tested automatically leads to getting mark 0p by both offenders.

When writing a test one is allowed to use any programming language and literature he wants.

Near each task there is a maximum of points, which one can get for it. System of estimation is the following:

• 50 % of maximum - for correct answer;
• up to 25% of maximum - for efficient solution;
• up to 25% of maximum - for good style.

Time for writing a test is given at the rate of 200 minutes per 100 points (2 minutes per 1 point).

When writing a test please remember it will be checked by another person, so it's to your interest to write neatly and plainly. Don't forget to write as many commentaries as possible.

If when doing tasks 3, 5, 6 you forgot the name of the standard library function you can give it your own name, describe this function and its arguments in your commentaries and use it when doing the task. The only restriction: this function has to be similar to really existing standard library function.

In tasks 2, 4 input string doesn't contain tabulation and end of the line symbols ('\n').

The real test, which will be offered to you, has the maximum mark - 100 points (200 minutes) and passing mark is 60 points. To be hired you have to pass, besides the test, a number of interviews. For applicants from Dniepropetrovsk such interviews are held later. Test check for applicants from Dniepropetrovsk takes up to 7 days.