Здравствуйте, SemiCoder, Вы писали:
SC>Здравствуйте, мыщъх, Вы писали:
М>>короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
SC> Строго говоря, иногда на ноль делить-таки можно. И это скажет любой математик.
что такое деление? это многократное вычитание. например, 7/3.
1) 7 — 3 == 4;
4 > 3 делим дальше
2) 4 — 3 == 1;
1 < 3 — конец деления
итого, два и один в остатке.
деление на ноль, очевидно, никогда не будет завершено, хотя интуитивно понятно, что на выходе должна быть бесконечность, но это уже отдельная тема для разговора.
SC> Я помню лет десять назад в одном моем графическом движке, в линуксе, gcc при делении SC> на ноль помещал специально значение NaN в переменную.
float a,b; main(){; printf("%f\n", a/b);}
сl 1.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
1.exe
-1.#IND00
как бы предсказуемо.
SC>if (foo — foo == 0.0) SC> // good value — draw! SC>else SC> // NaN — skip drawing element SC>И ведь работало. Любой математик наверное сразу бы застрелился.
а если так:
float a = 333; float b = 0; float zero = a/b;
float x = 11; float y = 0;
if (x/y == zero) printf("ops");
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>Здравствуйте, blackhearted, Вы писали:
B>>Здравствуйте, мыщъх, Вы писали:
М>>>короче, вам передали дерево как аргумент функции. аргументы мы не проверяем, да? тогда объясните мне тупому, почему команда деления таки выполняет такие проверки, ведь на ноль делить нельзя -- это вам любой математик скажет.
B>>какие проверки выполняет команда деления? в каком языке? М>main(){ return 1/0;}
М>$cl 1.c М>Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86 М>Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
М>1.c М>1.c(1) : error C2124: divide or mod by zero
М>учите мат чать матъ вашу.
Команда деления или компилятор?
#include <iostream>
int main(int argc, char** argv)
{
int i=1;
std::cin >> i;
return 1/i;
}
Здравствуйте, blackhearted, Вы писали:
B>Здравствуйте, мыщъх, Вы писали:
М>>Здравствуйте, blackhearted, Вы писали:
B>>>Здравствуйте, мыщъх, Вы писали:
М>>1.c(1) : error C2124: divide or mod by zero М>>учите мат чать матъ вашу. B>Команда деления или компилятор?
процессор выбросит исключение. язык может его обрабатывать самостоятельно или игнорировать, но тогда его обработает ось и приложение помрет.
1>>------ Build started: Project: test, Configuration: Release Win32 ------
офигеть. а ключи компиляции кто показывать будет? показывайте весь код с ключами компиляции. есть подозрение, что если вы не используете результат деления, то его выкинул оптимизатор. проверяется это просто — при запуске программы не будет исключения. кстати, на результат деления на нуль я бы посмотрел...
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, anomander, Вы писали:
A>Здравствуйте, AndrewJD, Вы писали:
A> Это все конечно здорово, но, думаю, что не ошибусь, если скажу, что в большинстве мест, A> где зададут этот вопрос, захотят сначала услышать ответ, а потом уже, возможно, обсудить
давайте создадим на NTFS каталог в котором есть еще один каталог с жесткой ссылой на отца-с-матерью. и посмотрим сколько программ, обходящих дерево, которое по определению является ацикличным (ну они думают, что дерево каталогов это дерево) поедут крышей. вполне себе отказ в обслуживании, особенно с учетом того, что некоторые архиваторы позволяют распаковать архив, восстанавливая линки. современная почтовая бомба. но домашние компьютеры -- ладно. хрен с ними. а если это критичное к отказу в обслуживании?
классический обход дерева -- а что в нем сложного? это тривиально и описано даже на вики. обсуждать тут нечего. разве что упомянуть про проблемы рекурсивных алгоритмов, т.к. стека у нас порядка метра и в си нет легальных средств посмотреть сколько его осталось. и если одна рекурсивная функция вызывается из другой рекурсивной функции -- то это жопа. вы malloc проверяете на успешность выделения памяти? на фига. у вас порядка двух гигов. а стека всего метр, а сколько его осталось -- мы не знаем. а корректно обрабатывать исключение переполнения стека -- это на грани недокументированных возможностей. исключение выпрыгивает когда стека еще трохи есть (и потому обработать его таки можно), но вот только снимая сторожевой атрибут -- ось его не востанавливает. а это значит, что при повторном переполнении выскочит совсем другое исключение, а именно — аццесс виолейшен. или не выскочит. это зависит от. и если не выскочит, то мы окажемся в чужой памяти и очень клево так его покоцаем.
так же имеет смысл обсуждать возможность "натянуть" на дерево список. в этом случае его обход -- тривиален. и гибридные структуры данных по типу "список-дерево" очень даже рулят. список делает обход нересурсоемкой операцией не требующей выделения памяти, а если еще список является гибридом списка с массивом, то исключаются и циклические ссылки, т.к. мы пребираем только индексы.
> возможные проблемы (в зависимости от используемых языков, технологий и других факторов).
вот-вот. разворот списка сильно зависит от языка и от наличия в нем тех или иных средств.
> Где-то, возможно, пройдет ваш подход, но я бы посчитал его увиливанием от ответа > и сначала вывел бы на прямой ответ, а затем уже обсуждал особенности.
если вы хотите меня завалить, то я даже не буду сопротивляться -- валите. если вам нужен специалист, который пишет программы, которые работают 24/7 -- по моим "увиливаниям" вы поймете, что я уже сталкивался с такими проблемами и для меня не будет новостью, что дерево каталогов это не дерево и что алгоритмы обхода дерева работают только в ms-dos, да и то при условии целостности файловых структур.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, __lambda__, Вы писали: ___> В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack. ___>Несколько лет назад слышал, что кому-то попалась задачка, где нужно было применить RB-tree.
а что применить RB-tree это ужас-ужас?
что до thread safe Stack — так никто не просит вылизывать, главное показать знания, а не написать безупречный
Здравствуйте, Denis, Вы писали:
D>Здравствуйте, __lambda__, Вы писали: ___>> В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack. ___>>Несколько лет назад слышал, что кому-то попалась задачка, где нужно было применить RB-tree.
D>а что применить RB-tree это ужас-ужас? D>что до thread safe Stack — так никто не просит вылизывать, главное показать знания, а не написать безупречный
ну вот и я пытаюсь примерный уровень сложности понять всего-то. но мне уже за что-то -4 влепили
Здравствуйте, Denis, Вы писали:
D>Здравствуйте, __lambda__, Вы писали: ___>> В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack. ___>>Несколько лет назад слышал, что кому-то попалась задачка, где нужно было применить RB-tree.
D>а что применить RB-tree это ужас-ужас? D>что до thread safe Stack — так никто не просит вылизывать, главное показать знания, а не написать безупречный
а это в принципе возможно? тут же синхронизация на другом уровне требуется. допустим, есть несколько потоков. они кладут в стек. допустим, стек thread safe. это как бы не вопрос на счет safe. вопрос в том -- как вытащить оттуда элементы в порядке строго обратном их поклаже? а если порядок неважен, так это и не стек вовсе.
x = Stack.push(a);
...
y = Stack.pop();
что мы снимем если между push и pop в стек что-то положил другой поток?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
___>Самое интересное, что в соседних ветках от Паблика Морозова, сертифицированный MVP от MS с пеной у рта доказывает, что задача с переворотом списка слишком сложна для собеседований В то время, как в соседних ветках, обсуждают, что для поступления в этот же MS нужно написать thread-safe Stack.
и что, ты хочешь сказать, что в MS платят столько же, сколько у паблика?
подозреваю, что начальная зарплата там раза в 2 больше
Здравствуйте, мыщъх, Вы писали:
М>Здравствуйте, blackhearted, Вы писали:
B>>Здравствуйте, мыщъх, Вы писали:
М>>>Здравствуйте, blackhearted, Вы писали:
B>>>>Здравствуйте, мыщъх, Вы писали:
М>>>1.c(1) : error C2124: divide or mod by zero М>>>учите мат чать матъ вашу. B>>Команда деления или компилятор? М>процессор выбросит исключение. язык может его обрабатывать самостоятельно или игнорировать, но тогда его обработает ось и приложение помрет.
Язык?
1>>>------ Build started: Project: test, Configuration: Release Win32 ------ М>офигеть. а ключи компиляции кто показывать будет? показывайте весь код с ключами компиляции. есть подозрение, что если вы не используете результат деления, то его выкинул оптимизатор. проверяется это просто — при запуске программы не будет исключения. кстати, на результат деления на нуль я бы посмотрел...
Всё отлично падает с access violation, если ввести 0.
Как оптимизатор мог его выбросить, если он возвращается как результат выполнения?
Чем тут помогут ключи компиляции?
Пожалуй стоит еще раз сказать, что интервью (даже в МС) — это не ЕГЭ.
Т.е. важно даже не то, правильно ли вы решили задачу, а то, КАК вы ее решаете. Интервьюера не интересует как разворачивать список, его инетерсует — понимаете ли Вы как подходить к задаче. Побольше говорите, объясняйте почему выбрали тот или иной подход.
По алгоритмам и стурктурам данных задачи будут такие, чтобы решение (или аутлайн решения) поместился на доске. Т.е. (условно говоря) реализовывать красно-черные деревья вам не надо будет (но надо знать зачем они нужны!).
М>даю вводную. М>винда (проверял хрюшу, что под рукой), NTFS. FAR. М>F7, "demo_1", cd demo_1, Alt-F6, "demo_1\demo_2".
М>работает! можно бесконечно входить в demo, спускаясь все глубже и глубже (в FAR'e). а теперь посмотрите сколько программ развалится, если их попросить обработать директорию с под-директориями.
подозреваю, что там есть апи для отличания такой ссылки от честной директории
под линуксом, афайк, ext2/ext3 не дает создать настоящие хардлинки на директорию; симлинки пожалуста, но их при желании можно отличить
Здравствуйте, мыщъх, Вы писали:
М>а это в принципе возможно? тут же синхронизация на другом уровне требуется. допустим, есть несколько потоков. они кладут в стек. допустим, стек thread safe. это как бы не вопрос на счет safe. вопрос в том -- как вытащить оттуда элементы в порядке строго обратном их поклаже? а если порядок неважен, так это и не стек вовсе.
М>x = Stack.push(a); М>... М>y = Stack.pop();
М>что мы снимем если между push и pop в стек что-то положил другой поток?
зависит от того что хотим добиться . можно спросить определение стека у собеседующего и приватно его ... ну сделать что хочется
завайте вопросы, смотрите на реакцию интервьювера.
Здравствуйте, Ilias, Вы писали:
I>ну вот и я пытаюсь примерный уровень сложности понять всего-то. но мне уже за что-то -4 влепили
про минусы не справшивайте, я не понимаю за что, видимо у господ Klatu, blackhearted, asktomsk, dilmah чесотка рук
про уровень сложности — в компании МС работает 95тыс человек. общей гребенки нет, как повезет. В одну группу спрашивать будут до изнеможения, в другую все будет попроще.
имхо, подготовится немного стоит (я список привел в этом треде), что бы на мелочах типа перевернуть список не обжигаться. но дальше опыт поможет и фортуна.
я спрашиваю обычно дизайн и многопоточность. головоломки не спрашиваю вообще, прочитав много книг про интервью так и не понял в чем их прелесть (так же как и наняв несколько человек, которые их раскусили и вообще были круты, но вот с просто кодом были проблемы )
Здравствуйте, blackhearted, Вы писали:
B>Здравствуйте, мыщъх, Вы писали:
B>>>Команда деления или компилятор? М>>процессор выбросит исключение. язык может его обрабатывать самостоятельно М>>или игнорировать, но тогда его обработает ось и приложение помрет. B>Язык?
пишу же, что любой компилятор или интерпретатор любого языка не сможет обработать ситуацию деления на ноль без дополнительных телодвижений. процессор не обязан выбрасывать исключение при делении на ноль (зависит от процессора) и у процессора может не быть команды деления вообще. но где бы ни было реализовано деление (в железе или софте), деление на ноль является особой ситуацией, обрабатываемой отдельно. как именно обрабатываемой -- это отдельный разговор.
1>>>>------ Build started: Project: test, Configuration: Release Win32 ------ М>>офигеть. а ключи компиляции кто показывать будет? показывайте весь код с ключами компиляции. есть подозрение, что если вы не используете результат деления, то его выкинул оптимизатор. проверяется это просто — при запуске программы не будет исключения. кстати, на результат деления на нуль я бы посмотрел...
B>Всё отлично падает с access violation, если ввести 0. B>Как оптимизатор мог его выбросить, если он возвращается как результат выполнения?
я ж не видел целиком вашего проекта.
B>Чем тут помогут ключи компиляции?
без ключей компиляции (т.е. с настройками по умолчанию) ms vc возвращает ошибку. во всяком случае у меня. а у вас даже предупреждения нет. странно все это.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, m e, Вы писали:
М>>работает! можно бесконечно входить в demo, спускаясь все глубже и глубже (в FAR'e). а теперь посмотрите сколько программ развалится, если их попросить обработать директорию с под-директориями. ME>подозреваю, что там есть апи для отличания такой ссылки от честной директории
и тут мы подходим к вопросу как решать такие задачи в общем виде. нам нужно либо API, которое позволит установить что узел А и узел Б в действительности является одним и тем же узлом. такое есть в ntfs, но это сильно нестандартное и непортируемое. а хардлинки есть много где. и що делать? как альтернатива -- можно создавать в каждой директории которую мы посетили специальный файл и не входить в директорию если он там есть (но это требует прав записи).
другой способ -- если у каждого узла дерева (ну директории) есть некая уникальная характеристика, которую можно считать документированными средствами -- при наличии доп. памяти можно заносить эти характеристики в базу и смотреть -- посещали мы этот узел или нет. и тут всплывает интересная проблема. при решении задачи "в лоб" мы храним _все_, но это ж сколько памяти требуется?! немного подумав, мы соображаем, что все хранить необязательно и в определенный момент от части инфы можно избавляться, поскольку она гарантированно нам не нужна и расходы на память резко сокращаются.
для тренировки можно написать программу на js, которая дампит объекты от корня и до многодетной матери. там как раз возникает проблема циклических ссылок.
ME>под линуксом, афайк, ext2/ext3 не дает создать настоящие хардлинки на директорию; ME>симлинки пожалуста, но их при желании можно отличить
кто ж спорит, что при желании можно. и не только можно, но и нужно. но вы все-таки проведите эксперимент и посмотрите сколько програм падает при попытке обработки такой директории с поддиректориями.
я как бы молчу, что можно так испортить MBR, чтобы винда зацикливалась при монтировании диска, а так как она это делает автоматически, то автоматически виснет. флеха с таким MBR вгоняла w2k в синий экран. XP SP0 (другую не проверял) на однопроцессорной машине просто зависала где-то в ядре. на двух цп хрюша выживала, но жутко тормозила и показывала 100% загрузку ядра одного ЦП.
а все потому что в MBR можно создавать циклические ссылки и их никто не проверял.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, Denis, Вы писали:
D>а что применить RB-tree это ужас-ужас? D>что до thread safe Stack — так никто не просит вылизывать, главное показать знания, а не написать безупречный
Relax, мы на одной стороне баррикад Это я прикалываюсь над теми, для кого переворот списка сверх сложная задача на собеседовании
Computer science is no more about computers than astronomy is about telescopes (c) Edsger Dijkstra
Здравствуйте, Denis, Вы писали:
D>Здравствуйте, мыщъх, Вы писали:
М>>x = Stack.push(a); М>>... М>>y = Stack.pop(); М>>что мы снимем если между push и pop в стек что-то положил другой поток? D>зависит от того что хотим добиться . можно спросить определение стека у собеседующего и приватно его...
гм, а если собеседующий спросит: "как?! вы не знаете что такое стек?! нууууу....". вообще, такое очень даже можно сделать. только нужно ввести дополнительные условия.
1) всякий поток может юзать обший стек, но об этом он должен сигнализировать всем остальным;
2) после того как поток поюзал стек он должен снять все, что туда поклал;
3) между (1) и (2) доступ к стеку всем остальным потокам блокируется
4) разновидность (3) -- доступ не блокируется, но результат временно сохраняется в другом месте;
5) развитем идеи (4) будет предоставление каждому потоку своего стека. это можно делать "прозрачно" для потоков. например, компиляторы могут при необходимости ложить глобальные и статические переменные в раздельные области памяти, которые у каждого потока свои и программисту не нужно парится об этом явно. ну так почему не создать объект стек с функциями push и pop, где смотреть ID потока и юзать персональный стек? но для этого нам нужно API для взятия ID потока, причем для быстрого взятия, а совсем не то API, которое нам дают. впрочем, если извратиться, то ID потока можно определять косвенным путем по адресу локальных переменных.
D> завайте вопросы, смотрите на реакцию интервьювера.
так ведь уже ответили, что технически реализовать safe возможно и даже тривиально, но это будет не стек, или это будет стек, но он не будет работать. по русски стек это стопка. стек не допускает адресации. адресация локальных переменных к стеку никакого отношения не имеет. в общем случае стек не предоставляет такой фичи. а потому между push и pop никто не может трогать стек иначе все рухнет. кто писал резиденты под дос -- тот знает.
safe имеет смысл для словарей, т.к. им порядок по фиг. у них порядок итерации вообще не гарантирован. у них главное -- уникальность ключа. и доступ к словарю из двух и более потоков очень даже полезная штука. можно сходу придумать кучу задач, где она нужна. а вот вообразить себе задачу с общим стеком... ладно бы очередь. очередь очень близка к стеку, но она используется иначе. в очередь потоки-писцы кладут задачи, а другие потоки из извлекают и обрабатывают и могут в ту же самую очередь еще и результат запихать, особенно если он промежуточный. на ум приходит телепортирование сайтов. считываем страницы из разных потоков, парсим их, кидаем в очередь результат нашей работы (извлеченные ссылки) и снова извлекаем их, скачивая еще больше страниц.
а если наш собеседник хотел очередь, а просил нас реализовать стек -- такое не лечится.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
ME>подозреваю, что там есть апи для отличания такой ссылки от честной директории
ME>под линуксом, афайк, ext2/ext3 не дает создать настоящие хардлинки на директорию; симлинки пожалуста, но их при желании можно отличить
но в юниксах ты можешь размножать директории многократным монтированием
Здравствуйте, hokkaido, Вы писали:
H>Т.е. важно даже не то, правильно ли вы решили задачу, а то, КАК вы ее решаете. Интервьюера не интересует как разворачивать список, его инетерсует — понимаете ли Вы как подходить к задаче. Побольше говорите, объясняйте почему выбрали тот или иной подход.
H>По алгоритмам и стурктурам данных задачи будут такие, чтобы решение (или аутлайн решения) поместился на доске. Т.е. (условно говоря) реализовывать красно-черные деревья вам не надо будет (но надо знать зачем они нужны!).
В целом согласен, но когда я проводил интервью здесь, по крайней мере для простых задач вроде "развернуть список", я ожидал что человек напишет работающее решение от и до. Вы не представляете сколько людей не могут найти простые баги в своем коде на 20 строчек — а ведь им потом code review делать для чужого...
Здравствуйте, мыщъх, Вы писали: М>гм, а если собеседующий спросит: "как?! вы не знаете что такое стек?! нууууу....".
1) если собеседующий дебил, это не лечится. радуйтесь, что вам с ним не работать
2) задавать вопрос надо так, что бы минимизировать неправильное понимание вопроса
