I recently did a few hacker rank questions. No promises that these are ideal solutions, but this is my work below.

Problems

import big_o
import random
from typing import List, Tuple, Dict, Optional

Q1

Given the number of rows and columns for a grid, find the number of different paths when you can only move down or right assuming you start at the top left and finish at the bottom right.

Example: (7, 3) -> 28; (3,3) -> 6

def calc_matrix_paths(rows:int, columns:Optional[int]=None) -> int:
    if columns is None: columns = rows
    first_row, first_column = 0, 0
    count_matrix = [[0 for column in range(columns)] for row in range(rows)] 
    
    # r
    for row in range(rows): 
        count_matrix[row][first_column] = 1
    
    # c
    for column in range(columns): 
        count_matrix[first_row][column] = 1 
    
    # r*c
    for row in range(1, rows): 
        for column in range(1, columns):  
            count_matrix[row][column] = count_matrix[row-1][column] + count_matrix[row][column-1] 
            
    return count_matrix[rows-1][columns-1]   

cases = [
    (3, 3), # square matrix
    (7, 3), # non square matrix
]   
    
for rows, columns in cases:
    print(f"rows: {rows} | columns: {columns}")
    result = calc_matrix_paths(rows, columns)
    print(f"number of paths: {result}")

rows: 3 | columns: 3
number of paths: 6
rows: 7 | columns: 3
number of paths: 28

big_o.complexities.ALL_CLASSES

[big_o.complexities.Constant,
 big_o.complexities.Linear,
 big_o.complexities.Quadratic,
 big_o.complexities.Cubic,
 big_o.complexities.Polynomial,
 big_o.complexities.Logarithmic,
 big_o.complexities.Linearithmic,
 big_o.complexities.Exponential]

gen = lambda n: n
best, others = big_o.big_o(calc_matrix_paths, gen, min_n=2, max_n=5_000, n_measures=10, n_repeats=2)

print(f"predicted: {best}")
print()
for class_, residual in sorted(others.items(), key=lambda t: t[1], reverse=False):
    print(f"{class_} | {residual}")

predicted: Exponential: time = -3.2 * 0.002^n (sec)

Exponential: time = -3.2 * 0.002^n (sec) | 9.055977664509317
Polynomial: time = -7.5 * x^1.3 (sec) | 22.531114726371193
Cubic: time = -49 + 4.3E-09*n^3 (sec) | 56631.68144191306
Quadratic: time = -72 + 2E-05*n^2 (sec) | 101322.81044136792
Linearithmic: time = -1.1E+02 + 0.01*n*log(n) (sec) | 165159.6456644176
Linear: time = -1.1E+02 + 0.086*n (sec) | 176698.92796259583
Logarithmic: time = -1E+02 + 29*log(n) (sec) | 324034.55046488193
Constant: time = 1E+02 (sec) | 364452.09251446975

I wonder if the looping is that bad in python... Unless I'm missing something it looks like O(r*c) so should be polynomial time

Q2

Given an r x c grid, print all cells in spiral order

Example: [[1,2,3],[4,5,6],[7,8,9]] -> 1,2,3,6,9,8,7,4,5

def get_spiral_order(inp_matrix:List[List[int]]) -> List[int]:
    start_row = 0
    start_col = 0
    end_row = len(inp_matrix)
    end_col = len(inp_matrix[0])
    result = []

    while end_row > start_row and end_col > start_col:

        for item in inp_matrix[start_row][start_col: end_col]:
            result.append(item)

        for row in range(start_row+1, end_row):
            result.append(inp_matrix[row][end_col-1])
            
        for col in reversed(list(range(start_col, end_col-1))):
            result.append(inp_matrix[end_row-1][col])
            
        for i in reversed(list(range(start_row+1, end_row-1))):
            result.append(inp_matrix[i][start_col])
        
        start_col += 1
        start_row += 1
        end_col -= 1
        end_row -= 1
            
    return result
        
cases = [
    [[1,2,3],[4,5,6],[7,8,9]],
    [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]],
]

for case in cases:
    print(f"input matrix: {case}")
    spiral_order = get_spiral_order(case)
    print(f"spiral order: {spiral_order}")

input matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
spiral order: [1, 2, 3, 6, 9, 8, 7, 4, 5]
input matrix: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]
spiral order: [1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]

Q3

Scheduling Problem

You are tasked with creating an algorithm to determine the execution order of a set of tasks. This algorithm will be provided with a list of task labels and a list of task dependencies. Your algorithm should determine a valid execution order of the provided tasks. If there is no valid execution order your algorithm should return None.

Example 1:

labels = ['a', 'b', 'c', 'd', 'e']

where each element in "labels" represents a task label

dependencies = [('b', 'a'), ('c', 'a'), ('d', 'c')]

where each element tuple represents a task dependency in which the first element depends on the second

i.e. 'b' depends on 'a', 'c' depends on 'a', and 'd' depends on 'c'

In this case a valid execution order would be ['a', 'b', 'c', 'd']

another valid execution order could be ['a', 'c', 'b', 'd']

Example 2:

labels = ['a', 'b']

dependencies = [('b', 'a'), ('a', 'b')]

In this case there is no valid execution order so your algorithm should return None

from collections import defaultdict, deque

def make_dependency_graph(labels: List[str], dependencies: List[Tuple[str]]) -> Dict[str, List[str]]:
    graph = {}
    for l in labels:
        graph[l] = []
    for k, v in dependencies:
        deps = graph[k]
        deps.append(v)
    
    return graph


def get_execution_plan(nodes: List[str], graph: Dict[str, List[str]]) -> Optional[List[str]]:   
    to_visit, visited, checked = deque(labels), [], defaultdict(int)
    while to_visit:
        cur_place = to_visit.pop()
        checked[cur_place] += 1
        for dep_place in graph.get(cur_place): # dependencies
            if dep_place not in visited: 
                to_visit.append(cur_place)
                break
        else:
            visited.append(cur_place)
        if checked[cur_place] > 2:
            return None
            
    return visited
    
            
for labels, dependencies in [
    [['a', 'b', 'c', 'd', 'e'],
     [('a', 'e'), ('a', 'b'), ('b', 'c'), ('c', 'd')]],
    [['a', 'b'],
    [('b', 'a'), ('a', 'b')]],]:
    graph = make_dependency_graph(labels, dependencies)
    print(f"Dependency Graph: {graph}")

    visited = get_execution_plan(labels, graph) 
    print(f"Suggested Execution Plan: {visited}")

Dependency Graph: {'a': ['e', 'b'], 'b': ['c'], 'c': ['d'], 'd': [], 'e': []}
Suggested Execution Plan: ['e', 'd', 'c', 'b', 'a']
Dependency Graph: {'a': ['b'], 'b': ['a']}
Suggested Execution Plan: None