lopespm

# https://stackoverflow.com/a/34435207/1765893
git rm -r --cached .
git add .
git commit -m "Remove all ignored files in .gitignore"

lopespm

# This solution to compute a random subset avoids the use of extra auxiliary space, with O(k + n) time complexity and O(1) space complexity, in Python (5.15 Compute a random subset, on EPI (Elements of Programming Interviews)) (September 2018 edition)).
# The idea here is to pick the r-th combination, and find its constituents by incrementing them in a Odometer like fashion, and taking into account that the next digit in the combination will be greater than the previous one.
# For example, the combination sequence for n=5 and k=2 is:
# 0 - [0,1]
# 1 - [0,2]
# 2 - [0,3]
# 3 - [0,4]
# 4 - [1,2]
# 5 - [1,3]
# 6 - [1,4]

lopespm

# Alternative python solution for 9.12 Reconstruct a binary tree from a preorder traversal with markers on EPI (Elements of Programming Interviews)) (September 2018 edition)
# Time complexity: O(n)
# Space complexity: O(n + h) - the size of the hash table plus the maximum depth of the function call stack

class BstNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
    def __repr__(self):

lopespm

# Alternative python solution for 5.17 The Sudoku Check Problem on EPI (Elements of Programming Interviews)) (September 2018 edition)
# For an nxn Sudoku grid:
# Time complexity: O(n^2)
# Space complexity: O(n)

from typing import List
import math

from typing import List, Set
import math

lopespm

# (Variant #4 for exercise 16.2 on EPI (Elements of Programming Interviews)) (September 2018 edition)
# The core idea is calculate the levenshtein distance, while taking into account the special cases of the regex expression
# *, +, ? and . were taken into account for the regex expression. Expression blocks are not supported
# This algorithm uses dynamic programming, yielding a O(mn) time complexity, O(m) auxiliary space for cache
# (m and n are the lengths of regex and target strings respectively)
#
# Version using recursion with memoization: https://gist.github.com/lopespm/53a215d0b2b0518b52b6bb6687bdaff6

def regex_dist(regex: str, target: str):

lopespm

# (Variant #4 for exercise 16.2 on EPI (Elements of Programming Interviews)) (September 2018 edition)
# The core idea is calculate the levenshtein distance, while taking into account the special cases of the regex expression
# *, +, ? and . were taken into account for the regex expression. Expression blocks are not supported
# This algorithm uses recursion with memoization (could be transposed to a DP solution), yielding a O(mn) time complexity, O(mn) auxiliary space for cache and O(max(m,n)) function call stack
# (m and n are the lengths of regex and target strings respectively)
#
# Version using dynamic programming: https://gist.github.com/lopespm/2362a77e7bd230a4622a43709c195826

def regex_dist(regex: str, target: str):
    def regex_dist_aux(r_i, t_i):

lopespm

# (Variant #6 for exercise 5.18 on EPI (Elements of Programming Interviews)) (September 2018 edition)
# Consider a 10x7 (mxn) matrix, in which we get 30 elements for the the outer ring, the next outer ring would have 22 elements, then 14 elements, and the most inner ring has the remaining elements. The number of elements per ring is given by 2 x (m - (1 + (2 x (r-1) ))) + 2 x (n - (1 + (2 x (r-1) ))), for the rth ring.
# Save from the most inner ring, the difference between the number of elements of each adjacent ring is 8 elements. If we want to know the number of elements of the current ring plus all the other previous ones, we get an arithmetic series (https://en.wikipedia.org/wiki/Arithmetic_progression#Sum).
# The sum of all the elements until a given r is given by sum = (r(a1 + ar)) / 2, being a1 = 2(m-1) + 2(n-1), ar = 2 x (m - (1 + (2 x (r-1) ))) + 2 x (n - (1 + (2 x (r-1) ))). If we solve the equation in relation to r, using the quadratic formula to disentangle the final polynomial, we reach r = mat

lopespm

# Print tree by levels - using BFS
# The idea behind it is to use BFS and keep a level marker integer which marks the end the last node of the level. This is similar to Naresh's sentinel approach, but without the need of inserting a sentinel inside the queue, since this is accomplished by the level marker.
# Time complexity of O(n)
# Space complexity: O(2^tree_height)

from collections import deque

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data

lopespm

Keybase proof

I hereby claim:

• I am lopespm on github.
• I am lopespm (https://keybase.io/lopespm) on keybase.
• I have a public key ASBVOGTQ7FFo3e2z4-HGjCwpsxKjqroop4en_wFUDWevBwo

To claim this, I am signing this object:

lopespm

# (Variant #4 for exercise 11.1 on EPI (Elements of Programming Interviews))
# The rationale behind it to perform a binary search which only considers a given character index of the strings.
# If these are present, continue to the next character index. If any of the prefix characters cannot be found in any string, return immediatly
# Considering n strings and k prefix length:
#    Time complexity: O(k * log(n))
#    Space complexity: O(1)

from typing import List

def first(items: List[str], prefix: str, i: int, c: str, left: int, right: int):