Source notebook: algo14_misc_time_permits.ipynb

MISCELLANEOUS (FROM UDEMY MOCK INTERVIEWS)

E-Commerce Company

Problem 1

** 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

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]

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}

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!

Search Engine

Question 1

Given a dice which rolls 1 to 7 (uniform probability), simulate a 5 sided dice. In other words, your given a function random_7() and you have to take it as an input and create random_5()

Focus on requirement: final distribution should be uniform; no Time and Space reqs - very simple solution - keep re-rolling if you get a number greater than 5!

from random import randint
 
def dice7():
    return randint(1, 7)

def dice5():
    
    # Starting roll (just needs to be larger than 5)
    roll = 7
    
    while roll > 5:
        
        roll = dice7()
        print('\tdice7() produced a roll of ', roll)
    print('Your dice5() returned roll is:', end=' ')
    return roll

dice5()

	dice7() produced a roll of  7
	dice7() produced a roll of  1
Your dice5() returned roll is: 1

Question 2

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

SOLUTION: Check the manipulated range from 1 to 25, if it's less than 22 => remainder divide by 7, if greater than 21 => reroll
Explanation: 25 possible combinations for two rolls (can't use 1 roll as it's less than 7). 25 is not divisible by 7, 21 is. Using more than 2 rolls doen'st make sense because 5 and 7 are primes => no exponent of 5 will be divisible by 7.
Start by converting two rolls into a unique outcome number in range(1, 25): a) take first roll, subtract 1, multiply by 5 => [0, 5, 10, 15 and 20]; b) add second roll to the result => range(1-25)

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

def dice7():
    
    while True:                                                      # constant re-roll until return
        
        roll_1 = dice5()
        roll_2 = dice5()        
        print('The rolls were {} and {}'.format(roll_1,roll_2))
       
        num = ( (roll_1-1) * 5 ) +  ( roll_2 )                       # convert to range(1, 25)
        print('The converted range number was:',num)
        
        if num > 21:                                                 # re-roll if out of range
            continue

        return num % 7 + 1
        
dice7()

The rolls were 4 and 4
The converted range number was: 19
6

Question 3

Recursive string reversal

def reverse(s):    
    
    if len(s) <= 1:                        # base case
        return s
    
    #return reverse(s[1:]) + s[0]          # recursion
    return s[-1] + reverse(s[:-1])         # recursion (either one works)

reverse('abyrvalg')

'glavryba'

Question 4

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

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

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

print(solution(14))
print(solution(15))
print(solution(16))

3
3
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

print(solution(14))
print(solution(15))
print(solution(16))

3
3
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!

Question 5

Write a function for Nth fibonacci number

# LOOPING
def fib(n):
    
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a

print('Looping:', fib(11))
    
# RECURSION
def fibR(n):
    if n==1 or n==2:
        return 1
    return fib(n-1)+fib(n-2)

print('Recursion:', fibR(11))
 
# GENERATORS
a,b = 0,1
def fibI():
    global a,b
    while True:
        a,b = b, a+b
        yield a
f=fibI()
for i in range(10):
    f.__next__()
print('Generators:', f.__next__())

 
# MEMOIZATION
def memoize(fn, arg):
    memo = {}
    if arg not in memo:
        memo[arg] = fn(arg)
    return memo[arg]
 
## fib() for looping
fibm = memoize(fib, 11)
print('Memoization:', fibm)
 
# MEMOIZATION AS DECORATROR
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('Memoization as decorator:', fib(11))

Looping: 89
Recursion: 89
Generators: 89
Memoization: 89
Memoization as decorator: 89

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

Ride Share

Question 1

Given list int, find largest product of 3 int from list The list will always have at least 3 integers **

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

Question 2

Given a target amount of money and a list of possible coin denominations, returns the number of ALL possible ways to make change

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

Question 3

Given a binary tree, confir it's a BST (no buil-in libs)

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) 

Question 4

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?

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!

Social Network

Question 1

Given list of int and target number, write f(x) returning bool == its possible to sum two int from list to get target number (cannot use an int element twice; optimize for time over space)

SOLUTION: use set, make single pass, treating each list elem as first int of possible sum, check if there is a second int to hit the target sum - use set to check if we've already seen it, add current num to seen set

def solution(lst,target):    
    
    seen = set()                                  # keep track of duplicates   
    
    for num in lst:                               # find if num2 + num = target
        
        num2 = target - num
        
        if num2 in seen:
            return True
        
        seen.add(num)        
   
    return False                                  # if there is no match

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

True
False

Question 3

Write f(x) that takes list of unsorted int and max int and returns sorted list int (O(nlogn) time)
SOLUTION: use counting sort - works well if u know range of int in advance

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


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

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

Question 4

Keeping only first occurrences of every char in a string (removing duplicates). E. g. 'tree traversal' => 'tre avsl'
SOLUTION: need a data structure to keep track of chars seen and efficient search (array of size 128 for ASCII, but 100K for Unicode - inefficient for a few chars). Set perfectly suits the purpose - constant time search

O(n) time complexity where n = len(string) because set supports O(1) to insert and find => optimal solution. Similar to some other array questions

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


remove_duplicates('tree traversal')

'tre avsl'

REFERENCES

Google Interview Questions (Geekstogeeks)

General: https://www.geeksforgeeks.org/google-interview-preparation/
More coding challanges from Google: https://practice.geeksforgeeks.org/explore/?company%5B%5D=Google&page=1

Source notebook: dm_coding_interview_question.ipynb

# There is a self-driving car in the middle lane at the beginning of a 3-lane, 1000 unit long highway. Along the road, there are some obstacles (marked "O") and refueling stops (marked "F"). If the car overlaps an obstacle, it crashes and cannot continue. If it chooses to use a refueling stop, it adds 50 units of fuel (the car has a tank capable of holding 100 units of fuel, and it starts with 50 units).
# The car has a very limited memory. It can accept a string of 10 characters, which can be D, R, L, or F. The letter D instructs the car to drive forward 1 unit, the letters R or L will shift the car to the right or left without moving forward. All these consume 1 unit of fuel. The letter F causes the car to attempt to refuel, this only succeeds if it is currently on a refueling stop. This does not consume any fuel. The car continuously loops over this string of 10 commands, until it reaches the end, crashes, or runs out of fuel.
# Find a string of 10 characters that brings the car to the end of the road the fastest. It is guaranteed that it is possible to find such a string.

# matrix 3 x 1000
# each cell "O", "F" or "." (OKdef)

# def optimize(matrix) -> command_string

def simulate(command, roadmap) -> bool:

    lane = 1
    position = 0
    fuel = 50
    count = 10000

    for i in range(count):
        c = command[i%10]
        if fuel <= 0:
            return False, count
        if c=='D':
            position += 1
            fuel -= 1
        elif c=='R':
            lane += 1
            if lane > 2:
                return False, count
        elif c=='L':
            lane -= 1
            if lane < 0:
                return False, count
        elif c=='F':
            if roadmap[lane][position]=='F':
                fuel = min(fuel+50, 100)

        if position >= len(roadmap[0]):
            return True, count

        if roadmap[lane][position]=='O':
            return False, count

    return False, count


def optimize(roadmap) -> str:
    
    import itertools

    directions = ['D', 'R', 'L', 'F']

    res = []

    for command_string in itertools.product(directions, repeat=10):
        success, count = simulate(command_string, roadmap)
        if success:
            res.append((count, success, command_string))

    if res:
        res = sorted(res, labmda x: key=x[0])
        return res[0][2]


def optimize_bfs(roadmap):
    directions = ['D', 'R', 'L', 'F']
    queue = [ ((0,0,50), '')]
    visited = set()

    while queue:
        (lane, position, fuel), commamd = queue.pop(0)
        if position == len(roadmap[0]-1):
            return command

        for d in directions:
            # iterate
            new_position
            new_lane
            new_fuel
            new_command
            visited
            queue