задачка

Хорошая программистская задачка:

Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).

Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.

P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.

лытдыбр

Заболел (довольно сильно простудился). Весьма некстати. Сижу дома и чихаю.

Самое время дать ссылку на запись birdwatcher'а о простуде. Я совершенно согласен с ним. Мне тоже обидно, что простуда не просто имеет вирусную природу, но даже успокоительные “лазейки”, которые я себе придумывал для того, чтобы как-то связать заражение простудой с охлаждением, не работают.

Кстати: у нас тут идёт Иерусалимский кинофестиваль. Я сходил в пятницу на подборку мультфильмов (оказалась ужасной совершенно) и сдох после этого: несколько дней уговаривал себя изучить программку и пойти ещё на что-то, но так и не нашёл ничего, что действительно бы манило. А сейчас ещё и заболел. Я это к тому, что нескольким людям я обещал поделиться своим выбором: извините, дорогие, я уже никуда в этот фестиваль не пойду. Вот singolare дорогой пишет о том, что они выбрали, и может ещё кто-то пишет. А я пас.

сэлинджер

virtualsushi раздумывает о том, чтобы переводить “Над пропастью во ржи” Сэлинджера, и предлагает сравнить два перевода первого абзаца — его и Райт-Ковалёвой.

Вот мой вариант того же. Дисклеймер: написано в больном состоянии и на очень скорую руку. Но критика всё равно принимается.

( Read more... )

Update: Оригинал этого абзаца см. в комментариях.