Instantly share code, notes, and snippets.

# Pedro Lopeslopespm

• Sort options
Created Jun 19, 2019
Compute a random subset - Python
View random_subset.py
 # 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]
Created May 10, 2019
Reconstruct a binary tree from a preorder traversal with markers - Alternative Solution (Python)
View binary_tree_from_preorder_inorder.py
 # 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):
Last active May 6, 2019
The Sudoku Check Problem - Alternative Solution (Python)
View is_valid_sudoku.py
 # 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
Last active May 1, 2019
Levenshtein distance between regex expression and target string - Dynamic Programming (Python)
View levenshtein_regex_dp.py
 # (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):
Last active May 1, 2019
Levenshtein distance between regex expression and target string - Recursion with memoization (Python)
View levenshtein_regex_recursion_memo.py
 # (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):
Last active Apr 17, 2019
Compute the kth element in spiral order for an m x n 2D array in O(1) time (Python)
View kth_element_spiral.py
 # (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
Created Apr 6, 2019
Prints a given tree in levels, using BFS - using Python
View print_levels_tree.py
 # 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
Created Apr 4, 2019
View keybase.md

### 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:

Created Apr 1, 2019
Test if prefix is present in an array of sorted strings problem (Python)
View is_prefix_in_strings.py
 # (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):
Last active Mar 28, 2019
Dutch national flag problem: four colors - in Python
View dutch_flag_four_colors.py
 # (Variant for exercise 5.1 on EPI (Elements of Programming Interviews)) # The rationale behind it is to squeeze the forth color (middle right color) in between the middle left and right sub-arrays. It defines the colors as the algorithm progresses. # It has a O(n) time complexity and O(1) space complexity from typing import List def dutch_variant_four_colors(array: List[int]) -> List[int]: left = array[0] mid_left = None right = None
You can’t perform that action at this time.