# Coding Interviews: Searching and Sorting

A **transformation sequence** from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return *all the ***shortest transformation sequences*** from* beginWord *to* endWord*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words *[beginWord, s1, s2, ..., sk].

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return **the median** of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Given a **non-empty** array of integers nums, every element appears *twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Given an array nums with n objects colored red, white, or blue, sort them **in-place **so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Given an m x n integers matrix, return *the length of the longest increasing path in *matrix.

From each cell, you can either move in four directions: left, right, up, or down. You **may not** move **diagonally** or move **outside the boundary** (i.e., wrap-around is not allowed).

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Given an m x n grid of characters board and a string word, return true *if* word *exists in the grid*.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are **sorted lexicographically** by the rules of this new language.

Return *a string of the unique letters in the new alien language sorted in ***lexicographically increasing order*** by the new language's rules. *If there is no solution, return ""*. *If there are multiple solutions, return* ***any of them**.

People are waiting in line (British english: "queue" not the data structure "queue"). You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with **exactly** ki other people in front who have a height greater than or equal to hi.

Reconstruct and return *the queue that is represented by the input array *people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Given two positive integers m and n which are the height and width of a **0-indexed** 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board.

Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited **exactly** once (the starting cell is considered visited and you **shouldn't** visit it again).

Return *the array* board *in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight).*

Note that a **knight** can **move** from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1 and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

Given an integer array nums and an integer k, return *the* kth *largest element in the array*.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Given an array of integers nums and an integer target, return *indices of the two numbers such that they add up to **target*.

You may assume that each input would have **exactly**** one solution**, and you may not use the *same* element twice.

You can return the answer in any order.