Skip to content

Instantly share code, notes, and snippets.

View gogsbread's full-sized avatar

Antony Thomas gogsbread

  • facebook
  • San Francisco Bay area,CA
View GitHub Profile
@gogsbread
gogsbread / surroundedregions.java
Last active December 20, 2015 18:59
leetcode - surrounding regions
public class Solution {
private static int M;
private static int N;
public void solve(char[][] board) {
M = board.length;
N = board[0].length;
//graph = new Node[M, N];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
@gogsbread
gogsbread / scc.cs
Last active December 20, 2015 16:18
Kosaraju's SCC implementation
using System;
using System.Collections.Generic;
using System.IO;
namespace SCC
{
class Node
{
public Node(int label) { Label = label; Descendents = new List<Node>(); Antecedents = new List<Node>(); Visited = false; }
public int Label { get; private set; }
@gogsbread
gogsbread / remove_empty_albums.py
Created July 31, 2013 03:27
Lifehacker series 1) Remove empty albums( with zero photos) from Picasa 1) Upload your photos to Picassa(Google +)
#-- Algorithm---
# recurse thru all albums
# delete albums that have 0 photos
#-----------------
import os
import sys
import gdata.photos.service
import gdata.media
@gogsbread
gogsbread / PalidromeParts.cs
Created May 10, 2013 22:24
Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut. http://leetcode.com/onlinejudge#question_132
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Console.WriteLine(CutPalidrome("bananadad"));
}
static int CutPalidrome(string s)
@gogsbread
gogsbread / fault_table.py
Last active December 16, 2015 10:48
Fault table for KMP algorithm
def construct_fault_table(pattern):
fault_table = []
fault_table.extend((0,0) # indexes 0 & 1 are always '0'
j=0 # poniter to the prefix
for i in xrange(2,len(pattern),1):
if pattern[i] == pattern[j]:
fault_table.append(fault_table[i-1]+1)
j+=1
else:
j=0 # reset j to the start of the pattern if it breaks
@gogsbread
gogsbread / same_shard.py
Last active December 16, 2015 02:50
Simple algorithm that returns the same shard irrespective of the number of new boxes added.
'''
Question:
Assume you want to shard big SQL user table. How will you obtain the same shard even after increasing the sql boxes.
Answer:
Same shard number can be obtained if the current system state is preserved before adding new boxes.
NOTE: Code below requires python 2.6 or 2.7
'''
using System;
using System.Collections.Generic;
class Solution
{
//Get N
// Read N sequences into an array
// scan N array
//read q
// read each operation and perform action.
@gogsbread
gogsbread / Pairs.cs
Created January 28, 2013 22:30
o(n) algorithm for finding the number of pairs that have a difference of k
using System;
using System.Collections.Generic;
class Solution
{
//Get N and K
// Read N and split.
// scan N array
//create a bucket
//count =0
@gogsbread
gogsbread / SortTester.cs
Last active December 11, 2015 17:08
Testing Sort algorithms -Insertion & Quicksort . Tested with Sorted,ReverseSorted and Random suites of n=2^3 to 2^8. Results show that insertionsort beats quicksort for lower n and things change between n = 64 to 256
/*
Testing Sort algorithms -Insertion & Quicksort . Tested with Sorted,ReverseSorted and Random suites of n=2^3 to 2^8. Results show that insertionsort beats quicksort for lower n and things change between n = 64 to 256
---Testing with n=8---
QuickSort(sorted,reversesorted,random): 5322 11 6
InsertionSort(sorted,reversesorted,random): 1745 4 3
---Testing with n=16---
QuickSort(sorted,reversesorted,random): 30 19 19
InsertionSort(sorted,reversesorted,random): 13 11 8
@gogsbread
gogsbread / UnorderedSet.cs
Created January 5, 2013 05:32
UnorderedSet
using System;
using System.Collections.Generic;
namespace RandomMusings
{
public class UnOrderedSet:IEnumerable<int>
{
Dictionary<int,int> _set = null;
public UnOrderedSet ()