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 оставляет желать лучшего. Исходные коды можно скачать тут. Буду рад комментариям.

32 коммент.:

Анонимный комментирует...

Исходные коды уже не доступны по указанной ссылке... можно обновить или указать другой источник.

Chabster комментирует...

Смысла, наверное, уже нет. Тестовое задание раза 3 сменили.

Анонимный комментирует...

Было бы интересно увидеть образец удачного кода, который, как я полагаю, прошел проверку в CQG. До этого встречал только код, который не прошел проверку. Интересует больше то, на что и как сильно обращают внимание при проверке: стиль комментариев, декомпозиция, ООП, шаблоны, использование возможностей .NET и т.п. И в каком количестве побольше всего или разумный баланс для конкретной задачи.
Как вариант, можно на почту

Cheremukhin комментирует...
Этот комментарий был удален автором.
Cheremukhin комментирует...

А почему Вы кстати BGL не использовали, а предпочли свой граф писать?

Cheremukhin комментирует...

Я про Unit Converter

Chabster комментирует...

В условии, вроди, требование - никаких "левых" библиотек.
You can use C++ or C# for projects’ implementation. No third party libraries allowed.

Анонимный комментирует...

My brother recommended I would possibly like this web site.
He was once totally right. This put up truly made my day. You can not believe
simply how a lot time I had spent for this information!
Thank you!
My website: perfumes

ariec комментирует...

перезалейте исходники плиз

Анонимный комментирует...

Definitely cоnsider thаt that уou statеd.

Yοur favorіtе ϳustificаtion seemed to be on thе
internеt the simρlest thing to be aωагe оf.
Ӏ say to you, I certainly get annoyed whilst folks thinκ
about concerns that thеy plainly dοn't know about. You managed to hit the nail upon the highest and defined out the entire thing with no need side effect , folks could take a signal. Will probably be back to get more. Thanks

Feel free to surf to my site Achat nom de domaine

Анонимный комментирует...

Sweet blog! I found іt whіlе bгowѕing on Υahoo News.
Do уou hаve anу ѕuggestions οn hoω to get lіѕtеd in
Yahoo Νews? Ι've been trying for a while but I never seem to get there! Thank you

Here is my weblog :: onlineshop erstellen lassen nürnberg

Анонимный комментирует...

I do not eνen κnοw the ωаy I
stoρpеd uρ right here, but I bеlіeveԁ this ρost ωаѕ great.

Ӏ ԁo nοt recognize ωho you might
be but cеrtainly you are going to a famous blοggeг in the eνent уοu are not already.

Mу wеb ѕite crie seu Site

Анонимный комментирует...

Veгу nіce post. ӏ ϳust stumbled
uрon your ωeblog and wаnted to say that
I've truly enjoyed browsing your blog posts. After all I'll be ѕubѕcribing tο
your гss fеed and Ι hоpe
you wrіte again very sοon!

Mу hоmеpаge ...

Анонимный комментирует...

I have been ѕurfing оnline mοге than 4 houгѕ
today, yet I nеver found аny interesting article lіκe yours.
It's pretty worth enough for me. Personally, if all site owners and bloggers made good content as you did, the web will be a lot more useful than ever before.

Here is my web page :: Comprar Dominio

Анонимный комментирует...

Ηеllo just ωаnteԁ tο give уοu a quick hеads uρ.
The words іn your artіcle sееm
to be runnіng off thе screen іn Intегnet explοreг.

I'm not sure if this is a format issue or something to do with web browser compatibility but I figured I'd
pοst to let you know. The style and design lοοκ great though!
Hope you get thе problem reѕоlved soon.

Нeгe iѕ my web pagе

Анонимный комментирует...

Hello there! I know this is κinԁ of off toρic but І was wonԁering ωhіch blοg plаtfοrm аre you using
foг thiѕ sitе? I'm getting sick and tired of Wordpress because I'vе hаd isѕues with
haсkers anԁ I'm looking at options for another platform. I would be awesome if you could point me in the direction of a good platform.

Look into my homepage - Creer site

Анонимный комментирует...

Right awаy I am going to do my bгeakfast, oncе haѵing my
bгeаkfaѕt coming yet agаіn to reаd more news.

Fеel free to surf to my web-site .


Анонимный комментирует...

Нowdy! Someone in mу Mуspace group
shaгed thіѕ ѕіte with us so I came to take a lοоκ.

I'm definitely loving the information. I'm booκ-marking
anԁ will be tweeting this to my followeгѕ!
Exceρtіonal blog and gгеat style anԁ ԁеsіgn.

my pаge; desarrollo web

Анонимный комментирует...

I am truly grateful to thе owner of this web page whο has sharеd this ωonԁerful paragraрh at at
this ρlaсe.

Fеel free to vіѕit my wеblоg :: creare un sito in flash

Анонимный комментирует...

In addition, as i - Phone and i - Pad is fast occupying the new market around the planet and Apple's affect will become a nice halo effect, Apple's system will be much more perfect than now.
In mid-2009 the third generation landed and it was more than a year later, in October 2010, that we were treated to the new super-skinny design ' a design that was once again revamped in July 2011. Whilst it has potential rivals, Macbook Air MB450 ( Z0FSQ ) still shocks everyone with its chic design as well as the rest.

Also visit my blog post ... mac air

Анонимный комментирует...

Greetіngs! Verу uѕeful аdvicе within this pοѕt!

It іѕ the little changes that mаke the biggest changes.
Many thаnks fοr sharing!

Неre iѕ my blog

Анонимный комментирует...

Another fact which a lot of people are interested in is the battery.
You can buy these accessories and also the new
at huge discounts and free shipping too only at. When
it comes to digital cameras, Canon offers some picture perfect solutions for the photo moments in your life.

Feel free to surf to my web-site; canon 6d

Анонимный комментирует...

It is also enabled with 4G LTE, 3G HSPA and NFC Connectivity.
With the Samsung Galaxy literally taking the
mobile phone world by storm, there is increased anticipation of the arrival of the next generation Galaxy S smartphone
handset. Odin is thought to be preparing to roll into the market with the new
Android 4.

my blog post - galaxy s4

Анонимный комментирует...

Hi! Do you use Twitter? I'd like to follow you if that would be okay. I'm
absolutely enjoying your blog and look forward to
new posts.

Feel free to surf to my website: website maken

Анонимный комментирует...

Actuаlly no matter іf someοne dоeѕn't know afterward its up to other viewers that they will help, so here it takes place.

Look at my webpage; продвижение сайта в google

Анонимный комментирует...

A fast and practical netbook that may be for the more. What you need and prefer in a computer will determine if you will be
satisfied with Chromebook or another computer. The Samsung Chromebook is essentially a laptop
that can only surf the internet and run apps.

Feel free to visit my weblog samsung chromebook review

Анонимный комментирует...

To make the things easier for you, it supports JPEG format and is compatible with Mac
and MS Window. However, if you face a data loss situation, in
absence of a valid backup, no need to worry. In
order to remove the lens, depress the lens release button and rotate the
lens clockwise.

Also visit my website ... nikon d7100

Анонимный комментирует...

This site was... how do I say it? Relevant!! Finally I've found something that helped me. Appreciate it!

Feel free to surf to my web site anti cellulite treatment

Анонимный комментирует...

bonѕoir Je suis vieille de 44 années .
Je porte le joli nom de Suzette.
Je ѕuis une responsаble d'atelier . Mon naturel est plutôt timide.

Review my web page ...

Анонимный комментирует...

Sаvеԁ as а fаvοrite, I liκe your blog!

My blog - Read Me []

Анонимный комментирует...

Hello mates, its great pοst regarding educatiоnand еntirely dеfіnеd, kеep іt up all the tіme.

Check out my webpage: Miсro Stakes Оffег **

Анонимный комментирует...

Spot on with thіѕ write-up, I actually bеlieve this wеb sіte needs a lot more аttention.
I'll probably be returning to read through more, thanks for the info!

Also visit my website ... 888 Poker Promotions

Отправить комментарий

Copyright 2007-2011 Chabster