Skip to content

Instantly share code, notes, and snippets.

Pedro Lopes lopespm

Block or report user

Report or block lopespm

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@lopespm
lopespm / random_subset.py
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]
@lopespm
lopespm / binary_tree_from_preorder_inorder.py
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):
@lopespm
lopespm / is_valid_sudoku.py
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
@lopespm
lopespm / levenshtein_regex_dp.py
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):
@lopespm
lopespm / levenshtein_regex_recursion_memo.py
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):
@lopespm
lopespm / kth_element_spiral.py
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
@lopespm
lopespm / print_levels_tree.py
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
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:

@lopespm
lopespm / is_prefix_in_strings.py
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):
@lopespm
lopespm / dutch_flag_four_colors.py
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.