Выпуск#17: ITренировка — актуальные вопросы и задачи от ведущих компаний

[CakeOfChaos]

Задача 2. Gold for work

Спойлер

Разламываем слиток:
Первый раз разламываем слиток на две части: 3/7 и 4/7
Второй раз разламываем 3/7 слитка на две части: 1/7 и 2/7
Оплата:
Первый день: отдаем 1/7
Второй день: отдаем 2/7, работник дает сдачу 1/7
Третий день: отдаем 1/7
Четвертый день: отдаем 4/7, работник дает сдачу 1/7 + 2/7
Пятый день: отдаем 1/7
Шестой день: отдаем 2/7, работник дает сдачу 1/7
Седьмой день: отдаем 1/7

[prika148]

Эта задача (точнее, ее решение) всегда вызывала у меня негодование: получается, что мы должны запретить работнику тратить его зарплату. Плохая задача, я считаю

[reci]

А часто она Вам встречается?

[prika148]

До сегодняшнего дня — не меньше одного раза.

[kardan2]

Во-первых получая предоплату, вы в случае неудачи должны её вернуть, т.е. иметь на балансе.
Во-вторых, данный дискомфорт обоюден, т.к. заказчик тоже не может свободно распоряжаться своей долей во времени. И это надо понимать, и находить компромисс…

[prika148]

Вы, безусловно, правы, но речь идет не о предоплате. Первый кусок слитка — полноценная зарплата за один рабочий день.

[kardan2]

Мои решения.

Вопрос 1

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

Вопрос 2

Нужно разделить слиток на 3 части в пропорции 1-2-4.
В первый день отдает 1.
Во второй день забираем 1 обратно и отдаем 2.
в среду отдает 1 и ничего не берем в замен.
в четверг отдает 4 и забираем обратно 1 и 2
и т.д.

Задача 3

Пока без кода. Если воспринимать условия, как «в любой момент должна сохраняться последовательность четных и нечетных», то задача может решится только за O(n^2).
В этом случае, замену местами можно сделать только если 2 элемента стоят рядом. А это квадратичная зависимость.
Если же последовательность не обязана сохраняться, а должна быть только восстановлена в конце, то я предлагаю такой ход мыслей.
У нас есть фиксированный набор переменных, можно ограничится всего 1. Это значит, что элементы в массиве можно ТОЛЬКО менять местами.
Нам нужна линейная зависимость. Вспоминаем, что сумма убывающей геометрической прогрессии линейна. n+1/2n+1/4n+1/8n+...<2n.
Делим наш массив на 3 зоны, в пропорции 1-2-1. Добиваемся, что все числа из первой и третей зоны стали на место, а вторая часть опять заполнена в перемешку. Таким образом мы за 1 итерацию свели задачу с ней самой же, но сократили длину в 2 раза.
Т.е. если у нас есть 1a2b3c4d5e6f, то после первой итерации получим 123-4a5b6c-def.
Здесь есть вопросы нечетной длины, и теоретического обоснования, но суть концепции представлена. Постараюсь оформить в виде кода.

[kardan2]

Задача 1. Легкотня

public class Node {
    public String value = null;
    public Node next = null;

    public Node(String _value, Node _next) {
        value = _value;
        next = _next;
    }
    
    public static Node reverse(Node _node){
        Node base = _node;
        Node result = null;     
        while(base!=null){
            Node temp = base;
            base = temp.next;
            temp.next = result;
            result = temp;
            
        }
        return result;
    }
}

Задача 2. Без кода.

По сути сводится к нахождению для каждого элемента убывающей последовательности слева и справа, и суммированию длин этих последовательностей. Правда решается за квадратичные затраты от n. ХМ, э нет, я пожалуй поищу решение получше.

А вообще мне понравились задачи от Майкрософт, и пусть к самому продукту отношение негативное, задачи что здесь, что раньше, очень адекватные для тестирования. Ни через чур сложные, ни слишком легкие.

[Alpha_di]

Оптимизация жеж

Наибольшая возрастающая подпоследовательность(ну его просто так по дефолту кличут), имеет оптимизацию до O(n*log n) за счет динамики