101_150.md

101

This problem was asked by Lyft

Given a list of integers and a number K, return which contiguous elements of the list sum to K.

For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4].

Solution

102

This problem was asked by Square

Given a string and a set of characters, return the shortest substring containing all the characters in the set.

For example, given the string "figehaeci" and the set of characters {a, e, i}, you should return "aeci".

If there is no substring containing all the characters in the set, return null.

Solution

103

This problem was asked by Google

Determine whether a doubly linked list is a palindrome. What if it’s singly linked?

For example, 1 -> 4 -> 3 -> 4 -> 1 returns true while 1 -> 4 returns false.

Solution

104

This problem was asked by Facebook

Given a function f, and N return a debounced f of N milliseconds.

That is, as long as the debounced f continues to be invoked, f itself will not be called for N milliseconds.

Solution

105

This problem was asked by Pinterest

Given an integer list where each number represents the number of hops you can make, determine whether you can reach to the last index starting at index 0.

For example, [2, 0, 1, 0] returns true while [1, 1, 0, 1] returns false.

Solution

106

This problem was asked by Microsoft

Print the nodes in a binary tree level-wise. For example, the following should print 1, 2, 3, 4, 5.

  1
 / \
2   3
   / \
  4   5

Solution

107

This problem was asked by Google

Given two strings A and B, return whether or not A can be shifted some number of times to get B.

For example, if A is abcde and B is cdeab, return true. If A is abc and B is acb, return false.

Solution

108

This problem was asked by Cisco

Given an unsigned 8-bit integer, swap its even and odd bits. The 1st and 2nd bit should be swapped, the 3rd and 4th bit should be swapped, and so on.

For example, 10101010 should be 01010101.

Bonus: Can you do this in one line?

Solution

109

This problem was asked by Facebook

Given a binary tree, return all paths from the root to leaves.

For example, given the tree

1 /
2 3 /
4 5 it should return [[1, 2], [1, 3, 4], [1, 3, 5]].

Solution

110

This problem was asked by Google

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.

Solution

111

This problem was asked by Twitter

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Assume that each node in the tree also has a pointer to its parent.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

Solution

112

This problem was asked by Google

Given a string of words delimited by spaces, reverse the words in string. For example, given "hello world here", return "here world hello"

Follow-up: given a mutable string representation, can you perform this operation in-place?

Solution

113

This problem was asked by Facebook

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"

Solution

114

This problem was asked by Google

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Solution

115

This problem was asked by Jane Street

Generate a finite, but an arbitrarily large binary tree quickly in O(1).

That is, generate() should return a tree whose size is unbounded but finite.

Solution

116

This problem was asked by Facebook

Given a binary tree, return the level of the tree with minimum sum.

Solution

117

This problem was asked by Google

Given a sorted list of integers, square the elements and give the output in sorted order.

For example, given [-9, -2, 0, 2, 3], return [0, 4, 4, 9, 81].

Solution

118

This problem was asked by Google

Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them.

For example, given the intervals [0, 3], [2, 6], [3, 4], [6, 9], one set of numbers that covers all these intervals is {3, 6}.

Solution

119

This problem was asked by Microsoft

Implement the singleton pattern with a twist. First, instead of storing one instance, store two instances. And in every even call of getInstance(), return the first instance and in every odd call of getInstance(), return the second instance.

Solution

120

This problem was asked by Google

Given a string which we can delete at most k, return whether you can make a palindrome.

For example, given 'waterrfetawx' and a k of 2, you could delete f and x to get 'waterretaw'.

Solution

121

This question was asked by Zillow

You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.

For example, in this matrix

0 3 1 1 2 0 0 4 1 5 3 1 The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins.

Solution

122

This problem was asked by LinkedIn

Given a string, return whether it represents a number. Here are the different kinds of numbers:

"10", a positive integer "-10", a negative integer "10.1", a positive real number "-10.1", a negative real number "1e5", a number in scientific notation And here are examples of non-numbers:

"a" "x 1" "a -2" "-"

Solution

123

This problem was asked by Microsoft

You have 100 fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains?

Write a function that, given n, returns the number of rounds you'd expect to play until one coin remains.

Solution

124

This problem was asked by Google

Given the root of a binary search tree, and a target K, return two nodes in the tree whose sum equals K.

For example, given the following tree and K of 20

10

/
5 15 /
11 15 Return the nodes 5 and 15.

Solution

125

This problem was asked by Facebook

Write a function that rotates a list by k elements. For example, [1, 2, 3, 4, 5, 6] rotated by two becomes [3, 4, 5, 6, 1, 2]. Try solving this without creating a copy of the list. How many swap or move operations do you need?

Solution

126

This problem was asked by Microsoft

Let's represent an integer in a linked list format by having each node represent a digit in the number. The nodes make up the number in reversed order.

For example, the following linked list:

1 -> 2 -> 3 -> 4 -> 5 is the number 54321.

Given two linked lists in this format, return their sum in the same linked list format.

For example, given

9 -> 9 5 -> 2 return 124 (99 + 25) as:

4 -> 2 -> 1

Solution

127

The Tower of Hanoi is a puzzle game with three rods and n disks, each a different size.

All the disks start off on the first rod in a stack. They are ordered by size, with the largest disk on the bottom and the smallest one at the top.

The goal of this puzzle is to move all the disks from the first rod to the last rod while following these rules:

You can only move one disk at a time. A move consists of taking the uppermost disk from one of the stacks and placing it on top of another stack. You cannot place a larger disk on top of a smaller disk. Write a function that prints out all the steps necessary to complete the Tower of Hanoi. You should assume that the rods are numbered, with the first rod being 1, the second (auxiliary) rod being 2, and the last (goal) rod being 3.

For example, with n = 3, we can do this in 7 moves:

Move 1 to 3 Move 1 to 2 Move 3 to 2 Move 1 to 3 Move 2 to 1 Move 2 to 3 Move 1 to 3

Solution

128

Given a real number n, find the square root of n. For example, given n = 9, return 3.

Solution

129

This problem was asked by Facebook

Given an array of numbers representing the stock prices of a company in chronological order and an integer k, return the maximum profit you can make from k buys and sells. You must buy the stock before you can sell it, and you must sell the stock before you can buy it again.

For example, given k = 2 and the array [5, 2, 4, 0, 1], you should return 3.

Solution

130

This question was asked by Snapchat

Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list.

Solution

131

This question was asked by Riot Games

Design and implement a HitCounter class that keeps track of requests (or hits). It should support the following operations:

record(timestamp): records a hit that happened at timestamp total(): returns the total number of hits recorded range(lower, upper): returns the number of hits that occurred between timestamps lower and upper (inclusive) Follow-up: What if our system has limited memory?

Solution

132

This problem was asked by Amazon

Given a node in a binary tree, return the next bigger element, also known as the inorder successor.

For example, the inorder successor of 22 is 30.

10 /
5 30 /
22 35 You can assume each node has a parent pointer.

Solution

133

This problem was asked by Facebook

You have a large array with most of the elements as zero.

Use a more space-efficient data structure, SparseArray, that implements the same interface:

init(arr, size): initialize with the original large array and size. set(i, val): updates index at i with val. get(i): gets the value at index i.

Solution

134

This question was asked by Apple

Given a binary tree, find a minimum path sum from root to a leaf.

For example, the minimum path in this tree is [10, 5, 1, -1], which has sum 15.

10 /
5 5 \
2 1 / -1

Solution

135

This question was asked by Google

Given an N by M matrix consisting only of 1's and 0's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

[[1, 0, 0, 0], [1, 0, 1, 1], [1, 0, 1, 1], [0, 1, 0, 0]] Return 4.

Solution

136

This problem was asked by Amazon

Implement a bit array.

A bit array is a space efficient array that holds a value of 1 or 0 at each index.

init(size): initialize the array with size set(i, val): updates index at i with val where val is either 1 or 0. get(i): gets the value at index i.

Solution

137

This problem was asked by Google

Find the minimum number of coins required to make n cents.

You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

For example, given n = 16, return 3 since we can make it with a 10¢, a 5¢, and a 1¢.

Solution

138

This problem was asked by Google.

Given an iterator with methods next() and hasNext(), create a wrapper iterator, PeekableInterface, which also implements peek(). peek shows the next element that would be returned on next().

Here is the interface:

class PeekableInterface(object): def init(self, iterator): pass

def peek(self):
    pass

def next(self):
    pass

def hasNext(self):
    pass

Solution

139

This problem was asked by Facebook

Given an array of integers in which two elements appear exactly once and all other elements appear exactly twice, find the two elements that appear only once.

For example, given the array [2, 4, 6, 8, 10, 2, 6, 10], return 4 and 8. The order does not matter.

Follow-up: Can you do this in linear time and constant space?

Solution

140

This problem was asked by Microsoft

Implement 3 stacks using a single list:

class Stack: def init(self): self.list = []

def pop(self, stack_number):
    pass

def push(self, item, stack_number):
    pass

Solution

141

This problem was asked by Google

You're given a string consisting solely of (, ), and *. * can represent either a (, ), or an empty string. Determine whether the parentheses are balanced.

For example, (()* and () are balanced. )( is not balanced.

Solution

142

This problem was asked by Amazon

Given a pivot x, and a list lst, partition the list into three parts.

The first part contains all elemenets in lst that are less than x The first part contains all elemenets in lst that are equal to x The first part contains all elemenets in lst that are larger than x Ordering within a part can be arbitrary.

For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10], one partition may be `[9, 3, 5, 10, 10, 12, 14]

Solution

143

This problem was asked by Google

Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

If two distances to larger numbers are the equal, then return any one of them. If the array at i doesn't have a nearest larger integer, then return null.

Follow-up: If you can preprocess the array, can you do this in constant time?

Solution

144

This problem was asked by Google

Given the head of a singly linked list, swap every two nodes and return its head.

For example, given 1 -> 2 -> 3 -> 4, return 2 -> 1 -> 4 -> 3.

Solution

145

This question was asked by BufferBox

Given a binary tree where all nodes are either 0 or 1, prune the tree so that subtrees containing all 0s are removed.

For example, given the following tree:

0 /
1 0 /
1 0 /
0 0 should be pruned to:

0 /
1 0 / 1 We do not remove the tree at the root or its left child because it still has a 1 as a descendant.

Solution

146

Given a list, sort it using this method: reverse(lst, i, j), which sorts lst from i to j.

Solution

147

This problem was asked by Apple

Gray code is a binary code where each successive value differ in only one bit, as well as when wrapping around. Gray code is common in hardware so that we don't see temporary spurious values during transitions.

Given a number of bits n, generate a possible gray code for it.

For example, for n = 2, one gray code would be [00, 01, 11, 10].

Solution

148

This problem was asked by Goldman Sachs

Given a list of numbers L, implement a method sum(i, j) which returns the sum from the sublist L[i:j] (including i, excluding j).

For example, given L = [1, 2, 3, 4, 5], sum(1, 3) should return sum([2, 3]), which is 5.

You can assume that you can do some pre-processing. sum() should be optimized over the pre-processing step.

Solution

149

This problem was asked by LinkedIn

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)].

Solution

150

Given a 2-D matrix representing an image, a location of a pixel in the screen and a color C, replace the color of the given pixel and all adjacent same colored pixels with C.

For example, given the following matrix, and location pixel of (2, 2), and 'G' for green:

B B W
W W W
W W W
B B B

Becomes

B B G
G G G
G G G
B B B

Solution