Skip to content

Instantly share code, notes, and snippets.

@ylegall
ylegall / Hamming.java
Created November 27, 2013 02:14
Generate hamming numbers in order
import java.util.*;
class Hamming
{
static List<Integer> getHamming(int n) {
int count = 1;
List<Integer> hams = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
hams.add(1);
@ylegall
ylegall / Intersect.java
Last active December 28, 2015 06:29
Compute the intersection of a collection of sets
import java.io.*;
import java.util.*;
public class Intersect {
static Set<Integer> intersection(List<Set<Integer>> sets) {
Set<Integer> s1 = sets.get(0);
List<Integer> removeList = new ArrayList<>();
for (int s = 1; s < sets.size(); ++s) {
for (int i : s1) {
if (!(sets.get(s).contains(i))) removeList.add(i);
@ylegall
ylegall / Kperm.java
Created November 13, 2013 22:15
Find the k permutations of n items.
import java.io.*;
import java.util.*;
public class Kperm {
static void kperm(List<Integer> items, int k) {
kperm(items, new ArrayList<Integer>(), k);
}
static void kperm(List<Integer> items, List<Integer> accum, int k) {
if (accum.size() == k) {
@ylegall
ylegall / maxdiff.d
Created November 13, 2013 18:32
Given an array A, find the maxium difference, D = A[j] - A[i] such that j >= i
import std.stdio;
import std.algorithm;
auto maxDiff(T)(T[] array) {
T m = 0, minVal = array[0];
foreach (i; 1 .. array.length) {
auto diff = array[i] - minVal;
m = max(m, diff);
minVal = min(minVal, array[i]);
}
@ylegall
ylegall / Coins.java
Created November 10, 2013 20:41
Find smallest collection of coins with a given sum.
import java.util.*;
public class Coins
{
static List<Integer> makeChange(int[] coins, int sum) {
return makeChange(coins, new ArrayList<Integer>(), sum);
}
static List<Integer> makeChange(int[] coins, List<Integer> accum, int sum) {
@ylegall
ylegall / Parens.java
Created November 9, 2013 16:53
balance parentheses
import java.util.*;
public class Test
{
static String balance(String input) {
int count = 0;
StringBuilder sb = new StringBuilder();
for (char c : input.toCharArray()) {
@ylegall
ylegall / triples.d
Created November 9, 2013 15:28
find 3 elements of an unsorted array whose sum is 0.
import std.stdio;
import std.typecons;
alias Tuple!(int, int) Pair;
// O(n^2)
auto triple(int[] array) {
Pair[int] map;
for (int j = 1; j < array.length-1; ++j) {
for (int i = 0; i < j; ++i) {
@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);
}
@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 / 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()) {