Skip to content

Instantly share code, notes, and snippets.

Sümer Cip sumerc

Block or report user

Report or block sumerc

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
@sumerc
sumerc / union_find_by_rank.py
Last active May 2, 2019
UnionFind data structure - (by rank) (Inspired from networkx.utils.unionfind)
View union_find_by_rank.py
"""
Inspired from the great Graph lib.: networkx.utils.unionfind
The one implemented in networkx was union by weight and implicitly adds element upon __getitem__. I changed it to union-by-rank and
have a add() call equivalent to the make_set() call in the original data structure.
to_sets() changed a bit too to remove dependency to networkx.
Other than above most of the code is same.
"""
@sumerc
sumerc / gist:74ebc1002d407109f1be82ecfd20b095
Last active Jul 16, 2018
O(lgN) weighted random python
View gist:74ebc1002d407109f1be82ecfd20b095
import random
from bisect import bisect
class WeightedRandom2(object):
def __init__(self, weights):
# init interval tree
self._psum = []
self._wsum = 0
for k,v in weights.items():
assert v > 0, "weight must be a positive integer"
@sumerc
sumerc / topcoder_q.py
Last active Aug 29, 2015
TopCoder Problems
View topcoder_q.py
# Solution of Level 1 ZigZag Problem. (http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493)
def zigzag(a):
if len(a) <= 1: return 1
result = 1
prev_diff = 0
for i in range(len(a)-1):
diff = a[i+1] - a[i]
if diff == 0:
continue
@sumerc
sumerc / interview_q1.py
Last active Jun 4, 2018
A Microsoft Interview Question
View interview_q1.py
# Q: Given an array of numbers, shift 0 and 1 numbers to the end of the array without changing the orders.
# Example:
# input = [912, 92, 0, 1, 1, 3, 0, 7]
# output = [912, 92, 3, 7, 0, 1, 1, 0]
# This, BTW, is a tough problem. All the inplace(0(1) space) solutions have O(n^2) time complexity below. But have a
# hard logarithmic solution. You can see this Quora thread for details on this:
# http://www.quora.com/What-algorithms-move-all-negative-numbers-before-positive-numbers-and-preserve-their-original-orders-at-the-same-time-O-n-time-and-O-1-space-are-required
def d(a):
@sumerc
sumerc / interview_q2.py
Last active Aug 29, 2015
A Twitter Interview Question
View interview_q2.py
# Python solution for https://qandwhat.runkite.com/i-failed-a-twitter-interview/
# Actually the original implementation is as following which is done in n-pass:
def water_vol_orig(a):
lv = rv = -1
result = lmax = rmax = l = 0
r = len(a)-1 # no pass on array
while (l < r):
lv = a[l]
if lv > lmax:
You can’t perform that action at this time.