Skip to content

Instantly share code, notes, and snippets.

@ddrone
ddrone / big_int.cpp
Created June 21, 2011 14:52
Big integer class with boost unit test
#include "big_int.h"
std::vector <int64> read_big_int(std::string s)
{
std::vector <int64> res;
for (int i = (int)s.length(); i > 0; i-=9)
if (i < 9)
{
res.push_back(atoi(s.substr (0, i).c_str()));
}
@ddrone
ddrone / main.cpp
Created June 26, 2011 00:20
Double number representation
#include <cstdio>
#include <iostream>
using namespace std;
static union
{
double use;
char output[8];
};
@ddrone
ddrone / Main.java
Created September 28, 2011 10:48
Hindley-Millner type inference
import java.util.TreeMap;
public class Main {
// Expression type definitions
static abstract class Expression implements Comparable<Expression> {
@Override
public int compareTo(Expression arg0) {
return this.toString().compareTo(arg0.toString());
@ddrone
ddrone / gist:1262658
Created October 4, 2011 20:13
BrandAnalyst DB schema
drop table if exists InfoSource;
create table InfoSource(
id int primary key not null,
title varchar(100),
description text,
website varchar(400)
);
drop table if exists Article;
create table Article(
@ddrone
ddrone / mergesort.py
Created June 12, 2012 20:02
Mergesort implementation in Python
def merge(ls, left, mid, right):
it1 = 0
it2 = 0
result = [0] * (right - left)
while left + it1 < mid and mid + it2 < right:
if ls[left + it1] < ls[mid + it2]:
result[it1 + it2] = ls[left + it1]
it1 += 1
else:
result[it1 + it2] = ls[mid + it2]
@ddrone
ddrone / lca.py
Created June 22, 2012 18:35
Implementation of binary-uplift algorithm for solving LCA problem
# This code is in public domain.
# Written by Andrew Shulayev, 2012
from pprint import pprint
test_tree = ([0, 0, 1, 0, 2, 3, 0, 3, 2, 4, 5, 6, 8], 0)
def print_tree(tree):
par, root = tree
n = len(par)
@ddrone
ddrone / suffixarray.py
Created June 22, 2012 19:59
Implementation of suffix array construction in O(n log^2 n)
# This code is in public domain.
# Written by Andrew Shulayev, 2012
# Implementation of Karp-Miller-Rosenberg algorithm
# Builds suffix array of a string with length n
# in O(n log^2 n) time
def count_classes(arr, key = lambda x : x):
result = []
for i, x in enumerate(arr):
@ddrone
ddrone / LinearTimeRMQ.java
Created June 22, 2012 23:06
Implementation of online static RMQ-problem with O(N) preprocessing time and O(1) query time
// This code is in public domain.
// Written by Andrew Shulayev, 2012
import java.util.*;
import java.io.*;
// current version doesn't work properly
public class LinearTimeRMQ
{
#lang racket
(require plot)
(plot-new-window? #t)
(define (flatmap f ls)
(if (null? ls) '()
(append (f (car ls)) (flatmap f (cdr ls)))))
(define (range n)
@ddrone
ddrone / OS.hs
Created November 7, 2012 01:44
OS / FP midterm solutions
{-# LANGUAGE MultiParamTypeClasses #-}
import System.IO (readLn)
data Request = ReadInt Int | WriteInt Int Int | Halt | Fork | Pipe
newtype Program = Program { runProgram :: Int -> (Request, Program) }
mainP :: Program
mainP = undefined