Войти
ФлеймФорумПрограммирование

Задачки с собеседований! (4 стр)

Страницы: 13 4 5 611 Следующая »
#45
12:35, 25 авг. 2017

FordPerfect
> void assign(K const& keyBegin, K const& keyEnd, const V& val)
> {
> if(keyBegin<keyEnd)
> {
> V N=(*this)[keyEnd];
> m_map.erase(m_map.upper_bound(keyBegin),m_map.lower_bound(keyEnd));
> m_map[keyBegin]=K;
> m_map[keyEnd]=N;
> }
> }

Это не корректное решение.

дана же понятная задача:

// Assign value val to interval [keyBegin, keyEnd).
// Overwrite previous values in this interval.
// Do not change values outside this interval.

Т.е. пробежаться по всем ключам в заданном интервале и всем им записать  val в значение.  Ты же удалил все записи в заданном интервале, а потом добавил в мапу только 2 записи.  При чём записал значение и в keyEnd хотя он по условию НЕ включен в интервал.

 V N=(*this)[keyEnd]; 
А если запись с ключом keyEnd не была в контейнере? Ты её взял и создал зачем-то в этой строке и мусор закешировал.

#46
12:40, 25 авг. 2017

L
> Т.е. пробежаться по всем ключам в заданном интервале и всем им записать val в
> значение. Ты же _удалил_ зачем-то все записи в заданном интервале (нафига же),
> да ещё и добавил в мапу только 2!! записи.
Я только сейчас понял, какое было задание и что там было сделано.

#47
12:43, 25 авг. 2017

1 frag / 2 deaths
Я поправил текст, ибо сам чуть тупанул, решил что там есть отдельный метод добавления записей. А тут реально один метод assign заполняющий интервалы.

Задача ж тупая - сгенерить записи в мапе записи с ключами от keyBegin до keyEnd (не включительно) и им всем назначить value. Если они были уже в мапе то перезаписать.

#48
12:54, 25 авг. 2017

L
в этой мапе ключи - не числа, а интервалы.

#49
13:05, 25 авг. 2017

kipar
Согласен, не мой день )

#50
13:14, 25 авг. 2017

Дано: массив точек в прямоугольной системе координат на плоскости.
Требуется:
1. Определить, существует ли такая точка на оси Ох, через которую можно провести прямую, перпендикулярно этой оси, так чтобы точки относительно прямой располагались симметрично.
2. Составить оптимальный по времени алгоритм и оценить его сложность.
3. Написать функцию, которая на вход принимает вектор произвольных точек (х,у), а на выходе возвращает истину если все точки расположены симметрично, и ложь если хотя бы одна точка нарушает симметрию.

#51
14:02, 25 авг. 2017

kipar
У меня так вышло (upd, обновил код,  очипятался и не то значение закешировал)

if (keyBegin < keyEnd) {
  auto e = m_map.upper_bound(keyEnd);
  V oldValue = e == m_map.begin() ? e->second : std::prev(e)->second;
  m_map.erase(m_map.lower_bound(keyBegin), e);
  m_map[keyBegin] = val;
  m_map[keyEnd] = oldValue;
}
#52
14:35, 25 авг. 2017

totoro
Отсортировать точки любым алгоритмом по X координате, а потом, любым стабильным алгоритмом по Y. Идти с середины (если число точек нечетное, среднюю просто выкинуть) и сравнивать дельту слева и справа и равенство Y координат.
Итого сложность O(N log N) - на сортировку. Задача неинтересная.

Давайте лучше обсуждать про существование произвольной прямой на этой плоскости.

#53
15:40, 25 авг. 2017

9К720
> Отсортировать точки любым алгоритмом по X координате, а потом, любым стабильным
> алгоритмом по Y. Идти с середины (если число точек нечетное, среднюю просто
> выкинуть) и сравнивать дельту слева и справа и равенство Y координат.
Ну допустим имеем такую последовательность:
(-1.0f, 1.0f), (1.0f, 1.0f), (-2.0f, 1.0f), (2.0f, 1.0f), (4.0f, 2.0f), (-4.0f, 2.0f), (-8.0f, 2.0f), (8.0f, 2.0f), (0.0f, 3.0f)
На графике точки вот таким способом будут расположены:

            ^
            |
            *
    *  *  |  *  *
        **|**
—--————————>
            |
            |


Отсортировали, получили вот такую последовательность:
(-2, 1), (-1, 1), (1, 1), (2, 1), (-8, 2), (-4, 2), (4, 2), (8, 2), (0, 3),
выкинули среднюю точку:
(-2, 1), (-1, 1), (1, 1), (2, 1), (-4, 2), (4, 2), (8, 2), (0, 3),
Выходит несимметрично точки расположены, хотя на самом деле это не так. Неверное решение.

#54
15:43, 25 авг. 2017

Почему нельзя просто отсортировать по критерию "сравниваем Y, если равны то сравниваем X"? Ну и дальше там легко для каждого слоя проверить где середина.

#55
15:51, 25 авг. 2017

kipar
> Почему нельзя просто отсортировать по критерию "сравниваем Y, если равны то
> сравниваем X"? Ну и дальше там легко для каждого слоя проверить где середина.
Ну понятно, что решение нужно искать исходя из этих соображений, но задача как раз заключается в том чтобы придумать правильный и главное оптимальный алгоритм, т.е. подробно описать что и в какой последовательности нужно сделать.

#56
16:14, 25 авг. 2017

totoro
сортировка все равно съест больше времени, дальше там за O(N) как ни делай. Ну допустим берем первую точку, находим последнюю с той же координатой Y, берем полусумму X, сравниваем с остальными точками на том же уровне Y( идя с двух сторон) и с найденной на прошлом этапе (если он не первый). Берем следующую точку, повторяем.

#57
16:20, 25 авг. 2017

totoro
>Отсортировали
>(-2, 1), (-1, 1), (1, 1), (2, 1), (-8, 2), (-4, 2), (4, 2), (8, 2), (0, 3),
Отсортировали - это когда у тебя выполняется условие Xi<=Xi+1
У тебя неотсортированная последовательность получается.
>выкинули среднюю точку:
Да, ее конечно нельзя выкидывать, тут я погорячился. Надо проверить что она на этой пярмой лежит.

>. Неверное решение.
Это ты цифры сравнивать не умеешь, лол. Ну или скорее не знаешь, чем отличается стабильная сортировка от нестабильной.
да, я затупил конечно же с сортировкой. Надо сортировать один раз по компаратору, который вначале проверяет X, а при равенстве Y

#58
16:25, 25 авг. 2017

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

#59
16:25, 25 авг. 2017

9К720
> Да, ее конечно нельзя выкидывать, тут я погорячился. Надо проверить что она на
> этой пярмой лежит.
И не только её, надо просто выкинуть из массива все точки, у которых такая координата X. А после этого уже должно остаться чётное количество точек, которые уже сравнивать.

Страницы: 13 4 5 611 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.