Skip to content

Instantly share code, notes, and snippets.

@sumerc
sumerc / interview_q2.py
Last active August 29, 2015 13:56
A Twitter Interview Question
# 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:
@sumerc
sumerc / interview_q1.py
Last active June 4, 2018 15:51
A Microsoft Interview Question
# 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 / topcoder_q.py
Last active August 29, 2015 14:00
TopCoder Problems
# 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 / gist:74ebc1002d407109f1be82ecfd20b095
Last active July 16, 2018 12:39
O(lgN) weighted random python
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 / union_find_by_rank.py
Last active May 2, 2019 12:38
UnionFind data structure - (by rank) (Inspired from networkx.utils.unionfind)
"""
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 / profile_clocks.c
Last active January 16, 2020 20:46
profile different clock types - Linux
#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 / gist:8d6bbc40cc67dae1bf4f6193a71cfc3b
Last active December 2, 2020 15:58
Run GDB repeatedly and get a backtrace when error happens
#!/bin/bash
set -eu
i=1
while [ $i -le 10 ]
do
gdb_output=$(gdb -batch -ex "run" -ex "bt" --args python regression.py 2>&1)
if [[ ${gdb_output} != *'No stack'* ]]; then
echo -e "${gdb_output}"
break
@sumerc
sumerc / bench_ch_compression.go
Last active March 2, 2022 10:55
Benchmark different codecs in Clickhouse table
// I am trying to benchmark different ways to store stack traces in Clickhouse db with different codecs and benchmark the compression
// The way it works is:
// 1. drop/create table with selected codecs
// 2. insert ARRAY(UInt32) (or ARRAY(UUID)) of data which mimics a valid stacktrace. Similar to pprof list of LocationIDs.
// minCallStackDepth/maxCallStackDepth defines the height range of the callstack and maxLocationCount defines the LocationID cardinality.
// The default value is selected as 10_000 which might be OKish since for a mid-sized application there will not be more than 10_000 unique
// functions/LocationsIDs? This is an assumption, though.
// 3. Optimize table and run stats Query to see column stats. Most important is the ratio. For example with (T64+ZSTD) on ARRAY(Uint32) I get
// ~2.3x compression on my local machine.
// This is the way I ran clickhouse on my M1:
@sumerc
sumerc / gist:35fe8c213fb7623360157f28be5aebd2
Last active September 28, 2022 10:11
pprof benchmark code v1
package main
import (
"bytes"
"fmt"
"os"
//"runtime"
"runtime/pprof"
"strconv"
"sync"
@sumerc
sumerc / main.c
Last active December 29, 2022 12:25
pyframe_getback Crash
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include "frameobject.h"
void DebugPrintObjects(unsigned int arg_count, ...)
{
unsigned int i;
va_list vargs;
va_start(vargs, arg_count);