Math & Stats Strategies

Question 1

Find kth Permutation

Given a set of n elements, find their kth permutation.

Answer 1

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

Question 2

Integer Division

Given two integers: x and y; return x ÷ y without using ‘/’ (division) or ‘*’ (multiplication) operators. Assume that both integers are positive.

Answer 2

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.

Question 3

Pythagorean Triplets

Given an integer array, find all Pythagorean triplets (a² + b² = c²).

Answer 3

Quadratic O(n²) 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 a² + b² = c².

• Sort the list of integers.
• Iterate the list from start to end. Select the current element as c².
  
  • In order to find the other two elements (a²+b² = c²), 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: a²+b² + (-c²) = 0.
  • a² = list[start] * list[start]
  • b² = list[end] * list[end]
  • If the current values of start & end iterators make such a triplet, we’ll save it.
  • If a²+b² + (-c²) > 0, we’ll decrement the end iterator in hope of hitting the target sum. Remember, (list[start] <= list[end]).
  • If a²+b² + (-c²) < 0, we’ll increment the start iterator.

Question 4

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.

Answer 4

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.

Question 5

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.

Answer 5

Linear Runtime, Constant Memory

Here are the steps to find the missing number.

1. Find the sum ‘sum_of_elements’ of all the numbers in the array. This would require a linear scan, O(n).
2. Then find the sum ‘expected_sum’ of first ‘n’ numbers using the arithmetic series sum formula i.e. ( n * (n + 1) ) / 2.
3. The difference between these i.e. ‘expected_sum - sum_of_elements’, is the missing number in the array.

Question 6

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

Answer 6

factorial, O(n!) runtime, factorial O(n!) memory (because it’s recursive)

Question 7

All Subsets

We are given a set of integers and we have to find all the possible subsets of this set of integers.

Answer 7

Exponential runtime, O(2ⁿ * n) - where ‘n’ is number of integers in the given set. Exponential O(2ⁿ * 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

Question 8

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)

Answer 8

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 (x₁, y₁) and (x₂, y₂) then their slope will be (y₂ - y₁) / (x₂ - x₁) which can be a double value and can cause precision problems. To get rid of the precision problems, we treat slope as pair ((y₂ - y₁), (x₂ - x₁)) 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.

Question 9

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.

Answer 9

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.

Question 10

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

Answer 10

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)

Question 11

Calculate Square Root

Given a double number, write a function to calculate its square root.

Answer 11

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)

Question 12

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.

Answer 12

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:

1. 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.
2. 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.

Question 13

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.

Answer 13

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

Question 14

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.

Answer 14

We simply “re-roll” whenever we get a number greater than 5.

Question 15

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.

Answer 15

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