Skip to content

Instantly share code, notes, and snippets.

Avatar

Sümer Cip sumerc

View GitHub Profile
@sumerc
sumerc / profile_clocks.c
Last active Jan 16, 2020
profile different clock types - Linux
View profile_clocks.c
#include "time.h"
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
# include <sys/resource.h>
struct timeval curtime;
struct timespec tp;
struct rusage usage;
@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.