Тестирование... на знание

← →
vasIZmax © (2007-04-10 14:04) [0]

Предположим есть такая ситуация: вам рекомендуют взять на работу/ в штат какого-то молодого программиста/стажера.

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

Так вот собственно вопрос: как бы это узнали, т.е. предложили решить какую-то задачу (если можно пример), или может чисто "по всем разделам справки", или просто задали пару ключевых каких-то вопросов, или может как-то иначе?

ЗЫ. Ясное дело, что у всех интересы/специализация разная(кто работает напр. с БД, а кто-то с графикой), но это в принципе не суть столь важно.

← →
tesseract © (2007-04-10 14:06) [1]

> или просто задали пару ключевых каких-то вопросов, или может
> как-то иначе?

Тест на мозги надо проводить :-)

← →
stone © (2007-04-10 14:07) [2]

> Предположим есть такая ситуация: вам рекомендуют взять на
> работу/ в штат какого-то молодого программиста/стажера.
>

Зависит от того, кто именно и на сколько настойчиво "рекомендует". Если от "рекомендации" невозможно отказаться, то какая мне разница, что он знает/умеет.

← →
db2admin (2007-04-10 14:07) [3]

я обычно прошу рассказать алгоритмы сортировки,
если человек не нравиться прошу рассказать шейкерную сортировку

← →
vasIZmax © (2007-04-10 14:11) [4]

> tesseract © (10.04.07 14:06) [1]

Примерчик задания в студию :)

> stone © (10.04.07 14:07) [2]

Да кто бы не рекомендовал. Разве не интересно "действительно ли хорош рекомендованный спец или ламерюга еще тот":)

> db2admin (10.04.07 14:07) [3]

Начало уже есть: Сортировки.

← →
Игорь Шевченко © (2007-04-10 14:12) [5]

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

Ни на сколько. Этого не может быть по определению

← →
Чапаев © (2007-04-10 14:14) [6]

> Да кто бы не рекомендовал. Разве не интересно "действительно
> ли хорош рекомендованный спец или ламерюга еще тот":)
Хмык. Ну если рекомендовал "хороший спец", то вряд ли он рекомендовал "ламерюгу", не так ли?

← →
tesseract © (2007-04-10 14:15) [7]

> Примерчик задания в студию :)

Попроси дом нарисовать, если сразу начнёт рисовать, то минус. А если спросит какой дом рисовать - то плюс и тд.

← →
tesseract © (2007-04-10 14:17) [8]

Каких не надо брать :

http://www.nowa.cc/showthread.php?t=86016

← →
Чапаев © (2007-04-10 14:17) [9]

> [7] tesseract © (10.04.07 14:15)
Если сразу начнёт, его в руководящий состав, если станет уточнять -- в исполнительный. %-)

← →
palva © (2007-04-10 14:20) [10]

> А если спросит какой дом рисовать - то плюс
Это почему? Чем больше решений программист берет на себя, тем легче начальству. И всегда будет ясно, кого наказывать за провал проекта.

← →
pasha_golub © (2007-04-10 14:39) [11]

> tesseract © (10.04.07 14:15) [7]
>
>

> Попроси дом нарисовать, если сразу начнёт рисовать, то минус.
> А если спросит какой дом рисовать - то плюс и тд.

Бред!

ТЗ озвучено: нарисовать дом.

← →
db2admin (2007-04-10 14:40) [12]

pasha_golub © (10.04.07 14:39) [11]
вполне нормальное уточнение к ТЗ, человек сразу стал ТРП составлять в чем бред?

← →
db2admin (2007-04-10 14:40) [13]

pasha_golub © (10.04.07 14:39) [11]
вполне нормальное уточнение к ТЗ, человек сразу стал ТРП составлять в чем бред?

← →
pasha_golub © (2007-04-10 14:44) [14]

> db2admin (10.04.07 14:40) [12]

Стал уточнять - молодец, стал рисовать - еще больший молодец. :) В чем бред?

← →
Reindeer Moss Eater © (2007-04-10 14:46) [15]

я обычно прошу рассказать алгоритмы сортировки,
если человек не нравиться прошу рассказать шейкерную сортировку

Очень полезный навык для прикладного программиста-предметника.
Помогает выигрывать детсадовские, школьные и университетские олимпиады по программированию.

← →
DVM © (2007-04-10 14:50) [16]

> tesseract © (10.04.07 14:15) [7]

Это тест для художников.

> db2admin (10.04.07 14:07) [3]

Знание алгоритмов сортировки ничего не доказывает.

← →
Reindeer Moss Eater © (2007-04-10 14:53) [17]

>Знание алгоритмов сортировки ничего не доказывает.

И незнание тоже.
:)

← →
StriderMan © (2007-04-10 14:56) [18]

Да кто их помнит-то эти алгоритмы... В Инсте как изучил так и забыл. Ну квиксорт с напрягом может вспомню. Это специфические знания.

Я в первую очеред поинтресовался бы знаниями ООП, причем не определениями (я их и сам не произнесу правильно), а практической задачкой.

← →
Zeqfreed © (2007-04-10 14:57) [19]

А чем шейкерная такая интересная? Я вот квиксорт наизусть не помню :( Сортировку слиянием помню. Не возьмут меня на работу, эх.

← →
tesseract © (2007-04-10 14:59) [20]

> Это тест для художников.

Для ДАО - художников тогда. Просто тест на умение ставить конкретную задачу.

ТЗ "написать программу" - клёво звучит!!!!!!!!!!!!!!!!!!

← →
default © (2007-04-10 15:01) [21]

вот только не надо этих идиотских задачек про домики и сортировки:)

← →
default © (2007-04-10 15:02) [22]

хотя мне как-то самому дали задачу на сортировку, но та была не на знание алгоритмов сортировки, а на умение сходу порождать оригинальные решения

← →
db2admin (2007-04-10 15:04) [23]

Zeqfreed © (10.04.07 14:57) [19]
а ее обычно не знают ))

← →
Kolan © (2007-04-10 15:08) [24]

Проверить может ли класс от объекта отличить.

← →
tesseract © (2007-04-10 15:13) [25]

> а ее обычно не знают ))

Так от неё пользы практической никакой :-). Лучше переставкой или etc.

← →
Павел Калугин © (2007-04-10 15:13) [26]

Пару запросов на "подумать" и беседа по результатам тестирования.

← →
_Аноним (2007-04-10 15:17) [27]

Сортировка не в тему, согласен.

Мы давали обычно вот такое задание: сажали за компьютер,
минут за 30-40 написать программку
на форме кнопка и три-вью
по нажатию на кнопку появляется диалог выбора папки
по нажатию на OK три вью заполняется содержимым выбранной папки

пользоватеся при этом можно хелпом, нельзя интернетом.

как ни странно тех, кто решил задачу, было очень мало.
(две трети отсеялись сразу по незнанию функции SelectDirectory)

← →
pasha_golub © (2007-04-10 15:18) [28]

Я, кстати, только "бульбашками" (укр., пузырьками) помню. Преинтересный случай был у меня с ним.

На 5 курсе на практике давал методы сортировки, и пузырь, как типа основной. Жена с утра собирается на учебу и из кухни кричит: "Тебе суп нагреть?". Я в полудреме: "Конечно, только методом бульбашек грей!"

После этого она меня разбудила и заставила рассказать, что это за метод такой.

← →
default © (2007-04-10 15:23) [29]

предлагаю тут повыкладывать задачки на сообразительность кому какие поподались на собеседованиях, будет интересно

← →
ferr © (2007-04-10 15:23) [30]

> На 5 курсе на практике давал методы сортировки, и пузырь,
> как типа основной.

боже милостивый.. господе исусе..

← →
Gero © (2007-04-10 15:27) [31]

> Мы давали обычно вот такое задание: сажали за компьютер,
>
> минут за 30-40 написать программку
> на форме кнопка и три-вью
> по нажатию на кнопку появляется диалог выбора папки
> по нажатию на OK три вью заполняется содержимым выбранной
> папки
>
> пользоватеся при этом можно хелпом, нельзя интернетом.

Ну такие задания можно давать, чтобы отсеять тех, кто полный 0 и не тратить на них время при собеседоввании. Более сложные задания, на мой взгляд, стоит давать только в случае узкой специализации.

← →
MBo © (2007-04-10 15:56) [32]

О базовых алгоритмах и структурах данных, конечно, нужно представление иметь. На примере сортировок - это не значит, что человек код квиксорта обязан наизусть помнить, но должен по крайней мере понимать, какую сортировку выгодно использовать в конкретном случае, а какую - вредно

← →
tesseract © (2007-04-10 16:09) [33]

> предлагаю тут повыкладывать задачки на сообразительность
> кому какие поподались на собеседованиях, будет интересно

Было как-то "А как tlb в exe или dll храниться у Com-сервера " ? :-)

← →
default © (2007-04-10 16:10) [34]

tesseract © (10.04.07 16:09) [33]
тьфу...:)

← →
tesseract © (2007-04-10 16:16) [35]

> default © (10.04.07 16:10) [34]

Подкололся ?

← →
_Аноним (2007-04-10 16:17) [36]

> Gero ©

> Ну такие задания можно давать, чтобы отсеять тех, кто полный
> 0

В общем то да, для этого и давали.

с другой стороны, если человек (по подобном тесту) не полный 0, то дальнейшее проф. тестирование не проводилось, дальше разговор был о "где работали ,что делали", ну и также попытки понять, насколько он впишется "по психологии". Но тут уже гарантированно в процессе собеседования ничего не поймешь, имхо.
То есть иногда можно понять, что "нет", но понять, что "да", нереально.

← →
default © (2007-04-10 16:21) [37]

tesseract © (10.04.07 16:16) [35]
я про другие задачи спрашивал:)

← →
pasha_golub © (2007-04-10 16:27) [38]

> ferr © (10.04.07 15:23) [30]

> боже милостивый.. господе исусе..

Какое конкретно словосочетание вызвало такую бурю эмоций? :)

← →
default © (2007-04-10 16:28) [39]

pasha_golub © (10.04.07 16:27) [38]
вероятно это
> На 5 курсе на практике давал методы сортировки, и пузырь,
> как типа основной.

← →
Плохиш © (2007-04-10 16:36) [40]

> MBo © (10.04.07 15:56) [32]
> О базовых алгоритмах и структурах данных, конечно, нужно
> представление иметь. На примере сортировок - это не значит,
> что человек код квиксорта обязан наизусть помнить, но должен
> по крайней мере понимать, какую сортировку выгодно использовать
> в конкретном случае, а какую - вредно

order by 1

Блин не возьмут на работу...

> _Аноним (10.04.07 16:17) [36]

Во людям заняться нечем 8-О
Всегда считал, что первым идёт конкурс заявлений (на туалетной бумаге - в корзину не читая, оформление не понравилось - в корзину, повторное использование - в корзину, с ошибками - в карзину), следующий этап - собеседование и уже оставшимся даётся тест...

← →
TUser © (2007-04-10 16:36) [41]

Дай ему полку с книгами и прикажи не выкладывая книги на пол или на стол или на другую полку расставить книги по алфавиту. Можно и соревнования по такому программированию устраивать.

Одна из книг на полке сшита пьяным переплетчиком, который страницы 1000-1010 вставил на место после страницы 892. Найти участок, где страницы вставлены неправильно.

Та же задача, если в книге 100 томов с единой нумерацией (но, возможно с разным числом страниц в томе). Общее число страниц неизвестно.

Купить игрушечную железную дорогу и коробку кубиков. Кубики-города расставить на полу. Спроектировать железнодорожные линии, соединив вместе все города (пусть и ненапрямую), кто быстрее соберет дорогу, тот и молодец.

Спроектировать расписание движения поездов на построенных линиях про задынных максимальных пасажжиропотоках. Число вагонов в поезде может быть произвольным. Если учтет, что на перегоне однокалейки не может оказаться сразу два поезда - то это плюс, возможно сумеет везде использовать критические секции и пр.

Описать в стихах муки древневавилонских школьников, вынужденных идучать таблицу умножения для 60-ной системы исчисления.

...

← →
_Аноним (2007-04-10 16:50) [42]

> Плохиш ©

> Всегда считал, что первым идёт

Все так. Только собеседование как раз и начинается с теста.
Пробовали и наоборот - получилось, что в большинстве случаев зря потратили время. И вот что обидно - вроде человек все гладко рассказывает, уже про себя думаешь "ага.. наконец то"
а потом тест - и все, полный привет. Каждый раз разочарование :-)

Потом мы стали делать по другому - заменили тест на бумажный.
15 вопросов (простейших).
например:
найдите ошибку в коде:
procedure ClearList(List: TList);
var
I: Integer;
begin
for I:=0 to List.Count do
List.Delete(I);
end;

В общем то, полностью все равно никто не ответил.

← →
IA (2007-04-10 17:03) [43]

Я обычно даю кусок кода, который в себя включает некоторое количество недочетов и ошибок. Непроверка на null, неосвобождение ресурсов в finally, public переменные в классе и проч и проч. Очень мало кто видит хотя бы половину.
На дизайн у меня любимый вопрос - автоматическая парковка. Нарисовать систему машина - гараж для парковки без человека, кто и чем управляет.
Самое хорошее в этой задаче - у нее нет правильного ответа.

> procedure ClearList(List: TList);
> var
> I: Integer;
> begin
> for I:=0 to List.Count do
> List.Delete(I);
> end;

В этом коде _две_ ошибки.

← →
pasha_golub © (2007-04-10 17:04) [44]

> default © (10.04.07 16:28) [39]

А почему бы 11-классникам не дать алгоритм сортировки пузырем как основной?

← →
ferr © (2007-04-10 17:13) [45]

> А почему бы 11-классникам не дать алгоритм сортировки пузырем
> как основной?

Потому что это глупо. Иногда возникают задачи где требуется отсортировать порядка 100 элементов, но даже в таких случаях рекомендуется использовать другие квадратичные алгоритмы, например SelectionSort, который программируется ничуть не сложнее пузырька. А вот как основной надо подавать что-то логрифмичесое, я бы предпочёл MergerSort, хотя она и не по месту, зато устойчивая и достаточно простая. В java например реализовано именно она.

← →
isasa © (2007-04-10 17:20) [46]

IA (10.04.07 17:03) [43]
В этом коде _две_ ошибки.
:)
... и, вообще, удаление так никто не пишет ...

← →
_Аноним (2007-04-10 17:22) [47]

> В этом коде _две_ ошибки.

Совершенно верно. Процентов 70 увидели только одну.

← →
default © (2007-04-10 17:23) [48]

pasha_golub © (10.04.07 17:04) [44]
а смысл это декларировать как основной метод?

← →
Юрий © (2007-04-10 17:25) [49]

> [43] IA (10.04.07 17:03)

Вторая ошибка проверка на NIL?

← →
_Аноним (2007-04-10 17:27) [50]

> Юрий ©

Проверка на nil - это действительно чаще всего ошибка. Тут ее нету :-)

← →
Юрий © (2007-04-10 17:27) [51]

> [50] _Аноним (10.04.07 17:27)

Я это и имел в виду. :)

← →
tesseract © (2007-04-10 17:28) [52]

> Вторая ошибка проверка на NIL?

первая ошибка - размерность list.

вторая Delete довольно скоро будет уничтожать несуществующие элементы list-а.

← →
Юрий © (2007-04-10 17:29) [53]

> [52] tesseract © (10.04.07 17:28)

Умываю руки.

← →
Gero © (2007-04-10 17:31) [54]

> [47] _Аноним (10.04.07 17:22)
> > В этом коде _две_ ошибки.
>
> Совершенно верно. Процентов 70 увидели только одну.

Процентов 70 среди кого? Студентов первого курса? Мне кажется, ошибки слишком очевидны, чтобы можно быть говорить о каком-то уровне тестируемого.

← →
tesseract © (2007-04-10 17:32) [55]

> Юрий © (10.04.07 17:29) [53]

С подобным приколом при работе с Tlist/ДинМассивами в приниципе столкнулся на 3 месяц работы программистом :-) Весьма часто попадающийся костыль у новичков.

← →
Юрий © (2007-04-10 17:33) [56]

> [55] tesseract © (10.04.07 17:32)

Я почему то сразу подумал, про проверки, туда-сюда... Смотришь в книгу, видишь ...

← →
isasa © (2007-04-10 17:44) [57]

Юрий © (10.04.07 17:33) [56]
:)
... главное TLict.Count свеженький брать ...
а for ... downto или while дело десятое

← →
_Аноним (2007-04-10 17:48) [58]

> Gero ©

> Процентов 70 среди кого?

Среди тех, кто пришел на собеседование.
То есть среди тех, чье резюме не отправилось в корзину сразу.
(а куча резюме отправилась в нее сразу по причинам, описанным Плохишом выше).

> tesseract ©

> Весьма часто попадающийся костыль у новичков.

ну как раз ставка сделана на то, чтобы проверить - а правда ли есть опыт. Если есть, костыль был, то ответ готов сразу :-)

← →
StriderMan © (2007-04-10 17:48) [59]

> tesseract © (10.04.07 17:28) [52]

+1, я сразу внимание обратил :)

кстати про листы. обычно принято очищать листы "обратным" циклом от Count-1 do 0. Я, пока этого не знал, придумал другой способ:

while List.Count > 0 do
List.Delete(List.Count - 1);

не нужна переменная i :)

← →
Чапаев © (2007-04-10 17:48) [60]

> [54] Gero © (10.04.07 17:31)
Я только со второй попытки обнаружил, что цикл от 0 до List.Count, а не до List.Count-1. Сам бы такой ошибки не допустил, на бумажке чужую наверняка не заметил бы...

← →
tesseract © (2007-04-10 17:51) [61]

> ... главное TLict.Count свеженький брать ...а for ... downto
> или while дело десятое

For i:=0 to List.count-1 do
begin
dispose(list[0])
list.delete(0);
end;

Вроде должно сработать без утечек, хлтя репа ща чугунная.

← →
Gero © (2007-04-10 17:52) [62]

> [42] _Аноним (10.04.07 16:50)
> найдите ошибку в коде:

Вобще нехорошо, что говорится про ошибку. Тогда ответ про Count  1 можно считать верным.

← →
isasa © (2007-04-10 17:54) [63]

Кстати о птичках. В данной ситуации постановка вопроса

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

← →
Юрий © (2007-04-10 17:56) [64]

> [57] isasa © (10.04.07 17:44)

В любом случае, делать тут мне нечего, пошёл топится. :о)

← →
Ega23 © (2007-04-10 17:56) [65]

for i:=List.Count-1 downto 0 do List.Delete(i);

Но, впрочем, дело-то не в этом. ИМХО, главное тут - желание работать.

← →
_Аноним (2007-04-10 17:58) [66]

> Gero ©

Формулировка была такая:
"Найдите в приведенных примерах ошибки, если они есть"
и было 5 примеров - это один из них.
второй был на тему: "функция вернула PChar (result:=PChar(s)) , а s - локальная переменная типа string
еще один был вообще без ошибок.

← →
default © (2007-04-10 18:00) [67]

> может вогнать испытуемого в ступор, т.к. приведен, совсем
> не корректный код, а человек волнуется, стрессовое состояние,
> может и в морду дать, что бывало. :)

про морду можно поподробнее!

← →
isasa © (2007-04-10 18:08) [68]

default © (10.04.07 18:00) [67]
про морду можно поподробнее!
Давно, была тут ветка о том, как на собеседовании двое не поделили индексы. А TList, он, посерьезнее будет. :)

← →
Плохиш © (2007-04-10 18:09) [69]

> StriderMan © (10.04.07 17:48) [59]

> кстати про листы. обычно принято очищать листы "обратным"
> циклом от Count-1 do 0. Я, пока этого не знал, придумал
> другой способ:
>
> while List.Count > 0 do
> List.Delete(List.Count - 1);

Фигня, это круче:
List.Delete(0);
;-)

← →
isasa © (2007-04-10 18:15) [70]

Плохиш © (10.04.07 18:09) [69]

Фигня, это круче:
List.Delete(0);
;-)

Да ну, легче перегрузиться.:)

← →
default © (2007-04-10 18:16) [71]

проще вообще List.Clear:)

← →
Бишоп (2007-04-10 18:27) [72]

> Плохиш © (10.04.07 18:09) [69]
> Фигня, это круче:
> List.Delete(0);

да, прочитал и вспомнил, что так и делал :)))

> default © (10.04.07 18:16) [71]
> проще вообще List.Clear:)

кстати для TObjectList - самое оно

← →
StriderMan © (2007-04-10 18:27) [73]

> Бишоп (10.04.07 18:27) [72]

это я :)

← →
Юрий Зотов © (2007-04-10 19:03) [74]

Познавшие ДАО очищают списки так:

procedure ClearList(List: TList);
begin
List.Clear;
end;

:o)

← →
pasha_golub © (2007-04-10 19:03) [75]

> ferr © (10.04.07 17:13) [45]
>
> > А почему бы 11-классникам не дать алгоритм сортировки
> пузырем
> > как основной?
>
> Потому что это глупо. Иногда возникают задачи где требуется
> отсортировать порядка 100 элементов, но даже в таких случаях
> рекомендуется использовать другие квадратичные алгоритмы,
> например SelectionSort, который программируется ничуть
> не сложнее пузырька. А вот как основной надо подавать что-
> то логрифмичесое, я бы предпочёл MergerSort, хотя она и
> не по месту, зато устойчивая и достаточно простая. В java
> например реализовано именно она.

Роман, Вы заканчивали пед. ВУЗ? Вы понимаете, что такое информатика в средней неспециализированной школе и ее задачи?

← →
Чапаев © (2007-04-10 19:13) [76]

А мне сортировка выбором всегда представлялась проще пузырьковой... В том числе и в реализации.

← →
pasha_golub © (2007-04-10 19:20) [77]

> Чапаев © (10.04.07 19:13) [76]
>
> А мне сортировка выбором всегда представлялась проще пузырьковой.
> .. В том числе и в реализации.

Может быть. Это на рассмотрение преподавателя. Сам понимаешь, если у людей два часа (это в лучшем раскладе) в неделю, то тут не заборзеешь.

← →
ferr © (2007-04-10 19:22) [78]

> А мне сортировка выбором всегда представлялась проще пузырьковой...
> В том числе и в реализации.

Selection = выбор. Это факт - она лучше.

> Роман, Вы заканчивали пед. ВУЗ? Вы понимаете, что такое
> информатика в средней неспециализированной школе и ее задачи?

Я учусь(!) в техническом, с натяжкой сказать вузе. Ну если так подходить тогда думаю лучше контр-страйк установить..

P.S. MergeSort, опечаточка.

← →
ferr © (2007-04-10 19:25) [79]

С вашего позволения вставлю некоторые свои "выкройки". При сортировке целых чисел мною были получены следующие результаты(мс).
Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761 Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936 Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436 Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597 InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466 QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100 QuickSortO 0.0016 0.0040 0.0092 0.0210 0.0468 0.1000 0.2250 0.4910 1.0600 2.2800 4.8700 10.410 23.270 HeapSort 0.0027 0.0061 0.0136 0.0305 0.0678 0.1493 0.3261 0.7000 1.5400 3.3800 7.4100 15.930 37.570 MergeSort 0.0015 0.0042 0.0104 0.0251 0.0571 0.1290 0.2871 0.6339 1.3996 3.0379 6.9225 15.633 35.464

← →
ferr © (2007-04-10 19:27) [80]

Съехало, есть основания полагать что из-за DMClient"а, ибо в блокноте всё было замечательно.

← →
ferr © (2007-04-10 19:32) [81]

Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761 Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936 Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436 Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597 InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466 QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100 QuickSortO 0.0016 0.0040 0.0092 0.0210 0.0468 0.1000 0.2250 0.4910 1.0600 2.2800 4.8700 10.410 23.270 HeapSort 0.0027 0.0061 0.0136 0.0305 0.0678 0.1493 0.3261 0.7000 1.5400 3.3800 7.4100 15.930 37.570 MergeSort 0.0015 0.0042 0.0104 0.0251 0.0571 0.1290 0.2871 0.6339 1.3996 3.0379 6.9225 15.633 35.464
Попробую ещё разок вставить, через вебформу.

← →
ferr © (2007-04-10 19:35) [82]

Премного перед всеми извиняюсь, особенно перед DMClient"ом ;-). Сам дурак.

P.S. Хотел лишь показать что BubbleSort самый медленный..

← →
IA (2007-04-10 19:40) [83]

Две ошибки, как уже сказано выше многократно, это

просто неправильный код, который приведет к AV. Ну а count или count -1, и Delete(i) это уже не существенно, считаем как одну. Вторая - это проверка на nil, человек который такое не заметил или "переписал" с list.Clear() на позицию выше начального уровня не годится, по-моему. В принципе, красиво - первая отсекает чайников, а вторая - кодеров.

← →
IA (2007-04-10 19:47) [84]

> P.S. Хотел лишь показать что BubbleSort самый медленный.
> .

Хм. А для этого надо тесты проводить? К тому же выводы у вас неправильные. Идите перечитывайте Кнута.

← →
ferr © (2007-04-10 19:53) [85]

> Хм. А для этого надо тесты проводить?

Нет, тесты я проводил для сравнения логарифмических методов.

> К тому же выводы у вас неправильные.

С этого места попрошу поподробнее. Я вроде и выводов-то никаких не делал..

> Идите перечитывайте Кнута.

Предлагаю обойтись без взаимопосылательства.

← →
IA (2007-04-10 19:58) [86]

> > К тому же выводы у вас неправильные.
>
> С этого места попрошу поподробнее. Я вроде и выводов-то
> никаких не делал..

Да? А это что?

> P.S. Хотел лишь показать что BubbleSort самый медленный

"На тестированном объеме и структуре данных". В ВУЗах уже не учат не делать глобальные выводы из частного случая?

>> Идите перечитывайте Кнута.

>Предлагаю обойтись без взаимопосылательства.

Ничего личного, но вам действительно надо почитать Кнута. Я даже сделал допуск что вы его уже читали.

← →
ferr © (2007-04-10 20:28) [87]

> Да? А это что?
>
> > P.S. Хотел лишь показать что BubbleSort самый медленный
>
> "На тестированном объеме и структуре данных". В ВУЗах уже
> не учат не делать глобальные выводы из частного случая?

Пожалуй и соглашусь, и не соглашусь. Я преподнёс это как пример, а не как эксперимент, не углубляясь в детали. Я мог бы углубить описания и специализировать выводы, но не стал, ибо незачем. А раз дополнительно ничего не написано, то значит рассматривается общая ситуация(случайный вход). Следовательно от алгоритма ожидается среднее время работы.

← →
Loginov Dmitry © (2007-04-10 20:32) [88]

> найдите ошибку в коде:
> procedure ClearList(List: TList);
> var
> I: Integer;
> begin
> for I:=0 to List.Count do
> List.Delete(I);
> end;

На самом деле задание очень простое (в данном случае все ошибки выявились за пол-сукунды). Имхо, лучше чтобы было примерно так:

procedure ClearList(List: TList); var I: Integer; begin for I:=0 to List.Count do begin List.Delete(I); Dispose(List[I]); end; end;

Сколько тут ошибок? :)
Здесь уж соискателям действительно мало шансов :)

А вот отсутствие проверки Assigned(List), имхо, не является ошибкой.

← →
MsGuns © (2007-04-10 21:26) [89]

Короче, воин, который не знает, что такое "дао вэнь линь" - не джидай.

← →
Eraser © (2007-04-10 21:43) [90]

Автоматически написал бы через downto, т.к. на практике, когда появляется похожая задача, обычно нужно удалять не все элементы, то только некоторые, согласно какому-то условию, в этом случае, downto более читабелен, imho.

← →
IA (2007-04-10 22:06) [91]

> А вот отсутствие проверки Assigned(List), имхо, не является
> ошибкой.

Разумеется. А потом ищи где у юзера AV выскочило. Проверка аргументов должна быть во всех public & protected методах, и в private зачастую. Что делать если аргумент пустой, кидать ошибку или молча обходить зависит от конкретного случая.
Собственно, наличие подобного кода один из различительных признаков между профессиональным разработчиком и кодером на коленке.

← →
Loginov Dmitry © (2007-04-10 22:42) [92]

> [91] IA (10.04.07 22:06)

Очень и очень сильно зависит от ситуации. Если по контексту задачи в функцию ClearList() не может попасть нулевая или битая ссылка, то НЕ стоит делать подобных проверок. Если по контексту задачи допускается передача в функцию нулевого указателя, то проверка нужна.

> Проверка аргументов должна быть во всех public & protected
> методах

Опять же, сильно зависит от ситуации. Часто бывает, что лучше выкинуть ошибку.

← →
vasIZmax © (2007-04-10 23:08) [93]

Итак, некоторые итоги:
для проверки логики (точнее писать алгоритмы, программирование как ни как на алгоритмах строится) - рекомендовано использовать сортировки. (более подробно пост MBo © в [32]).

Так же немало важным считаю и

> Проверить может ли класс от объекта отличить.
,
все это хорошо, но теорию тож надо знать/понимать/(уметь) объяснить.

Ну и проверка на понимание/способность читать/корректировать чужой код/переработка и усовершенствование.

Вот получается основные критерии. Но, это имхо.

ЗЫ. Честно говоря думал "задания" будут "по легче": ну там компонентик наваять, или запросик сделать в БД, или что-нибудь с графикой - хотя это конечно же зависит от специализации).

ЗЫЫ. Не ошибся ли я с такими выводами?

← →
Mystic © (2007-04-11 02:03) [94]

Если вопрос по алгоритмам, могу попросить решить какую-то задачу... Например, максимально быстро получить список всех ходов в шахматах/шашках.

← →
TUser © (2007-04-11 06:32) [95]

> > procedure ClearList(List: TList);
> > var
> > I: Integer;
> > begin
> > for I:=0 to List.Count do
> > List.Delete(I);
> > end;
>
>
> В этом коде _две_ ошибки.

Зависит от архитектуры проекта в целом. Может так оказаться, что и три.

← →
MBo © (2007-04-11 06:43) [96]

Задача: Есть файл 16 гигабайт, содержащий числа Double. Как (эффективно) выбрать из него миллион наибольших чисел, если свободных памяти и дискового пространства только порядка 10 мегабайт?

← →
SlymRO © (2007-04-11 07:51) [97]

MBo © (11.04.07 6:43) [96]
array[миллион] of double - 7,63Мб какие сложности? самое главное этот милион сортированным держать.

← →
MBo © (2007-04-11 08:00) [98]

>SlymRO © (11.04.07 07:51) [97]
Хорошее начало. А дальше как?

← →
SlymRO © (2007-04-11 08:03) [99]

Задачка с ограничением на память...
Как проверить полный диск FAT32 максимального для FAT32 объема на отсутствие рекурсивных и пересекающихся цепочек файлов с ограничением по памяти 600кб (в досе) :)

← →
MBo © (2007-04-11 08:10) [100]

>SlymRO © (11.04.07 08:03) [99]
FAT - это же списочная структура, т.е примерно
файл-> первый кластер
кластер = record
Data: array[512]
Next: кластер
end;

так?

← →
SlymRO © (2007-04-11 08:14) [101]

MBo © (11.04.07 8:00) [98]
1.Читаем double
2. сравниваем с Min(из милиона)// если милион сортирован то с 1 значением
3. если больше то Min(из милиона) выталкиваем из милиона и вставляем новое значение (желательно с сохранением сортированности) (но тут трабла, на flat массиве много фетчей памяти)
4. из траблы п.3 появляется следующая задача: поддержание массива данных с сортированном состоянии при обновлениях с минимальным фетчем памяти

← →
SlymRO © (2007-04-11 08:16) [102]

MBo © (11.04.07 8:10) [100]
итого у тебя множество больших односвязных списков в одном адресном пространстве :) и тебе нужно проверить что разные приски не ссылаются на один и тотже элемент, и что нет зацикливаний элементов

← →
MBo © (2007-04-11 08:18) [103]

>SlymRO © (11.04.07 08:14) [101]
ОК, значит, задача свелась к тому, чтобы эффективно поддерживать сортированную структуру, и быстро удалять из нее.

← →
MBo © (2007-04-11 08:22) [104]

>SlymRO © (11.04.07 08:16) [102]
Ага. А сколько может быть начальных кластеров (файлов) - есть ограничения?
Естественное ограничение MaxInt/размер кластера, т.е. порядка 2^22 файлов для кластера 512 байт, или более сильное?

← →
SlymRO © (2007-04-11 08:24) [105]

MBo © (11.04.07 8:18) [103]
свелась
Как в геометрии доказали теорему сославшись на другую доказанную теорему, Доказательство которой нет необходимости приводить за необходимостью доказать только исходную теорему.

← →
SlymRO © (2007-04-11 08:29) [106]

MBo © (11.04.07 8:22) [104]
http://ru.wikipedia.org/wiki/FAT32

← →
MBo © (2007-04-11 08:30) [107]

>MBo © (11.04.07 08:22) [104]
>Ага. А сколько может быть начальных кластеров (файлов) - есть ограничения?

пардон, это я,пожалуй, зря спросил, к ограничениям задачи это не имеет отношения.

>SlymRO © (11.04.07 08:24) [105]
>Как в геометрии доказали теорему сославшись на другую доказанную теорему,

;) нее... Логика предоставила начальные условия для решения задачи, а далее требуются некоторые знания по структурам данных и алгоритмам

← →
ferr © (2007-04-11 08:46) [108]

← →
MBo © (2007-04-11 09:06) [109]

ОК. Про рекурсивные цепочки я уже знал (нахождение цикла в однонаправленном списке, давал в пятничнх задачах), а для пересекающихся цепочек диска с количеством кластеров до 2^27 (мин. 68 Гиг, что больше ограничения в досе 2 гиг и в Win32 - 32 Гиг) придумалось обнаружение факта пересечения c затратами 512 Кб

← →
SlymRO © (2007-04-11 09:50) [110]

MBo © (11.04.07 9:06) [109]
придумалось
Последние сектора на уникальность? тест прошел...

← →
MBo © (2007-04-11 09:53) [111]

>Последние сектора на уникальность?
Нет, до этого не допер.
Битовый массив использовал.

← →
SlymRO © (2007-04-11 09:54) [112]

MBo © (11.04.07 9:53) [111]
Это что я зря ответ выложил?!
А про "Битовый массив" поподробней?

← →
Loginov Dmitry © (2007-04-11 10:00) [113]

> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

Я бы использовал TFileStream. По первых - универсальнее (позволяет и на Win9x обрабатывать весьма большие файлы). Во вторых - более переносимо (потоки будут работать не только по Винду). В третьих - файловые потоки очень мало уступают в плане скорости технологии FileMapping, если конечно не читать файл по байтам :) В четвертых - потоки проще использовать для обработки действительно больших файлов (хотя кому то может не влом лишний раз будет сделать MapViewOfFile()). В пятых - файловые потоки более экономно работают с памятью (при неумении правильно работать с FileMapping"ом :)

← →
ferr © (2007-04-11 10:07) [114]

> Я бы использовал TFileStream. По первых - универсальнее
> (позволяет и на Win9x обрабатывать весьма большие файлы)
> . Во вторых - более переносимо (потоки будут работать не
> только по Винду). В третьих - файловые потоки очень мало
> уступают в плане скорости технологии FileMapping, если конечно
> не читать файл по байтам :) В четвертых - потоки проще использовать
> для обработки действительно больших файлов (хотя кому то
> может не влом лишний раз будет сделать MapViewOfFile()).
> В пятых - файловые потоки более экономно работают с памятью
> (при неумении правильно работать с FileMapping"ом :)

Лишь бы что-то ляпнуть, да? Вот причём здесь компонент инкапсулирующий чтения из файла.. Задача стояла в выборе структуры данных для обработки уже считанных данных..

P.S. щас кто-нибудь придёт и скажет что TFileStream гавно, т.к. java ...

← →
KSergey © (2007-04-11 10:08) [115]

Каждый приводит из той области, где копался сам... Вот и все :(

> MBo © (11.04.07 06:43) [96]
> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

И смысл от таких задач по большому счету?
Если пишется код для embeded контроллеров - да, очевидно будет иметь смысл умение/знание всяких таких штук. Или если дисковые тулзы контора пишет - да, тут тоже критично, видимо.

А мне вот - нафиг такое ни раз не понадобилось. Равно как и сортировки - SQL сервер и так сортирует, а накладные расходы в клиентском коде по манипулированю данными в сравнении с ресурсами и временем, которые жрутся SQL-сервером - да просто пренебрежительно малы! Не говоря уже про, например, отъедаемые ресурсы платформой .NET, например. Это ж какую надо прогу наваять, чтобы это перекрыть? Замучаешься.

Реальная задача из практики - укажи какое нужно железо, чтобы эта прога обслуживала 1000 клиенстких подключений при приемлемом (нравится мне конкретность этого слова) времени отклика. А 100 000?

Или того хуже: вот тебе софтина, напиши цифирьки какое нужно железо. чтобы она обслуживала 1000 клиенстких подключений при приемлемом времени отклика. Нет, железа мы тебе не дадим для симуляции всего этого, нету его. Давай в тырнете чего-нибудь найдем, или проведи тестики и экстаполируй.

Т.е. умеет ли пользовать google (читай: литературу) для решения новых задач.

Хотя, конечно, собеседование - оно чтобы выявить чего вообще знает и умеет собразить, куда забурялся хоть раз...

← →
KSergey © (2007-04-11 10:16) [116]

> IA (10.04.07 22:06) [91]
> > А вот отсутствие проверки Assigned(List), имхо, не является
> > ошибкой.
>
> Разумеется. А потом ищи где у юзера AV выскочило. Проверка
> аргументов должна быть во всех public & protected методах,
> и в private зачастую.

Замечательно.
Пусть наша супер-пупер функция поимела след. вид:

procedure ClearList(List: TList); var I: Integer; begin if Assigned(List) then begin ... //как-то супер правильно чистим. end; end;

и пусть я вызвал ее следующим образом:

var
SuperPuperList: TList;
...
SuperPuperList := TList.Create();
SuperPuperList.Free();
ClearList(SuperPuperList);

Вопрос: что я выиграю в случае наличия проверки Assigned(List)?

Только не надо говорить, что вызывающий код не верен: раз уж мы взялись проверять аргументы, то логично (на мой взгляд) предположить, что наша мега функция будет однозначно детектировать корректность/не корректность входных параметров. Если же она этого не может - то какой смысл эту проверку добавлять?

← →
SlymRO © (2007-04-11 10:18) [117]

ferr © (11.04.07 10:07) [114]
гавно, т.к. java
я ооп изучал по java, фрактал мондельброта в распределенке делал... мне нравится жава...
[113] ржунимагу

← →
SlymRO © (2007-04-11 10:21) [118]

KSergey © (11.04.07 10:16) [116]
:)
procedure TThread1.Execute;
begin
Sleep(random(1000));
ClearList(SuperPuperList);
end;

procedure TThread2.Execute;
begin
Sleep(random(1000));
SuperPuperList.Free;
end;

← →
Loginov Dmitry © (2007-04-11 10:23) [119]

> Лишь бы что-то ляпнуть, да? Вот причём здесь компонент инкапсулирующий
> чтения из файла.. Задача стояла в выборе структуры данных
> для обработки уже считанных данных..

> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

Я-то может и загнался малось, но формум-то по Дельфи, вот я и думаю, как можно было бы данную задачу реализовать на Дельфи...

← →
_Аноним (2007-04-11 10:27) [120]

> IA

> Разумеется. А потом ищи где у юзера AV выскочило. Проверка
> аргументов должна быть во всех public & protected методах,
> и в private зачастую.

не ввовдите людей в заблуждение, кто-то может и поверить.

> Что делать если аргумент пустой, кидать ошибку или молча
> обходить зависит от конкретного случая.

А вот за это увольнять надо. И никакой Кнут не поможет

← →
ferr © (2007-04-11 10:30) [121]

> Задача стояла в выборе структуры данных
> > для обработки уже считанных данных..

Т.е. имелось ввиду то что данные каким-то неведом нам образом поступают нам на вход.. И надо предложить эффективный способ отыскания наибольших чисел. Ответом к задачи является слово куча(Heap). А на каком языке это писать и что испольовать это дело десятое.

← →
Чапаев © (2007-04-11 10:39) [122]

> > Что делать если аргумент пустой, кидать ошибку или молча
> > обходить зависит от конкретного случая.
> А вот за это увольнять надо.
Думаю, имелось в виду, что для "нулевого" аргумента может быть какой-нибудь "нулевой" результат.

← →
_Аноним (2007-04-11 10:44) [123]

> Чапаев ©

Я полагаю так.
Если нулевой аргумент - это штатная ситуация, то тогда проверять разумеется надо. Если это ситуация нештатная (ошибка программиста), то не надо.

← →
REA (2007-04-11 10:50) [124]

Мой патентованный тест для отсева новичков (старенький уже, пора обновить):

Контрольные вопросы (отвечать максимально полно; если имеется, указывать опыт работы)
Что такое Int21h?
Что такое IRQ3?
Что такое DMA?
Что такое EMS, UMB, XMS?
Что такое LBA?
Что такое IPX?
Что такое CMOS?
Что такое PCI, PCMCIA?
Что такое PCAD?
Что такое FIDO?
Что такое IDE?
Что такое FAT, HPFS, NTFS, WinFS?
Что такое GDI, GDI+?
Что такое DDE, IPC?
Что такое OLE?
Что такое MDI?
Что такое VxD?
Что такое DLL?
Что такое ADO, DAO, ODBC, BDE?
Что такое MAPI?
Что такое RTL?
Что такое USB?
Что такое TSR?
Что такое QNX?
Что такое SQL?
Что такое NNTP, SMTP, SOAP?
Что такое CGI, ISAPI, NSAPI?
Что такое API, SDK, DDK?
Что такое RTTI?
Что такое IDDQD, RTFM, LMD?
Что такое MSDN?
Что такое COM, RPC, DCOM, COM+?
Что такое WDM?
Что такое UML?
Что такое .Net, C#?
Что такое CHM?
Что такое XML, ASP, CDO?
Что такое RFC?

> _Аноним (11.04.07 10:44) [123]
> Я полагаю так.
> ... то тогда проверять разумеется надо.
> ... то не надо.

Да фиг с ним с проверкой.
Увольнять то будем или нет?

> REA (11.04.07 10:50) [124]
> Мой патентованный тест

Абалдеть!
А может поделитесь главным: как результаты интерпретируете?

> Что такое IDDQD, RTFM, LMD?

+5

← →
_Аноним (2007-04-11 11:00) [128]

>REA (11.04.07 10:50) [124]
А где ответы на это можно почитать ?

У нас на прошлой работе была анкета, в ней вопрос:
"Уровень владения компьютером" и варианты ответов "On/Off, C&C, <и что-то еще>". Обычно у народа на C&C взгляд даже не останавливался :)

а что значит C&C ?

комманд энд конкур?

← →
REA (2007-04-11 11:23) [134]

Результаты на глаз интерпретируются, ответы все в интернете :)

Я так и подумал :)

> Что такое IDDQD, RTFM, LMD?

Только вчера писал скрипт на начальное заполнение базы. Написал автоматом, потом задумался:
Insert into AccessRoles (AccRoleID, AccRoleNam, AccRoleLab, AccRoleMsk, AccRoleOrd, AccRoleNot) Values (0, "Разработчег", "IDDQD", 1, 0, "God Mode");

> REA (11.04.07 11:23) [134]
> Результаты на глаз интерпретируются

По каким критериям?
Ну положим, кандидат будет с упоением рассказывать обо всех граблях, на которые он наступил при юзании интерфейса Int21h? и даже сможет перечислить половину комадн из этого интерфейса на память? А так же подробно расскажет о том, как он выпивал с Васлием Иванычем лично из именной кружки. (Ибо сказано: "указывать опыт работы".) и что? В вашей конторе есть отделы под все эти ключевые слова?

>Loginov Dmitry
Если в данном случае неправильно организовать обработку данных, то время на чтение файла будет ничтожно мало, и метод не будет иметь значения.

>KSergey
Ну автор поста в самом начале еще говорил
>Ясное дело, что у всех интересы/специализация разная(кто работает напр. с БД, а кто-то с графикой),

Вот и я подкинул то, что мне ближе

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

Речь о 16 гигабайтах же вроде? :) Время на чтенее в любом случае не может быть ничтожно малым.

> на которые он наступил при юзании интерфейса Int21h?

Гм вроде это не интерфейс, а функция bios для работы с фс.

> tesseract © (11.04.07 12:05) [141]
> > на которые он наступил при юзании интерфейса Int21h?
> Гм вроде это не интерфейс, а функция bios для работы с фс.

"Ти как хочишь эта назави!" :)
Вопрос терминологии, по-моему.

> Гм вроде это не интерфейс, а функция bios для работы с фс.

А я бы назвал «сервис».

> функция bios для работы с фс.
Уууууу, совсем низачот... ;-) Биос к int 21h никакого отношения не имеет, да и работа с фс -- только малая часть функций.

>KSergey
>А мне вот - нафиг такое ни раз не понадобилось.

может, я ошибаюсь, но мне кажется, что несколько лет назад ты сталкивался с задачей размещения текстовых кусков на газетном листе.
Это алгоритмическая задача комбинаторной оптимизации, умением SQL-запросы писать тут не отделаешься, так что не все так просто, наверно...

>SlymRO © (11.04.07 09:54) [112]
>А про "Битовый массив" поподробней?
Заводим массив байтов длиной Число кластеров/8, вначале обнуляем.
Проходим цепочки каждого файла, для каждого номера кластера выставляем соответствующий бит (бит номер (i mod 8) в байте [i div 8] в 1, если он нулевой. Если он уже был единичным - нашли пересечение.
C числом кластеров я наврал, максимум получается 2^22, но для доса хватит ;)

> Уууууу, совсем низачот... ;-) Биос к int 21h никакого отношения
> не имеет, да и работа с фс -- только малая часть функций.
>

Я на экзамен по асм под ДОС и не записывался :-)

> MBo © (11.04.07 12:31) [145]
> может, я ошибаюсь, но мне кажется, что несколько лет назад
> ты сталкивался с задачей размещения текстовых кусков на
> газетном листе.

А ведь и правда... вот ведь как оно: из конторы ушел - и все начисто позабыл...

>homm © (11.04.07 11:57) [140]
>Речь о 16 гигабайтах же вроде? :) Время на чтенее в любом случае не может быть ничтожно малым.

Мало относительно обработки. Порядок времени чтения - 1000 секунд.
Если допустить, что у нас есть неограниченная память, то любая из быстрых сортировок такого массива займет не меньше времени, а при ограничении ресурсов - несравненно больше.

> любая из быстрых сортировок такого массива займет не меньше времени

Дак нам же вроде не требуется именно его сортировать нужно сортировать только милин значений, но правда 16 миллиардов раз :)

Хм. Везде куда я приходил или меня приглашали, вопрос собеседования был один:
покажи что писал. Реже еще код спрашивали...
Этого не достаточно, чтобы определить профессионализм программера?

P.S.
Только одно собеседование в жизни было нормальным, на тестера и то там задавали вопросы по программированию...
Имел глупость сказать, что писал сетевые приложения... И на вопросе под 1 или 2 завалился? Вылетело напрочь из головы, что винсоков две версии...

homm © (11.04.07 12:43) [149]
>Дак нам же вроде не требуется именно его сортировать нужно сортировать только милин значений, но правда 16 миллиардов раз :)

Вот в том-то и дело, что применив подходящую структуру данных - очередь по приоритетам на основе Heap в массиве, как ferr написал, мы радикально сократим время обработки. Подробнее:
1. Заводим массив длиной миллион, читаем в него первый миллион чисел.
2. Выполняем его упорядочение кучей с минимумом на вершине
3. Читаем очередное число (для скорости, конечно, блоками, например, по мегабайту), сравниваем его с текущим минимумом, и если оно больше, удаляем старый минимум, вставляем новое число, восстанавливаем пирамидальность кучи.

Если в файле N чисел, а нужно выбрать M, то затраты:
на чтение: O(N)
на первоначальное упорядочение: O(M)
на обработку последующих чисел:
Лучший случай - O(N) - для убывающего файла
Худший случай - O(N Log M) - для возрастающего файла

Общее асимптотическое время, т.о., O(N Log M)

> 2. Выполняем его упорядочение кучей с минимумом на вершине

Что имеется ввиду под упорядоченностью? Если сортировка, то это имхо избыточно. Нужно только что-бы минимальный элемент всегда был сверху (либо был известен его номер, что одно и то-же) А отсортировать мы можем и в конце. Так не оптимальнее?

> @!!ex © (11.04.07 12:46) [150]
> покажи что писал. Реже еще код спрашивали...

О, к слову:
Как-то в переписке с одной конторой меня попросили привести куски имеющихся текстов на ASP.NET (моего исполнения, в смысле).
На что я ответил, что своих у меня нет, т.к. дома от нефиг делать уже давно этим не занимаюсь, а присылать куски корпоративного кода даже и писанные мною - считаю не этичным и, кроме того, явно противоречащим взятым на себя обязательствам. Но могу сделать тестовое задание какое предложите".
На что ответа не последовало вовсе (хотя до этого переписка была, по другим технологиям).
Может я чего не того сказал? Мне просто любопытно.
(Впрочем, вполне вероятно, что проблема была совсем не в том :) .)

Вообще, корректный ответ - очередь с приоритетами. То, что она построена на куче - это уже частный случай ;)

>Что имеется ввиду под упорядоченностью?
Свойство кучи (бинарной пирамиды) - полное двоичное дерево, каждый элемент меньше обоих дочерних элементов, но дочерние элементы между собой неупорядочены (в отличие от бинарного дерева поиска, в котором левый элемент меньше родителя, а правый больше). При нумерации массива с единицы детками I-го будут 2*I и 2*I+1
Вот пример такого упорядочения: 1 2 4 5 3 7 5
Все это позволяет хранить данные в массиве без дополнительного расхода памяти (в отличие от деревьев с узлами-указателями) и быстро восстанавливать Heap-порядок за LogM операций

>только что-бы минимальный элемент всегда был сверху (либо был известен его номер, что одно и то-же)
Пусть мы используем обычный массив, вначале отсортировали массив, первый элемент - наименьший.
Если очередной элемент больше минимума - куда вставлять его? Если на положенное место и сдвигать часть массива влево - затраты большие, в среднем порядка M/2 операций ,что для M=1000000 в десять тысяч раз хуже кучи. Если заменять минимум, а указатель минимума сдвигать на второй элемент - то после нескольких вставок весь порядок нарушится

> Если заменять минимум, а указатель минимума сдвигать на
> второй элемент - то после нескольких вставок весь порядок
> нарушится

Зачем нам упорядоченность никак не пойму :) Вставили этот элемен на место минимума, нашли номер теперешнего минимума (самая долгая операция), сравниваем следующий элемент с теперешним минимумом.

Впрочем по [155] видно, что мое знание матчасти в этом вопросе ... увы :)

>нашли номер теперешнего минимума (самая долгая операция),
Вот именно! этот поиск потребует порядка M операций, а нехитрое упорядочение кучей сокращает это время офигенно.

← →
db2admin (2007-04-11 13:58) [158]

int 21 это прирывание

> Думкин © (11.04.07 11:22) [132]
> Чапаев © (11.04.07 11:22) [133]
Угу, оно. Анкету ребята составляли, которые в то время всеми вечерами по сети баталии устраивали. Ну и типа пошутили :)

> Угу, оно. Анкету ребята составляли, которые в то время всеми
> вечерами по сети баталии устраивали. Ну и типа пошутили
> :)

тест на совместимость с коллективом :-)

← →
REA (2007-04-11 14:28) [161]

>Ну положим, кандидат будет с упоением рассказывать обо всех граблях, на которые он наступил при юзании интерфейса Int21h?

Ну уже неплохо. Опыт не пропьешь :) Я не претендую на объективность этого теста - на профессиональные знания нужны тесты другие, а этот обзорный, на эрудицию тсзть.

> REA (11.04.07 14:28) [161]
> Ну уже неплохо. Опыт не пропьешь :) Я не претендую на объективность
> этого теста - на профессиональные знания нужны тесты другие,

Какие проффесиональные знания можно было бы определить этим тестом?

> а этот обзорный, на эрудицию тсзть.

И какой пункт оценивает эрудицию?

PS. Тест по набору пионэров из песочницы...

Аааа.. тут меряются у кого длинее ;)))

Тогда вот таакой тест:

выпить за 3,5 часа 7,5 л. пива, а потом еще поллитры водки, "догнаться" портюшей (пара стаканОв) и на сон грядущий полирнуть стопарем свеколки (кто не в курсе, самогналь такой)..
А поутряни встать и сдать икзамен по сопромату на ХОРОШО.

СЛАБО, пацанва ???

← →
_Аноним (2007-04-11 22:08) [164]

Это кич сапроматом. :)

Ну раз пошла такая пьянка... то есть, кич... )

Тест по русскому языку. Стандартно, вставить буквы и запятые.
Подчеркиваю, вставить. Убирать уже стоящие запятые - нельзя.

Доп. условие - в одном из предложений уже стоящие запятые не оставляют шанса расставить знаки припинания правильно (мнение не только мое, но и моей учительницы русского).

Задача на слабо - получить 100 баллов из 100.

← →
REA (2007-04-12 14:15) [167]

>PS. Тест по набору пионэров из песочницы...

по отсеву. критиковать все горазды, давай твой вариант.

Я на собеседовании каждый раз спрашиваю про джойны и юнионы в SQL после стандартного опроса о былых проектах и достижениях.
Если вдруг человек знает что это такое, вопрос на отличие левого от правого. На это отвечает примерно 10% кандидатов.

левого джойна от правого

> Плохиш © (11.04.07 16:45) [162]
> PS. Тест по набору пионэров из песочницы...

Главное - тест не отнимает много времени у тестирующего. Однако сразу отвечает на вопрос стоит ли продолжать беседу :)

В общем-то, очевидно, "входной" тест таким и должен быть.

> второй был на тему: "функция вернула PChar (result:=PChar(s)
> ) , а s - локальная переменная типа string
Забавненько... Мне сегодня в тесте как раз такой вопрос подсунули... %-)

← →
Sergey Masloff (2007-04-14 09:31) [172]

Плохиш © (11.04.07 16:45) [162]
>PS. Тест по набору пионэров из песочницы...
Вот не просто согласен а абсолютно.
Все это фигня и технические детали которые усваиваются за два дня. С довольно большой вероятностью понять может ли человек думать можно из простой беседы не вставляя как обезьяна в нее шаблонные вопросы найденные в интернете. Понять может ли человек работать можно только по испытательному сроку. Если он не умеет думать или работать - дальше по хрен знает он джойн или детали работы с типами. Если он умеет - все детали при необходимости узнает.
Не имхо.

> Sergey Masloff (14.04.07 09:31) [172],

по вашей статистике, сколько примерно кандидатов умеют думать (работать)? И подразумевается ли под этим общая эрудиция или простая внимательность к задаваемым вопросам? Что тут есть работа? Придумывание оригинальных идей или "сделай мне это вот так"?

(я не иронизирую и ничего такого, интересно)

← →
Sergey Masloff (2007-04-21 23:15) [174]

capkoh © (21.04.07 22:50) [173]
У меня статистики нет а если бы была то она была бы необъективна. Исключительно по моему субъективному взгляду у нас из приходящих на собеседование берется на исп. срок 1% то есть на сто человек 1.
Из тех кого взяли на исп. срок остается работать 90%.
Но вообще из отсеяных еще 10-15% вполне нормальные но не подходят нам (или мы им) по косвенным причинам.
еще 10% небезнадежны но их учить и учить а на это ни времени ни сил.
Оставшиеся - по моему скромному - лучше бы им заняться чем-то другим.
Но это статистика с искажениями - до нас не доходят отсеянные кадровой службой.

Тестирование... на знание Найти похожие ветки