Взломайте интервью по кодированию, создав эти 5 реальных особенности

Подготовка к собеседованиям по кодированию – непростая задача. Вам нужны навыки, чтобы разобраться в проблеме и использовать правильные инструменты. Попытка запомнить более 1500 проблем с кодами – не лучший способ добиться успеха.

Вот почему сегодня мы хотим подойти к подготовке к собеседованию немного по-другому, решив некоторые проблемы реального мира , с которыми сталкиваются технологические компании. Учимся создавать функции реального мира (например, “как объединить рекомендации на Amazon”) веселее, и гораздо легче запомнить то, что вы узнали. Если вы можете понять основную структуру проблемы, вы можете применить ее практически к любому вопросу.

Мы рассмотрим решения нескольких распространенных проблем с кодированием в реальном мире и создадим 5 функций. Мы будем предлагать наши решения на Java. Если вы хотите увидеть их на Python, ознакомьтесь с моим оригинальным сообщением .

Этот учебник с первого взгляда:

Функция Netflix: Группировать похожие названия (хэш-карты)
Функция Facebook: Круги друзей (DFS)
Функция календаря Google: Поиск Конференц-залов (куча)
Особенность Amazon: Товары в ценовом диапазоне (ЛУЧШИЕ)
Функция Твиттера: Добавляйте лайки (строки)
Куда идти дальше

Функция Netflix: Группировать похожие названия (хэш-карты)

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

Задача: Наша задача здесь состоит в том, чтобы улучшить результаты поиска , позволив пользователям видеть соответствующие результаты поиска без помех из-за опечаток, которые мы называем “Группа похожих названий” особенность.

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

Во-первых, нам нужно разделить наши названия на наборы слов, чтобы слова в наборе были анаграммами. У нас есть три набора: {"дуэль", "дуэль", "дуэль"} , {"скорость", "скорость"} и {"автомобили"} . Результаты поиска должны включать все элементы набора, в котором найдена строка.

Примечание: Лучше всего предварительно вычислять наши места, а не формировать их при поиске пользователя.

Члены каждого набора имеют одинаковую частоту каждого алфавита, поэтому частота каждого алфавита в словах одной и той же группы одинакова. Например, в вашем наборе {{"скорость", "скорость"}} частота символов одинакова в каждом слове: s , p , e и d .

Итак, как мы разрабатываем и реализуем эту функциональность? Давайте разберемся с этим.

Для каждого заголовка нам нужно вычислить вектор из 26 элементов . Каждый векторный элемент представляет частоту английской буквы в названии. Мы можем представить частоту с помощью строки, которая фиксируется символами # . Этот процесс сопоставления генерирует идентичные векторы для строк, которые являются анаграммами. Например, мы представляем abccc как #1#2#3#0#0#0... #0 .
Затем мы используем этот вектор в качестве ключа для вставки заголовков в хэш-карту. Все наши анаграммы будут сопоставлены с одной и той же записью. Когда пользователь выполняет поиск по названию или слову, он должен вычислить 26-элементный вектор частоты английских букв на основе входных данных. Затем он выполнит поиск по хэш-карте и вернет все записи карты с использованием вектора.
Затем мы сохраняем список вычисленных значений символов в виде ключа в хэш-карте и присваиваем строку в качестве ее значения.
Каждое значение представляет собой отдельный набор, поэтому мы возвращаем значения хэш-карты.

import java.util.*;
class Solution {
    public static List> groupTitles(String[] strs){
      if (strs.length == 0) 
            return new ArrayList>();

        Map> res = new HashMap>();

        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()){
                int index = c - 'a';
                count[index]++;
            }

            StringBuilder delimStr = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                delimStr.append('#');
                delimStr.append(count[i]);
            }

            String key = delimStr.toString();
            if (!res.containsKey(key)) 
                res.put(key, new ArrayList());

            res.get(key).add(s);
        }

        return new ArrayList>(res.values());
    }

    public static void main(String[] args) {
        // Driver code
        String titles[] = {"duel","dule","speed","spede","deul","cars"};

        List> gt = groupTitles(titles);
        String query = "spede"; 

        // Searching for all titles
        for (List g : gt){
            if (g.contains(query))
                System.out.println(g);
        }
  }
}

Показатели сложности

n – размер списка строк, а k – максимальная длина одной строки.

Временная сложность: O(n*k) , поскольку мы подсчитываем каждую букву для каждой строки в списке

Сложность пространства: O(n*k) , так как каждая строка хранится как значение в словаре, а размер строки может быть k .

Функция Facebook: Круги друзей (DFS)

Facebook – крупнейшая социальная медиа-компания в мире. Они также владеют и управляют Instagram. Представьте, что вы являетесь командой инженеров Facebook, и вам поручено улучшить интеграцию между их родственными платформами.

Задача: Наша задача здесь – найти всех людей на Facebook, которые входят в круг друзей пользователя, который мы называем функцией “Круги друзей”.

Сначала нам нужно определить людей, входящих в круг друзей каждого пользователя, который включает пользователей, прямо или косвенно являющихся друзьями другого пользователя. Давайте предположим, что на Facebook есть n пользователей. Дружеская связь является переходной .

Пример: Если Ник является прямым другом Эми, а Эми – прямым другом Мэтта, то Ник является косвенным другом Мэтта.

Мы будем использовать n*n квадратная матрица. Например, ячейка [i,j] сохранит значение 1 если эти пользователи являются друзьями. Если нет, то ячейка будет содержать значение 0 . На иллюстрации ниже в приведенном выше примере показаны два круга друзей. Ник дружит только с Эми , но Эми дружит с Ник и Мэтт . Это образует круг друзей. Марио самостоятельно создает еще один круг друзей.

Думайте о нашей симметричной входной матрице как о неориентированном графике . Как косвенные, так и прямые друзья, входящие в один круг друзей, также существуют в одном связном компоненте нашего графика. Это означает, что количество связанных компонентов графика даст нам, сколько у нас кругов друзей.

Итак, наша задача – найти количество подключенных компонентов. Мы рассматриваем входную матрицу как матрицу смежности . Итак, как нам это спроектировать и реализовать? Давайте разберемся с этим.

Сначала мы инициализируем массив с именем посещенный . Это позволит отслеживать посещенные вершины размера n с 0 как значение для каждого индекса.
Затем мы пересекаем график с помощью DFS, если посещенный[v] равен 0 . Если нет, мы переходим к следующему v .
Затем установите посещенный[v] на 1 для каждого v , с которым сталкивается наш обход DFS.
Когда обход DFS завершен, мы должны увеличить счетчик кругов на 1 . Это означает, что подключенный компонент был полностью пройден.

class Solution {

  public static void DFS (boolean[][] friends, int n, boolean[] visited, int v) {
    for (int i = 0; i < n; ++i) {

        // A user is in the friend circle if he/she is friends with the user represented by
        // user index and if he/she is not already in a friend circle
        if (friends[v][i] == true && !visited[i] && i != v) {
            visited[i] = true;
            DFS(friends, n, visited, i);
        }
    }
  }

  public static int friendCircles(boolean[][] friends, int n) {
    if (n == 0) {
        return 0;
    }

    int numCircles = 0;     //Number of friend circles

    //Keep track of whether a user is already in a friend circle
    boolean visited[] = new boolean[n];

    for (int i=0;i < n; i++){
      visited[i] = false;
    }

    //Start with the first user and recursively find all other users in his/her
    //friend circle. Then, do the same thing for the next user that is not already
    //in a friend circle. Repeat until all users are in a friend circle. 
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            DFS(friends, n, visited, i); //Recursive step to find all friends
            numCircles = numCircles + 1;
        }
    }

    return numCircles;
  }

  public static void main(String args[]) 
  { 
      int n = 4;
      boolean[][] friends = {
        {true,true,false,false},
        {true,true,true,false},
        {false,true,true,false},
        {false,false,false,true}
      };
     System.out.println("Number of friends circles: " + friendCircles(friends, n)); 
  } 

}

Показатели сложности

Временная сложность: |/O (n ^ 2) потому что мы проходим полную матрицу размера n^2

Сложность пространства: O(n) потому что посещенный массив , в котором хранятся наши посещенные пользователи , имеет размер n .

Функция календаря Google: Поиск Конференц-залов (куча)

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

Задача: Ваша цель – создать функциональность для планирования встреч. Вам необходимо определить и заблокировать минимальное количество конференц-залов для этих собраний.

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

Время наших встреч может быть указано следующим образом: {{2, 8}, {3, 4}, {3, 9}, {5, 11}, {8, 20}, {11, 15}} . Мы могли бы запланировать каждую встречу в отдельной комнате, но мы хотим использовать минимальное количество комнат. Мы наблюдаем, что три встречи пересекаются: {2, 8} , {3, 4} , и {3, 9} . Поэтому, по крайней мере, для этих трех потребуются отдельные комнаты.

Чтобы решить эту проблему, мы используем либо кучу, либо очередь приоритетов для хранения расписания собраний, используя end_time каждой встречи в качестве ключа. Комната наверху нашей кучи освободится раньше всего. Если конференц-зал с вершины кучи не свободен, значит, ни одна другая комната еще не свободна.

Итак, как мы создаем эту функциональность? Давайте разберемся с этим.

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

import java.util.Arrays; 
import java.util.PriorityQueue;
class Solution {

    public static int minMeetingRooms(int[][] meetingTimes){

        if(meetingTimes.length == 0){
            return 0;
        }

        Arrays.sort(meetingTimes, (a, b) -> Integer.compare(a[0], b[0]));       
        //min Heap keeps track of earliest ending meeting:
        PriorityQueue minHeap = new PriorityQueue<>((A, B) -> A - B);

        minHeap.add(meetingTimes[0][1]);

        for (int i = 1; i < meetingTimes.length; i++) {
            int currStart = meetingTimes[i][0];
            int currEnding = meetingTimes[i][1];
            int earliestEnding = minHeap.peek();

            if (earliestEnding <= currStart) {
                minHeap.remove();
            } 
            //update heap with curr ending
            minHeap.add(currEnding);
        }
        return minHeap.size();
    }

    public static void main( String args[] ) {
        // Driver code
        int[][] meetingTimes = {{2, 8}, {3, 4}, {3, 9}, {5, 11}, {8, 20}, {11, 15}};
        System.out.print(minMeetingRooms(meetingTimes));
    }
}

Показатели сложности

Временная сложность: |/O(n*log(n))

Сложность пространства: O(n) , где n – количество заседаний

Особенность Amazon: Товары в ценовом диапазоне (ЛУЧШИЕ)

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

Задача: Внедрить фильтр поиска для поиска товаров в заданном ценовом диапазоне. Данные о продукте представлены в виде двоичного дерева поиска. Значения – это цены на продукты.

Параметры, с которыми мы работаем, являются низкими и высокий , которые представляют ценовой диапазон пользователя. Приведенный ниже примерный список товаров сопоставлен с их ценами.

Затем они сохраняются в двоичном дереве поиска:

Мы можем предположить, что выбранный ценовой диапазон является низким и высокий , поэтому наше функциональное решение должно возвращать только цены {9, 8, 14, 20, 17} . Итак, как нам это реализовать? Давайте разберемся с этим.

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

Реализуйте рекурсивную вспомогательную функцию для обхода предварительного заказа.
Проверьте, находится ли текущее значение узла в нашем заданном диапазоне. Если да, добавьте его в массив вывод .
Рекурсивно вызовите функцию предварительного заказа для левого дочернего узла, если текущее значение узла больше или равно low .
Если текущее значение узла меньше или равно высокому , рекурсивно пересекает правый дочерний элемент узла.
Когда обход будет завершен, будет возвращен массив output .

Когда обход будет завершен, будет возвращен массив || output ||.

class Solution {
    public static void preOrder(Node node, int low, int high, List output){
        if (node != null) {
            if (node.val <= high && low <= node.val)
                output.add(node.val);
            if (low <= node.val)
                preOrder(node.leftChild, low, high, output);
            if (node.val <= high)
                preOrder(node.rightChild, low, high, output);
        }
    }
    public static List productsInRange(Node root, int low, int high){
        List output = new ArrayList();
        preOrder(root, low, high, output);
        return output;
    }
    public static void main( String args[] ) {
        // Driver code
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(9);
        bst.insert(6);
        bst.insert(14);
        bst.insert(20);
        bst.insert(1);
        bst.insert(30);
        bst.insert(8);
        bst.insert(17);
        bst.insert(5);

        System.out.println(productsInRange(bst.root, 7, 20));
    }
}

Когда обход будет завершен, будет возвращен массив || output ||.

public class BinarySearchTree{
    public Node root;
    public BinarySearchTree(){
        this.root = null;
    }

    public void insert(int val){
        if (this.root == null)
            this.root = new Node(val);
        else
            this.root.insert(val);
    }
}

class Node{
    public int val;
    public Node leftChild;
    public Node rightChild;

    public Node(int val){
        this.val = val;
        this.leftChild = null;
        this.rightChild = null;
    }

    public void insert(int val){
        Node current = this;
        Node parent = current;
        while (current != null){
            parent = current;
            if (val < current.val)
                current = current.leftChild;
            else
                current = current.rightChild;
        }
        if(val < parent.val)
            parent.leftChild = new Node(val);
        else
            parent.rightChild = new Node(val);
    }
}

Временная сложность

Временная сложность: O(n)

Сложность пространства: O(n)

Функция Твиттера: Добавляйте лайки (строки)

Твиттер – популярная платформа для социальных сетей. Представьте, что вы разработчик Twitter, и ваша команда должна создать API, который вычисляет количество лайков в твитах данного человека.

Задача: Создать API, который вычисляет общее количество лайков в твитах человека. Создайте модуль, который принимает два числа и возвращает сумму чисел.

Данные уже извлечены и сохранены для вас в простом текстовом файле. Все значения должны оставаться строками и не могут быть преобразованы в целые числа . Мы должны выполнять сложение цифр за цифрами из-за этих ограничений. Итак, как нам создать этот модуль? Давайте разберемся с этим.

Инициализировать пустую переменную res и нести как 0 .
Затем установите два указателя, p1 и p2 , которые будут указывать на конец как 1 и как 2 .
Пройдите по строкам с конца, используя эти указатели. Установите его на остановку, когда обе строки будут готовы.
Установите x1 равным цифре из строки как 1 при индексе p1 . Если p1 достиг начала , как 1 , установите x1 в 0 . Сделайте то же самое для x2 с как 2 при индексе p2 .
Вычислите текущее значение, используя значение = (x1 + x2 + перенос) % 10 . Затем обновите перенос так что перенос = (x1 + x2 + перенос)/10 .
Добавьте текущее значение к результату.
Если обе строки пройдены, но перенос все еще не равен нулю, добавьте перенос в rbs .
Наконец, измените результат на противоположный и преобразуйте его в строку. Верните последнюю строку.

class Solution {
    public static String addLikes(String like1, String like2){
        StringBuilder res = new StringBuilder();

        int carry = 0;
        int p1 = like1.length() - 1;
        int p2 = like2.length() - 1;
        while (p1 >= 0 || p2 >= 0) {
            int x1, x2;
            if(p1 >= 0)
                x1 = like1.charAt(p1) - '0';
            else 
                x1 = 0;
            if(p2 >= 0)
                x2 = like2.charAt(p2) - '0';
            else 
                x2 = 0;
            int value = (x1 + x2 + carry) % 10;
            carry = (x1 + x2 + carry) / 10;
            res.append(value);
            p1--;
            p2--;    
        }

        if (carry != 0)
            res.append(carry);

        return res.reverse().toString();
    }
    public static void main(String args[]) {
        System.out.println(addLikes("1545", "67"));
    }
}

Показатели сложности

Временная сложность: O(макс(n ^ 1,n ^ 2)) , где n^1 и n^2 – это длина входного сигнала.

Сложность пространства: O(макс(n ^ 1,n ^ 2))

Куда идти дальше

Поздравляю с тем, что вы добрались до конца! Вы просто создаете 5 реальных функций, используя такие навыки, как DFS, НО, кучи и многое другое. Как вы можете видеть, это мощный способ подготовки к собеседованиям по кодированию, который, как правило, более эффективен. Если вы можете понять основную структуру проблемы, вы можете решить практически любой вопрос .

Существуют еще десятки других практических проблем, подобных этой, например:

Объединять твиты в ленте Твиттера
AT&T Определяет местоположение
Масштабирование: Отображение собрания в вестибюле
Поисковая система: Поиск слов

Если вы хотите попрактиковаться в решении подобных проблем, ознакомьтесь с единственным в своем роде образовательным курсом Расшифруйте интервью по кодированию: Примеры из реального мира . Доступный на нескольких языках, этот курс поможет вам ответить на более чем 100 реальных вопросов, подобных этим. После каждого проекта вы будете лучше понимать, какие методы вы только что применили.

Это подготовка к собеседованию по кодированию переосмыслена с учетом ваших потребностей!

Счастливого обучения!

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

Оригинал: “https://dev.to/educative/crack-coding-interviews-by-building-these-5-real-world-features-24f0”