Сравнительный статистический анализ популярных задач на собеседованиях по темам, сложности и популярности на основе списка pgmreddy. Этот обзор может помочь вам выбрать оптимальную стратегию подготовки и автоматически проанализировать любые другие задачи, в зависимости от необходимости.
📂 Моя страница GitHub с данными и блокнотами Jupyter находится здесь.
Полный список вопросов интервью, которые я включил в статистику:
- Facebook (мета) июль 2020 г. — июль 2021 г.
- Google Январь — июнь 2020 г., Июль — октябрь 2020 г.
- Amazonиюль 2020 г. — июль 2021 г.
- Bloombergиюль 2020 г. — июль 2021 г.
- Apple, Uber, Flipkart, Swiggyиюль 2020 г. — июль 2021 г.*
*Учитывая небольшое количество задач для Apple, Uber, Flipkart и Swiggy, все они были объединены в общую базу данных и в тексте обозначены как Apple. Также следует отметить, что в статистику не попали премиальные задачи.
Итак, для начала создадим скрипт, который будет автоматически сканировать страницу LeetCode с вопросом по программированию и считывать все нужные нам параметры. На основе ответа QHarr на StackOverflow мы создадим SQL-запрос к серверной базе данных, используя graphql:
# sample problem to parse: # https://leetcode.com/problems/sliding-window-median/ titleslug = "sliding-window-median" data = {"operationName":"questionData","variables":{"titleSlug":str(titleslug)},"query":"query questionData($titleSlug: String!)...} # check it on github r = requests.post('https://leetcode.com/graphql',json=data).json() number = r['data']['question']['questionId'] title = r['data']['question']['title'] complexity = r['data']['question']['difficulty'] likes = r['data']['question']['likes'] dislikes = r['data']['question']['dislikes'] topics = r['data']['question']['topicTags']
Если мы выведем нужные переменные, вывод фрагмента кода с проанализированными параметрами будет выглядеть так:
480. Sliding Window Median Complexity: Hard, LIkes: 2210, Dislikes: 134 Topics: Array, Hash Table, Sliding Window, Heap(Priority Queue)
При доступе к серверной части LeetCode в SQL-запросе мы передаем только один строковый параметр, "str(titleslug)", который содержится в исходном URL-адресе. Таким образом, собрав нужные задачи в текстовый файл, мы можем пройтись по всему списку в цикле и сгенерировать один pandas dataframe для всего набора задач:
Теперь у нас есть отдельный фрейм данных для каждого набора задач. Вы можете создать свой собственный список проблем в виде текстового файла и получить подробную статистику в несколько кликов.
Хорошо! Давайте посмотрим на наборы задач интервью. Общее распределение сложности задач для каждой компании показано на рисунке ниже.
Как мы видим, несмотря на разное количество задач, практически все компании придерживаются правила 25% для простых и сложных задач, а задачи средней сложности занимают ~50%. Google, в свою очередь, в основном ориентирован на средние и сложные вопросы.
Каждое задание на leetcode может относиться сразу к нескольким темам. Задания во всех наборах интервью имеют в общей сложности 43 возможные темы. Если собрать все проблемы по каждому отдельному набору и посчитать количество упоминаний каждой темы отдельно, то распределение по темам для каждой компании будет выглядеть так:
«Массив», очевидно, упоминается чаще всего. Другими популярными темами являются "Строки", различные виды "Поиска", "Сортировка", "Хеш-таблицы", "Динамическое программирование" и "Деревья". . Распределение и пересечение Top 20 самых популярных тем среди всех компаний удобно представить в виде полярного графика с логарифмической шкалой:
Однако популярность одних и тех же задач для интервью среди пользователей не коррелирует с частотой выбора тем вопросов среди технических интервьюеров. Распределение индекса популярности тем среди пользователей по всем выбранным задачам интервью для каждой компании представлено ниже.
Взвешенный индекс популярности темы (TPI) рассчитывался следующим образом:
Где p — упоминание (может быть как ноль, так и единица) темы на странице с проблемой (раздел «Похожие темы»), N — общее количество проблем в рассматриваемом наборе интервью.
Например, тема «Математика» получила 2 упоминания в двух разных вопросах с 600 и 1000 лайками-дизлайками соответственно. Итак, индекс популярности «Математики» равен TPI = (1000+600)/2 = 800 (среднее количество лайков-дизлайков на одно упоминание). Тема «Массив», в свою очередь, получила 23 вопроса по 1000 лайков-дизлайков каждый, значит «Массив» в сумме набрал 23000 лайков-дизлайков, и, следовательно, имеет индекс популярности TPI = 23000/23 = 1000 ( среднее количество лайков-дизлайков на одно упоминание).
Следующим интересным для нас параметром будет соотношение упоминаний разных тем программирования.
Если, например, у нас есть набор из трех задач:
- №1 по темам "Массив", "Строка" и "Динамическое программирование"
- №2 с темами "Массив", "Строка" и "Сортировка"
- №3 с темами "Массив" и "Дерево"
Тогда тема «Массив» будет иметь все три пересечения с каждой из задач, «Строка» — два пересечения, а темы «Динамическое программирование», «Сортировка» и «Дерево» будут иметь нули.
На рисунке ниже показана корреляция тем для наборов задач Google и Meta. Число внутри каждой ячейки означает количество упоминаний (пересечений) темы по оси Y при наличии ключевого слова по оси X в описании проблемы (раздел «Похожие темы» на страницах LeetCode с заданными проблемами).
Если мы объединим все пять наборов интервью (Meta, Google, Amazon, Bloomberg и Apple*) вместе и удалим повторяющиеся задачи, общая картина корреляции будет выглядеть так:
Например, если вы в настоящее время изучаете хеш-таблицы, следующими темами для рассмотрения могут быть «Строка», «Поиск», «Массив» и «Сортировка».
Теперь мы можем посмотреть на распределение каждой темы по сложности задач. Мета, как мы видим из сюжета, имеет самый высокий процент сложных задач в области динамического программирования и мемоизации (что также можно рассматривать как часть динамического программирования). Значительная часть сложных задач наблюдается в областях графа, сортировки, очереди и комбинаторики.
Хороший! 👍 Что еще мы можем сделать дальше?
Теперь мы выберем те вопросы, которые встречаются несколько раз (в наборах интервью не менее двух компаний).
Здесь лучше всего упомянуть известный слепой список 75, составленный из 75 лучших вопросов LeetCode, разделенных на следующие категории: массив, Бинарный, динамическое программирование, график, интервал, связанный список, матрица, строка, дерево и куча. Этот список был создан в 2018 году и по сей день остается популярным и считается обязательным. для подготовки к собеседованию (очень тщательный анализ всех этих вопросов провел NeetCode).Есть и его обновленная версия, Grind 75, того же автора.
В этой статье мы составили еще один список (см. ниже), представляющий собой перекрестный набор из 84 вопросов для интервью в Meta, Google, Amazon, Bloomberg, Apple, Uber, Flipkart и Swiggy в 2021 году. Для удобства мы сгруппировали задачи по тем же категориям, что и в Blind 75.
✅ Перекрестный набор из 84 вопросов для интервьюв Meta, Google, Amazon, Bloomberg, Apple, Uber, Flipkart и Swiggy в 2021 году
Звездочка (*) и жирный шрифт означают, что вопрос также находится в списке Blind 75
ARRAY *1: Two Sum *238: Product of Array Except Self *153: Find Minimum in Rotated Sorted Array 31: Next Permutation 34: Find First and Last Position of Element in Sorted Array 41: First Missing Positive 42: Trapping Rain Water 84: Largest Rectangle in Histogram 88: Merge Sorted Array 283: Move Zeroes 349: Intersection of Two Arrays 380: Insert Delete GetRandom O(1) 399: Evaluate Division 452: Minimum Number of Arrows to Burst Balloons 529: Minesweeper 560: Subarray Sum Equals K 973: K Closest Points to Origin 977: Squares of a Sorted Array 994: Rotting Oranges 1010: Pairs of Songs With Total Durations Divisible by 60 1095: Find in Mountain Array 1169: Invalid Transactions 1235: Maximum Profit in Job Scheduling 1293: Shortest Path in a Grid with Obstacles Elimination BINARY 29: Divide Two Integers 67: Add Binary DYNAMIC PROGRAMMING *322: Coin Change *91: Decode Ways 63: Unique Paths II 72: Edit Distance 139: Word Break 140: Word Break II 329: Longest Increasing Path in a Matrix 688: Knight Probability in Chessboard 1125: Smallest Sufficient Team 1335: Minimum Difficulty of a Job Schedule GRAPH *133: Clone Graph *200: Number of Islands 210: Course Schedule II 128: Longest Consecutive Sequence INTERVAL *56: Merge Intervals LINKED LIST *21: Merge Two Sorted Lists *23: Merge k Sorted Lists 2: Add Two Numbers 138: Copy List with Random Pointer 146: LRU Cache 203: Remove Linked List Elements 445: Add Two Numbers II STRING *3: Longest Substring Without Repeating Characters *76: Minimum Window Substring *242: Valid Anagram *20: Valid Parentheses 680: Valid Palindrome II 127: Word Ladder 155: Min Stack 227: Basic Calculator II 389: Find the Difference 394: Decode String 415: Add Strings 692: Top K Frequent Words 778: Reorganize String 833: Find And Replace in String 953: Verifying an Alien Dictionary 1047: Remove All Adjacent Duplicates In String 1209: Remove All Adjacent Duplicates in String II 1249: Minimum Remove to Make Valid Parentheses 1396: Design Underground System TREE *124: Binary Tree Maximum Path Sum *102: Binary Tree Level Order Traversal *297: Serialize and Deserialize Binary Tree *98: Validate Binary Search Tree *236: Lowest Common Ancestor of a Binary Tree 116: Populating Next Right Pointers in Each Node 278: First Bad Version 528: Random Pick with Weight 547: Number of Provinces 721: Accounts Merge 987: Vertical Order Traversal of a Binary Tree 1376: Time Needed to Inform All Employees HEAP *295: Find Median from Data Stream 239: Sliding Window Maximum 621: Task Scheduler 658: Find K Closest Elements
Кроме того, ряд популярных шаблонов программирования для эффективного подхода к решению задач:
- 14 шаблонов для ответа на любой вопрос на собеседовании по программированию
- От 5 до 23 паттернов, чтобы пройти любое собеседование по программированию
- Шаблоны LeetCode от csgator
- Официальные карты LeetCode Explore
- Вопросы наилучшей практики автора Blind 75
Спасибо! Сохраняйте спокойствие и LeetCode.