Just a bunch of practice interview questions that i'll work on. te
- Amazon Coding Interview Question - Recursive Staircase Problem
- Google Coding Interview Question - First Recurring Character
- Daily Coding Problems
This question asks you to find the number of ways you can go up a staircase given the size of the staircase and knowing you can only take one or two steps at a time like so.
The next part of the problem asks you how you would do it if you were given a set of steps that you could take. So for example given the set X = {1,3,5} that means you can only take 1 step, 3 steps, or 5 steps at a time. And then you have to figure out the number of ways to solve this problem.
This question asks you to find the first repeating character given a string of characters like so:
"ABCA" -> "A"
"HELLO" -> "L"
"COW" -> "NONE"
"DBCABA" -> "B"
Given a list of tuples like points_tuple = [(-2,4), (0,-2), (-1,0), (2,5), (-2,-3), (3,2), (1,0)] find the k closest points to origin. So in this case, if k=2 then the k closest points would be (-1,0) and (0,-2)
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
This problem can be solved in several different ways.
-
Brute force way would involve a nested iteration to check for every pair of numbers. This would take O(N^2).
-
use a set to remember the numbers we've seen so far. Then for a given number, we can check if there is another number that, if added, would sum to k. This would be O(N) since lookups of sets are O(1) each.
-
Yet another solution involves sorting the list. We can then iterate through the list and run a binary search on K - lst[i]. Since we run binary search on N elements, this would take O(N log N) with O(1) space.
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?
This problem would be easy with division: an optimal solution could just find the product of all numbers in the array and then divide by each of the numbers.
Without division, another approach would be to first see that the ith element simply needs the product of numbers before i and the product of numbers after i. Then we could multiply those two numbers to get our desired product.
In order to find the product of numbers before i, we can generate a list of prefix products. Specifically, the ith element in the list would be a product of all numbers including i. Similarly, we would generate the list of suffix products.
This runs in O(N) time and space, since iterating over the input arrays takes O(N) time and creating the prefix and suffix arrays take up O(N) space.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = rightThe following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'There are many ways to serialize and deserialize a binary tree, so don't worry if your solution differs from this one. We will be only going through one possible solution.
We can approach this problem by first figuring out what we would
like the serialized tree to look like. Ideally, it would contain the
minimum information required to encode all the necessary information
about the binary tree. One possible encoding might be to borrow S-expressions from Lisp.
The tree Node(1, Node(2), Node(3)) would then look like '(1 (2 () ()) (3 () ()))',
where the empty brackets denote nulls.
To minimize data over the hypothetical wire, we could go a step further and prune out
some unnecessary brackets. We could also replace the 2-character () with #. We can then infer leaf nodes by their form
val # # and thus get the structure of the tree that way. Then our tree would look like 1 2 # # 3 # #.
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.
The solution is way more complicated but doesn't use any extra space
Our lives would be easier without the linear time constraint: we would just sort the array
while filtering out negative numbers, and iterate over the sorted array and return the first
number that doesn't match the index. However, sorting takes O(n log n), so we can't use that here.
Clearly we have to use some sort of trick here
to get it running in linear time. Since the first missing
positive number must be between 1 and len(array) (why?), we
can ignore any negative numbers and numbers bigger than len(array).
The basic idea is to use the indices of the array itself to reorder the
elements to where they should be. We traverse the array and swap
elements between 0 and the length of the array to their value's index.
We stay at each index until we find that index's value and keep on swapping.
By the end of this process, all the first positive numbers
should be grouped in order at the beginning of the array.
We don't care about the others. This only takes O(N) time
since we swap each element at most once.
Then we can iterate through the array and return the index of the first number that doesn't match, just like before.
Another way we can do this is by adding all the numbers to a set, and then use a counter initialized to 1 Then continuously increment the counter and check whether the value is in the set.
cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.
Given this implementation of cons:
def cons(a, b):
def pair(f):
return f(a, b)
return pairImplement car and cdr.
This is a really cool example of using closures to store data. We must look at the signature type of cons to retrieve its first and last elements. cons takes in a and b, and returns a new anonymous function, which itself takes in f, and calls f with a and b. So the input to car and cdr is that anonymous function, which is pair. To get a and b back, we must feed it yet another function, one that takes in two parameters and returns the first (if car) or last (if cdr) one.
so it ends up something like this:
def car_answer(pair):
return pair(lambda a, b: a)
def cdr_answer(pair):
return pair(lambda a, b: b)or you can use the __closure__ method and call the first value in the cell
def car_my(pair):
return pair.__closure__[0].cell_contents
def cdr_my(pair):
return pair.__closure__[1].cell_contentsAn XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.
If using a language that has no pointers (such as Python), you can assume you have access to get_pointer and dereference_pointer functions that converts between nodes and memory addresses.
Given the linked list and a positive integer k, rotate the list to the right by k places. For example given the linked list 7 -> 7 -> 3 -> 5 and k=2 it should become 3 -> 5 -> 7 -> 7
Given the linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 3, it should become 3 -> 4 -> 5 -> 1 -> 2.
Let's look at the structure of the solution:
a -> b -> c -> d -> e, k = 2
becomes
d -> e -> a -> b -> c
To generalize this, we take the k last elements (in order) and move them to the front. We fix the pointers up so that the last element points to the old head, and the kth element's next points to null.
We can accomplish this by using fast and slow pointers.
The basic idea is this. First, advance the fast pointer k steps ahead. Then move the fast and slow pointers together until the fast one hits the end first.
However, to handle the case where k is larger than the length of the linked list itself, we first get the length of the linked list first n, and check k % n first.