Big O на интервью

[voyager3]

Я, честно, не понимаю, как они этого добились, даже если через плавающую точку вычитали.

https://en.m.wikipedia.org/wiki/Signed_zero

Да я как бы не против нулей или бесконечностей со знаком. Но вычитая 1 из 1, минус ноль не получится. При умножении или делении - согласен.

Видимо, исходный бюджет был слегка меньше, чем показывался, и действительно внутри хранится с плавающей точкой. Т.е. не ровно 50 000, а где-то 49 999.99999. То есть деление все же было (например, наверху раскидали проценты между подразделениями).

Так бабло в двоичной плавающей точке хранить - вообще моветон: ваши 10% в ней превращаются в периодическую дробь, и на ровном месте будет ошибка округления.

[Mmodel]

по моему любой процессор просто не умеет всётаки делить полностью точно

[KOT MATPOCKUH]

по моему любой процессор просто не умеет всётаки делить полностью точно

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

[IvanGrozniy]

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

[Likenew]

Привет,

Пугают как-бы при наёме что могут про биг О спросить.
Интересуюсь что тут такого коварного с ним могут спросить на интервью?

Биг О нотатион ис а матхематицал нотатион тхат десцрибес тхе лимитинг бехавиор оф а фунцтион шхен тхе аргумент тендс тошардс а партицулар валуе ор инфиниты.

вроде как надо подсчитать шорст сценарио, т.е. если даже дают код и строки кода то надо брать каждую строку за один степ и дальше всякие лоопс за Н*Н ну и это всё сложить.

Допустим

фунцтион(н) {
досометхинг();
фор(и=0; и<n;i++){
dosomething();
}
}

то это будет О(н+н*н)
даже если досометхинг не всегда срабатывает.

Вроде как функция стремиться и функция доходит и не идёт дальше одно и тоже в Цомпутер Сциенце.

Наверное могут спросить сколько алгоритм жрёт ЦПУ, а сколько меморы в бест цасе и шорст цасе и баланце бетшеен тхем используя всякие алгоритмы.

Допустим бинары сеарч жрёт меньше всего ЦПУ, но больше всего меморы хттпс://ен.шикипедиа.орг/шики/Бинарысеарчалгоритхм

Только О(н) для одинокого цикла, всеми константами можно принебречь при достaточно большом н.
Для двойного цикла О(н^2) and so on.

Всего 6 классов сложности, даны в порядке убывания еффективности.
< O(1) - denotes constant running time
O(logn) -denotes logarithmic running time
O(n) - denotes linear run. time
O(nlogn) - denotes log-linear run. time
O(n^c) - denotes polynomial run. time, c=const
O(c^n) - exponential run time >
Я класс брала в <MIT>, там рассказывали. А на интервью v < Chase> конкретно спрашивали слышала ли я о <Big О> в виду не молодого возраста.

[Grand Canyon]

Только О(н) для одинокого цикла, всеми константами можно принебречь при достaточно большом н.
Для двойного цикла О(н^2) and so on.

Всего 6 классов сложности, даны в порядке убывания еффективности.
< O(1) - denotes constant running time
O(logn) -denotes logarithmic running time
O(n) - denotes linear run. time
O(nlogn) - denotes log-linear run. time
O(n^c) - denotes polynomial run. time, c=const
O(c^n) - exponential run time >
Я класс брала в <MIT>, там рассказывали. А на интервью v < Chase> конкретно спрашивали слышала ли я о <Big О> в виду не молодого возраста.

Ничего себе какие коварные женщины бывают...

[IvanGrozniy]

Привет,

Пугают как-бы при наёме что могут про биг О спросить.
Интересуюсь что тут такого коварного с ним могут спросить на интервью?

Биг О нотатион ис а матхематицал нотатион тхат десцрибес тхе лимитинг бехавиор оф а фунцтион шхен тхе аргумент тендс тошардс а партицулар валуе ор инфиниты.

вроде как надо подсчитать шорст сценарио, т.е. если даже дают код и строки кода то надо брать каждую строку за один степ и дальше всякие лоопс за Н*Н ну и это всё сложить.

Допустим

фунцтион(н) {
досометхинг();
фор(и=0; и<n;i++){
dosomething();
}
}

то это будет О(н+н*н)
даже если досометхинг не всегда срабатывает.

Вроде как функция стремиться и функция доходит и не идёт дальше одно и тоже в Цомпутер Сциенце.

Наверное могут спросить сколько алгоритм жрёт ЦПУ, а сколько меморы в бест цасе и шорст цасе и баланце бетшеен тхем используя всякие алгоритмы.

Допустим бинары сеарч жрёт меньше всего ЦПУ, но больше всего меморы хттпс://ен.шикипедиа.орг/шики/Бинарысеарчалгоритхм

Только О(н) для одинокого цикла, всеми константами можно принебречь при достaточно большом н.
Для двойного цикла О(н^2) and so on.

Всего 6 классов сложности, даны в порядке убывания еффективности.
< O(1) - denotes constant running time
O(logn) -denotes logarithmic running time
O(n) - denotes linear run. time
O(nlogn) - denotes log-linear run. time
O(n^c) - denotes polynomial run. time, c=const
O(c^n) - exponential run time >
Я класс брала в <MIT>, там рассказывали. А на интервью v < Chase> конкретно спрашивали слышала ли я о <Big О> в виду не молодого возраста.

Забыли еще одну, седьмую, написать

[voyager3]

Забыли еще одну, седьмую, написать

Их можно сколько угодно придумать с математической точки зрения. А с практической - всё, что больше - безнадёга.

[Likenew]

Только О(н) для одинокого цикла, всеми константами можно принебречь при достaточно большом н.
Для двойного цикла О(н^2) and so on.

Всего 6 классов сложности, даны в порядке убывания еффективности.
< O(1) - denotes constant running time
O(logn) -denotes logarithmic running time
O(n) - denotes linear run. time
O(nlogn) - denotes log-linear run. time
O(n^c) - denotes polynomial run. time, c=const
O(c^n) - exponential run time >
Я класс брала в <MIT>, там рассказывали. А на интервью v < Chase> конкретно спрашивали слышала ли я о <Big О> в виду не молодого возраста.

Забыли еще одну, седьмую, написать

За что купила, за то и продаю
Все претензии к MIT

[Likenew]

Ничего себе какие коварные женщины бывают...

Хуже не бывает

[IvanGrozniy]

Забыли еще одну, седьмую, написать

Их можно сколько угодно придумать с математической точки зрения. А с практической - всё, что больше - безнадёга.

Мы рассматриваем здесь с точки зрения алгоритмов. Поэтому если не будете знать о факториальной функции при необходимости оценки такого алгоритма, то впросак на интервью можете попасть. Таких алгоритмов ну очень много. Например list of all permutations.

[IvanGrozniy]

Только О(н) для одинокого цикла, всеми константами можно принебречь при достaточно большом н.
Для двойного цикла О(н^2) and so on.

Всего 6 классов сложности, даны в порядке убывания еффективности.
< O(1) - denotes constant running time
O(logn) -denotes logarithmic running time
O(n) - denotes linear run. time
O(nlogn) - denotes log-linear run. time
O(n^c) - denotes polynomial run. time, c=const
O(c^n) - exponential run time >
Я класс брала в <MIT>, там рассказывали. А на интервью v < Chase> конкретно спрашивали слышала ли я о <Big О> в виду не молодого возраста.

Забыли еще одну, седьмую, написать

За что купила, за то и продаю
Все претензии к MIT

Кстати посмотрел лекцию у них. Писателю этой лекции незачет!

[8K]

О, вопрос на засыпку: копирование строк в цикле от 1 до N. Зависит от языка программирования, конечно, и прочих тонкостей.

[Krys-Krys]

О, вопрос на засыпку: копирование строк в цикле от 1 до N. Зависит от языка программирования, конечно, и прочих тонкостей.

Вопрос не ясен. Что значит копирование? Каких строк?

[8K]

О, вопрос на засыпку: копирование строк в цикле от 1 до N. Зависит от языка программирования, конечно, и прочих тонкостей.

Вопрос не ясен. Что значит копирование? Каких строк?

У вас есть массив строк. Его надо скопировать. Например, std::vector<std::string> на C++. Или то же самое на Питоне или Яве.

Копирование одной строки не всегда O(1), особенно на C++. Перековавшиеся джависты - зло.

Так себе задачка для затравки. Можно поговорить про small string optimization, mutable vs immutable, copy on write, etc.

[Krys-Krys]

О, вопрос на засыпку: копирование строк в цикле от 1 до N. Зависит от языка программирования, конечно, и прочих тонкостей.

Вопрос не ясен. Что значит копирование? Каких строк?

У вас есть массив строк. Его надо скопировать. Например, std::vector<std::string> на C++. Или то же самое на Питоне или Яве.

Тогда time complexity - O(n)
А по memory - вообще ничего или O(1), т к результатирующий и входной массив не учитываются.

[8K]

Define n.

[Krys-Krys]

Define n.

n в данном случае будет размер входного массива, поэтому и O(n) - time complexity

[8K]

Я и говорю, джависты программируют на С++, и хрен втолкуешь разницу между передачей параметров по значению или по ссылке. Вектора так и летают туда-сюда.

Не примите на свой счет, я о своем, наболевшем. Трудно найти C++ разработчика без Java background.

[roadman]

В общем случае О(n x m), где n -число строк в векторе, m- средняя длина строки.

[8K]

В общем случае О(n x m), где n -число строк в векторе, m- средняя длина строки.

В случае С++ и без всяких вывертов в имплементации строк.

А в общем случае строки, скорее, immutable и их копирование будет O(1), т.е. Krys-Krys со своей джавистской колокольни где-то права. Тогда на интервью я бы копнул дальше. Например, спросил то же самое про сортировку. Часто игнорируют стоимость сравнения ключей. Тут бы это m и всплыло, опять же в зависимости от распределения.

В реальности же, к сожалению, приходится ограничиваться вариациями на тему написания bubble sort, кто справился - тот и в дамках. Не тот контингент.

[Krys-Krys]

В общем случае О(n x m), где n -число строк в векторе, m- средняя длина строки.

В случае С++ и без всяких вывертов в имплементации строк.

А в общем случае строки, скорее, immutable и их копирование будет O(1), т.е. Krys-Krys со своей джавистской колокольни где-то права. Тогда на интервью я бы копнул дальше. Например, спросил то же самое про сортировку. Часто игнорируют стоимость сравнения ключей. Тут бы это m и всплыло, опять же в зависимости от распределения.

Я не замечала чтоб на интервью где-то так глубоко капали, но я на Джаве, да.
Скопировать строки вообще наверное нельзя в Джаве по описанной вами причине. Можно скопировать ссылку на старую строку, String strCopy = str, это будет O(1) действительно. Так же можно создать новую строку из старой, тут я не знаю наверняка какое будет O, думаю что O(k) где к - длина строки - String strCopy = String.valueOf(str); - в этом случае это будет deep copy.

[8K]

Я не замечала чтоб на интервью где-то так глубоко копали.

Вспоминается бессмертное во валит, гад!

[Мальчик-Одуванчик]

Я и говорю, джависты программируют на С++, и хрен втолкуешь разницу между передачей параметров по значению или по ссылке. Вектора так и летают туда-сюда.

Не примите на свой счет, я о своем, наболевшем. Трудно найти C++ разработчика без Java background.

Так вы же сами горорили о копировании, а не о перемещении.

[8K]

Я и говорю, джависты программируют на С++, и хрен втолкуешь разницу между передачей параметров по значению или по ссылке. Вектора так и летают туда-сюда.

Не примите на свой счет, я о своем, наболевшем. Трудно найти C++ разработчика без Java background.

Так вы же сами горорили о копировании, а не о перемещении.

Я вижу на tech screen, что он передает параметр-массив по значению. Спрашиваю, знаком ли с концепцией O-большого, прошу написать руками копирование массива (обычный цикл с поэлементным копированием) и дать оценку (time and space complexity). Вижу, не понимает, что bi = ai не всегда O(1) операция, а просто запомнил, что если цикл на N элементов, то автоматически O(N). Не видит неявных вложенных циклов.

Типа как bead sort, который в теории O(1), а на практике фигушки.