какие вопросы по алгоритмам

[shadow7256]

Собственно интерсует следующее. Какие обычно вопросы по алгоритмам задают на интервью? Отбросим в сторону вопросы по конкретным языкам программирования или платформам. Просто давно не был на интервью и хочется освежить (или выучить) память.

Спасибо

[Cabron]

Из того что помню:
- найти все подмножества множества (powerset)
- найти все комбинации и пермутации множества
- сравнить два BST
- поиск элемента в массиве, матрице
- поиск уникальных символов в строке
- первести число в римских цифрах в число из арабских цифр
- повернуть матрицу на 90 градусов без использования дополнительных структур данных
- определение простого числа
- поиск n-го числа фибоначи

Вообще все вопросы можно разделить на определенные группы - поиск, сортировка, использование различных структур данных и т.д. Если поднатаскаться по каждому типу вопросов, то на интервью нового уже мало встретится. У Гугла, Майкрософта, Амазона и др. в основном одни и те же вопросы задаются, у них фантазия ограничивается после определенного числа вопросов.

[crypto5]

Собственно интерсует следующее. Какие обычно вопросы по алгоритмам задают на интервью? Отбросим в сторону вопросы по конкретным языкам программирования или платформам. Просто давно не был на интервью и хочется освежить (или выучить) память.

Спасибо

Я обычно захожу на glassdoors и смотрю что спрашивают в конкретную контору, помогает освежить память, и потом на интервью часто получал вопросы с которыми уже разобрался.

[shadow7256]

Я обычно захожу на glassdoors

посмотрел пару фирм и потом он попросил оставить свое review чтобоы смотреть дальше. Регистриться надо?

[crypto5]

Я обычно захожу на glassdoors

посмотрел пару фирм и потом он попросил оставить свое review чтобоы смотреть дальше. Регистриться надо?

Не помню, но это ведь не очень принципиально?

[Cabron]

+1 glassdoors, там самые свежие вопросы можно посмотреть.

Вот из этой книги часто вопросы попадались: http://www.careercup.com/book.

[zzhou]

А Гугл обязательно вопросы по алгоритмам задаёт? Просто я думаю туда послать резюме через пару месяцев (надо GC) - а у меня знаний по алгоритмам - ноль (образование экономическое) и я надеялся предложить им море опыта по разработке IDE на основе Eclipse + опыт очень сеньёрной работы по теме в конкуренте. Без алгоритмов не стоит и пытаться?

[crypto5]

А Гугл обязательно вопросы по алгоритмам задаёт? Просто я думаю туда послать резюме через пару месяцев (надо GC) - а у меня знаний по алгоритмам - ноль (образование экономическое) и я надеялся предложить им море опыта по разработке IDE на основе Eclipse + опыт очень сеньёрной работы по теме в конкуренте. Без алгоритмов не стоит и пытаться?

Думаю что пытаться стоит но алгоритмы стоит подучить

[Асти]

Не то чтобы я встречал эти вопросы на интервью, но я бы спросил:

Есть текстовый файл в 100Гиг. У вас сутки чтобы отсортировать строки в алфавитном порядке.

Надо часто перемножать довольно большие матрицы (скажем 4000х4000). Напишите быстрый алгоритм перемножения. Написали? Сравните производительность в гигафлопах с заявленной производительностью проца. Если отличается более чем в 10 раз, объясните и перепишите. Если все равно отличается более чем в 2 раза, объясните почему и что надо делать. А если проц многоядерный? А если матрицы очень большие, можно ли еще ускорить?

На интервью однажды из 4 собеседований 3 раза спросили написать double-linked list

[mudi]

Ворочать матрицы ни разу не просили, реверсировать строку, развернуть односвязный список или посчитать биты в байте просят гораздо чаще. Обычно большинство задач не выходят за пределы знания основных структур данных и базовых алгоритмов сортировки и поиска. Я перед началом поиска работы перечитываю первые несколько глав Кормена - всегда очень помогает. По поводу Google почитайте Get that job at Google - там где-то с середины описано что надо учить и почему.

[Sergunka]

Ворочать матрицы ни разу не просили, реверсировать строку, развернуть односвязный список или посчитать биты в байте просят гораздо чаще. Обычно большинство задач не выходят за пределы знания основных структур данных и базовых алгоритмов сортировки и поиска. Я перед началом поиска работы перечитываю первые несколько глав Кормена - всегда очень помогает. По поводу Google почитайте Get that job at Google - там где-то с середины описано что надо учить и почему.

mudi,

(ох и угораздило Вас выбрать никнейм, сначало написал по русски потом зачеркнул и переписал в оригинальной транскрипции )

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

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

[mudi]

mudi,

(ох и угораздило Вас выбрать никнейм, сначало написал по русски потом зачеркнул и переписал в оригинальной транскрипции )

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

Пожалуйста. Рад, что ссылки пригодились. Кстати, вот еще одна ссылка, не помню давал я ее уже или нет - здесь собрано множество задач, которые дают на интервью в Microsoft и не только. Я тоже иногда даю на интевью задачки оттуда, и мне они попадались когда интевьюировался сам.

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

Ну вобщем да. Полезно научиться распознавать класс задачи, запомнить несколько неочевидных решений или формул и понимать какие задачи к ним сводятся и какие сводятся к знанию базовых алгоритмов. Для примера из самого простого - нужно помнить, что x&(x-1) удаляет младший значимый бит. Интервьюшные задачи посчитать биты в слове или написать функцию, которая определяет является ли число степенью двойки решаются с ее помощью.

[crypto5]

Для примера из самого простого - нужно помнить, что x&(x-1) удаляет младший значимый бит.

Это ведь вроде неправильно, пример: x = 2 => x & (x - 1) = 2 & 1 = 10 & 01 = 0 - то есть удалило все биты..

Интервьюшные задачи посчитать биты в слове или написать функцию, которая определяет является ли число степенью двойки решаются с ее помощью.

Мне кажется это очень не эфективно.

[crypto5]

Для примера из самого простого - нужно помнить, что x&(x-1) удаляет младший значимый бит.

Это ведь вроде неправильно, пример: x = 2 => x & (x - 1) = 2 & 1 = 10 & 01 = 0 - то есть удалило все биты..

Сорри, заглючил, это действительно работает.

[mudi]

Интервьюшные задачи посчитать биты в слове или написать функцию, которая определяет является ли число степенью двойки решаются с ее помощью.

Мне кажется это очень не эфективно.

Это не единственный способ и не самый быстрый но самый простой пожалуй (не считая тупого цикла со сдвигом единички). Можно заранее посчитать все варианты и потом просто в массиве ответ по индексу доставать, если нужна скорость, ну и еще наверное с десяток способов есть.

[hogzie]

Обычно ожидают, что читал Hacker's Delight и знаешь как искать биты маской:

Code: Select all

    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;

Способов дейсвительно много. Зависит все от постановки задачи (размер слова, параетры оптимизации и.т.д.).

[Cabron]

Mне подсчет битов путем Brian Kernighan тоже лучше всего заполнился,
здесь есть несколько других путей, от сдвига на единицу до lookup table:

http://graphics.stanford.edu/~seander/b ... tKernighan

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

http://sergey-vyatkin.livejournal.com/1433.html
Вообще на мой взгляд все задачки практически известные так, что можно выучить без вопросов просто не ленится.

Вот сегодня задал задачку про x>y индусу у которого в резюме прописано знание Java.
Он даже и этого не смог одолеть.
Но что поразило как при всем при этом он умудрялся нести бодрую околесицу, совершенно не сбиваясь с ритма.

[Lateralus]

http://sergey-vyatkin.livejournal.com/1433.html
Вообще на мой взгляд все задачки практически известные так, что можно выучить без вопросов просто не ленится.

Вот сегодня задал задачку про x>y индусу у которого в резюме прописано знание Java.
Он даже и этого не смог одолеть.
Но что поразило как при всем при этом он умудрялся нести бодрую околесицу, совершенно не сбиваясь с ритма.

Надеюсь вы не ожидали довольно странного ответа (который находится по отквоченной ссылке), что нужно добавить throws NullPointerException в декларацию метода для unchecked исключения?

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

Меня бы вполне устроило если бы оппонент понимал разницу между int и Integer.

[Komissar]

экий Вы строгий к братьям меньшим

[JMorgan]

Меня бы вполне устроило если бы оппонент понимал разницу между int и Integer.

Вы имеете ввиду Int ?

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

Меня бы вполне устроило если бы оппонент понимал разницу между int и Integer.

Вы имеете ввиду Int ?

между простым типом int и обьектом Integer.

[JMorgan]

тогда ОК вам..
и нах-нах таких индусов...
трудно представить более простого вопроса
- хотя идея этих обёрточных классов
с разными именами
с соответствующими базовыми типами
- немного корявая

[olg2002]

Одноклассники ищут разработчиков на Java:

1. Сколько массивов размера 10000000 или более будет выделено в памяти при выполнении данного куска кода?

Code: Select all

Integer[] intArr = new Integer[10000000];
List<Integer> list = Arrays.asList(intArr);
List<Integer> list2 = new ArrayList<Integer>(list);
List<Integer> list3 = Collections.unmodifiableList(list);
List<Integer> list4 = Collections.synchronizedList(list);
Integer[] array = list2.toArray(new Integer[0]);

Выберите вариант ответа:

• 1

• 2

• 3

• 4

2. Выберите реализацию класса Increment, которая будет корректно работать в многопоточной среде.

Code: Select all

class Increment1 {
    volatile int i = 0;
    void increment() {
        i++;
    }

    void decrement() {
        i--;
    }
}

class Increment2 {
    int i = 0;
    synchronized void increment() {
        i++;
    }
    void decrement() {
        synchronized (this) {
            i--;
        }
    }
}

class Increment3 {
    int i = 0;
    void increment() {
        synchronized ((Object) i) {
            i++;
        }
    }
    void decrement() {
        synchronized ((Object) i) {
            i--;
        }
    }
}

Отметьте все верные варианты ответа:

• Increment1

• Increment2

• Increment3

3. Выберите вариант реализации hashCode, который совместно с приведенной реализацией equals позволит использовать экземпляры класса Book в качестве элементов java.util.HashSet.

Code: Select all

class Book {
    private final String title;
    private final String firstAuthor;
    private final String secondAuthor;
...
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Book book = (Book) o;

        return title.equalsIgnoreCase(book.title) &&
            ((firstAuthor.equals(book.firstAuthor)
                && secondAuthor.equals(book.secondAuthor))
             || (secondAuthor.equals(book.firstAuthor)
                && firstAuthor.equals(book.secondAuthor)));
    }

    public int hashCode1() {
        return 31 * (
             31 * title.toUpperCase().hashCode()
             + firstAuthor.hashCode()
        ) + secondAuthor.hashCode();
    }

    public int hashCode2() {
        return 31 * title.hashCode()
            + firstAuthor.hashCode() + secondAuthor.hashCode();
    }

    public int hashCode3() {
        return 31 * title.toLowerCase().hashCode()
            + firstAuthor.hashCode() + secondAuthor.hashCode();
    }
}

Отметьте все верные варианты ответа:

• hashCode1

• hashCode2

• hashCode3

4. Какие из следующих утверждений верны для экземпляра класса CachingFactory?

Code: Select all

import java.util.concurrent.*;

class CachingFactory<K, V> implements Factory<K, V> {
    private final Factory<K, V> factory;
    private final ConcurrentMap<K, Future<V>> cache
            = new ConcurrentHashMap<K,Future<V>>();

    CachingFactory(Factory<K, V> factory) {
        this.factory = factory;
    }

    @Override
    public V newInstance(final K key) {
        Future<V> future = cache.get(key);
        if (future == null) {
            FutureTask<V> futureTask = new FutureTask<V>(new Callable<V>() {
                @Override
                public V call() throws Exception {
                    return factory.newInstance(key);
                }
            });
            future = cache.putIfAbsent(key, futureTask);
            if (future == null) {
                future = futureTask;
                futureTask.run();
            }
        }
        try {
            return future.get();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

interface Factory<K, V> {
    V newInstance(K key);
}

Отметьте все верные варианты ответа:

• 1. Если k1.equals(k2), то вызов newInstance(k1) всегда возвращает ссылку на тот же объект, что и вызов newInstance(k2), независимо от потока, который делает вызов.

• 2. Если !k1.equals(k2), то при параллельном вызове newInstance(k1) и newInstance(k2) из двух потоков, создание соответствующих объектов V может происходить параллельно.

• 3. Если k1.equals(k2), то при параллельном вызове newInstance(k1) и newInstance(k2) из двух потоков, в любом случае, будет создано не более одного объекта FutureTask<V>.

• 4. Если k1.equals(k2), то при параллельном вызове newInstance(k1) и newInstance(k2) из двух потоков, в любом случае, будет создано не более одного объекта V.

5. Какова оценка сложности приведенного ниже алгоритма в O-нотации, если N := set1.size(), K := set2.size()?

Code: Select all

boolean haveCommonElements(TreeSet<?> set1, TreeSet<?> set2) {
    if (set1.size() > set2.size()) {
        return haveCommonElements(set2, set1);
    }
    for (Object e : set1) {
        if (set2.contains(e)) return true;
    }
    return false;
}

Выберите вариант ответа:

• O(N * K)

• O(N * log(K))

• O(min(N,K) * log(max(N,K)))

• O(max(N,K) * log(min(N,K)))