Hungry Mind , Blog about everything in IT - C#, Java, C++, .NET, Windows, WinAPI, ...

CQG в Киеве (часть 1)

Сейчас веду поиск работы. Компания CQG была расхвалена сотрудником. Нашел вакансию, отправил резюме. Ответ был получен мгновенно. Поговорил по телефону с HR-менеджером Алевтиной. Предложила прийти на интервью, сообщила, что после интервью дают два технических задания. Как правило, я отказываюсь выполнять подобные задания просто так (без оплаты), но тут интерес меня задавил и я попросил отправить задание немедленно, что и было сделано.

Текст письма с заданием:
“Unit Conversion” problem (came from “ACM Programming Contest” sponsored by IBM); “File Manager” problem proposed by CQG developers.
Preliminary recommendations applicable to both tasks are:
  1. Technical assignments are provided “as is”; we assume that all significant information is mentioned in the tasks’ descriptions and the letter below.
  2. You can use C++ or C# for projects’ implementation. No third party libraries allowed.
    If your CV states that you have good experience with C++ then one of the tasks must be implemented using C++.
  3. Let it be console applications with input/output from/to standard stream with no command line arguments. Output files must be readable and verifiable enough.
    (Hint: use “myprogram.exe < in.txt > out.txt” command line syntax).
    We provide minimum set of the test cases for every assignment for your convenience (See attaches).
  4. Send us zip file(s) with the source code for application and with test data sets you’ve used, if any.
  5. As a first step for your assignments’ evaluation we will compile the source code using Microsoft Visual C++ or C#. And run the tests. Your code should be compilable and your application SHOULD return the correct results. After that, your code will be very carefully inspected and checked by CQG developers.
  6. Please, keep assignments as simple as possible, but at the same time we should be able to assess your OOD/OOP skills from your code.
  7. We kindly ask you to keep total code size for both assignments below 800 lines of code (in sum), but if it will require more, it should be easy to say “why?”
  8. Your code is like your business card. Please, try to demonstrate your vision of the professional quality reliable code in your projects. Please, don’t let ignoring of these recommendations discard your candidature from the evaluation. Pay additional attention to #3, #5 and #6.
  9. You are expected to spend 4…8 hours for both assignments. We ask you to provide actually spent time for the assignments to get feedback about complexity of the tasks. We promise do not include this number in grading the assignments and your candidature.
Задание 1
File Manager Emulator
File Manager Emulator (FME) emulates the details of creating, removing, copying and moving
files and directories. It also handles commands related to these file management tasks. FME shall be
capable to read and execute a batch file with different kind of commands. After the batch file execution
it shall generate and print out formatted directory structure or an error message if something went
wrong to standard output. Note that program should do nothing with the real file structure on local hard
drives and shall only emulate these activities. Your goal is to write such File Manager Emulator.
FME Commands
• MD – creates a directory.
Command format: MD [drive:]path
Notes: MD should not create any intermediate directories in the path.
a) MD C:\Test – creates a directory called Test\ in the root directory.
b) MD Test – creates a subdirectory called Test\ in the current directory
c) MD C:\Dir1\Dir2\NewDir – creates a subdirectory “NewDir” if directory “C:\Dir1\Dir2” exists.
• CD – changes the current directory.
Command format: CD [drive:][path]
Note that using CD without parameters is not allowed.
a) CD C: – set root as the current directory.
b) CD C:\Dir1 – set “C:\Dir1” as the current directory.
c) CD Dir1 – set Dir1 subdirectory of the current directory as new current directory.
• RD – removes a directory if it is empty (doesn’t contain any files or subdirectories).
Command format: RD [drive:]path
Notes: It is not allowed to delete the current directory in such way.
RD Dir2 – remove subdirectory “Dir2”.
• DELTREE – removes a directory with all its subdirectories.
Command format: DELTREE [drive:]path
Note that you can’t remove a directory that contains current directory as one of its subdirectories.
See notes 3 and 4 also.
• MF – creates a file.
Command format: MF [drive:]path
Notes: If such file already exists with the given path then FME should continue to the next
command in the batch file without any error rising.
MF Dir2\Dir3\file.txt – create a file named file.txt in the current directory’s “Dir2\Dir3”
• MHL – creates a hard link to a file/directory and places it in given location.
Command format: MHL [drive:]source [drive:]destination
Notes: Destination should contain only path without any file name. Actual link name will be created
as mentioned in note 10. If such link already exists then FME should continue to the next
command in the batch file without any error rising.
a) MHL C:\Dir2\Dir3\file.txt C:\Dir4 – create a hard link to the file “file.txt” and place it into the
directory “C:\Dir4”
b) MHL C:\Dir1\Dir4 C:\Dir2 – create a hard link to the directory “C:\Dir1\Dir4” and place it into
the directory “C:\Dir2”
• MDL– creates a dynamic link to a file/directory and places it in given location.
Command format: MDL [drive:]source [drive:]destination
Notes: Destination should contain only path without any file name. Actual link name will be created
as mentioned in note 10. If such link already exists then FME should continue to the next
command in the batch file without any error rising.
• DEL – removes a file or link.
Command format: DEL [drive:]path
Notes: See notes 3 and 4.
DEL C:\Dir2\Dir3\file.txt – removes a file “file.txt” form a directory “C:\Dir2\Dir3”.
• COPY – copy an existed directory/file/link to another location.
Command format: COPY [drive:]source [drive:]destination
Notes: Program should copy directory with all its content. Destination path should not contain any
file name otherwise FME should raise error.
a) COPY Dir2\Dir3\ C:\Dir1 – copy the current directory’s subdirectory Dir2\Dir3\ into C:\Dir1.
b) COPY Dir2\Dir3\file.txt C:\Dir1 – copy a file “file.txt” form current directory’s subdirectory
Dir2\Dir3\ into C:\Dir1.
c) COPY Dir2\Dir3\file.txt C:\Dir1\newfile.txt – is illegal!
• MOVE – move an existing directory/file/link to another location
Command format: MOVE [drive:]source [drive:]destination
Notes: Program should move directory with all its content. In case when a file or directory which is
being moved has a hard link, FME should terminate the MOVE operation and batch file execution.
In case when any dynamic link(s) found and no hard link exists, then dynamic link(s) should be
modified and contain new location information instead of the old one.
a) Let suppose that we have the following directories structure –
| |_DIR2
| | |_DIR3
| | |_readme.txt
| |
| |_EDIR4
| | |_ hlink[C:\DIR1\DIR2\DIR3\readme.txt]
| |
| |_GDIR5
| | |_ dlink[C:\DIR1\DIR2\DIR3\readme.txt]
And FME found command MOVE C:\DIR1\DIR2\DIR3 C:\DIR1\EDIR4 in a batch file.
Following to our requirements FME should terminate command execution because of the
hard link hlink[C:\DIR1\DIR2\DIR3\readme.txt] existence.
b) Let suppose that we have a little bit different directories structure –
| |_DIR2
| | |_DIR3
| | |_readme.txt
| |
| |_EDIR4
| |
| |_GDIR5
| | |_ dlink[C:\DIR1\DIR2\DIR3\readme.txt]
After MOVE C:\DIR1\DIR2\DIR3 C:\DIR1\EDIR4 command execution the directories
structure and dlink will be changed by the following way.
| |_DIR2
| |
| |_EDIR4
| | |_DIR3
| | |_readme.txt
| |
| |_GDIR5
| | |_ dlink[C:\DIR1\EDIR4\DIR3\readme.txt]
Additional Implementation Notes:
1. Initially file system contains only the root directory marked as “C:”
2. Commands, file and directory names are case insensitive. Cd, CD, Cd, cD does mean the same
3. One can not delete a file which has an attached hard link but can delete a dynamic link.
4. When a file is deleted its all dynamic links are also should be deleted. If a file has both hard and
dynamic links FME should keep them all unchanged.
5. Files and directories naming conventions shall be the following
a. File or directory names shall not exceed 8 characters length.
b. File extension shall not exceed 3 characters length.
c. Only alphabetical [a…z] and numerical [0…9] characters allowed in the file or directory
names and extensions.
6. Any action beside cd shall not change the current directory.
7. If a path doesn’t contain “C:\” prefix then FME shall perform actions in the current directory.
8. In case of any error occurs, the program shall stop and output a descriptive error message.
9. The output shall be organized by the manner given below. The output should be organized in
alphabetical ascending order.
10. The output format for dynamic and hard links should be the following:
hlink[ full path ] for hard links and dlink[ full path ] respectively.
11. It is not allowed to create links to links.
| |_DIR2
| | |_DIR3
| | |_readme.txt
| |
| |_EDIR4
| | |_temp.dat
| |
| |_GDIR5
| | |_hlink[C:\Dir1\EDir\4temp.dat]
Simple Test Case
Simple input:
MD Dir1
MD Dir1\Dir2
CD Dir1
MD EDir4
MD GDir5
MD Dir2\Dir3
MF Dir2\Dir3\readme.txt
CD EDir4
MF temp.dat
| |_DIR2
| | |_DIR3
| | |_readme.txt
| |
| |_EDIR4
| | |_temp.dat
| |
| |_GDIR5
Задание 2
Problem I
Unit Conversion
A (measurement) unit is here represented by a single word containing only lower-case letters. All
units are written as singular both in input and in output. A conversion fact relates the size of two
You are to convert a quantity in one unit to the equivalent quantity in a different unit using only
a given set of conversion facts. These conversion facts are self consistent; there is never more
than one conversion chain from any unit to any other unit.
The input will start with a number of lines, each containing a conversion fact in the form:
<v1> <u1> = <v2> <u2>
The elements <v1> and <v2> are positive real numbers (a sequence of decimal digits, containing
at most one decimal point), and <u1> and <u2> are strings containing only lower case letters
representing the name of a unit. The elements are separated by single spaces. The conversion fact
asserts that the quantity <v1><u1> is equal to the quantity <v2><u2>.
There will then a number of lines each representing a conversion request in the form:
<v3> <u1> = ? <u2>
The elements <u1> and <u2> are again unit names, which may or may not have occurred in the
conversion facts. All elements on the line are separated by single spaces (the equality sign and
question mark are surrounded by single spaces too). The end of data is represented by end-offile.
For each conversion request there should be either the line
No conversion is possible.
if insufficient conversion facts have been given, or a line of the form
<v3> <u1> = <v4> <u2>
• where all elements are as in the conversion request, except that the ‘?’ has been replaced by a
decimal number <v4>, and is calculated, using only the given conversion facts previously
given, so that the left and right-hand side quantities are equal. There should be a single space
between all elements in the line. The numbers <v3> and <v4> must be formatted as follows:
• If <v4> is greater than or equal to 1,000,000 or less than 0.1, it must be printed in scientific
notation: a number between 1.000000 and 9.999999 printed with exactly six digits after the
decimal point, followed by “e+nn” or “e-nn”, where “e” represents “times ten to the power
of”, and “nn” is a two digit number.
• Otherwise, <v4> must be printed in standard decimal notation, with a decimal point
followed by exactly six digits.
• In both cases, the number printed must be the closest such number to the true answer, i.e.
round, don’t truncate.
Sample Input:
7200.0 second = 2 hour
10.0 glob = 1 decaglob
1 day = 24.0 hour
1 minute = 60 second
1 glob = 10 centiglob
1 day = 24 hour
1 year = 365.25 day
50 centiglob = ? decaglob
5.6 second = ? hour
3 millisecond = ? hour
5.6 second = ? day
1 day = ? glob
1 hour = ? second
1 year = ? second
Sample Output (corresponding to sample input)
50.000000 centiglob = 0.500000 decaglob
5.600000 second = 1.555556e-03 hour
No conversion is possible.
5.600000 second = 6.481481e-05 day
No conversion is possible.
1.000000 hour = 3600.000000 second
1.000000 year = 3.155760e+07 second
Unit Conversion я выполнил на С++, File Manager Emulator на C#. Замечу, что условие задачи Unit Conversion составлено грамотно и четко, а File Manager Emulator оставляет желать лучшего. Исходные коды можно скачать тут. Буду рад комментариям.
Copyright 2007-2011 Chabster