Coding interview scrapbook

  269.   Alien Dictionary Вы обнаружили инопланетный язык, который использует латинский алфавит. Но порядок букв в алфавите вам неизвестен. Дан список строк words из инопланетного словаря, эти строки отсортированы в лексикографическом порядке согласно инопланетному алфавиту . Вернуть список неповторящихся букв, отсорторованных в лексикографическом порядке инопланетного алфавита. Если решения не существует, вернуть пусту строку "" . Если существует несколько решений, вернуть любое из них . Строка s лексикографически меньше строки t , если в первой букве, в которой они отличаются, буква из  s идет перед буквой из t в инопланетном алфавите . Если первые min(s.length, t.length) бквы одинаковы, тогда s меньше тогда итольео тогда, если s.length < t.length . Пример 1: Дано: words = ["wrt","wrf","er","ett","rftt"] Результат: "wertf" Пример 2: Дано : words = ["z","x"] Результат : "...

 827.   Making A Large Island Дана матрица размеров n x n состоящая из нулей и единиц grid . Можно сделать не более одной операции по изменению 0 в 1. Вернуть размер наибольшего острова в grid после применения этой операции . Остров - это связная группа из 1 по 4 направлениям: вверх/вниз/вправо/влево . Пример 1: Дано: grid = [[1,0],[0,1]] Результат: 3 Пояснение : Мы можем поменять любой 0 на 1 и получим связный остров размером 3. Пример 2: Дано : grid = [[1,1],[1,0]] Результат : 4 Пояснение: Мы поменять единственный 0 на 1 и получим связный остров размером 4. Пример 3: Дано : grid = [[1,1],[1,1]] Результат : 4 Пояснение : Нулей нет, мы не можем провести операцию по смене 0 на 1, поэтому размер острова = 4. Ограничения: n == grid.length n == grid[i].length 1 <= n <= 500 grid[i][j] в каждой ячейке содержит 0 или 1 . Идея решения  Для каждой 1 в матрице , мы закращиваем существующие островаразными красками (2, 3 и т.д.). Мы также запоминаем разм...

  1376 .   Time Needed to Inform All Employees В компании работаю т n сотрудников, каждый с уникальным ID от 0 до n - 1 . У главы компании ID= headID . У каждого работника есть менеджер, заданный в массиве manager , где manager[i] - это менеджер сотрудника с индексом i ,   manager[headID] = -1 . Также отношения субординации представляют собой дерево. Глава компании хочет известить всех сотрудников срочными новостями. Он передает новость своим прямым субординатам, а те - своим.И так далее, пока все сотрудники не получат эту новость. Сотруднику с индексом i треубуется informTime[i] минут, чтобы известить своих субординатов. То есть после informTime[i] минут, все его субординаты начнут передавать новость дальше. Вернуть число минут, которые нужны, чтобы известить всех сотрудников. Пример 1: Дано: n = 1, headID = 0, manager = [-1], informTime = [0] Результат: 0 Пояснение: Глава компании - единственный сотрудник. Пример 2: Дано: n = 6, headID = 2, manager = [2,...

1438 .   Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Дан массив целых чисел nums и целочисленный порог limit , вернуть размер самого длинного не пустого подмассива, у которого абсолютная разность между его двумя любыми элементами не превышает limit . Пример 1: Дано: nums = [8,2,4,7], limit = 4 Результат: 2 Пояснение: Все подмассивы: [8] максимальная абсолютная разность |8-8| = 0 <= 4. [8,2] максимальная абсолютная разность |8-2| = 6 > 4. [8,2,4] максимальная абсолютная разность |8-2| = 6 > 4. [8,2,4,7] максимальная абсолютная разность |8-2| = 6 > 4. [2] максимальная абсолютная разность |2-2| = 0 <= 4. [2,4] максимальная абсолютная разность |2-4| = 2 <= 4. [2,4,7] максимальная абсолютная разность |2-7| = 5 > 4. [4] максимальная абсолютная разность |4-4| = 0 <= 4. [4,7] максимальная абсолютная разность |4-7| = 3 <= 4. [7] максимальная абсолютная разность |7-7| = 0 <= 4. Подмассивы, которые соответствуют услов...