Skip to content

Instantly share code, notes, and snippets.

@vo
vo / main.c
Created February 12, 2014 02:43
Rotate N size list by K to the right in O(N) time, O(1) space.
#include <stdio.h>
#define N 20
#define K 5
// reverses letters in indices s[from:to]
void reverse_string(char * s, int from, int to)
{
char * p1 = s + from;
char * p2 = s + to;
@vo
vo / gist:8994837
Last active August 29, 2015 13:56
Rough outline of a Trie in Python, storing 10 digit numbers
import random
class Trie:
def __init__(self):
self.children = [None]*10
def insert(self, i, n):
if n == 1:
self.children[i] = True
else:
d = i / 10**(n-1)
@vo
vo / gist:8994858
Created February 14, 2014 02:36
Shuffle an array of ints
#include <stdlib.h>
void shuffle(int *array, size_t n)
{
if (n > 1) {
size_t i;
for (i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
@vo
vo / gist:8995789
Last active August 29, 2015 13:56
Reverse order of words in string in C
#include <stdio.h>
#include <string.h>
int main() {
char s[] = "hello world!";
int n = strlen(s);
// reverse string in-place.
int i, j, t;
@vo
vo / gist:9040649
Created February 16, 2014 21:07
Sample n samples without replacement from a population [0,N]
void sample(int * samples, size_t n, size_t N) {
size_t t = 0, m = 0;
while(m < n)
{
double u = rand() / (double)RAND_MAX;
if((N-t)*u >= n-m) t++;
else samples[m++] = t++;
}
}
@vo
vo / gist:9045230
Last active August 29, 2015 13:56
Q Learner for Nim, in Python
import random
num_sticks = 22
num_states = num_sticks + 6
num_actions = 3
action_list = range(num_actions)
num_iterations = 10000
gamma = 0.1
alpha = 0.5
@vo
vo / divide_naive.c
Last active August 29, 2015 13:56
Divide two unsigned ints without division operator
#include <stdio.h>
typedef unsigned int UINT;
// does not handle overflow or negative numbers
UINT divide_naive(UINT a, UINT b)
{
UINT result;
while (b < a) {
UINT k=0, b2k = b;
while(b2k << 1 < a)
@vo
vo / gist:9284932
Created March 1, 2014 04:04
Different ways to check for duplicates in a string
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <climits>
// using STL MAP
bool duplicate_check_maphist(std::string s)
{
std::map<char, int> h;
@vo
vo / gist:9331376
Created March 3, 2014 18:26
Checking if one string is a permutation of another
#include <iostream>
void build_histogram(std::string s, int * m) {
size_t len = s.length();
for(int i = 0; i < len; ++i)
m[s[i]] +=1;
}
bool check_permutation(std::string s1, std::string s2)
{
@vo
vo / gist:9331392
Created March 3, 2014 18:27
Rotating an NxN array 90 degrees in-place with a transpose and flip operation
#include <iostream>
#include <cstdio>
#define DIM 5
void swap(int s[DIM][DIM], int i, int j, int k, int l) {
char c = s[i][j];
s[i][j] = s[k][l];
s[k][l] = c;
}