Mock Interviews: Four Company Simulations

01Phone Screen

Source notebook: Phone Screen.ipynb

Phone Screen

This phone screen will consist of a non-technical series of questions about you and the company, and then a second half of a simple technical question to be coded out

Non-Technical Questions

Answer the following questions (2-5 minute responses) technical answers not required, more interested in hearing about your reasoning

• Give me some quick background about you (go over your resume)
• Why do you want to work here?
• What's your favorite programming language and why?
• Where do you see yourself in 5 years?
• Do you have any questions about the company for me?

Solution

There aren't really any "correct" answers here, just make sure you're prepared to answer the following questions about the company you're interviewing with. Be honest, friendly and ready to defend any statements you make with logical arguments to back them up. Note, you should ALWAYS have follow-up questions.

Technical Questions

Answer the following question in the Markdown cell below. It's important to note that the cell below does NOT have syntax highlighting, its common in a phone screen interview to be given a text editor hich doesn't have anything more than basic text support

1. Write a function that computes the Nth fibonacci number

Solution

There's many ways to answer this question, you might be required to solve it multiple ways and discuss some pros and cons of each way. Listed below are various solutions

## Example 1: Using looping technique
def fib(n):
    
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a

print fib(7)
    
# Using recursion    
def fibR(n):
    if n==1 or n==2:
        return 1
    return fib(n-1)+fib(n-2)

print fibR(7)
 
## Example 3: Using generators
a,b = 0,1
def fibI():
    global a,b
    while True:
        a,b = b, a+b
        yield a
f=fibI()
f.next()
f.next()
f.next()
f.next()
f.next()
f.next()
print f.next()

 
## Example 4: Using memoization
def memoize(fn, arg):
    memo = {}
    if arg not in memo:
        memo[arg] = fn(arg)
    return memo[arg]
 
## fib() as written in example 1.
fibm = memoize(fib,7)
print fibm
 
## Example 5: Using memoization as decorator
class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, arg):
        if arg not in self.memo:
            self.memo[arg] = self.fn(arg)
            return self.memo[arg]
 
@Memoize
def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(7)

13
13
13
13
13

Below is a table depicting averaged relative performance time in seconds over 10 runs to caluclate the 15000th fibonacci number.

Good Job!

02On-Site Question 1

Source notebook: On-Site Question 1 - SOLUTION.ipynb

On-Site Question 1 - SOLUTION

Question

** Given a dice which rolls 1 to 7 (with uniform probability), simulate a 5 sided dice. Preferably, write your solution as a function. **

Requirements

** You MUST do this on pen and paper or on a whiteboard. No actual coding is allowed until you've solved it on pen and paper! **

SOLUTION

This is a new problem we haven't seen directly before! Many times this question is asked in the form of functions e.g. your given a function random_7() and you have to take it as an input and create random_5()

The key to solving this problem is to make sure you focus on the requirement that the final distribution of the rolls be uniform, also you were not given any requirements on Time and Space, so the solution is actually very simple, just keep re-rolling if you get a number greater than 5!

We can code this out:

from random import randint
 
def dice7():
    return randint(1, 7)
 
# Our Solution
def convert7to5():
    
    # Starting roll (just needs to be larger than 5)
    roll = 7
    
    while roll > 5:
        
        roll = dice7()
        print 'dice7() produced a roll of ',roll
    print ' Your final returned roll is below:'
    return roll

convert7to5()

dice7() produced a roll of  7
dice7() produced a roll of  5
 Your final returned roll is below:
5

Now, the next problem (On-Site Question 2) will be harder, the reverse conversion of rolls! This question should serve as a reminder not to overthink the solution to a question! Keep in mind that our solution has the potential to run for infinity if we keep rolling 6s and 7s (although this is highly unlikely).

Good Job!

03On-Site Question 2

Source notebook: On-Site Question 2 - SOLUTION.ipynb

On-Site Question 2 - SOLUTION

Question

** Given a dice which rolls from 1 to 5, simulate a uniform 7 sided dice! **

Requirements

** You MUST do this on pen and paper or on a whiteboard. No actual coding is allowed until you've come up with a solution by hand! **

SOLUTION

Because the 5 sided dice can not produce 7 possible outcomes on a single roll, we immediately know that we need to roll the dice at least twice.

If we roll the dice twice we have 25 possible combinations of the results of the two rolls. While 25 is not divisible by 7, 21 is. This means we can implement our previous strategy of throwing out rolls not in our intended range.

It's also important to note that we can't expand the solution to implement more rolls in order to not throw any out, because 5 and 7 are both prime which means that no exponent of 5 will be divisible by 7 no matter how high you go.

We will define our range as a section of the 25 possible combinations of rolls. A good way to do this is by converting the two rolls into a unique outcome number in the range 1 through 25.

We will create this number by taking the rolls, then we take the first roll and after subtracting 1 from it we multiply it by 5. Now the first roll corresponds with a value of 0, 5, 10, 15 and 20.

Then we take the second roll and add it to the result of the first manipulation. Giving us a range of 1-25.

So our final solution is to roll the dice twice. Check the manipulated range from 1 to 25, if its greater than 21, do a reroll. Let's see it in action:

from random import randint
 
def dice5():
    return randint(1, 5)

Now for our conversion function:

def convert5to7():

    # For constant re-roll purposes
    while True:

        # Roll the dice twice
        roll_1 = dice5()
        roll_2 = dice5()
        
        #print 'The rolls were {} and {}'.format(roll_1,roll_2)

        # Convert the combination to the range 1 to 25
        num = ( (roll_1-1) * 5 ) +  ( roll_2 ) 

        #print 'The converted range number was:',num
        if num > 21:

            # re-roll if we are out of range
            continue

        return num %7 + 1       

convert5to7()

2

Good Job!

04On-Site Question 3

Source notebook: On-Site Question 3 -SOLUTION.ipynb

On-Site Question 3 - SOLUTION

Question

**Given a string, write a function that uses recursion to reverse it. **

Requirements

** You MUST use pen and paper or a whiteboard to answer this, no coding allowed! **

SOLUTION

Hopefully you remember this problem, you've already seen it! The solution is:

def reverse(s):
    
    # Base Case
    if len(s) <= 1:
        return s

    # Recursion
    return reverse(s[1:]) + s[0]

Notes

Remember when recursion questions arise, think about the base case and the recursive case. Review the recusion section of the course for review for this problem.

Good Job!

05On-Site Question 4

Source notebook: On-Site Question 4 - SOLUTION.ipynb

On-Site Question 4 - SOLUTION

Question

Find the squareroot of a given number rounded down to the nearest integer, without using the sqrt function. For example, squareroot of a number between [9, 15] should return 3, and [16, 24] should be 4.

Requirements

** Feel free to code this out (but its recommended that you use paper/pencil or whiteboard)**

Solution

The squareroot of a (non-negative) number N always lies between 0 and N/2. The straightforward way to solve this problem would be to check every number k between 0 and N/2, until the square of k becomes greater than or rqual to N. If k^2 becomes equal to N, then we return k. Otherwise, we return k-1 because we're rounding down. Here's the code:

def solution(num): 
    if num<0: 
        raise ValueError 
    if num==1: 
        return 1 
    for k in range(1+(num/2)): 
        if k**2==num: 
            return k 
        elif k**2>num: 
            return k-1 
    return k  

solution(14)

3

solution(15)

3

solution(16)

4

The complexity of this approach is O(N), because we have to check N/2 numbers in the worst case. This linear algorithm is pretty inefficient, we can use some sort of binary search to speed it up. We know that the result is between 0 and N/2, so we can first try N/4 to see whether its square is less than, greater than, or equal to N. If it’s equal then we simply return that value. If it’s less, then we continue our search between N/4 and N/2. Otherwise if it’s greater, then we search between 0 and N/4. In both cases we reduce the potential range by half and continue, this is the logic of binary search. We’re not performing regular binary search though, it’s modified. We want to ensure that we stop at a number k, where k^2<=N but (k+1)^2>N. For example:

def better_solution(num): 
    if num<0: 
        raise ValueError 
    if num==1: 
        return 1 
    low=0 
    high=1+(num/2) 
    
    while low+1<high: 
        mid=low+(high-low)/2 
        square=mid**2 
        if square==num: 
            return mid 
        elif square<num: 
            low=mid 
        else: high=mid 
            
    return low

better_solution(14)

3

better_solution(15)

3

better_solution(16)

4

One difference from regular binary search is the condition of the while loop, it’s low+1<high instead of low<high. Also we have low=mid instead of low=mid+1, and high=mid instead of high=mid-1. These are the modifications we make to standard binary search. The complexity is still the same though, it’s logarithmic O(logN). Which is much better than the naive linear solution.

There’s also a constant time O(1) solution which involves a clever math trick. Here it is:

$$ \sqrt{N} = N^{0.5} = 2^{\log_2 N^{0.5}} = 2^{0.5 \log_2 N} $$

This solution exploits the property that if we take the exponent of the log of a number, the result doesn’t change, it’s still the number itself. So we can first calculate the log of a number, multiply with 0.5, take the exponent, and finally take the floor of that value to round it down. This way we can avoid using the sqrt function by using the log function. Logarithm of a number rounded down to the nearest integer can be calculated in constant time, by looking at the position of the leftmost 1 in the binary representation of the number. For example, the number 6 in binary is 110, and the leftmost 1 is at position 2 (starting from right counting from 0). So the logarithm of 6 rounded down is 2. This solution doesn’t always give the same result as above algorithms though, because of the rounding effects. And depending on the interviewer’s perspective this approach can be regarded as either very elegant and clever, or tricky and invalid. Either way, you should let your interviewer know that you are capable of the shortcut!

Good Job!

06Phone Screen

Source notebook: Phone Screen - SOLUTION.ipynb

Phone Screen - SOLUTION

Problem

A tower has 100 floors. You've been given two eggs. The eggs are strong enough that they can be dropped from a particular floor in the tower without breaking. You've been tasked to find the highest floor an egg can be dropped without breaking, in as few drops as possible. If an egg is dropped from above its target floor it will break. If it is dropped from that floor or below, it will be intact and you can test drop the egg again on another floor.

Show algorithmically how you would go about doing this in as few drops as possible

Requirements

** Use paper/pencil or a whiteboard for this problem **

Solution

** We've already seen this problem in the Riddles section, here is the answer from that section.(Alternatively just google "2 eggs 100 floors" for a plethora of explanations regarding this same solution **

Start from the 10th floor and go up to floors in multiples of 10.

If first egg breaks, say at 20th floor then you can check all the floors between 11th and 19th with the second egg to see which floor it will not break.

In this case, the worst-case number of drops is 19. If the threshold was 99th floor, then you would have to drop the first egg 10 times and the second egg 9 times in linear fashion.

Best solution: We need to minimize this worst-case number of drops. For that, we need to generalize the problem to have n floors. What would be the step value, for the first egg? Would it still be 10? Suppose we have 200 floors. Would the step value be still 10?

The point to note here is that we are trying to minimize the worst-case number of drops which happens if the threshold is at the highest floors. So, our steps should be of some value which reduces the number of drops of the first egg.

Let's assume we take some step value m initially. If every subsequent step is m-1, then, $$m+m−1+m−2+.....+1=n$$

This is

$$\frac{m∗(m+1)}{2}=n$$

If n =100, then m would be 13.65 which since we can't drop from a decimal of a floor, we actually use 14.

So, the worst case scenario is now when the threshold is in the first 14 floors with number of drops being 14.

Note that this is simply a binary search!

Good Job!

07On-Site Question 1

Source notebook: On-Site Question 1 - SOLUTION.ipynb

On-Site Question 1 - SOLUTION

Problem

** You've been given a list of historical stock prices for a single day for Amazon stock. The index of the list represents the timestamp, so the element at index of 0 is the initial price of the stock, the element at index 1 is the next recorded price of the stock for that day, etc. Your task is to write a function that will return the maximum profit possible from the purchase and sale of a single share of Amazon stock on that day. Keep in mind to try to make this as efficient as possible.**

For example, if you were given the list of stock prices:

prices = [12,11,15,3,10]

Then your function would return the maximum possible profit, which would be 7 (buying at 3 and selling at 10).

Requirements

** Try to solve this problem with paper/pencil first without using an IDE. Also keep in mind you should be able to come up with a better solution than just brute forcing every possible sale combination **

** Also you can't "short" a stock, you must buy before you sell the stock. **

Solution

Let's think about a few things before we start coding. One thing to think about right off the bat is that we can't just find the maximum price and the lowest price and then subtract the two, because the max could come before the min.

The brute force method would be to try every possible pair of price combinations, but this would be O(N^2), pretty bad. Also since this is an interview setting you should probably already know that there is a smarter solution.

In this case we will use a greedy algorithm approach. We will iterate through the list of stock prices while keeping track of our maximum profit.

That means for every price we will keep track of the lowest price so far and then check if we can get a better profit than our current max.

Let's see an implementation of this:

def profit(stock_prices):
    
    # Start minimum price marker at first price
    min_stock_price = stock_prices[0]
    
    # Start off with a profit of zero
    max_profit = 0
    
    for price in stock_prices:
        
        # Check to set the lowest stock price so far
        min_stock_price = min(min_stock_price,price)
        
        # Check the current price against our minimum for a profit 
        # comparison against the max_profit
        comparison_profit = price - min_stock_price
        
        # Compare against our max_profit so far
        max_profit = max(max_profit,comparison_profit)
        
    return max_profit

profit([10,12,14,12,13,11,8,7,6,13,23,45,11,10])

39

Currently we're finding the max profit in one pass O(n) and in constant space O(1). However, we still aren't thinking about any edge cases. For example, we need to address the following scenarios:

• Stock price always goes down
• If there's less than two stock prices in the list.

We can take care of the first scenario by returning a negative profit if the price decreases all day (that way we can know how much we lost). And the second issue can be solved with a quick len() check. Let's see the full solution:

def profit2(stock_prices):
    
    # Check length
    if len(stock_prices) < 2:
        raise Exception('Need at least two stock prices!')
    
    # Start minimum price marker at first price
    min_stock_price = stock_prices[0]
    
    # Start off with an initial max profit
    max_profit = stock_prices[1] - stock_prices[0]
    
    # Skip first index of 0
    for price in stock_prices[1:]:
        
        
        # NOTE THE REORDERING HERE DUE TO THE NEGATIVE PROFIT TRACKING
        
        # Check the current price against our minimum for a profit 
        # comparison against the max_profit
        comparison_profit = price - min_stock_price
        
        # Compare against our max_profit so far
        max_profit = max(max_profit,comparison_profit)
        
        # Check to set the lowest stock price so far
        min_stock_price = min(min_stock_price,price)
        
        
        
        
        
    return max_profit

# Exception Raised
profit2([1])

---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-11-7bd2f0c7e63b> in <module>()
      1 # Exception Raised
----> 2 profit2([1])

<ipython-input-10-e06adf3c45a7> in profit2(stock_prices)
      3     # Check length
      4     if len(stock_prices) < 2:
----> 5         raise Exception('Need at least two stock prices!')
      6 
      7     # Start minimum price marker at first price

Exception: Need at least two stock prices!

profit2([30,22,21,5])

-1

Great! Now we can prepare for worst case scenarios. Its important to keep edge cases in mind, especially if you are able to solve the original question fairly quickly.

Good Job!

08On-Site Question 2

Source notebook: On-Site Question 2 - SOLUTION.ipynb

On-Site Question 2 - SOLUTION

Problem

** Given a list of integers, write a function that will return a list, in which for each index the element will be the product of all the integers except for the element at that index **

**For example, an input of [1,2,3,4] would return [24,12,8,6] by performing [2×3×4,1×3×4,1×2×4,1×2×3] **

Requirements

** You can not use division in your answer! Meaning you can't simply multiply all the numbers and then divide by eahc element for each index!**

** Try to do this on a white board or with paper/pencil.**

Solution

If you look at the list above with the multiplication you'll notice we are repeating multiplications, such as 2 times 3 or 3 times 4 for multiple entries in the new list.

We'll want to take a greedy approach and keep track of these results for later re-use at other indices. We'll also need to think about what if a number is zero!

In order to find the products of all the integers (except for the integer at that index) we will actually go through our list twice in a greedy fashion.

On the first pass we will get the products of all the integers before each index, and then on the second pass we will go backwards to get the products of all the integers after each index.

Then we just need to multiply all the products before and after each index in order to get the final product answer!

Let's see this in action:

def index_prod(lst):
    
    # Create an empty output list
    output = [None] * len(lst)
    
    # Set initial product and index for greedy run forward
    product = 1
    i = 0
    
    while i < len(lst):
        
        # Set index as cumulative product
        output[i] = product
        
        # Cumulative product
        product *= lst[i]
        
        # Move forward
        i +=1
        
    
    # Now for our Greedy run Backwards
    product = 1
    
    # Start index at last (taking into account index 0)
    i = len(lst) - 1
    
    # Until the beginning of the list
    while i >=0:
        
        # Same operations as before, just backwards
        output[i] *= product
        product *= lst[i]
        i -= 1
        
    return output    

index_prod([1,2,3,4])

[24, 12, 8, 6]

index_prod([0,1,2,3,4])

[24, 0, 0, 0, 0]

Review the solution and make sure you understand it! It uses O(n) time and O(n) space complexity!

Good Job!

09On-Site Question 3

Source notebook: On-Site Question 3 - SOLUTION.ipynb

On-Site Question 3 - SOLUTION

Problem

Given two rectangles, determine if they overlap. The rectangles are defined as a Dictionary, for example:

r1 = {
    
         # x and y coordinates of the bottom-left corner of the rectangle
         'x': 2 , 'y': 4,
         
         # Width and Height of rectangle
         'w':5,'h':12}

** If the rectangles do overlap, return the dictionary which describes the overlapping section**

Requirements

** Make sure the dictionary you output is in the same form as the input.**

** Feel free to use an IDE for the code, but make sure you use paper/pencil or whiteboard to draw out your plan and logic**

Solution

This is a problem where it helps a lot to draw out your thinking. There are a few things we will need to think about:

• How can we determine an intersection?
• What if a rectangle is fully inside another rectangle?
• What if there is no intersection, but the rectangles share an edge?

The key to solving this problem is to break it up in to sub-problems. We can split up the problem into an x-axis problem and a y-axis problem.

We will create a function that can detect overlap in 1 dimension. Then we will split the rectangles into x and width, and y and height components. We can then determine that if there is overlap on both dimensions, then the rectangles themselves intersect!

In order to understand the calc_overlap function, draw out two flat lines and follow along with the function and notice how it detects an overlap!

Let's begin by creating a general function to detect overlap in a single dimension:

def calc_overlap(coor1,dim1,coor2,dim2):
    """
    Takes in 2 coordinates and their length in that dimension
    """
    
    # Find greater of the two coordinates
    # (this is either the point to the most right
    #  or the higher point, depending on the dimension)
    
    # The greater point would be the start of the overlap
    greater = max(coor1,coor2)
    
    # The lower point is the end of the overlap
    lower = min(coor1+dim1,coor2+dim2)
    
    # Return a tuple of Nones if there is no overlap
    
    if greater >= lower:
        return (None,None)
    
    # Otherwise, get the overlap length
    overlap = lower-greater
    
    return (greater,overlap)

Now let's use this function to detect if the rectangles overlap!

def calc_rect_overlap(r1,r2):
    
    
    x_overlap, w_overlap = calc_overlap(r1['x'],r1['w'],r2['x'],r2['w'])
    
    y_overlap, h_overlap = calc_overlap(r1['y'],r1['h'],r2['y'],r2['h'])
    
    # If either returned None tuples, then there is no overlap!
    if not w_overlap or not h_overlap:
        print 'There was no overlap!'
        return None
    
    # Otherwise return the dictionary format of the overlapping rectangle
    return { 'x':x_overlap,'y': y_overlap,'w':w_overlap,'h':h_overlap}

Our solution is O(1) for both time and space! Let's see it in action:

r1 = {'x': 2 , 'y': 4,'w':5,'h':12}
r2 = {'x': 1 , 'y': 5,'w':7,'h':14}
calc_rect_overlap(r1,r2)

{'h': 11, 'w': 5, 'x': 2, 'y': 5}

Make sure to review the answer and practice writing it out by hand!

Good Job!

10Phone Screen

Source notebook: Phone Screen - SOLUTION.ipynb

Phone Screen - SOLUTION

Problem

** Remove duplicate characters in a given string keeping only the first occurrences. For example, if the input is ‘tree traversal’ the output will be ‘tre avsl’. **

Requirements

Complete this problem on a text editor that does not have syntax highlighting, such as a goolge doc!

Solution

We need a data structure to keep track of the characters we have seen so far, which can perform efficient find operation. If the input is guaranteed to be in standard ASCII form, we can just create a boolean array of size 128 and perform lookups by accessing the index of the character’s ASCII value in constant time. But if the string is Unicode then we would need a much larger array of size more than 100K, which will be a waste since most of it would generally be unused.

Set data structure perfectly suits our purpose. It stores keys and provides constant time search for key existence. So, we’ll loop over the characters of the string, and at each iteration we’ll check whether we have seen the current character before by searching the set. If it’s in the set then it means we’ve seen it before, so we ignore it. Otherwise, we include it in the result and add it to the set to keep track for future reference. The code is easier to understand:

def removeDuplicates(string): 
    result=[] 
    seen=set() 
    
    for char in string: 
        if char not in seen: 
            seen.add(char) 
            result.append(char)
            
    return ''.join(result) 

The time complexity of the algorithm is O(N) where N is the number of characters in the input string, because set supports O(1) insert and find. This is an optimal solution to one of the most common string interview questions.

This problem should have felt very similar to some other array questions you've been asked! Remember that many basic interview question ideas overlap, just their presentation is different!

Good Job!

11On-Site Question 1

Source notebook: On-Site Question 1 - SOLUTION.ipynb

On-Site Question 1 - SOLUTION

Problem

** Given a list of integers and a target number, write a function that returns a boolean indicating if its possible to sum two integers from the list to reach the target number **

Requirements

** Try pen/paper before coding out your solution **

** You can not use an integer element twice. Optimize for time over space **

Solution

For this problem we will take advantage of a set data structure. We will make a single pass through the list of integers, treating each element as the first integer of our possible sum.

At each iteration we will check to see if there is a second integer which will allow us hit the target number, adn we will use a set to check if we've already seen it in our list.

We will then update our seen set by adding the current number in the iteration to it.

Let's see this coded out:

def solution(lst,target):
    
    # Create set to keep track of duplicates
    seen = set()
    
    # We want to find if there is a num2 that sums with num to reach the target
    
    for num in lst:
        
        num2 = target - num
        
        if num2 in seen:
            return True
        
        seen.add(num)
        
    # If we never find a pair match which creates the sum
    return False

solution([1,3,5,1,7],4)

True

solution([1,3,5,1,7],14)

False

Good Job!

12On-Site Question 2

Source notebook: On-Site Question 2 - SOLUTION.ipynb

On-Site Question 2 - SOLUTION

Problem

** Given a list of account ID numbers (integers) which contains duplicates , find the one unique integer. (the list is guaranteed to only have one unique (non-duplicated) integer **

Requirements

** Do not use built-in Python functions or methods **

Solution

This should feel very familiar to one of the problems we did in the array section of the course! We can use an XOR operation. The exclusive or operations will take two sets of bits and for each pair it will return a 1 value if one but not both of the bits is 1.

In Python we can use the ^ symbol to perform an XOR.

Now for our solution we can simply XOR all the integers in the list. We start with a unique id set to 0, then every time we XOR a new id from the list, it will change the bits. When we XOR with the same ID again, it will cancel out the earlier change.

By the end, we wil be left with the ID that was unique and only appeared once!

def solution(id_list):
    
    # Initiate unique Id
    unique_id = 0
    
    # XOR fo revery id in id list
    for i in id_list:
        
        # XOR operation
        unique_id ^= i
    
    return unique_id

Good Job!

13On-Site Question 3

Source notebook: On-Site Question 3 - SOLUTION.ipynb

On-Site Question 3 - SOLUTION

Problem

** Create a function that takes in a list of unsorted prices (integers) and a maximum possible price value, and return a sorted list of prices**

Requirements

** Your function should be able to perform this in less than O(nlogn) time. **

Solution

We can actually solve this problem by using a counting sort. Basically a counting sort works well when you know the range of integer values you will have ahead of time.

Read the wikipedia article linked above for a full break down, and an implementation is here below (using the prices situation described in the problem above).

def solution(unsorted_prices,max_price):
    
    # list of 0s at indices 0 to max_price
    prices_to_counts = [0]* (max_price+1)
    
    # populate prices
    for price in unsorted_prices:
        prices_to_counts[price] +=1
        
    # populate final sorted prices
    sorted_prices = []
    
    # For each price in prices_to_counts
    for price,count in enumerate(prices_to_counts):
        
        # for the number of times the element occurs
        for time in range(count):
            
            # add it to the sorted price list
            sorted_prices.append(price)
            
    return sorted_prices

solution([4,6,2,7,3,8,9],9)

[2, 3, 4, 6, 7, 8, 9]

This was a great exercise in learning about a new sorting algorithm, make sure to read up on it and practice this problem again!

Good Job!

14Phone Screen

Source notebook: Phone Screen - SOLUTION.ipynb

Phone Screen - SOLUTION

Problem

** If you were given a list of n integers and knew that they were sorted, how quickly could you check if a given integer was in the list? Elaborate on your reasoning and search methods in general**

Requirements

** Try explaining your solution to someone and see if it makes sense ot them. Don't code anything for this problem **

Solution

Hopefully this problem sounds familiar! We can use a binary search to search for an intger since the list is already sorted! This means we can find the item in O(logn) time and O(1) space!

Revisit the lectures on Binary Search and its implementation to fully get the reasoning behind this solution and problem!

Good Job!

15On-Site Question 1

Source notebook: On-Site Question 1 - SOLUTION.ipynb

On-Site Question 1 - SOLUTION

Problem

** Given a list of integers, find the largest product you could make from 3 integers in the list **

Requirements

** You can assume that the list will always have at least 3 integers **

** Paper/pencil only, don't code this out until you've solved it as far as you can by hand. **

Solution

We can solve this problem in O(n) time with O(1) space, we should also be able to take into account negative numbers, so that a list like: [-5,-5,1,3] returns (-5)(-5)(3) = 75 as its answer.

Hopefully you've begun to realize the similarity between this problem and the Amazon stock problem from the E-Commerce Company mock interview questions! You could brute force this problem by just simply trying every single combination of three digits, but this would require O(n^3) time!

How about we use a greedy approach and keep track of some numbers. In the stock problem we kept track of max profit so far, in this problem we are actually going to keep track of several numbers:

• The highest product of 3 numbers so far
• The highest product of 2 numbers so far
• The highest number so far

Since we want to keep negative numbers in account, we will also keep track of the lowest product of two and the lowest number:

• The lowest product of 2
• The lowest number

Once we iterate through the list and reach the end we will have the highest posiible product with 3 numbers. At each iteration we will take the current highest product of 3 and compare it to the current integer multiplied by the highest and lowest products of 2.

Let's see this coded out:

def solution(lst):
    
    # Start at index 2 (3rd element) and assign highest and lowest 
    # based off of first two elements
    
    # Highest Number so far
    high = max(lst[0],lst[1])
    
    # Lowest number so far
    low = min(lst[0],lst[1])
    
    # Initiate Highest and lowest products of two numbers
    high_prod2 = lst[0]*lst[1]
    low_prod2 = lst[0]*lst[1]
    
    # Initiate highest product of 3 numbers
    high_prod3 = lst[0]*lst[1]*lst[2]
    
    # Iterate through list
    for num in lst[2:]:
        
        # Compare possible highest product of 3 numbers
        high_prod3 = max(high_prod3,num*high_prod2,num*low_prod2)
        
        
        # Check for possible new highest products of 2 numbers
        high_prod2 = max(high_prod2,num*high,num*low)
        
        # Check for possible new lowest products of 2 numbers
        low_prod2 = min(low_prod2,num*high,num*low)
        
        # Check for new possible high
        high = max(high,num)
        
        # Check for new possible low
        low = min(low,num)
        
    return high_prod3

l = [99,-82,82,40,75,-24,39, -82, 5, 30, -25, -94, 93, -23, 48, 50, 49,-81,41,63]

solution(l)

763092

Great! Through the use of a greedy approach we have been able to complete the problem in O(n) time. Keep this sort of approach in mind when you have to iterate through a list and a brute force solution is on the order of an exponential!

Good Job!

16On-Site Question 2

Source notebook: On-Site Question 2 - SOLUTION.ipynb

On-Site Question 2 - SOLUTION

Problem

** Write a function that given a target amount of money and a list of possible coin denominations, returns the number of ways to make change for the target amount using the coin denominations**

Requirements

** Write out your work on paper/pencil, then see if you can code up your solution **

Solution

This is a classic interview problem, so classic that you've already seen a very similar problem in the recursion section! Make sure to review that problem first before reading our solution here!

In this solution we will use a bottom-up algorithm.

• As we iterate through each coin, we are adding the ways of making arr[i - coin] to arr[i]
• If we have 2 ways of making 4, and are now iterating on a coin of value 3, there should be 2 ways of making 7.
• We are essentially adding the coin we are iterating on to the number of ways of making arr[i].

def solution(n, coins):
    
    # Set up our array for trakcing results
    arr = [1] + [0] * n
    
    for coin in coins:
        for i in range(coin, n + 1):
            arr[i] += arr[i - coin]
            
    if n == 0:
        return 0
    else:
        return arr[n]
    

solution(100, [1, 2, 3])

884

This solution results in O((m)(n)) with m being the number of coins, where we iterate about n operations. This is O(n) space.

Good Job!

17On-Site Question 3

Source notebook: On-Site Question 3 - SOLUTION.ipynb

On-Site Question 3 - SOLUTION

Problem

** Given a binary tree, check whether it’s a binary search tree or not. **

Requirements

** Use paper/pencil, do not code this in an IDE until you've done it manually**

** Do not use built-in Python libraries to do this, but do mention them if you know about them **

Solution

The first solution that comes to mind is, at every node check whether its value is larger than or equal to its left child and smaller than or equal to its right child (assuming equals can appear at either left or right). However, this approach is erroneous because it doesn’t check whether a node violates any condition with its grandparent or any of its ancestors.

So, we should keep track of the minimum and maximum values a node can take. And at each node we will check whether its value is between the min and max values it’s allowed to take. The root can take any value between negative infinity and positive infinity. At any node, its left child should be smaller than or equal than its own value, and similarly the right child should be larger than or equal to. So during recursion, we send the current value as the new max to our left child and send the min as it is without changing. And to the right child, we send the current value as the new min and send the max without changing.

class Node: 
    def __init__(self, val=None): 
        self.left, self.right, self.val = None, None, val   
        
INFINITY = float("infinity") 
NEG_INFINITY = float("-infinity")  

def isBST(tree, minVal=NEG_INFINITY, maxVal=INFINITY): 
    if tree is None:
        return True   
    if not minVal <= tree.val <= maxVal: 
        return False   
    
    return isBST(tree.left, minVal, tree.val) and isBST(tree.right, tree.val, maxVal) 

There’s an equally good alternative solution. If a tree is a binary search tree, then traversing the tree inorder should lead to sorted order of the values in the tree. So, we can perform an inorder traversal and check whether the node values are sorted or not.

def isBST2(tree, lastNode=[NEG_INFINITY]): 
    
    if tree is None: 
        return True   
    
    if not isBST2(tree.left, lastNode):
        return False   
    
    if tree.val < lastNode[0]: 
        return False   
    
    lastNode[0]=tree.val   
    
    return isBST2(tree.right, lastNode) 

This is a common interview problem, its relatively simple, but not trivial and shows that someone has a knowledge of binary search trees and tree traversals.

Good Job!