Shaunwei’s gists

Shaunwei / subsetsum_constraints.py

Last active January 25, 2016 04:12

Given an array, try to divide them into two subsets, which makes two subsets sum equal. Constraints: values divisible by 3 and values divisible by 5 should be separated. Values that divisible by 3 and 5 should be in the divisible 5 subset.

	class Solution:
	def find_equal_subsets(self, arr):
	"""
	@param: arr: List[str]
	@return: Tuple
	"""
	total = sum(arr)
	# if half subsets value exist
	if total % 2 != 0:
	return

Shaunwei / interval_minimum_number.py

Created January 22, 2016 06:20

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

	class SegmentTreeNode:
	def __init__(self, st, ed, mval):
	self.st = st
	self.ed = ed
	self.min = mval

	class SegmentTree:
	def __init__(self, arr):
	if not arr:
	raise 'Empty input array'

Shaunwei / binary_search_tree.py

Last active January 20, 2016 09:32

Binary Search Tree: range search operation and delete one node operation

	"""
	Definition of TreeNode:
	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left, self.right = None, None
	"""
	class Solution:
	"""
	@param root: The root of the binary search tree.

Shaunwei / tree_traversal.py

Last active January 20, 2016 07:47

Binary Tree iterative ordering traversal: preorder, postorder, inorder

	"""
	Definition of TreeNode:
	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left, self.right = None, None
	"""


	class Solution:

Shaunwei / binary_tree_level_order_traversal.py

Created January 20, 2016 07:31

Binary Tree Level Order Traversal. Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

	"""
	Definition of TreeNode:
	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left, self.right = None, None
	"""
	import collections

Shaunwei / general_trees2binary_trees.py

Created January 20, 2016 07:26

Encoding general trees as binary trees. There is a one-to-one mapping between general ordered trees and binary trees, which in particular is used by Lisp to represent general ordered trees as binary trees.

	class TreeNode:
	def __init__(self, label):
	self.label = label
	self.childrens = []
	self.sibling = None

	def __str__(self):
	return 'Tree[' + str(self.label) + ']'

	class BinaryTreeNode:

Shaunwei / mergesort_quicksort.py

Created January 19, 2016 08:20

Algorithm Post: Divide and Conquer - Merge Sort and Quick Sort

	class QuickSort:
	def sort(self, arr):
	self.qsort(arr, 0, len(arr) - 1)
	return arr

	def qsort(self, arr, st, ed):
	if st >= ed:
	return

	index = self.partition(arr, st, ed)

Shaunwei / lowest_common_ancestor.py

Created January 19, 2016 07:13

Algorithm Post: Divide and Conquer - Lowest Common Ancestor

	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left = self.right = None
	def __str__(self):
	return '[' + str(self.val) + ']'

	class LCA:
	def find_lca(self, root, A, B):
	if not root:

Shaunwei / search_for_a_range.py

Created January 19, 2016 06:10

Algorithm Post: Binary Search - Search for a range

	class BinarySearch:
	@staticmethod
	def find_first_position(arr, target):
	st, ed = 0, len(arr) - 1
	while st + 1 < ed:
	mid = (st + ed) / 2
	if arr[mid] == target:
	ed = mid
	elif arr[mid] < target:
	st = mid

Shaunwei / failure_chars_detection.py

Last active January 15, 2016 00:12

File encoding issue with chardet library. A few characters '{', '}', '~' with several combinations will cause chardet to fail. Find out who are the bad guys!! For fancy looks, I used colorclass and terminaltables.

	#!/usr/bin/env python3
	import chardet
	from colorclass import Color
	from terminaltables import AsciiTable


	def generate_test(chars_list):
	table_data = [['Chars', 'Confidence', 'Encoding', 'Issue'], ]
	for chars in chars_list:
	result = chardet.detect(chars.encode('utf-8'))

shaun Shaunwei