ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка
25 сообщений из 35, страница 1 из 2
  1  все
задачка
    #36979939
truel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
truel
Участник
Добрый день, всем!

Есть задачка:

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

Есть идеи?

Заранее спасибо.
...
Рейтинг: 0 / 0
26.11.2010, 17:44
| Ответить | Цитировать | Написать  
задачка
    #36979984
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
truel,

а номера какого вида? обычные российские?
...
Рейтинг: 0 / 0
26.11.2010, 17:58
| Ответить | Цитировать | Написать  
задачка
    #36979995
GSerg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
GSerg
Участник
Яростный Меча номера какого вида? обычные российские?
Дык не пофигу ли? Сравнение на тупое равенство наверняка.

Афтар, видимо, интересуется только цикловой строной вопроса.
Оба списка сортируются, потом одновременный односторонний проход по обоим.

Merge join , иными словами.
...
Рейтинг: 0 / 0
26.11.2010, 18:03
| Ответить | Цитировать | Написать  
задачка
    #36980003
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
GSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность.
...
Рейтинг: 0 / 0
26.11.2010, 18:04
| Ответить | Цитировать | Написать  
задачка
    #36980016
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
Яростный МечGSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность.
Тогда отсортированность списков вменяем в исходные условия ))) А то об этом же ни слова. Кто сказал, что они не отсортированы изначально? )))
...
Рейтинг: 0 / 0
26.11.2010, 18:11
| Ответить | Цитировать | Написать  
задачка
    #36980021
GSerg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
GSerg
Участник
Яростный МечТребуется линейная сложность.
Да, но ввиду уточняющей фразы автора "не должно быть вложенных циклов" мне представляется, что автор, не до конца разбираясь в тонкостях момента, имел в виду "не N^2", а не "обязательно N".

Также представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?
...
Рейтинг: 0 / 0
26.11.2010, 18:12
| Ответить | Цитировать | Написать  
задачка
    #36980044
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
GSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет.
Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь
...
Рейтинг: 0 / 0
26.11.2010, 18:19
| Ответить | Цитировать | Написать  
задачка
    #36980066
truel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
truel
Участник
GSergЯростный МечТребуется линейная сложность.
Да, но ввиду уточняющей фразы автора "не должно быть вложенных циклов" мне представляется, что автор, не до конца разбираясь в тонкостях момента, имел в виду "не N^2", а не "обязательно N".

Вопрос был с собеседования, насколько помню требовалось найти именно линейную сложность. Списки неотсортированы. Поэтому Merge join, как я понимаю, не годится, т.к. нету алгоритма сортировки с сложностью менее n*log(n).
...
Рейтинг: 0 / 0
26.11.2010, 18:26
| Ответить | Цитировать | Написать  
задачка
    #36980072
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
Яростный МечGSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет.
Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь
Там задачка "немного" другая.

А тут - есть массивы (пусть с целыми числами - это абсолютно ничего не даст):

[5, 6, 1, 10, 3, 4, 19]
[32, 2, 4, 8, 1, 11, 7, 13]

Ну как ты в один проход линейно найдешь пересечение этих двух массивов? Никак.
Только если они изначально упорядочены.
...
Рейтинг: 0 / 0
26.11.2010, 18:29
| Ответить | Цитировать | Написать  
задачка
    #36980076
truel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
truel
Участник
Яростный МечGSergТакже представляется маловероятным, чтобы гарантированно O(N)-ный алгоритм соединения существовал вообще. Иначе почему он не используется в современных СУБД?В общем виде нет.
Однако номера можно закодировать целыми числами, после чего искать подходы, как, например, здесь

Почитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись.
...
Рейтинг: 0 / 0
26.11.2010, 18:31
| Ответить | Цитировать | Написать  
задачка
    #36980094
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
truelПочитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись.
Замени набор букв и цифр на числа. Это поможет? Нет.
...
Рейтинг: 0 / 0
26.11.2010, 18:39
| Ответить | Цитировать | Написать  
задачка
    #36980105
truel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
truel
Участник
Edd.DragontruelПочитал, но непонятно, как применить тот подход. В той задачке в качестве элементов массива использовались простые числа, здесь же набор из букв и цифр, поэтому простой суммой не обойтись.
Замени набор букв и цифр на числа. Это поможет? Нет.
Не понимаю, как это может помочь. Пусть будет алгоритм кодирования номера в число и обратный алгоритм декодирования, и мы имеем тогда дело только с числами.

В том примере нужно было только один выкинутый номер, а здесь не просто номер, а серию номеров.
...
Рейтинг: 0 / 0
26.11.2010, 18:42
| Ответить | Цитировать | Написать  
задачка
    #36980125
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
truelНе понимаю, как это может помочь. Пусть будет алгоритм кодирования номера в число и обратный алгоритм декодирования, и мы имеем тогда дело только с числами.

В том примере нужно было только один выкинутый номер, а здесь не просто номер, а серию номеров.
Так я так и сказал - НЕ поможет.
Можно забыть о той задаче и не мусолить ее в мозгу.
...
Рейтинг: 0 / 0
26.11.2010, 18:57
| Ответить | Цитировать | Написать  
задачка
    #36980142
truel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
truel
Участник
Можно ли задачу решить так:

1. хэшируем 1 массив всех номеров города.
2. ищем каждый элемент 2 массива в хэш-таблице 1 массива.

Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)).
...
Рейтинг: 0 / 0
26.11.2010, 19:04
| Ответить | Цитировать | Написать  
задачка
    #36980150
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
truelМожно ли задачу решить так:

1. хэшируем 1 массив всех номеров города.
2. ищем каждый элемент 2 массива в хэш-таблице 1 массива.

Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)).в принципе так можно и за линейное время уложиться, но для этого надо хэш примерно на 35937000 персон. Что там с ограничением по памяти? Да и предварительно обнулить элементы придется...
...
Рейтинг: 0 / 0
26.11.2010, 19:08
| Ответить | Цитировать | Написать  
задачка
    #36980153
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
хотя нет, многовато. 4492125 байт понадобится.
...
Рейтинг: 0 / 0
26.11.2010, 19:10
| Ответить | Цитировать | Написать  
задачка
    #36980159
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
truelМожно ли задачу решить так:

1. хэшируем 1 массив всех номеров города.
2. ищем каждый элемент 2 массива в хэш-таблице 1 массива.

Сложность по теории получается, поправьте, если не прав, то O(n*ln(n)).
Тогда фраза "не должно быть вложенных циклов" отпадает.

Цикл по второму массиву
{
Цикл-поиск в таблице хешей
}
...
Рейтинг: 0 / 0
26.11.2010, 19:13
| Ответить | Цитировать | Написать  
задачка
    #36980332
tempestadept
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tempestadept
Гость
Яростный Меч,

В автомобильных номерах используются далеко не все буквы кириллицы, так что возможных номеров меньше. С
другой стороны, есть ещё код региона...
А необходимость обнулять табличку добавляет константное время и не влияет на асимптотику, так что требования формально соблюдены.
...
Рейтинг: 0 / 0
26.11.2010, 21:53
| Ответить | Цитировать | Написать  
задачка
    #36980336
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
select можно использовать?
...
Рейтинг: 0 / 0
26.11.2010, 21:59
| Ответить | Цитировать | Написать  
задачка
    #36980406
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
две таблички, индексы, джойн :)
...
Рейтинг: 0 / 0
26.11.2010, 22:54
| Ответить | Цитировать | Написать  
задачка
    #36980506
Фотография apxutektop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
apxutektop
Участник
Яростный МечGSergОба списка сортируются , потом одновременный односторонний проход по обоим.Требуется линейная сложность.

А в этом случае какова сложность будет? Разве не N?
...
Рейтинг: 0 / 0
27.11.2010, 00:57
| Ответить | Цитировать | Написать  
задачка
    #36980536
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Народ, вы чего?
Поскольку ограничения на ресурсы не указано, задача решается элементарно - составлением матрицы (решета).
Edd.Dragon и ЯрМеч были правы, смысл примерно таков и есть.
Давайте посчитаем ( http://gibdd.net/codes.html) - на данный момент мы имеем всего 10*10*10*12*12*12*122=210816000 федеральных автономеров. Для их запоминания (есть-нет) достаточно массива (матрицы) объемом 26352000 байт (т.е. всего ~25 МБайт). Даже с учетом номеров спецтранспорта и т.п. возрастает он ненамного. Таким образом, алгоритм прост:
- описываем функцию, позволяющие сопоставить конкретный номер с его местом в матрице
- инициализируем матрицу
- проходим 1 раз по массиву "проехавших авто" и отмечаем их в матрице
- проходим 1 раз по массиву "угнанных авто", преобразуем номер в место и сверяем с матрицей, в случае совпадения - запоминаем.
Усё...
...
Рейтинг: 0 / 0
27.11.2010, 01:56
| Ответить | Цитировать | Написать  
задачка
    #36980615
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Edd.Dragon
Участник
AndreTM,
А составление матрицы какую сложность имеет?
...
Рейтинг: 0 / 0
27.11.2010, 10:02
| Ответить | Цитировать | Написать  
задачка
    #36980617
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Edd.DragonAndreTM,
А составление матрицы какую сложность имеет?
Никакую. Поскольку заранее создаём массив нужного размера. Простое выделение памяти...
...
Рейтинг: 0 / 0
27.11.2010, 10:04
| Ответить | Цитировать | Написать  
задачка
    #36980619
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Ну, выдайте мне, например, сотню тысяч номеров машин и тысячу номеров "угнанных".
В любом табличном виде.
А я вам отвечу вышеописанным алгоритмом...
...
Рейтинг: 0 / 0
27.11.2010, 10:12
| Ответить | Цитировать | Написать  
25 сообщений из 35, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36980076&tid=1343300]:
 0ms
get settings:
 10ms
get forum list:
 8ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 185ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 43ms
get tp. blocked users:
 1ms
others: 216ms
total:  478ms
созд. / загр.: 478ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]