How to become an author
Search
Write a publication
Pull to refresh

Comments 101

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

Но в тоже время:
Если использовать язык с удобной семантикой для работы со списками и особенно не задумываться об использовании памяти и общей производительности, то код решения будет простым

То есть, придя на собеседование по Java вакансии, я могу реализовать тестовые задания, скажем, на питоне? Только не надо говорить, что «не важно на каком языке вы будете выполнять тестовое задание, ведь оцениваются общие способности программиста без привязка к конкретному языку».
Total votes 10: ↑7 and ↓3+4
Но ведь «не важно на каком языке вы будете выполнять тестовое задание, ведь оцениваются общие способности программиста без привязка к конкретному языку»
Total votes 3: ↑3 and ↓0+3
Если я ищу Java-разработчика, то буду слегка в недоумении, если кандидат будет решать тестовое задание на чём-то другом.
Total votes 8: ↑6 and ↓2+4
Наше основное разногласие здесь в том, разумно ли искать <язык программирования>-разработчика вообще.
Мое мнение, что это хорошая краткосрочная инвестиция, потому что человек быстрее начнет быть полезным, но это также сильно сужает круг потенциальных кандидатов, что должно ожидаемо уменьшить качество в долгосрочной перспективе.
Но это все субъективно и без статистики, я могу представить как противоположная моей точка зрения может быть разумной.
Total votes 2: ↑1 and ↓10
Просто в моём текущем проекте у нас нет возможности брать разработчиков на вырост, посему ищутся люди, которые смогут сразу же работать с тем, что у нас есть, так как сроки не резиновые.

Поэтому при ответе я отталкивался от этого опыта.

Total votes 1: ↑1 and ↓0+1
По-моему это вполне нормальная практика. Я сам прошел собеседование год назад на питон-разработчика, задачи решая на С++.
This comment wasn’t rated yet0
Не вижу проблемы в таких задачках. Главное, чтобы защиталось такое решение:

var listA = new List<int>() {1,2,3};
var listB = new List<int>() {3,2,1};
var listC = listA.Concat(listB).OrderBy(x => x).ToList();
Total votes 11: ↑8 and ↓3+5
Главное, чтобы защиталось такое решение:
from heapq import merge
Total votes 14: ↑12 and ↓2+10
Эээ… И что, решение, в котором минимум ищется, как нулевой элемент результата сортировки будет хоть как-то засчитано? Я понимаю, что можно не сразу вспомнить о приоритетной очереди для выбора очередного минимума. Но чтобы так?
Total votes 4: ↑3 and ↓1+2
Тоже удивлён, что про хип, который просто просится сюда, ни слова, как впрочем и про оценку сложности алгоритма.
Total votes 3: ↑2 and ↓1+1
---Программирование на собеседованиях останется распространенной практикой еще долгое время

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

Чем больше компания тем меньше у них требования к написанию кода.

Чем меньше компания и дурнее менеджеры тем мозгопарюшие у них задачи.
Total votes 20: ↑18 and ↓2+16
UFO just landed and posted this here
А что если у разработчика нет активности в открытых проектах? Отсутствие проектов на гитхабе ни как не говорит о несостоятельности разработчика.
Total votes 7: ↑7 and ↓0+7
UFO just landed and posted this here
Т.е. вы считаете, что случай когда у человека есть активность в публичном репозитории это единственно нормальный вариант? У меня, вот, нет ни строчки кода в публичном репозитории и меня почему-то взяли на нормальную работу. А так же у большинства нанимаемых разработчиков.
Total votes 3: ↑2 and ↓1+1
UFO just landed and posted this here
Мне кажется, что ваше представление о норме ошибочно. Но все равно статистики нет и ее надо собирать для того, чтобы что-то утверждать.
Total votes 4: ↑3 and ↓1+2
Например, у меня. Учитывая место, где я работаю — мои проекты никогда не будут в публичном доступе. Правда, большая часть кода, разумеется, ничего интересного не содержит и не выдаст область применения. Но такой порядок.
Total votes 2: ↑2 and ↓0+2
UFO just landed and posted this here
Зачем мне заводить pet проекты если я на работе занимаюсь тем, что мне интересно?
Total votes 10: ↑9 and ↓1+8
В репе нет динамики того как ты решаешь задачу и думаешь
Total votes 8: ↑5 and ↓3+2
Как это нет — а история коммитов?
Total votes 4: ↑3 and ↓1+2
Коммит это уже решение какой-то задачи. Особенно учитывая любовь к rebase и чистке истории ничего о том как решалась задача не остается.
Total votes 5: ↑4 and ↓1+3
Не встречал, если честно, большой любви к rebase. Если коммиты небольшие, то по ним как легко проследить ход решения на макроуровне, так и оценить скорость решения задач по частоте коммитов. (А делать большие коммиты непраивльно, и кандидат просто получает минус в карму) На микроуровне проследить действительно не получится, но оно нужно? (С учетом того, что решение и временные затраты понятны)?
Total votes 6: ↑3 and ↓30
UFO just landed and posted this here
Нет. Работодателю, если он хочет вас в коллектив разработчиков, а не нанять для решения конкретной задачи в качестве совершенно отдельного контрактора, важно знать как вы решаете, как делаете предположения об условиях, как контактируете с другими людьми при решении и множество других нюансов, которые можно посмотреть в процессе решения.
Total votes 6: ↑2 and ↓4-2
UFO just landed and posted this here
Это вы считаете, что нельзя ничего посмотреть. Работодатель вполне себе наблюдает.
Вот вам дают условия задачи и вы сразу садитесь и начинаете делать что-то? Не уточняете условия, не проясняете что от вас хотят и не планируете?
Total votes 2: ↑1 and ↓10
Если задача чётко поставлена, зачем что-то уточнять?
Total votes 4: ↑4 and ↓0+4
Для проверки взаимопонимания, для проверки того, что говорят используя одно и то же понимание термина, для того, чтобы банально не ослышаться. Для того, чтобы после не выяснилось, что решалась совсем другая задач.
Да и кто сказал, что дадут идеально сформулированые условия? Это же тоже проверяемые навыки — как человек воспринимает постановку задачи, видит ли он слабости или неопределенные умолчания.
Total votes 4: ↑2 and ↓20
Вы всё ссылаетесь на социальный аспект. Я когда выполняю/ставлю задачи, стараюсь почти не общаться с людьми. Есть система тикетов/вики, человек всегда может там спросить. А вербальное общение многим приносит дискомфорт.
Total votes 4: ↑3 and ↓1+2
Это не социальный аспект. В том же самом тикете могут написать такую же не идеально сформулированную задачу. И точно так же надо уточнить, задать дополнительные вопросы и т.д.
This comment wasn’t rated yet0
Например, хотят ли они, чтобы код был
— быстро написан
— красив
— понятен
— устойчив к некорректным входным данным
— эффективно работал
— экономно расходовал память.
Разные ответы или приоритеты этих параметров могут потребовать очень разного кода.
И ещё полезно узнать диапазон входных данных — а вдруг они хотят, чтобы программа считала числа Фибоначчи до номера 10^9?
Total votes 1: ↑1 and ↓0+1
Такие вещи мы обычном в тикете описываем, чтоб по 100 раз к ним не возвращаться.
Total votes 1: ↑0 and ↓1-1
Ну честно говоря конкретно ваша репа мало о чем скажет работодателю — мало проектов, они все без описания и без демок. Кроме того, мало коммитов, старов, issue и прочих социальных вещей, которые потенциально говорили бы работодателю об умении контактировать с другими разработчиками. Да и кода мало.
Total votes 5: ↑4 and ↓1+3
вы считаете себя реально такой звездой? вы в курсе, что на любую вакансию с нормальными деньгами тут же приходит больше сотни отзывов и после первичного фильтра остается 50? и что, мне таки по всем 50 ходить и читать репы? ищите дальше )
Total votes 10: ↑2 and ↓8-6
UFO just landed and posted this here
Зависит от уровня компании. Гугл получает в сотни раз больше резюме чем нанимает.
This comment wasn’t rated yet0
Да уж, с сотней вы мягко говоря преувеличили.
Total votes 2: ↑2 and ↓0+2
Типа я ищу разработчиков, но не вы мне нужны, а я вам. У меня деньги — построились и пляшем. К таким работодателям опытные разработчики обычно даже не приходят, а работу получают те, кто лучше пляшет. Выбрать из 50 кандидатов с портфолио одного или несколько подходящих — совсем несложно.
Total votes 2: ↑2 and ↓0+2
Все верно, кандидатов надо отбирать по портфолио. Очень часто, устраивая всякого рода экзамены, работодатель ищет не знания, а пробелы в знаниях для сбивания цены. Типа ищем опытного сантехника и устраиваем ему экзамен по сопромату и атлетике. Чем больше кандидат рвет пупок и тратит времени, тем легче после этого будет сбить цену.
Total votes 2: ↑1 and ↓10
Чтобы давать задачки на собеседованиях, надо уметь их адекватно оценивать. Зачастую работодатель хочет получить ответ, именно, то который он знает, а не тот который может предложить кандидат
Total votes 11: ↑11 and ↓0+11
какие еще вопросы можно было бы задать кандидату, который написал представленный выше код за отведенные ему 40 минут.

Любопытно, а сам Реджинальд уложился в 40 минут при написании кода из статьи?
Total votes 4: ↑4 and ↓0+4
Задачи на собеседовании это хорошо. Но задача должна решаться без привязки к методам (функциям) конкретного языка. Вы знание человеком плюшек JS (ES) проверяете или его умение составить алгоритм? По приведённым решениям задач скорее первое.
This comment wasn’t rated yet0
Тут же палка о двух концах. Если нужен просто толковый программист, то Вы правы. Но иногда нужен спец по конкретному языку/фреймворку.
Total votes 1: ↑1 and ↓0+1
Совершенно согласен! Просто исходя из названия статьи (туда не вынесен ЯП) ожидал увидеть описание универсальных вопросов, без привязки к конкретному ЯП.
This comment wasn’t rated yet0
Если бы кандидат писал слияние сортированных списков вручную, я бы ему минус поставил — не знает про библиотечные функции. Например в Java стандартный sort — это TimSort, который отлично работает именно на таких задачах.
Total votes 5: ↑0 and ↓5-5
Что важнее, знать библиотечные функции или понимать/уметь написать тоже самое самому? Извечный холивар.
Total votes 1: ↑1 and ↓0+1
а как же умение применять то, что написали другие и понимание того, как это работает?
Total votes 1: ↑1 and ↓0+1
Важнее всего через 3 года посмотреть на свой код и сразу же понять, что он делает.
А еще лучше, другой программист сразу должен его понять.
Библиотечные функции протестированы на кучу проектов и хорошо документированы.
Свой велосипед может содержать баги (только не надо говорить, что нужно писать без багов — вероятность допустить ошибку есть всегда).
This comment wasn’t rated yet0
Простите, не могу согласиться. Одно дело, когда вы решаете фундаментальные задачи, а другое дело, когда пишете бизнеслогику. Читать исходный код и понимать, что он делает, это не одно и тоже. Ну да, вот я вижу, что складываются два числа, но зачем? (это риторический вопрос).
This comment wasn’t rated yet0
Тут опять палка о двух концах. Если мне на Яве дать задание, то я тоже сходу не вспомню, где там стандартная сортировка. Просто потому, что на ней ничего не писал уже много лет. То есть да, можно сказать, что я не знаю про библиотечные функции, но в то же время я в кратчайшее время все вспомню. Не будем задаваться вопросом, почему я не подготовился к собеседованию, зная, что там будет Java. Я просто хочу сказать, что проводить собеседование по жестко заданным правилам нельзя — надо смотреть по обстоятельствам. Но проводить собеседование программиста должен тоже программист. Только он поймет, на что способен кандидат.
Total votes 6: ↑6 and ↓0+6
Я неправильно выразился. Не «поставил бы минус», а «поставил бы плюс за знание библиотечной функции» — так лучше? :)
Total votes 1: ↑1 and ↓0+1
Ну в принципе согласен. Знание их — плюс, незнание — не обязательно минус.
Total votes 1: ↑1 and ↓0+1
Если бы кандидат писал слияние сортированных списков вручную, я бы ему минус поставил — не знает про библиотечные функции. Например в Java стандартный sort — это TimSort, который отлично работает именно на таких задачах
.
Вот поэтому я и не люблю такие задачи на собеседованиях, так они скорее предназначены для поднятия ЭГО того кто их проводит.

Ничего что TimSort дает в среднем O(N log N) + O(N) объединение списков до сортировки, а слияние вручную простым движением по спискам и сравнением стабильно O(N), причем скорее всего значительно более быстрый O(N) чем Timsort? А то что затраты памяти будут вдвое больше? А если каждый список по нескольким миллионам элементов и требуется написать как можно более производительный код?
Total votes 8: ↑7 and ↓1+6
Что даст TimSort, если массив сразу состоит из двух отсортированных частей? O(N log N), или что-нибудь ближе к O(N)? И откуда «вдвое больше памяти»? Если исходные списки имели суммарный размер K, то при ручном слиянии вам потребуется дополнительно K для хранения результата, итого 2*К. Если идти через сортировку, то массив (который и будет результатом) имеет размер К, плюс дополнительный массив на слияния будет длиной К/2 (конечно, зависит от реализации, но если она написана хорошо, то больше не нужно). Итого 5/2*К, всего на 25% больше ручного слияния. А никак не вдвое.
По производительности. Стандартная сортировка, скорее всего, будет написана на низкоуровневом языке (например, на С), если тип данных базовый и операция сравнения стандартная. Обойти такую сортировку, работая со структурами высокого уровня (такими, как список), будет непросто.
Но, конечно, всё решает эксперимент. Результаты могут различаться в несколько раз в любую сторону.
Total votes 3: ↑1 and ↓2-1
А что гадать откройте исходники Java и посмотрите:
1. Никакой нативной реализации там, конечно, нет, так как это нарушило универсальность,
2. Там сначала списки объединяются addAll (O(n)) список превращается в Array (O(N)), потом производится сортировка (от O(N) до O( N log N), потом массив записывается обратно в список (O(N)), сколько раз вы переплатили за Trimsort?
3. Да, я ошибся памяти будет занято даже больше чем в два раза, так как будет копирование в массив и у TimSort занятость памяти указывается как N, то есть от 2 до 3 раз расход памяти увеличится.
4. А ручная реализация соединения очень простая, сравниваем текущие элементы, если больше первый добавляем его в результирующий список и итерируемся по первому списку, иначе добавляем второй и итерируемся по второму списку.
Total votes 5: ↑4 and ↓1+3
0. Для этого надо во-первых, знать, где лежат исходники Java, во вторых, ориентироваться в них. Честное слово, пока необходимости в этом у меня нет. Лучше я в исходниках C# поковыряюсь.
1. Если её нет — то это недостаток библиотеки. В C#, например, сортировка базовых типов переключается на низкий уровень, и никакой универсальности это не нарушает:
                if (comparer == Comparer.Default || comparer == null) {
                    bool r = TrySZSort(keys, items, index, index + length - 1); 
                    if (r)
                        return; 
                }

TrySZSort — native метод.
2. «Там» это где? Разве нельзя копировать списки сразу в нужные места массива? Кроме того, пересылка занимает гораздо меньше времени, чем поэлементное сравнение того же количества элементов, да ещё и со сложной логикой. И откуда у вас всё время возникает O(N log N)? Вы про TimSort говорите или про сортировку вообще?
3. Да, про обратное создание списка я забыл. Действительно потребуется 3*N (дополнительный массив TimSort и итоговый список одновременно в памяти не живут, поэтому память на них общая). Итого, 3/2 раза от ручного слияния. Но опять же, не 2 раза.
4. Спасибо, я в курсе.
Total votes 3: ↑0 and ↓3-3
всё решает эксперимент. Результаты могут различаться в несколько раз в любую сторону.

Если хотите проведите эксперимент, код для ручного объединения на вскидку будет примерно таким
Код
        List<String> result = new ArrayList<>(6);
        List<String> list1 = Arrays.asList("1","4","7");
        List<String> list2 = Arrays.asList("1", "2", "6");
        Iterator<String> iterator1 = list1.iterator();
        Iterator<String> iterator2 = list2.iterator();
        String first = iterator1.next();
        String last = iterator2.next();
        for(int i =0;i< list1.size() + list2.size(); i++) {
            if((last == null || (first != null && first.compareTo(last) < 0))) {
                result.add(first);
                first = iterator1.hasNext()? iterator1.next(): null;
            } else {
                result.add(last);
                last = iterator2.hasNext()? iterator2.next(): null;
            }
        }

Для соединения через сортировки, как я понимаю, таким: 
        List<String> result = new ArrayList<>(6);
        List<String> list1 = Arrays.asList("1","4","7");
        List<String> list2 = Arrays.asList("1", "2", "6");
        result.addAll(list1); 
        result.addAll(list2); 
        Collections.sort(result);

Проверять нет желания, но первый код раза в 3-4 должен быть быстрее, особенно если списки будут не из трех значений.
Total votes 2: ↑2 and ↓0+2
Увы, у меня Java не установлена ни на одной из доступных машин.
А почему вы решили сортировать именно string, а не int?
This comment wasn’t rated yet0
Проверил на C#. Слияние списков из 10^8 целых чисел через промежуточное копирование в массив идёт в 3 раза быстрее, чем прямое слияние, а в случае списков строк — на 30% медленнее.
Total votes 1: ↑1 and ↓0+1
Вот результаты для 3х элементов:
Benchmark                Mode  Cnt         Score        Error  Units
MyBenchmark.libSort     thrpt   20   8237393,323 ± 165506,734  ops/s
MyBenchmark.manualSort  thrpt   20  11939532,372 ± 359279,303  ops/s

gist.github.com/relgames/ad4ce8251bf69ebd391a

А вот для 1 000 000 элементов в каждом списке:
Benchmark                Mode  Cnt  Score   Error  Units
MyBenchmark.libSort     thrpt   20  6,091 ± 0,430  ops/s
MyBenchmark.manualSort  thrpt   20  8,738 ± 0,500  ops/s

gist.github.com/relgames/5a300229150420abf83f

Да, немного быстрее, но не в разы. В 1.3-1.5 раз.

Является ли это критическим? Каждый решает сам. Однако я бы не стал использовать manualSort, пока есть другие способы ускорить работу. Например, в этом конкретном случае можно использовать не строки, а Integer. Или вообще 2 массива int.
Вариант с библиотечной функцией короче и легче читается. Ручной вариант читается хуже.

Я выше уже написал, что неверно выразился. Не «поставил бы минус за незнание», а «поставил бы плюс за знание библиотечной функции» — так правильней.
This comment wasn’t rated yet0
Вы померили не правильно, вы создание списков из 200 тыс. строк поместили в Benchmark что забивало весь результат, правильный код будет таким:
Код
package com.company;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class MyBenchmark {
    private static final int N = 1000000;
    static List<String> list1 = list1();
    static List<String> list2 = list2();
    @Benchmark
    public List<String> manualSort() {
        List<String> result = new ArrayList<>(3*N);
        Iterator<String> iterator1 = list1.iterator();
        Iterator<String> iterator2 = list2.iterator();
        String first = iterator1.next();
        String last = iterator2.next();
        for (int i = 0; i < list1.size() + list2.size(); i++) {
            if ((last == null || (first != null && first.compareTo(last) < 0))) {
                result.add(first);
                first = iterator1.hasNext() ? iterator1.next() : null;
            } else {
                result.add(last);
                last = iterator2.hasNext() ? iterator2.next() : null;
            }
        }

        return result;
    }

    @Benchmark
    public List<String> libSort() {
        List<String> result = new ArrayList<>(3*N);
        result.addAll(list1);
        result.addAll(list2);
        Collections.sort(result);
        return result;
    }



    public static List<String> list1() {
        List<String> result = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            result.add(String.valueOf(i*2));
        }
        return result;
    }

    public static List<String> list2() {
        List<String> result = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            result.add(String.valueOf(i*2 + 1));
        }
        return result;
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(MyBenchmark.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}



И результаты:
Benchmark Mode Cnt Score Error Units
MyBenchmark.libSort thrpt 20 3,869 ± 0,112 ops/s
MyBenchmark.manualSort thrpt 20 17,458 ± 0,989 ops/s

В 4,5 раза, Карл! В 4,5 раза! Как в общем-то, я и предсказывал.
Total votes 2: ↑2 and ↓0+2
Да, действительно. Я ошибался про 1.3 раза.
Total votes 1: ↑1 and ↓0+1
Ваши рассуждения про O(N) неверны.

If the input array is nearly sorted, the implementation requires approximately n comparisons.
…
The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])

This comment wasn’t rated yet0
Почему? Я в курсе что в лучшем случае sort дает O(N), в среднем O(N log N), я бы предположил что будет несколько выше чем N и меньше N log N так как идеальный результат на то и идеальный что редко достижим. В любом случае учитывая затраты на объединение двух списков, копирование в массив, сортировку и копирование из массива в список это все не принципиально, ну будет алгоритм выполнятся не в 5 раз, а в 4 раза медленнее, это уже не так важно…
Total votes 2: ↑1 and ↓10
Что значит — «несколько выше, чем N»? Медленнее, чем O(N)? Или больше, чем N операций? Во втором случае — какие операции вы учитываете — ассемблерные команды? Их будет намного больше, чем N как для ручного слияния, так и для TimSort, а константа зависит от реализации. А также от сложности операций копирования и сравнения (которые для чисел и для строк совсем разные).
Про O(N log N) — вы хорошо разобрались в деталях алгоритма TimSort? Как он будет работать, когда массив состоит из двух отсортированных частей, и какая у него будет сложность?
Total votes 1: ↑1 and ↓0+1
Эээ, вы понимаете что значит O(N) и почему это никак не связано с ассемблерными командами? Выше это O(N log N) например, а не кол-во элементарных операций.

Про O(N log N) — вы хорошо разобрались в деталях алгоритма TimSort? Как он будет работать, когда массив состоит из двух отсортированных частей, и какая у него будет сложность?

Да, если даны два списка (1,2,3) (4,5,6) то сложность будет близка к N(работает метод галопа), если даны списки (1, 5, 7) и (2, 6, 8), то сложность будет вероятнее всего O(N log N), либо что-то среднее между O(N) и O(N log N), но не чистое O(N). Если даны другие варианты, то и сложность будет другой, но не меньше O(N) и не больше O(N log N)
Total votes 2: ↑1 and ↓10
Я понимаю, что это значит. И понимаю, что фраза «если даны списки (1, 5, 7) и (2, 6, 8), то сложность будет вероятнее всего O(N log N)» смысла не имеет: чтобы говорить, что сложность равна O(N) или O(N log N), надо, чтобы исходные данные зависели от N, и это N можно было сделать сколь угодно большим. Например, слить списки (1,3,5,...,2*N-1) и (2,4,6,...,2*N). И, что удивительно, с этими данными TimSort справится ровно за O(N): он найдёт два упорядоченных фрагмента и применит к ним функцию слияния.
Total votes 3: ↑2 and ↓1+1
что удивительно, с этими данными TimSort справится ровно за O(N): он найдёт два упорядоченных фрагмента и применит к ним функцию слияния.

Увы, только в идеальном случае. Да, функция слияния это O(N), но ведь забыли тот факт что найти два упорядоченных фрагмента это не бесплатно, положим TimSort найдет два упорядоченных фрагмента за sqrt(N), то сложность будет O(N + sqrt(N)), даже если представить что он так найдет два упорядоченных фрагмента за log N, то все равно как бы не была близка сложность O(N + log N) к O(N) это не чистое O(N). А если списки не равны по размеру и скажем первый список в 3,14 раза больше или меньше чем второй, то сложность поиска упорядоченных фрагментов будет, скорее всего, ещё выше. Вывод: в идеальном случае TimSort даст O(N), в реальном сложность будет выше чем O(N), может быть совсем немного, но выше.
Total votes 1: ↑1 and ↓0+1
Извините, но O(N+sqrt(N)), O(N+log(N)), и даже O(1000*N) — это то же самое, что O(N). Так что сложность будет O(N), даже если он будет искать фрагменты линейным поиском. А другого выхода у него нет: списки могут «зацепиться» только одним элементом (как [1,2,3,5] и [4,6,7,8]), и, чтобы найти переставленную пару, сортировке придётся просмотреть весь массив.
Total votes 2: ↑2 and ↓0+2
Да, сори написал ерунду, согласен. Хотя это не отменяет того факта, что на практике разные O(n) могут очень сильно отличаться друг от друга.
Total votes 2: ↑1 and ↓10
На практике нужно измерять. И «очень сильно», оцененное на глаз, оказывается не так уж и сильно.
Total votes 2: ↑0 and ↓2-2
Синтетическая разница. На практике же будет ближе к моим результатам. На практике, если это не узкая ниша, библиотечные функции лучше.
This comment wasn’t rated yet0
Что значит на практике? Если нам приходят два упорядоченных списка из разных источников, почему на практике функция sort будет лучше? Во многих случаях производительность важна. На практике важно знать когда можно и лучше использовать библиотечные функции, а когда их использовать нельзя, перекос в любую сторону всегда вреден.
Total votes 2: ↑1 and ↓10
Данные откуда-то читаются и куда-то пишутся. Может так оказаться, что сортировка — это лишь малая часть. Даже в моем примере, где данные генерируются из памяти, именно это заняло большую часть времени.
This comment wasn’t rated yet0
Мы и говорим про «лучший» случай — когда сливаются два сортированных массива. Про это написано в JavaDoc, который я выше цитировал.
Не в 4-5 раз, а в 1.3 раза — я выше привел результаты теста.
This comment wasn’t rated yet0
Кстати, на второй задаче TimSort покажет намного лучший результат, чем тот код, что приведён в статье: если сливается K потоков длины N, то TimSort справится за O(N*K*log(K)), а код из статьи за O(N*K^2*log(K)). Правда, про потребление памяти лучше не вспоминать: ручное слияние требует O(K), а слияние через сортировку — O(K*N),
Total votes 1: ↑1 and ↓0+1
Мне кажется, что хорошим программистом является тот, кто умеет решать проблемы в работе, с которыми ещё никто толком не сталкивался и не решал. Думаю правильным способом выбора из кандидатов будет вопрос о том, что значимого для себя он считает самым крутым из своих достижением. Вы сразу поймёте и социальную составляющую и практическую.

P.S. Ну почему на хабре никто не сделал кнопку перемотки к месту где я могу оставить комментарий? Только кнопка «вверх». Но это не единственное желаемое направление перемещения… :) или я её не вижу?
Total votes 4: ↑4 and ↓0+4
Я считаю, что задавать стоит вопросы по инструментам и сторонним проектам, которые используются на искомой позиции. Ищем iOS разработчика — так и гоняем его по хитростям UIKit, Autolayout, Core-Data и популярным сторонним проектам. Смотрим уровень его понимания, сколько человек вынес из своего опыта. Если ищется девелопер — так и стоит с него спрашивать то, что от него будет требоваться на рабочем месте. Вопросы вроде «как сделать мердж» или какой-либо другой алгоритм, you name it, стоит спрашивать у джуниора.
Total votes 5: ↑3 and ↓2+1
Вы считаете самым ценным в разработчике знания каких-то конкретных инструментов, но далеко не все с вами по этому вопросу согласны. Многие считают, что надо найти хорошего разработчика в целом, а не специалиста по каким-то иструментам. Потому что инструментов куча, они меняются постоянно и у всех свои наборы, а хороший разработчик в том числе быстро переключается.
Я до своей текущей работы на С++ не написал ни строчки помимо лабораторных работ и тем не менее вполне себе устраиваю работодателя.
Total votes 6: ↑6 and ↓0+6
Нельзя охватить все случаи. У меня есть проект на Go, и если я буду искать на его поддержку другого разработчика, я буду руководствоваться общими принципами, просто потому, что найти Go-разработчика достаточно трудоемко, а полноценно зашарить этот язык можно, по моей субьективной оценке, можно за дни-неделю. Тут случай сложной задачи и простого инструмента -> искать хорошего программиста (гонять по алгоритмам и general вопросам, возможно специфичным для сферы, тут это будет многопоточность и бэкенд разработка), пусть и не знакомого с инструментом.

Учитывая, что вы устраиваете работодателя в качестве С++ разработчика, имея за спиной пару лабораторных работ (и вспоминая обьем документа-спецификации языка С++, превышающий более чем в 10 раз онный для Си), то перед вами ставится как разработчиком ставится относительно простая задача с точки зрения С++ разработки, не требующая глубоких знаний инструмента (пока речь была только про язык, возможно Вы используете еще, например, boost, или qt). Простая задача, сложный инструмент -> (я) буду искать просто адекватного разработчика (простые алгоритмические задачи и простой-средней сложности общие вопросы) и немного знакомого с инструментом.

Однако, возвращаясь к iOS разработке, я говорил о сложной задаче (большое приложение с активным использованием advanced инструментов и сторонних популярных проектов) и сложном инструменте. Девелоперов — пруд прудей. И даже очень хороший Java\С++\Whatever разработчик, потратит очень уж много времени на то, чтобы на достаточном уровне въехать в тему. Я просто об этом не оговорился, my bad, но будь задача простая (маленькое тривиальное приложение), то я бы и не спрашивал про все эти инструменты, я думаю это логично. Так вот, тут сложная задача, сложный инструмент -> гоняем по инструментам в первую очередь, общие знание второчны и быстрее усваиваются, чем инструменты.
Total votes 3: ↑2 and ↓1+1
Иногда конкретные инструменты используются годами, если не десятилетиями. Если компания использует какой-то фреймворк во всех проектах (скажем, Spring), то если человек имеет опыт именно в этом фреймворке, это будет большой плюс.
This comment wasn’t rated yet0
Никто не спорит, что плюс. Но вопрос компенсирует ли этот плюс плохую базу?
This comment wasn’t rated yet0
Задавая «задачки» на собеседованиях интервьюер должен быть готов к тому, что его точно так же могут попросить решить «задачку»:
«Мне бы хотелось представлять с кем я собираюсь работать, поэтому пока я пишу ответ на вашу задачку про потоки, пожалуйста, напишите решение для вот этой задачки». И там тоже может быть все что угодно.

Я ненавижу писать код когда у меня из-за плеча кто-то смотрит. И пусть даже выходит из комнаты, но в таком стрессе человек нормально не реагирует. Если вам нужны программисты, которые будут работать в стрессовых условиях — ну что ж, ваше право. Но я предпочитаю работать спокойно — вот в таких условиях и надо давать задачи. в идеале — дайте задачу на дом, пусть пришлет решение по почте. Пусть поищет на stackoverflow, у друзей, где угодно. Вам же важен результат, а не как он потеет? Сумел найти решение интересующей вас проблемы из вашей области за день-два? Что вам еще надо?

Я на собеседованиях никогда не даю задач на «напишите программу вот на этой бумажке». Пока человек рассказывает о своем опыте — уже можно составить впечатление о задачах, которые он решал. Задайте парочку вопросов по его теме — будет понятно насколько глубоко он «в теме».
Хотите поумничать — спросите парочку общих вопросов из теории типа «что такое нормализация», «когда вы применяете наследование, а когда нет», и тп. Спросите что первым делом он настроит в MySQL когда поставит сервер. Или PostgreSQL.
И все без бумажек, простыми вопросами, ожидая простые ответы.
И он не должен ждать, что вы вдруг прицепитесь: «а у вас не запустится программа! Что тут не так?? А точка с запятой не стоит в конце!!!».

Как человек думает — видно и так. Как он отвечает на вопросы — присмотритесь — так он и будет работать в вашей команде.
Я выбирал людей «под себя» и под команду — сработается ли, будет ли обсуждать проблемы или замкнется и будет молча что-то делать? Будет ли принимать критику и готов ли будет, например, принимать мои замечания? Я сам достаточно авторитарен и приходилось отказываться от людей с опытом, но, по которым было видно, что с ними у меня могут быть конфликты (даже из-за меня).
Total votes 8: ↑8 and ↓0+8
А вы не предполагали, что не у всех могут быть такие же условия, как у вас? Например, если у компании своя инфраструктура, то ей предыдущий опыт и знания потаенных секретов совершенно не интересны. Ну и разговоры это прекрасно, вот только код это то, что работник будет писать. Есть люди которые очень хорошо говорят, но с кодом у них беда.
This comment wasn’t rated yet0
Хмм, лучше спрашивать не код, а скажем как бы вы решили какую-то задачу. Например, у вас есть данные о маршруте городского транспорта, как бы вы решили задачу оптимизации времени пути человека от точки А до Б, просто словами без кода, тут будет сразу видно насколько человек умеет решать задачи и вообще как он походит к разработке алгоритмов.

А код на бумажке… ну вот не помню я как точно называется функция, которая находит тангенс, или которая округляет вниз. При этом в IDE я напишу Math. и найду нужную функцию за пару секунд. Как часто у вас программисты решают реальные задачи программирования на бумажки на время в условиях стресса и без интернета? Если уж вы хотите давать задачи на программирование, дайте мне IDE, интернет и время на нормальное обдумывание и программирование (программист редко в реальной работе должен решать задачи из разряда, «а напиши решение бинома Ньютона за 90 секунд), иначе совершенно непонятно что пытаются замерить такими задачами.

Самое интересное, что интервьюер готовит задачи с IDE, интернетом и кучей времени (а то и вообще берет чужие задачи и решения), а потом чешет свое ЭГО, смотря как его головоломные задачи пытаются решить на бумажке из головы за 1 минуту в условиях стреса.
Total votes 5: ↑5 and ↓0+5
Преимущество кода в качестве решения — единообразное, легко оцениваемое решение и главное документирование размышлений о решении. И если вы забыли название функции никто не расстреляет и не выбросит с собеседования. Главное понимать что вы делаете и объяснить это интервьюеру.
Типичные хорошие задачи с собеседования это пара-тройка задач строк на 10-15 кода (чтобы к ним подготовиться не надо IDE) минут на 45 интервью. Потом пообщаться на тему как адаптировать решение к каким-то новым условиям.
Вы зачем-то демонизируете интервьюера как будто он не хочет нанимать никогда, а хочет самоутверждаться. Я не могут сказать, что таких нет, но зачем на них равняться?
This comment wasn’t rated yet0
Преимущество кода в качестве решения — единообразное, легко оцениваемое решение и главное документирование размышлений о решении.

Нет, выше был спор что лучше объединить списки вручную или вызывать sort. Кто-то пишет в стиле чистого кода, без комментариев, кто-то требует комментарии к каждой строчке, кто-то везде вставляет использования функционального стиля, кто-то наоборот. Интервьюер может ждать что кандидат вставит проверки во все возможные случае, а кандидат решил что надо просто реализовывать алгоритм по-простому в одном случае. Интервьюер легко может «зарубить» кандидата только потому что его решение не совпадает с тем что он написал бы сам (или его понимания как надо писать). Ещё хуже если кандидат окажется выше уровнем чем интервьюер, тогда вообще «что за фигня тут у вас написана»

А документированность тут причем? У вас кандидаты что подают апелляции на решение интервьюера? Вряд ли, если интервьюер скажет что кандидат не тянет, код кандидата будет кто-то ещё изучать.

Вы зачем-то демонизируете интервьюера как будто он не хочет нанимать никогда, а хочет самоутверждаться. Я не могут сказать, что таких нет, но зачем на них равняться?

Проблема в том, что сознательно интервьюер хочет найти хорошего сотрудника, но подсознательно любой человек хочет самоутвердиться. Очень сложно делать скидку на стресс, отсутствие компьютера, другой стиль программирования, и «уж я бы точно вспомнил бы функцию арктангенса!», «что это за старший программист который не помнит досконально принцип балансировки красно-черного дерева и шестую нормальную форму?».

И если вы забыли название функции никто не расстреляет и не выбросит с собеседования

Зато у меня возникнут сомнения в том что мне нужно в эту фирму.

Проблема в таких задачках, что их отлично проходят джуниоры/студенты/школьники, участвующие во всяких олимпиадах, при этом не факт что они смогут нормально работать, зато старшие программисты с огромным опытом без IDE и инета могут «плавать», так как они давно не писали быстрой сортировки руками, разработать архитектуру огромной корпортативной системы они могут легко, а быструю сортировку могут давно уже забыть за полной ненадобностью в реальной работе.
Total votes 4: ↑4 and ↓0+4
Все ваши претензии к возможному искажению результатов собеседования интервьюером точно так же можно применить к любому виду собеседования. Если вы не доверяете интервьюеру, то никакого успешного собеседования не будет.
А насчет старших программистов — никто же не говорит, что надо для всех вакансий вообще делать одинаковые вопросы? Можно задавать такие же задачи на архитектуру с довольно свободным полетом мысли. Но так же все равно разработчик должен уметь писать код и решать задачи.
This comment wasn’t rated yet0
Не совсем, по моему опыту большого количества код ревью в разных фирмах — анализ качества чужого кода вещь очень субъективная, а вот знание конкретных вещей — объективная. Если мне задают вопросы по коллекциям, патернам, базам данных, orm, nosql я либо на них отвечаю, либо нет. Это вполне объективный критерий c которым сложно спорить (если конечно интервьюер сознательно не пытается завалить кандидата), с кодом все сложнее — не так называл переменные — минус, использовал императивный подход вместо функционального — минус, не сделал проверку граничных условий — ещё один минус, написал не производительный код — минус, написал производительный код — минус за преждевременную оптимизацию (при этом интервьюер может даже не замечать своей субъективности). Наоборот, оценка кода как раз очень субъективна, она похожа на оценку рассказов (была такая байка что как-то Лев Толстой, тогда уже знаменитый писатель, решил проверки ради отправить один из своих рассказов от лица молодого автора — его все редакторы разнесли в пух и прах в самых уничижительных выражениях).

ИМХО, для программистов без опыта пара задач на кодирования может быть неплохая идея, но для опытных программистов слишком простые задачи ничего не скажут о умении программировать и стиле программирования (ну, напишет программист list1.addAll(list2); Collections.sort(list1); что это скажет о том как он умеет кодировать на Java? Проще просто спросить как можно отсортировать список), а слишком сложные — будут случайным образом отсеивать хороших кандидатов. Но это лишь мое личное мнение.
Total votes 3: ↑3 and ↓0+3
Очень редко удается найти человека, который до этого работал с *точно таким же* стеком технологий. Поэтому, практически всегда, ваша компания будет для него чем-то новым. И сразу требовать от него чтобы он разбирался досконально во всех ваших нюансах — не очень правильно. Если вы не готовы учить человека первые два-три месяца, то вы, конечно, можете требовать «все и сразу», но и будьте готовы платить ему в 2 раза больше.
А про код — повторюсь — можете дать задачу на дом. У вас в офисе он будет писать код точно так же — без человека за спиной и самостоятельно как минимум по день-два до очередного ревью.
Я сначала давал задачки на дом, но потом понял что даже они мало что определяют. Маленький кусочек кода ничего не покажет — работать он будет, а в большом проекте налажать может любой, в конце концов.

Почаще ставьте себя на место собеседуемого и смотрите на себя его глазами. Вам бы хотелось вот так сидеть и готовиться услышать вопрос «сколько в этой комнате поместится шариков» или «а ну-ка напишите за три минуты быструю сортировку»?
Ну вот он не написал, ошибся. А вы про себя сидите и думаете: «мда, обмельчала молодежь… Опять я очередного уделал. Какой я крутой!».

Это все, конечно, мое мнение. Возможно, в каких-то компаниях обязателен более строгий отбор, чтоб только «лучшие из лучших, которые помнят все алгоритмы, которые 100% соответствуют нашей вакансии и уже через три дня сделают все хорошо». Ок, возможно.
Total votes 1: ↑1 and ↓0+1
Дык поэтому и наплевать на стек технологий, главное чтобы было общие навыки и культура разработчка и способность к обучению и адаптируемости.
Задача на дом так же не показывает динамики решения и как человек идет к решению. Как он реагирует на усложнения условий. Способен ли он на поиск ошибок. И если человек сходу не может решить, то это не ужасная беда. Хороший интервьюер может дать толчок в нужную сторону и посмотреть как разработчик будет реагировать и как он понимает подсказки.
Total votes 1: ↑1 and ↓0+1
Ответная задачка интервьюеру — хорошая и совершенно справедливая идея, что-то вроде мести. Думаю, что все интервьюеры, которые отбирают кандидатов подобными задачками, получив такую же задачу в ответ от кандидата, сразу поймут насколько это плохой способ отбора. Вот только на практике такой поворот скорее всего будет воспринят как неимоверная наглость, что приведет к моментальному прощанию с кандидатом. Сложно представить себе интервьюера, который опустится до решения такой задачки.
This comment wasn’t rated yet0
Представить легко. Например, такого, который либо уже знает решение, либо может решить за несколько секунд. Он, скорее, похвастается своим мастерством, чем обидится.
This comment wasn’t rated yet0
Такое может произойти, если вернуть интервьюеру его же задачу. В ветке имелась ввиду ситуация, когда кандидат проверяет уровень интервьюера своей задачей. Мол раз ты хочешь, чтобы я доказывал свой уровень, решая твои задачки, то и ты докажи свой уровень, решая мои задачки.
This comment wasn’t rated yet0
Ну, и почему интервьюер не может оказаться опытнее кандидата (и знать аналоги большинства задач, которые кандидат может предложить)?
This comment wasn’t rated yet0
Оказаться опытнее он может. Готов ли интервьюер доказывать свой опыт каждому кандидату,
решая их задачи по программированию, в этом суть. Я вполне допускаю, что существуют интервьюеры, которые в ответной задаче увидят шанс блеснуть своим мастерством. В моем представлении о собеседованиях такая реакция кажется маловероятной.
Total votes 2: ↑2 and ↓0+2
Думаю, интервьюер от задачи скорее всего откажется.
Вопросы лучше по задавать. Из-за разных наборов знаний может выйти смешная ситуация, когда сначала интервьюер завалит вопросами кандидата, а потом кандидат интервьюера :)
Total votes 3: ↑3 and ↓0+3
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr