Skip to content

Instantly share code, notes, and snippets.

@ylegall
ylegall / partitions.d
Created October 17, 2013 19:47
integer partitions.
import std.stdio;
import std.algorithm;
auto partition(int n) {
part(n, [], n);
}
private void part(int n, int[] array, int start) {
if (n == 0) {
writeln(array);
@ylegall
ylegall / combinations.d
Created October 17, 2013 20:25
combinations
import std.stdio;
import std.algorithm;
void combinations(T)(T[] array) {
comb(array, []);
}
private void comb(T)(T[] array, T[] prefix) {
if (array.length) {
writeln(prefix ~ [array[0]]);
@ylegall
ylegall / skyscrapers.c
Created October 30, 2013 14:45
how much liquid will accumulate between the stacked boxes.
#include <stdio.h>
#include <stdlib.h>
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
void skyscrapers(int *h, int len) {
int* pks = (int*)malloc(sizeof(int)*len);
int i, p=h[0], v=0, sum=0;
v = pks[0] = h[0];
for (i = 1; i < len; ++i) {
@ylegall
ylegall / reverse_list.d
Created November 4, 2013 06:57
reverse a linked list, k nodes at a time.
Node reverse(Node head, int k) {
return reverse(head, k, length(head));
}
Node reverse(Node head, int k, int remaining) {
if (remaining < k) return head;
auto i = 0;
Node next, prev = null, first = head;
while (head && i < k) {
@ylegall
ylegall / Powersets.java
Created November 6, 2013 19:14
get the powerset of a set
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Powerset {
static Set<Set<Integer>> powerSet(Set<Integer> s) {
Set<Set<Integer>> ps = new HashSet<Set<Integer>>();
powerSet(s, new HashSet<Integer>(), ps);
return ps;
@ylegall
ylegall / maxsum.d
Created November 7, 2013 18:50
subarray with maximum sum
import std.stdio;
import std.typecons;
auto maxSubArray(T)(T[] array) {
auto start = 0, stop = 0, tmp = 0;
auto maxSum = 0, sum = 0;
foreach (i; 0 .. array.length) {
sum += array[i];
if (sum < 0) {
sum = 0;
@ylegall
ylegall / valid_tree.d
Created November 7, 2013 20:33
determine if a BST is valid
import std.stdio;
class Node
{
int val;
Node left, right;
this(int val, Node left=null, Node right=null) {
this.val = val;
@ylegall
ylegall / RLE.java
Created November 8, 2013 02:45
run length encode a string
import java.util.*;
public class Test
{
static String rle(String input) {
if (input == null || input.equals("")) return "";
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < input.length()) {
@ylegall
ylegall / select.d
Created November 8, 2013 04:17
Use order statistics to select the median of an array in linear time without sorting.
import std.stdio;
auto swap(T)(ref T a, ref T b) {
T tmp = a;
a = b;
b = tmp;
}
auto part(T)(T[] array, int low, int high) {
auto size = low-1;
@ylegall
ylegall / find-tree.d
Created November 9, 2013 05:29
find the kth smallest element of an in-order traversal of a BST.
int find(Node* root, int k) {
int result = -1;
find(root, k, result);
return result;
}
void find(Node* root, ref int k, ref int result) {
if (root.left) {
find(root.left, k, result);
}