найти средний элемент связанного списка

[valchkou]

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

а никто не пробовал попросить написать любой код по желанию ?

а смысл? вы ж не фантазёров на работу ищите.

так разве та контора не фантазеров искала.
Ну есть уже на яве и size() и get(i) на связаном списке, в чем смысл спрашивать как бы вы изобрели свой велосипед ?
Правильно, только в том, чтобы выяснить вашу велосипедную изобретательность, а не умение использовать уже говый.

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

зато это уникальная возможность выяснить, о чем в данный момент думает кандидат.
Жаль, но интервью по делу попадаются все реже и реже.
бывало что такие интересные вопросы и темы поднимали, и кажется что вот оно, проект должно быть крут.
Начинаю работать и не понимаю, к чему был весь этот цирк.
возможно, что я один такой невезучий

[fruit6]

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

а никто не пробовал попросить написать любой код по желанию ?

а смысл? вы ж не фантазёров на работу ищите.

так разве та контора не фантазеров искала.
Ну есть уже на яве и size() и get(i) на связаном списке, в чем смысл спрашивать как бы вы изобрели свой велосипед ?
Правильно, только в том, чтобы выяснить вашу велосипедную изобретательность, а не умение использовать уже говый.

альтернативы всегда есть. например придумать незнакомую структуру данных вместо более-менее понятного списка, потратить время на объяснение и получить "WTF" реакцию в ответ. человек быстро сделает выводы и будете искать заново.

[valchkou]

Нормальная задачка. На понимание связанных списков.
По моим наблюдениям, человек, решающий подобную задачу через size() и get(i), потом пишет такой код

for (i=0; i< list.size(); i++) {
if (list.get(i)==someObject) {....}
}

а как бы вы написали, не на интервью, а на реальной работе, на яве ?

[АццкоМото]

Нормальная задачка. На понимание связанных списков.
По моим наблюдениям, человек, решающий подобную задачу через size() и get(i), потом пишет такой код

for (i=0; i< list.size(); i++) {
if (list.get(i)==someObject) {....}
}

а как бы вы написали, не на интервью, а на реальной работе, на яве ?

например
if(set.contains(someObject))
Или что-то другое более подходящее к контексту, не?

mikeG на мой взгляд очень в корень воззрел: многие просто не хотят на секундочку задуматься, как должно быть правильнее и лепят что-то несусветное, вместо того, чтобы пользоваться готовыми кирпичиками, любезно предоставленными им умными людьми.
Из недванего. Нужно было добавить новую функциональность в модуль, куда даже не заглядывал ни разу. А там... мамочки. Чел получает с сервера список файликов, и список дирок. С какими-то малопонятными и многочисленными конвертациями между "просто массивом" и ArrayList и обратно слепляет их в общий список, после чего сортирует слегка модифицированным пузырьком, чтобы список был в алфавитном порядке, но сначала все дирки, а потом все файлики. Хоть святых выноси.
Не в том даже дело, что неэффективно или там комплексити квадратичный, да пофигу в целом. Просто несколько экранов малопонятного, запутанного, ненадежного и никому нахрен ненужного кода вместо нескольких простых строк

С автором я вживую не встречался, но уверен, он знает миллион шорткатов и очень быстро кодирует - так быстро, что мысль за пальцами не поспевает

[rzen]

ох у меня раз был "контакт" с человеком который в диапазоне 10 минут вверг меня сначала в полное восхищение владением клавиатурой (ну _ооочень_ быстро печатал). при чем не лирику, а оракловые директивы, а это целый огород не для слабонервных. но когда он одно и тоже начал перепечатывать в восьмой (не шучу) раз потому что очепятался (это как раз небыло удивительно, запросы были строк по 8-12). на вопрос а ноутпад запустить? чувак посмотрел на меня снисходительно и продолжил своё интеллектуальное занятие.

причем сам по себе нормальный чувак, я с ним в отличных отношениях.

[valchkou]

Нормальная задачка. На понимание связанных списков.
По моим наблюдениям, человек, решающий подобную задачу через size() и get(i), потом пишет такой код

for (i=0; i< list.size(); i++) {
if (list.get(i)==someObject) {....}
}

а как бы вы написали, не на интервью, а на реальной работе, на яве ?

например
if(set.contains(someObject))
Или что-то другое более подходящее к контексту, не?

mikeG на мой взгляд очень в корень воззрел: многие просто не хотят на секундочку задуматься, как должно быть правильнее и лепят что-то несусветное, вместо того, чтобы пользоваться готовыми кирпичиками, любезно предоставленными им умными людьми.

извиняюсь неправильно спросил, я имел ввиду как бы mikeG достал средний элемент в реальном коде, а не на собеседовании.
Он просто сделал странное наблюдение, а по мне, так size() и get(i) и есть те самые любезные кирпичики.
size в момент вызова size() не вычисляется, можно сказать константа, поэтому и производительность О(n/2) и код в 3 раза короче и читабельней.

[АццкоМото]

извиняюсь неправильно спросил, я имел ввиду как бы mikeG достал средний элемент в реальном коде, а не на собеседовании.
Он просто сделал странное наблюдение, а по мне, так size() и get(i) и есть те самые любезные кирпичики.
size в момент вызова size() не вычисляется, можно сказать константа, поэтому и производительность О(n/2) и код в 3 раза короче и читабельней.

извиняюсь, неправильно понял
Ну да, в реальной жизни 99% решений будут именно такими и ничего плохого в этом нет

[8K]

Ну да, в реальной жизни 99% решений будут именно такими и ничего плохого в этом нет

Плохо то, что вырабатывается неправильная привычка (предполагать, что списки всегда реализованы при помощи массива).

[АццкоМото]

Ну да, в реальной жизни 99% решений будут именно такими и ничего плохого в этом нет

Плохо то, что вырабатывается неправильная привычка (предполагать, что списки всегда реализованы при помощи массива).

Где вы вообще нашли такое предположение?

[8K]

Плохо то, что вырабатывается неправильная привычка (предполагать, что списки всегда реализованы при помощи массива).

Где вы вообще нашли такое предположение?

Там, где использовали size() и get(i).

[АццкоМото]

Плохо то, что вырабатывается неправильная привычка (предполагать, что списки всегда реализованы при помощи массива).

Где вы вообще нашли такое предположение?

Там, где использовали size() и get(i).

Ничего подобного. Размер списка достаточно просто хранить - инкрементируя его при добавлении элемента и декрементируя при удалении. Тогда size() - константное время. А сложность get(N/2) была честно оценена как О(N/2) - что справделиво как раз для классического односвязного списка, а не для массива
Более того, даже если размер списка нужно каждый раз вычислять пробегая по нему целиком, сложность один хрен выйдет O(3N/2) - точно такая же, как в алгоритме с двумя указателями. Т.е. чтобы он возымел смысл, нужно вводить дополнительное условие - что список насколько односвязный, что мы не можем вернуться не то, что к предыдущему элементу, но даже и к первому. А такое условие выглядит очень искусственным

[8K]

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

[АццкоМото]

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

Поскольку контекст был - "в обычной каждодневной работе на джаве", мне не кажется надуманным обязательное присутствие этих двух функций в интерфейсе java.util.List

[mr boombastic]

считаю что size() вполне оправданная функция,
get(i) - вряд ли. не предаставляю как можно его сделать в O(1).
если посмотреть на STL list, то там даже operator[] отсуствует именно по этой причине.

[8K]

считаю что size() вполне оправданная функция

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

И сколько байт под счетчик отведете?

[АццкоМото]

get(i) - вряд ли. не предаставляю как можно его сделать в O(1).

а про O(1) никакой речи и не было - его считали как O(n)

[АццкоМото]

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

А в джавовском списке нет операции "попилить надвое вот тут"

И сколько байт под счетчик отведете?

int size()
Returns the number of elements in this list. If this list contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Вообще, конечно, в каждой конкретной ситуации могут быть свои вводные. Где-то есть смысл хранить размер, где-то нет

[8K]

А в джавовском списке нет операции "попилить надвое вот тут"

Естественно, это ж массив, а не список.

Но мы-то не про джаву, а про программирование вообще? И про то, что некоторые привычки хуже других.

А джавистов переучивать совершенно беспонтово, тут я согласен. Уже был опыт.

[8K]

И сколько байт под счетчик отведете?

int size()
Returns the number of elements in this list. If this list contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Hadoop, болезный, при полтораста "гектар" оперативки вынужден свопать все данные на диск, потому что даже 64-битная Джава не умеет создавать массивы больше 2 гектар, и потому что разработчики Hadoop'а не осилили идею хранить данные от маперов в настоящем списке.

[valchkou]

А в джавовском списке нет операции "попилить надвое вот тут"

Естественно, это ж массив, а не список.

это именно список а не массив, если мы говорим про жававский LinkedList и его производные.
size изменяется в момент добавления/удаления элементов, и не вычисляется в момент size()

get(i) идет либо сверху, либо снизу по связаному списку до нужного элемента, взависимости от того куда ближе i.

[АццкоМото]

А в джавовском списке нет операции "попилить надвое вот тут"

Естественно, это ж массив, а не список.

java.util.List - это интерфейс. у него нет никакой имплементации. Имплементировать можно хоть через односвязный список, хоть через двухсвязный, хоть через массив, хоть через сине-зеленые деревья.

Но мы-то не про джаву, а про программирование вообще? И про то, что некоторые привычки хуже других.

Вы пропустили - там выше было разделение, что типа на интервью можно и так и эдак, а вот как бы сделали в реальной жизни в обычный рабочий день. Ну вдруг вот понадобилось найти средний. И тут выясняется, что l.get(l.size()/2) - в подавляющем большинстве ситуаций - самый верный вариант

А джавистов переучивать совершенно беспонтово, тут я согласен. Уже был опыт.

Нужно ли, вот в чем вопрос. Хорошие джависты думают не так, как сишники, но не могу сказать, что это плохо. А плохие джависты... тут уже пофигу, джависты они или нет, ключевое слово - плохие.

[avitya]

А в джавовском списке нет операции "попилить надвое вот тут"

Естественно, это ж массив, а не список.

это именно список а не массив, если мы говорим про жававский LinkedList и его производные.
size изменяется в момент добавления/удаления элементов, и не вычисляется в момент size()

get(i) идет либо сверху, либо снизу по связаному списку до нужного элемента, взависимости от того куда ближе i.

Так вот, я же написал выше: что это не аксиома. Например, в другом популярном языке с инкрементом, сайз вычисляется в момент вызова ( фактически distance(begin(), end()), так как оптимизирована другая функция).

[АццкоМото]

Так вот, я же написал выше: что это не аксиома. Например, в другом популярном языке с инкрементом, сайз вычисляется в момент вызова ( фактически distance(begin(), end()), так как оптимизирована другая функция).

Вот контекст, в котором шло обсуждение:

а как бы вы написали, не на интервью, а на реальной работе, на яве ?

[8K]

Это я так, брюзжу. Издержки возраста. В реальной жизни я список последний раз видел в Майкрософте лет десять назад и хотел его прибить нафиг, но мне не позволили старшие товарищи. Еще на интервью, конечно, и вот сейчас на Питоне, но тут уж о производительности или красоте речи нет.

Про джавский список - наверное, я его с с-шарповским перепутал. У тех доступ по индексу занимает O(1).

[avitya]

Ну потому что в С#, это ArrayList<T> из явы. То есть, IList<T> ~ List<T> и List<T> ~ ArrayList<T>