LINUX.ORG.RU

Тестовое задание веб программиста


0

0

[b]perl[/b]

Написать функцию, реализующую бинарный поиск значения по ключу в текстовом файле.

Аргументы: имя файла, значение ключа Результат: если найдено: значение, соответствующее ключу если не найдено: undef

Исходные данные и требования к реализации:

1. Объем используемой памяти не должен зависеть от размера файла, только от максимального размера записи.

2. Формат файла: ключ1\tзначение1\x0Aключ2\tзначение2\x0A...ключN\tзначениеN\x0A Где: \x0A - разделитель записей (код ASCII: 0Ah) \t - разделитель ключа и значения (табуляция, код ASCII: 09h) Символы разделителей гарантированно не могут встречаться в ключах или значениях. Записи упорядочены по ключу в лексикографическом порядке с учетом регистра. Все ключи гарантированно уникальные.

3. Ограничений на длину ключа или значения нет.

Правильная функция на файле размером 10Гб с записями длиной до 4000 байт будет отрабатывать любой запрос менее чем за 5 секунд.

igor@etvnet.ca

anonymous

Re: Тестовое задание веб программиста

А ты не охренел?

friday ★★★ ()

Re: Тестовое задание веб программиста

Впрочем, давай мы сделаем за тебя тестовое задание, и работать давай мы за тебя будем. Только зарплату получать будем тоже мы.

friday ★★★ ()

Re: Тестовое задание веб программиста

ПНХ

shimon ★★★★★ ()

Re: Тестовое задание веб программиста

Работодатель кретин. Собсно как и соискатель.

anonymous ()

Re: Тестовое задание веб программиста

>Правильная функция на файле размером 10Гб с записями длиной до 4000 байт будет отрабатывать любой запрос менее чем за 5 секунд.
>любой запрос менее чем за 5 секунд.

При этом время выполнения не должно зависеть от производительности железа, да? :))

manntes ★★ ()
Ответ на: Re: Тестовое задание веб программиста от manntes

Re: Тестовое задание веб программиста

я кого-то просил делать? нет.

я написал чтобы оценили

но я решил сделать!

можите подсказать тут массив нужно использовать или встроенные функции перла для работы с файми?

то есть бинарный поиск не получиттся если не массив! да?

anonymous ()
Ответ на: Re: Тестовое задание веб программиста от anonymous

Re: Тестовое задание веб программиста

>я кого-то просил делать? нет.
Этот ответ направь первому комментатору, а не мне

>я написал чтобы оценили

Идиотизм фразы про 5 секунд оценён :)

manntes ★★ ()

Re: Тестовое задание веб программиста

> Правильная функция на файле размером 10Гб с записями длиной до 4000 байт будет отрабатывать любой запрос менее чем за 5 секунд.

А еще она должна стирать носки, гладить трусы, готовить еду и возбуждать в твоем мозгу виртуальную вагину. Да, и совсем забыл, оно должно грабить корованы.

phasma ★☆ ()

Re: Тестовое задание веб программиста

Херасе, вот это быстрые парсеры на перле..

stave ★★★★★ ()
Ответ на: Re: Тестовое задание веб программиста от hizel

Re: Тестовое задание веб программиста

> для начала оцени простое чтение 10Гб файлика без обработки :)

там записи упорядочены, так что весь файл смотреть не надо.

true_admin ★★★★★ ()
Ответ на: Re: Тестовое задание веб программиста от manntes

Re: Тестовое задание веб программиста

> При этом время выполнения не должно зависеть от производительности железа, да?

Чтобы найти винт с временем сика больше 20мс -- это надо постараться :-) при 1Г записей бинарный поиск можно сделать в 30 сиков * 20 мс = 0.6 секунд независимо от железа.

www_linux_org_ru ★★★★★ ()

Re: Тестовое задание веб программиста

Судя по простоте задания, этот программист на перле будет кодить за еду...

www_linux_org_ru ★★★★★ ()
Ответ на: Re: Тестовое задание веб программиста от www_linux_org_ru

Re: Тестовое задание веб программиста

можно всё, никто не спорит и на любом языке программирваоние можно, а у вас были такие записи и 10Гб файл?

anonymous ()

Re: Тестовое задание веб программиста

ну чё, красивенько :)
нормальное ТЗ

vahvarh ★★★ ()

Re: Тестовое задание веб программиста

Думается 3 минуты, пишется за 10-20.

Для тестового задания выполняемого "на месте" вполне презентабельно.

roller ★★★ ()

Re: Тестовое задание веб программиста

File::SortedSeek

borisych ★★★★★ ()
Ответ на: Re: Тестовое задание веб программиста от manntes

Re: Тестовое задание веб программиста

>При этом время выполнения не должно зависеть от производительности железа, да? :))

В армии? В армии не должно. Как и в КПСС впрочем. Функция должна выполняться за менее чем 5 секунд на любом железе, иначе поедешь в Ливию охранять безопасность СССР

Karapuz ★★★★★ ()

Re: Тестовое задание веб программиста

Западло детектед: мы не можем делать fseek куда нибудь на середину - размер записи не фиксирован. Нам всё равно придется читать весь файл. Был-бы файл бинарным - было бы как два пальца. Можно "артилерийским методом" - стрельнули в середину и дальше вперед-назад, но это некрасиво как-то.

anonymous ()

Re: Тестовое задание веб программиста

кстати, если задача как-то связана с тем как всё устроено "по работе" - бежать от такого надо. Такие вещи делаются средствами БД, а не в текстовом файле.

anonymous ()
Ответ на: Re: Тестовое задание веб программиста от anonymous

Re: Тестовое задание веб программиста

>стрельнули в середину и дальше вперед-назад, но это некрасиво как-то

Зато будет работать в заданных условиях. Сикнули в середину файла, вероятно попали куда-то внутрь записи. Отмотали назад/вперед, нашли начало и конец, сравнили с искомой величиной. Дальше тривиальный поиск делением пополам. Думаю и правда можно в 5 секунд вложиться легко.

temp ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.