Skip to content

Instantly share code, notes, and snippets.

@alejandroerickson
alejandroerickson / contains_subtree.c
Last active August 15, 2016 11:56
Check if binary tree t2 on n nodes is a subtree of binary tree t1 on n nodes in O(m+(1+epsilon)n) time
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define max(a,b) ((a>b)?a:b)
#define timeit(a,b){ \
start=clock(); \
a; \
end=clock(); \
@alejandroerickson
alejandroerickson / isBigRect.py
Last active August 14, 2016 12:28
Given N rectangles, check whether they cover a rectangle exactly (with no overlaps).
def isBigRect(rectangles):
if rectangles==[]:
return True
L=processBoundaries(rectangles,leftOrRight='left')
R=processBoundaries(rectangles,leftOrRight='right')
# print L, R
if L==False or R==False or not len(L)==len(R):
return False
L[-1][0]=R[-1][0]
R[0][0]=L[0][0]
#include <stdlib.h>
#include <stdio.h>
void print_bits(uint32_t x);
uint32_t uint32_smear_right(uint32_t x){
x = x | x>>1;
x = x | x>>2;
x = x | x>>4;
x = x | x>>8;