Быстрая вставка

[Igors]

Добрый день

1) Есть такой контейнер

Sphere 1
Cube 1
Cube 3
Sphere 2
Sphere 5

Т.е. базовые имена (Sphere и Cube) идут в произвольном порядке, а вот номера уникальны (в пределах базового имени) и идут по возрастающей. Нужно вставить в этот контейнер другой с теми же базовыми именами но произвольными индексами, напр

Cube 2
Cube 3
Cube
Cube
Sphere 1

В рез-те должно получиться

Sphere 1   // override
Cube 1     
Cube 2      // insert   
Cube 3      // override
Cube 4      // insert with new index
Cube 5      // insert with new index
Sphere 2
Sphere 5

Не смог придумать способ без перебора    Создавать любые временные контейнеры можно

2)  Все то же, но первый контейнер - такое дерево

Sphere 1
  Cube 1
    Cone 1
Sphere 2
  Cube 2
Sphere 5
  Cube 5
    Cone 5

Спасибо

[Racheengel]

Контейнер проиндексировать придется, естественно.
Что то типа QMap<QString, QPair<int,int>> то есть <key, <number,line>>
Например будет так для примера 1:
<Sphere <1,1><2,4><5,5>>
<Cube <1,2><3,3>
Ну а дальше уже дело техники.

[Авварон]

1. отсортировать оба массива так чтобы номера без индексов были в конце пачки (а не в начале). например, можно для удобства сперва декомпозироваь строку на пару - ключ/номер
2. параллельно пробежаться по массивам склеивая сортированные пачки - примерно как делает std::merge/std::set_union и друзья, только помимо склейки надо считать кол-во элементов в "пачке" и если встретился элемент без номера, присваивать ему новый номер.

Хорошая задачка на собеседование.
Интересно можно ли за O(M+N) сделать?..

[Igors]

Контейнер проиндексировать придется, естественно.
Что то типа QMap<QString, QPair<int,int>> то есть <key, <number,line>>
Например будет так для примера 1:
<Sphere <1,1><2,4><5,5>>
<Cube <1,2><3,3>
Ну а дальше уже дело техники.

Наверное значение мапы - вектор пар. В любом случае если line - индекс строки, то он "уплывет" после первой же вставки

параллельно пробежаться по массивам склеивая сортированные пачки - примерно как делает std::merge/std::set_union и друзья,

Дело осложняется тем что пачек (по первому ключу) может быть сколько угодно, и они идут не подряд

Наверно сначала нужно упаковать идущие подряд, т.е.

Sphere <1, 1>
Cube <1, 1>
Cube <3, 3>
Sphere <2, 2>
Sphere <5, 5>

Теперь нужно вставить "Cube 2", возможно ли его найти пачку для него в массиве выше используя lower_bound ? Очевидно "просто так" нет, мешает первый ключ. А может как-то "непросто"?

[RedDog]

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

[Igors]

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

Ну как-то оно смотрится "инородным телом", да и хлопот с "прикручиванием" немало. Кстати не знаю умеет ли БД такое делать

[Racheengel]

Хорошая задачка на собеседование.
Интересно можно ли за O(M+N) сделать?..

Принципиально отказываюсь от собеседований "с задачами", особенно с такой идеологией.
Как бы "шашечки или ехать"?

[Авварон]

Принципиально отказываюсь от собеседований "с задачами", особенно с такой идеологией.
Как бы "шашечки или ехать"?

Если кандидат не в состоянии распознать и написать set_union/set_intersect, то зачем такой кандидат нужен? Я, собственно, люблю задачки которые в завуалированном виде мапятся на стандартный алгоритм - тогда даже не требуется реализовывать этот алгоритм, главное чтобы кандидат понял что это конкретный алгоритм, сумел преобразовать данные к виду в котором алгоритм применим, и применил его. Как follow up можно поговорить о том, как алгоритм устроен, в простых случаях (как этот) можно и попросить написать. Или уже параллельно пробежаться по двум массивам оказывается непосильной задачей?

[Пантер]

Хорошая задачка на собеседование.
Интересно можно ли за O(M+N) сделать?..

Принципиально отказываюсь от собеседований "с задачами", особенно с такой идеологией.
Как бы "шашечки или ехать"?

Я тоже отказываюсь. Несколько собеседований у меня закончились толком не начавшись. Зато время сэкономил.

[Авварон]

Я тоже отказываюсь. Несколько собеседований у меня закончились толком не начавшись. Зато время сэкономил.

Вот потому ты и не в гугле=) Впрочем, я тоже

Ну а что спрашивать? Знает ли человек что такое деструкторы? Это хорошо если ты на конкретную вакансию идешь, гуглы же нанимают толкового чувака а та уже куда получится его приткнуть по навыкам. Поэтому и оценивается алгоритмический скилл не привязываясь к языку.

[Пантер]

Я тоже отказываюсь. Несколько собеседований у меня закончились толком не начавшись. Зато время сэкономил.

Вот потому ты и не в гугле=) Впрочем, я тоже

Ну а что спрашивать? Знает ли человек что такое деструкторы? Это хорошо если ты на конкретную вакансию идешь, гуглы же нанимают толкового чувака а та уже куда получится его приткнуть по навыкам. Поэтому и оценивается алгоритмический скилл не привязываясь к языку.

Это проблема гугла, не находишь?

[Igors]

...в простых случаях (как этот) можно и попросить написать. Или уже параллельно пробежаться по двум массивам оказывается непосильной задачей?

А как пробегаться? Напр исходный массив

Cube 1
...

И нужно вставить "Cube 10". Я обязан просматривать исходный массив пока не обнаружу "Cube >= 10" или до упора. Только после этого могу вставлять или реплейсить. И после первой же вставки номера строк изменятся, как-то сохранять их (для 2 и более вставляемых) не выходит

[Igors]

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

Кстати здесь есть такая (или подобная) возможность. Как работает пресловутый O(log(N)): отрезок (контейнер) делится пополам, и, в зависимости от рез-та сравнения, операция повторяется с левой или правой частью.

Здесь прямолинейно использовать такое нельзя, мешает первый ключ. Но можно немного изменить стандартный алгоритм:

- делим отрезок пополам, если первый ключ "наш" ("Cube" в примере выше), то продолжаем как обычно. Иначе рекурсивно ищем в обеих частях. Правда нужно немного помозговать как сравнить рез-ты обеих частей - но это решаемо. Конечно эффективность будет не log(N), а меньше в зависимости от числа первых ключей. Но решение 100% "общее"

[Авварон]

Я же написал - предварительно отсортировать так что номера без номеров будут в конце. Тогда присвоить им уникальные номера - задача тривиальная.
Ну да, типа будет N*log(N) сортировка - надо быстрее - давайте обсудим.

[Igors]

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

Вставляемые "без номеров" - просто доп случай, это ничего не меняет

Ну да, типа будет N*log(N) сортировка - надо быстрее - давайте обсудим.

Как сделано сейчас: для каждого вставляемого (напр "Cube 10") просматривается весь массив до обнаружения "Cube >= 10", наилучшая позиция вставки запоминается. Напр нашли "Cube 5" в позиции (по-простому "в строке") 44, значит фиксируем: место вставки 44+1 = 45. Но еще не вставляем, ведь может найдется "Cube 7" и.т.п. Наконец весь массив просмотрен, вставляем в запомненное место, если оно -1 (вообще нет никаких "Cube"), то просто в конец.

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