This content originally appeared on Level Up Coding - Medium and was authored by Anh Dang
Can You Solve Them in four hours?
I looked at over 1000 coding interview questions and found the hardest questions as follows by tech giants.
Question 01
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
Question 02
Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
For example, given s = “abcba” and k = 2, the longest substring with k distinct characters is “bcb”.
Question 03
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.
Follow-up: Can you do this in O(N) time and constant space?
Question 04
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Follow-up: what if you can’t use division?
Question 05
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.
Question 06
Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.
For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.
Question 07
We’re given a hashmap associating each courseId key with a list of courseIds values, which represents that the prerequisites of courseId are courseIds.
- Return a sorted ordering of courses such that we can finish all courses.
- Return null if there is no such ordering.
For example, given {‘CSC300’: [‘CSC100’, ‘CSC200’], ‘CSC200’: [‘CSC100’], ‘CSC100’: []}, should return [‘CSC100’, ‘CSC200’, ‘CSCS300’].Question 08
A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:
- push(x): add a new item x to the left end of the list
- pop(): remove and return the item on the left end of the list
- pull(): remove the item on the right end of the list.
Implement a quack using three stacks and O(1) additional memory, so that the amortized time for any push, pop, or pull operation is O(1).
Question 09
Given an array of numbers of length N, find both the minimum and maximum using less than 2 * (N - 2) comparisons.
Question 10
Given a word W and a string S, find all starting indices in S which are anagrams of W.
For example, given that W is “ab”, and S is “abxaba”, return 0, 3, and 4.
Question 11
Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.
For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:
10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)
Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.
Question 12
Find an efficient algorithm to find the smallest distance (measured in number of words) between any two given words in a string.
For example, given words “hello”, and “world” and a text content of “dog cat hello cat dog dog hello cat world”, return 1 because there’s only one word “cat” in between the two words.
Question 13
Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?
Question 14
Typically, an implementation of in-order traversal of a binary tree has O(h) space complexity, where h is the height of the tree. Write a program to compute the in-order traversal of a binary tree using O(1) space.
Question 15
Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one.
For example, the longest palindromic substring of “aabcdcb” is “bcdcb”. The longest palindromic substring of “bananas” is “anana”.
Question 16
Implement an LFU (Least Frequently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:
- set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least frequently used item. If there is a tie, then the least recently used key should be removed.
- get(key): gets the value at key. If no such key exists, return null.
Each operation should run in O(1) time.
Question 17
Given a string consisting of parentheses, single digits, and positive and negative signs, convert the string into a mathematical expression to obtain the answer.
Don’t use eval or a similar built-in parser.
For example, given ‘-1 + (2 + 3)’, you should return 4.
Question 18
Connect 4 is a game where opponents take turns dropping red or black discs into a 7 x 6 vertically suspended grid. The game ends either when one player creates a line of four consecutive discs of their color (horizontally, vertically, or diagonally), or when there are no more spots left in the grid.
Design and implement Connect 4.
Question 19
There are N couples sitting in a row of length 2 * N. They are currently ordered randomly, but would like to rearrange themselves so that each couple's partners can sit side by side.
What is the minimum number of swaps necessary for this to happen?
Question 20
Recall that the minimum spanning tree is the subset of edges of a tree that connect all its vertices with the smallest possible total edge weight. Given an undirected graph with weighted edges, compute the maximum weight spanning tree.
Question 21
Sudoku is a puzzle where you’re given a partially-filled 9 by 9 grid with digits. The objective is to fill the grid with the constraint that every row, column, and box (3 by 3 subgrid) must contain all of the digits from 1 to 9.
Implement an efficient sudoku solver.
Question 22
A knight is placed on a given square on an 8 x 8 chessboard. It is then moved randomly several times, where each move is a standard knight move. If the knight jumps off the board at any point, however, it is not allowed to jump back on.
After k moves, what is the probability that the knight remains on the board?
Question 23
You are given an array of length 24, where each element represents the number of new subscribers during the corresponding hour. Implement a data structure that efficiently supports the following:
- update(hour: int, value: int): Increment the element at index hour by value.
- query(start: int, end: int): Retrieve the number of subscribers that have signed up between start and end(inclusive).
You can assume that all values get cleared at the end of the day, and that you will not be asked for start and end values that wrap around midnight.
Question 24
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.
Question 25
Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.
For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.
Question 26
An 8-puzzle is a game played on a 3 x 3 board of tiles, with the ninth tile missing. The remaining tiles are labeled 1 through 8 but shuffled randomly. Tiles may slide horizontally or vertically into an empty space, but may not be removed from the board.
Design a class to represent the board, and find a series of steps to bring the board to the state [[1, 2, 3], [4, 5, 6], [7, 8, None]].
Question 27
Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters.
For example, given “hello/world:here”, return “here/world:hello”
Follow-up: Does your solution work for the following cases: “hello/world:here/”, “hello//world:here”
Question 28
Given a list of points, a central point, and an integer k, find the nearest k points from the central point.
For example, given the list of points [(0, 0), (5, 4), (3, 1)], the central point (1, 2), and k = 2, return [(0, 0), (3, 1)].
Question 29
Given an array of positive integers, divide the array into two subsets such that the difference between the sum of the subsets is as small as possible.
For example, given [5, 10, 15, 20, 25], return the sets {10, 25} and {5, 15, 20}, which has a difference of 5, which is the smallest possible difference.Question 30
Given a sorted list of integers of length N, determine if an element x is in the list without performing any multiplication, division, or bit-shift operations.
Do this in O(log N) time.
Question 31
You come across a dictionary of sorted words in a language you’ve never seen before. Write a program that returns the correct order of letters in this language.
For example, given ['xww', 'wxyz', 'wxyw', 'ywx', 'ywz'], you should return ['x', 'z', 'w', 'y'].
Question 32
Describe what happens when you type a URL into your browser and press Enter.
Question 33
You are going on a road trip, and would like to create a suitable music playlist. The trip will require N songs, though you only have Msongs downloaded, where M < N. A valid playlist should select each song at least once, and guarantee a buffer of B songs between repeats.
Given N, M, and B, determine the number of valid playlists.
Question 34
Write a program that computes the length of the longest common subsequence of three given strings. For example, given “epidemiologist”, “refrigeration”, and “supercalifragilisticexpialodocious”, it should return 5, since the longest common subsequence is "eieio".
Question 35
Given a list, sort it using this method: reverse(lst, i, j), which reverses lst from i to j.
Can you solve all of them? Give us your solutions by commenting on your answer below.
The Hardest Coding Interview Questions Ever was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Anh Dang
Anh Dang | Sciencx (2021-09-09T12:51:49+00:00) The Hardest Coding Interview Questions Ever. Retrieved from https://www.scien.cx/2021/09/09/the-hardest-coding-interview-questions-ever/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.