Skip to content

Instantly share code, notes, and snippets.

@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 / 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 / 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 / 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 / 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 / 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 / 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 / minstack.d
Last active December 25, 2015 13:19
A stack with O(1) push, pop, and min
import std.array;
struct MinStack(T)
{
private {
Appender!(T[],T) items;
Appender!(T[],T) mins;
}
auto pop() {
@ylegall
ylegall / rotate.d
Created September 3, 2013 23:47
90 degree clockwise matrix rotation.
import std.stdio;
auto rotate(T)(T[][] array) {
foreach(i; 0 .. array.length/2) {
foreach(j; i .. array.length-i-1) {
T temp = array[i][j];
array[i][j] = array[array.length-j-1][i];
array[array.length-j-1][i] = array[array.length-i-1][array.length-j-1];
array[array.length-i-1][array.length-j-1] = array[j][array.length-i-1];
@ylegall
ylegall / endian.d
Created August 31, 2013 22:54
Determines whether a computer is big-endian or little-endian.
import std.stdio;
auto isLittleEndian() {
int i = 0x11223344;
byte* b = cast(byte*)&i;
return b[0] == 0x44;
}
void main() {
if (isLittleEndian()) writeln("little endian");