суббота, 12 февраля 2011 г.

Еще одно тестовое задание - собери плитки

Необходимо написать функцию link_tiles($tiles), которая сложит переданные в виде списка плитки последовательно и выведет на экран каждый шаг выкладывания плиток. Плитка - кварат, который поделен на 4 части, пронумерованные от 0 до 9. Плитка может быть приложена в том случае если хотя бы 2 числа подходят к соседним плиткам, но и остальные номера, если они прикладываются, тоже должны совпадать. Плитки можно поворачивать. Входные данные заданы таким образом, что всегда есть только 1 вариант расположения плиток.

Не надо думать о неккоретных данных или огромных наборах данных.

З.Ы. Хочу похвастаться, что сделал я его за 3 часа 50 минут. Дополнительно отправил еще и юнит-тесты. На сколько успешно - напишу позже.

Например:

$tiles1 = array(
 "11",     // 1
 "23",
 "",
 "44",     // 2
 "11",
 "",
 "16",     // 3
 "36",
 "",
 "51",     // 4
 "71",
 "",
 "46",     // 5
 "26",
 "",
 "14",     // 6
 "68",
 0);

link_tiles($tiles1) выведет:

6 tiles
link 1
11
23
 
link 2
44
11
11
23
 
link 3
44
11
1116
2336
 
link 4
  44
5111
711116
  2336
 
link 5 // note this tile had to be rotated 180 degrees clockwise
  44
5111
71111662
  233664
 
link 6 // note this tile had to be rotated 270 degrees clockwise
  4448
511116
71111662
  233664


$tiles2 = array(
 "12", // 1
 "34",
 "",
 "36", // 2
 "15",
 "",
 "56", // 3
 "78",
 "",
 "78", // 4
 "90",
 "",
 "46", // 5
 "26",
 "",
 "88", // 6
 "01",
 "",
 "93", // 7
 "54",
 0);


link_tiles($tiles2) выведет:

7 tiles
link 1
12
34

link 2 // note this tile had to be rotated 180 degrees clockwise
5112
6334

link 3 // note this tile had to be rotated 90 degrees clockwise
755112
866334

link 4 // note this tile had to be rotated 90 degrees clockwise
97755112
08866334

link 5 // note this tile had to be rotated 270 degrees clockwise
97755112
08866334
   66
   42

link 6 // note this tile had to be rotated 90 degrees clockwise
97755112
08866334
08 66
18 42

link 7 // note this tile had to be rotated 270 degrees clockwise
97755112
08866334
08 66 34
18 42 95

$tiles3 = array(
 "11",     // 1
 "12",
 "",
 "12",     // 2
 "93",
 "",
 "93",     // 3
 "99",
 "",
 "39",     // 4
 "98",
 "",
 "95",     // 5
 "86",
 "",
 "57",     // 6
 "66",
 "",
 "77",     // 7
 "57",
 "",
 "13",     // 8
 "24",
 "",
 "45",     // 9
 "47",
 "",
 "24",     // 10
 "39",
 0);

link_tiles(tiles3) выведет:

10 tiles
link 1
11
12
 
link 2
11
12
12
93
 
link 3
11
12
12
93
93
99
 
link 4
11
12
12
93
9339
9998
 
link 5
11
12
12
93
933995
999886
 
link 6
11
12
12
93
93399557
99988666
 
link 7
11
12
12    77
93    57
93399557
99988666
 
link 8
1113
1224
12    77
93    57
93399557
99988666
 
link 9
1113
122445
12  4777
93    57
93399557
99988666
 
link 10
1113
122445
12244777
9339  57
93399557
99988666

вторник, 1 февраля 2011 г.

Задачка на собеседовании

Интересная задачка, заданная мне недавно на собеседовании: вероятность некоторого события за час - 80%. Какова вероятность этого события за 20 мин?

Решение:

Домустим, у нас есть некоторое событие, которое 100% произойдет за час. Вероятность, что это событие произойдет в первые 20 мин - 100/3%. То, что это произойдет одновременно (по теории умножения вероятностей):

0.8% * 1/3 = 0.26(6)

Т.е, примерно 27% . Так что, самый очевидный и невероятный ответ доказан - надо было просто делить на 3 :)

PostgreSQL vs MySQL

Небольшая заметка о том, почему PostgreSQL круче MySQL:

  • лучшая работа со подзапросами
  • схемы - часто очень удобно пользоваться как пространствами имен
  • чеки - позволяют дополнительно проверять данные перед сохранением
  • рулы - позволяют создавать обновляемые вьюхи
  • каскадное удаление при дропе таблицы или колонки - мускуль попросит удалять все сначала ручками
  • наследование таблиц
  • триггеры: временное отключение, триггерные функции, табличные триггеры. Временное отключение бесценно при накатывании миграций, триггерные функции можно использовать повторно
  • отсутствие кучи ограничений внутри триггеров и функций типа обновить таблицу на которой был вызван триггер и т.п.
  • сиквенсы - позволяют реализовать паттерн "поле идентификации"
  • внешние ключи: составные, отложенная проверка. Отложенная проверка полезна, когда не нужно проверять целостность во время транзакции и можно отложить это до конца транзакции
  • индексы по выражению, составные, частичные и хэш индексы, возможность задавать порядок, конкурентное создание индекса
  • сам язык SQL мощнее - включает исключения и много чего другого
  • можно писать на любом языке (Java, C, PHP и др)
  • библиотека полнотекстового поиска и куча других полезных библиотек, возможность создавать собственные библиотеки
  • рекурсивные запросы
  • запросы к XML данным
  • возможность задавать порядок вывода null полей
  • масштабирование на многоядерных системах (мускуль в этом отношении мертвый)
  • транзакционный DDL - возможность делать миграции схемы БД в транзакции.
  • простое добавление и удаление колонок. В постгре по сути изменяются метаданные таблицы, поэтому все происходит очень быстро в не зависимости от размера таблицы; а в мускуле удаление колонки может днями идти блокируя все на своем пути
  • умный оптимизатор запросов
  • Строгая типизация, пользовательские типы, массивы, полноценые булевы

Последняя версия 9.0 получила поддержку репликаций "из коробки", так что исчезла последняя причина оставаться на MySQL.

Если у кого-нибудь еще что-то есть, добавляйте в каменты :)