Friday, December 24, 2010

Вопросы с собеседований Google, часть 4

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




Вопросы:
16) Напишите функцию (и вспомогательные функции, если потребуется), которая берет на вход имя колонки из Excel (A,B,C,…AA,AB,AC...AAA) и возвращает соответствующее ему целочисленное значение (A=1,B=2,AA=27...)

17) Вам дан бесконечный поток запросов (например, поисковые запросы которые вводят люди в поисковике Google в режиме реального времени). Вам нужно получить репрезентативную выборку размером 1000 элементов из этого бесконечного потока данных, опишите ваше решение и напишите соответствующий код.

18) Алгоритмы поиска по дереву. Напишите код BFS и DFS, оцените время выполнения и требования к памяти. Измените код BFS и DFS, так чтобы он работал с графами содержащими циклы и с графами со взвешенными ребрами. Сделайте так, чтобы код печатал путь от исходной вершины к искомой.

19) Вам дан циклический список чисел. Циклический, значит, что когда вы доходите до конца, вы снова возвращаетесь к началу. Напишите самый эффективный алгоритм поиска минимального числа в этом списке. Как найти заданное число в этом списке? Числа в списке упорядочены строго в порядке возрастания, но вы не знаете, в каком месте список начинается, например: 38, 40, 55, 89, 6, 13, 20, 23, 36.

20) В чем разница между локальными и глобальными переменными?


Возможные варианты решения...


16) Напишите функцию (и вспомогательные функции, если потребуется), которая берет на вход имя колонки из Excel (A,B,C,…AA,AB,AC…AAA) и возвращает соответствующее ему целочисленное значение (A=1,B=2,AA=27…)

Классическая задача по преобразовании из одной системы счисления в другую. Имя колонки в Excel – не что иное как число в 26-ричной системе счисления. От нас требуется преобразовать его в десятичную систему, что решается следующими строчками кода:
public int convert(String value){
        int num = 0;
        for(char ch : value.toCharArray()){
            int v = 1+ch-'A';
            num=26*num + v;
        }
        return num;
    }

Следует еще добавить проверку входных данных, что строчка не null, что строчка не пустая, что строчка не содержит ничего кроме символов A-Z и что число не выпадает за пределы int.

17) Вам дан бесконечный поток запросов (например, поисковые запросы которые вводят люди в поисковике Google в режиме реального времени). Вам нужно получить репрезентативную выборку размером 1000 элементов из этого бесконечного потока данных, опишите ваше решение и напишите соответствующий код.

Интересная задачка. Я бы взял за основу алгоритмом случайной выборки с резервуаром, разработанным Джефри Виттером Идея заключается в том, что мы создаем «резервуар» из 1000 элементов и по мере поступления новых элементов из потока заменяем элементы в резервуаре с некоторой вероятностью.
Если конкретно:
При получении i-ого запроса из бесконечного потока, мы либо добавляем его в резервуар с вероятностью p=1000/i, либо отбрасываем его переходя к следующему запросу. В случае добавления мы отбрасываем случайно выбранный элемент, имеющийся в резервуаре. На первую 1000 запросов из потока это не распространяется, первые запросы просто заполняют резервуар.
В некоторый момент времени, когда нам требуется репрезентативная выборка, мы просто берем все элементы резервуара.
А теперь код:
public class QueryStreamSampling {

    private Random RND = new Random();
    public static final int SAMPLE_SIZE = 1000;
    private String[] reservoir = new String[SAMPLE_SIZE];
    private int i;

    public void accept(String query){
        if (i<SAMPLE_SIZE){
            reservoir[i++]=query;
            return;
        }
        double p = SAMPLE_SIZE/(double)i++;
        if (RND.nextDouble()<p){
            reservoir[RND.nextInt(SAMPLE_SIZE)] = query;
        }
    }

    public String[] sample(){
        return reservoir;
    }


    private void test(){
        for(int i=0; i<100000; i++){
            accept(generateRandomString());
        }
        for(String sample : sample()){
            System.out.println(sample);
        }
    }

    private String generateRandomString(){
        StringBuilder res = new StringBuilder();
        while(RND.nextDouble()>0.1){
            res.append((char)('a' + RND.nextInt(25)));
        }
        return res.toString();
    }

    public static void main(String[] args) {
         new QueryStreamSampling().test();
    }
}

18) Алгоритмы поиска по дереву. Напишите код BFS и DFS, оцените время выполнения и требования к памяти. Измените код BFS и DFS, так чтобы он работал с графами содержащими циклы и с графами со взвешенными ребрами. Сделайте так, чтобы код печатал путь от исходной вершины к искомой.

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

Прежде всего граф. Возьмем за основу граф заданный в виде списков смежности. Этот выбор не принципиален, но т.к. в Java стандартной реализации графа нет, надо с чего-то начать.

class Edge<T>{
   double weight;
   Node<T> node;

    Edge(double weight, Node<T> node) {
        this.weight = weight;
        this.node = node;
    }
}

class Node<T> implements Iterable<Edge<T>>{
    private List<Edge<T>> childrenprivate T data;


    public Node(T value){
        children = new ArrayList<Edge<T>>();
        data = value;
    }

    public Node<T> add(Node<T> child){
        add(1, child);
        return this;
    }

    public Node<T> add(double weight, Node<T> child){
        children.add(new Edge<T>(weight, child));
        return this;
    }

    public Node<T> addBidirectional(Node<T> child){
        addBidirectional(1, child);
        return this;
    }

    public Node<T> addBidirectional(double weight, Node<T> child){
        children.add(new Edge<T>(weight, child));
        child.children.add(new Edge<T>(weight, this));
        return this;
    }


    @Override
    public String toString() {
        return data.toString();
    }

    @Override
    public Iterator<Edge<T>> iterator() {
        return children.iterator();
    }
}


Теперь, собственно, реализация поиска в глубину и в ширину:

public static <T> void dfs(Node root, Node<T> to){
        PriorityQueue<NodeDistancePair<T>> next = new PriorityQueue<NodeDistancePair<T>>(10, Collections.<Object>reverseOrder());
        next.add(new NodeDistancePair<T>(0, root));
        search(next, to);
    }

    public static <T> void bfs(Node<T> root, Node<T> to){
        PriorityQueue<NodeDistancePair<T>> next = new PriorityQueue<NodeDistancePair<T>>();
        next.add(new NodeDistancePair<T>(0, root));
        search(next, to);
    }

    private static <T> void search(Queue<NodeDistancePair<T>> next, Node<T> to) {
        Set<Node<T>> visited = new HashSet<Node<T>>();
        while(!next.isEmpty()){
            NodeDistancePair<T> ndp = next.poll();
            Node<T> nextNode = ndp.node;
            System.out.println(nextNode);
            if (nextNode.equals(to)){
                System.out.println("Found! " + printPathToRoot(ndp));
                break;
            }
            if (!visited.contains(nextNode)){
                visited.add(nextNode);
                for(Edge child : nextNode){
                    if (!visited.contains(child.node)){
                        NodeDistancePair<T> unvisited = new NodeDistancePair<T>(ndp.distance + child.weight, child.node);
                        unvisited.parent = ndp;
                        next.add(unvisited);
                    }
                }
            }
        }
    }

    private static <T> String printPathToRoot(NodeDistancePair<T> ndp) {
        StringBuilder res = new StringBuilder();
        res.append(ndp.node);
        ndp = ndp.parent;
        while(ndp!=null){
            res.append(" <-- ").append(ndp.node);
            ndp = ndp.parent;
        }
        return res.toString();
    }

    private static class NodeDistancePair<T> implements Comparable<NodeDistancePair>{
        double distance;
        Node<T> node;
        NodeDistancePair<T> parent;


        NodeDistancePair(double distance, Node<T> node) {
            this.distance = distance;
            this.node = node;
        }


        @Override
        public int compareTo(NodeDistancePair o) {
            return (int) Math.signum(distance - o.distance);
        }
    }

Что касается алгоритмической сложности, время выполнения, как для BFS так и для DFS в наихудшем случае: O(|E|+|V|)
Требование к памяти, опять же, в наихудшем случае, у BFS O(|E|+|V|), что несколько выше чем у DFS O(|V|)

19) Вам дан циклический список чисел. Циклический, значит, что когда вы доходите до конца, вы снова возвращаетесь к началу. Напишите самый эффективный алгоритм поиска минимального числа в этом списке. Как найти заданное число в этом списке? Числа в списке упорядочены строго в порядке возрастания, но вы не знаете, в каком месте список начинается, например: 38, 40, 55, 89, 6, 13, 20, 23, 36.

Первый вопрос, который следует задать интервьюеру, это какие операции можно выполнять со списком и каково их время выполнения. К чему это? А к тому, что циклический список может быть представлен как в виде связного списка (linked list) так и в виде массива (random access list) и решения этой задачи в том и другом случае кардинально отличаются.

В случае однонаправленного связного списка решение тривиально и имеет алгоритмическую сложность O(n) — это простой линейный поиск, т.е. обход всего списка в поисках наименьшего или заданного элемента.

Если же список реализован через массив, т.е. у нас есть способ эффективно получать i-ый элемент списка, то следует воспользоваться модификацией двоичного поиска. В таком случае оптимальное решение имеет сложность O(log(n))
Реализация для второго случая:

public static int min(CircularList list){
        int from = 0;
        int to = list.size()/2;
        if (list.get(from) < list.get(to)){
            from = to;
            to = list.size();
        }
        while(to-from > 1){
            int middle = (from+to)/2;
            if (list.get(from) < list.get(middle)){
                from = middle;
            }else{
                to = middle;
            }
        }
        return Math.min(list.get(to), list.get(from));
    }


class CircularList {

    private int[] values;
    private int seed;

    public CircularList(int[] values) {
        this.values = values;
        seed = (int) (Math.random() * values.length);
    }

    public int get(int pos){
        return values[(pos + seed)%values.length];
    }

    public int size(){
        return values.length;
    }

}

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

20) В чем разница между локальными и глобальными переменными?

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

2 comments:

  1. 20) Наверное, еще стоит отметить что в java глобальные переменные храняться на heap-е, а локальные на stack-е

    ReplyDelete
  2. Concoction at least half pc clear up .. Within snacks vacation, weight loss programs red wine, dark beer, or perhaps even
    sherry will incorporate tapas. Gas fire bowls are very simply the easiest, easy and quick provide of
    high temperatures just for socialising outside of the house.

    Move just cannot basically costly, obviously air-flow requires excessive space
    in your home, using up memory that curio cabinets and other instruments may possibly.
    Assemble the ease included in an ovenproof
    container deep in a homely pot for a minimum of 120 minutes.
    Suppose meals are cooked close to the outsides,
    for the medical center in order to tender or not make sure you done, or perhaps there's a a rediculous amount of shading varietie (a handful is typical), immediately go jar also known as decrease the heat of 10F. I like to start grilling, farrenheit, home or garden as well as engage in over-all Try it for yourself in the house but all my tangible eagerness is made for heating.

    My webpage toaster ovens reviews consumer reports (toasterovensplus.com)

    ReplyDelete