Math & Stats Strategies Flashcards
Find kth Permutation
Given a set of n elements, find their kth permutation.
Linear runtime, linear memory (recursive solution will consume memory on the stack)
- If input vector is empty return result vector
- block_size = (n-1)! [‘n’ is the size of vector]
- Figure out which block k will lie in and select the first element of that block (this can be done by doing (k-1)/block_size )
- Append selected element to result vector and remove it from original input vector
- Deduce from k the blocks that are skipped i.e k = k - selected*block_size and goto step 1
Integer Division
Given two integers: x and y; return x ÷ y without using ‘/’ (division) or ‘*’ (multiplication) operators. Assume that both integers are positive.
Logarithmic, O(logn) Runtime, Logarithmic, O(logn) Memory
The Naive approach goes like this
sum = divisor
count = 0
while sum is less than or equal to dividend
sum = sum + divisor
count = count + 1
return count
But we want to improve this runtime for big numbers. An efficient approach would be to use the bit shift operators ‘<>’ to multiply and divide. Here is how it works:
Num * 2 = Num << 1 (shift left by 1)
Num / 2 = Num >> 1 (shift right by 1)
Instead of adding the dividend to approach the divisor, we’ll keep multiplying the dividend and quotient by 2 (i.e. shift left) until we reach the divisor. Here is an overview of the algorithm.
Pythagorean Triplets
Given an integer array, find all Pythagorean triplets (a2 + b2 = c2).
Quadratic O(n2) runtime, Logarithmic O(logn) Memory
This solution is based on the 3SUM problem. Here is an overview of the approach where we try to find any elements matching the criteria a2 + b2 = c2.
- Sort the list of integers.
- Iterate the list from start to end. Select the current element as c2.
- In order to find the other two elements (a2+b2 = c2), we’ll traverse the list from start and end till start
- We can take advantage of the fact that the list is sorted. While traversing the list we’re looking for 3 numbers that sum up to 0: a2+b2 + (-c2) = 0.
- a2 = list[start] * list[start]
- b2 = list[end] * list[end]
- If the current values of start & end iterators make such a triplet, we’ll save it.
- If a2+b2 + (-c2) > 0, we’ll decrement the end iterator in hope of hitting the target sum. Remember, (list[start] <= list[end]).
- If a2+b2 + (-c2) < 0, we’ll increment the start iterator.
All Sum Combinations
Given a positive integer, target, print all possible combinations of positive integers that sum up to the target number.
For example, if we are given input ‘5’, these are the possible sum combinations.
Exponential Runtime, Linear complexity
The algorithm will recursively check all the numbers which can sum up to the target. In each recursive call, there is a for loop which runs from start to target. start is initially 1. The current_sum is the variable that is incremented in every recursive call.
Here is the logic of the code; every time a value is added to the current_sum, it is also added to the result list which is the sum combination for that particular call. Whenever current_sum becomes equal to target, we can be sure that the result list contains a possible combination for target. This list is appended to the final output list.
Find Missing Number
Given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one; find the missing number.
Linear Runtime, Constant Memory
Here are the steps to find the missing number.
- Find the sum ‘sum_of_elements’ of all the numbers in the array. This would require a linear scan, O(n).
- Then find the sum ‘expected_sum’ of first ‘n’ numbers using the arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
- The difference between these i.e. ‘expected_sum - sum_of_elements’, is the missing number in the array.
Permute String
Implement a method to print all permutations of a given string without duplicates.
For instance, all permutations of string “bad” are:
bad, bda, abd, adb, adb, dab, dba
factorial, O(n!) runtime, factorial O(n!) memory (because it’s recursive)
All Subsets
We are given a set of integers and we have to find all the possible subsets of this set of integers.
Exponential runtime, O(2n * n) - where ‘n’ is number of integers in the given set. Exponential O(2n * n) memory.
Here’s an overview of the algorithm we’ll use:
n = size of given integer set
subsets_count = 2^n
for i = 0 to subsets_count
form a subset using the value of ‘i’ as following:
bits in number ‘i’ represent index of elements to choose from original set,
if a specific bit is 1 choose that number from original set and add it to current subset,
e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
add current subset to list of all subsets
Line with Maximum Points
Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.
Input: points: [(-1, 1), (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]
Output : 4
Then maximum number of point which lie on same line are 4, those point are (0, 0), (1, 1), (2, 2), (3, 3)
We can solve above problem by following approach; For each point p, calculate its slope with other points and use a map to record how many points have same slope, by which we can find out how many points are on same line with p as their one point. For each point keep doing the same thing and update the maximum number of point count found so far.
Some things to note in implementation are that if two point are (x1, y1) and (x2, y2) then their slope will be (y2 - y1) / (x2 - x1) which can be a double value and can cause precision problems. To get rid of the precision problems, we treat slope as pair ((y2 - y1), (x2 - x1)) instead of ratio and reduce pair by their gcd before inserting into map. In below code points which are vertical or repeated are treated separately.
Is Number Valid?
Given an input string, determine if it makes a valid number or not.
For simplicity, assume that white spaces are not present in the input.
- *4.325** is a valid number.
- *1.1.1** is NOT a valid number.
- *222** is a valid number.
- *22.** is NOT a valid number.
- *0.1** is a valid number.
- *22.22.** is NOT a valid number.
- *1.** is NOT a valid number.
Linear runtime, constant memory. We’re basically building a state machine.
The initial state is ‘Start’. We’ll process each character to identify the next state. The input string is not a valid number if we reach an UNKNOWN state at any point or if it ends in a DECIMAL. For example:
- If we’re at START and the character is not [[0-9] or [.]], we move to UNKNOWN.
- If we’re at INTEGER and the character is not [[0-9] or [.]], we move to UNKNOWN.
- If we’re at DECIMAL and the character is not [0-9], we move to UNKNOWN.
- If we’re at AFTER_DECIMAL and the character is not [0-9], we move to UNKNOWN.
We are not looking at the sign (+ or -) at the start of a number in the state machine. If there is a sign at the start of the input string, we start processing the string for the state machine after that sign character.
Power of a Number
Given a double, ‘x’, and an integer, ‘n’, write a function to calculate ‘x’ raised to the power ‘n’.
Examples:
power(2,5) = 32
power(3,4) = 81
power(1.5,3) = 3.375
power(2,-2) = 0.25
Complexity: Logarithmic O(log n) Runtime. Logarithmic O(log n) Memory (The recursive solution has O(log n) memory complexity as it will consume memory on the stack)
A simple algorithm for this problem is to multiply ‘x’ by ‘n’ times. The time complexity of this algorithm would be O(n). We can use the divide and conquer approach to solve this problem more efficiently.
- In the dividing step, we keep dividing n by 2 recursively until we reach the base case i.e. n == 1
- In the combining step, we get the result, ‘r’, of the sub-problem and compute the result of the current problem using the two rules below:
- if n is even, the result is r * r (where r is the result of sub-problem)
- if n is odd, the result is x * r * r (where r is the result of sub-problem)
Calculate Square Root
Given a double number, write a function to calculate its square root.
We’ll use the below algorithm to find the square root of a number. Note that this algorithm is very similar to binary search.
Set low = 0 and high = 1 + n / 2
while True:
mid = (low + high) / 2
square = mid * mid
If square is equal to ‘n’ then
return mid (mid is the square root)
Else If square is less than n:
low = mid (square root lies in upper half i.e. between mid and high)
Else If square is greater than n then
high = mid (square root lies in lower half i.e. between low and mid)
Two Egg Problem
A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.
If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.
Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.
We’ll use the first egg to get a range of possible floors that contain the highest floor an egg can be dropped from without breaking. To do this, we’ll drop it from increasingly higher floors until it breaks, skipping some number of floors each time.
When the first egg breaks, we’ll use the second egg to find the exact highest floor an egg can be dropped from. We only have to drop the second egg starting from the last floor where the first egg didn’t break, up to the floor where the first egg did break. But we have to drop the second egg one floor at a time.
With the first egg, if we skip the same number of floors every time, the worst case number of drops will increase by one every time the first egg doesn’t break. To counter this and keep our worst case drops constant, we decrease the number of floors we skip by one each time we drop the first egg.
When we’re choosing how many floors to skip the first time we drop the first egg, we know:
- We want to skip as few floors as possible, so if the first egg breaks right away we don’t have a lot of floors to drop our second egg from.
- We always want to be able to reduce the number of floors we’re skipping. We don’t want to get towards the top and not be able to skip floors any more.
Knowing this, we set up the following equation where nn is the number of floors we skip the first time:
n+(n−1)+(n−2)+…+1=100
This triangular series reduces to n * (n+1) / 2 = 100 which solves to give n = 13.651. We round up to 14 to be safe. So our first drop will be from the 14th floor, our second will be 13 floors higher on the 27th floor and so on until the first egg breaks. Once it breaks, we’ll use the second egg to try every floor starting with the last floor where the first egg didn’t break. At worst, we’ll drop both eggs a combined total of 14 times.
In-Place Shuffle
Write a function for doing an in-place shuffle of a list.
The shuffle must be “uniform,” meaning each item in the original list must have the same probability of ending up in each spot in the final list.
Assume that you have a function get_random(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.
Complexity: O(n) time and O(1) space.
We choose a random item to move to the first index, then we choose a random other item to move to the second index, etc. We “place” an item in an index by swapping it with the item currently at that index.
Crucially, once an item is placed at an index it can’t be moved. So for the first index, we choose from nn items, for the second index we choose from n-1 items, etc.
This is a semi-famous algorithm known as the Fisher-Yates shuffle (sometimes called the Knuth shuffle).
Simulate 5-sided Die
You have a function rand7() that generates a random integer from 1 to 7. Use it to write a function rand5() that generates a random integer from 1 to 5.
rand7() returns each integer with equal probability. rand5()must also return each integer with equal probability.
We simply “re-roll” whenever we get a number greater than 5.
Simulate 7-sided Die
You have a function rand5() that generates a random integer from 1 to 5. Use it to write a function rand7() that generates a random integer from 1 to 7.
rand5() returns each integer with equal probability. rand7() must also return each integer with equal probability.
Complexity: Worst-case O(∞) time (we might keep re-rolling forever) and O(1) space.
Because rand5() has only 5 possible outcomes, and we need 7 possible results for rand7(), we need to call rand5() at least twice.
When we call rand5() twice, we have 5*5=25 possible outcomes. If each of our 7 possible results has an equal chance of occurring, we’ll need each outcome to occur in our set of possible outcomes the same number of times. So our total number of possible outcomes must be divisible by 7.
25 isn’t evenly divisible by 7, but 21 is. So when we get one of the last 4 possible outcomes, we throw it out and roll again.
So we roll twice and translate the result into a unique outcome_number in the range 1..25. If the outcome_number is greater than 21, we throw it out and re-roll. If not, we mod by 7 (and add 1).
