This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python2.4 | |
# -*- coding: utf-8 -*- | |
# | |
# Copyright (C) 2010 Google Inc. | |
# | |
# Licensed under the Apache License, Version 2.0 (the "License"); | |
# you may not use this file except in compliance with the License. | |
# You may obtain a copy of the License at | |
# | |
# http://www.apache.org/licenses/LICENSE-2.0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static double GetMedian(IEnumerable<double> list1, IEnumerable<double> list2) | |
{ | |
var arr1 = list1.ToArray(); | |
var arr2 = list2.ToArray(); | |
if(arr1.Length == 2 && arr2.Length == 2) | |
{ | |
return (Math.Max(arr1[0], arr2[0]) + Math.Min(arr1[1], arr2[1]))/2; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static double LargestSubsequenceSum(IEnumerable<double> list) | |
{ | |
var arr = list.ToArray(); | |
double currentMax = arr[0]; | |
double max = currentMax; | |
for (int i = 1; i < arr.Length; i++) | |
{ | |
currentMax = Max(currentMax, currentMax+arr[i]); | |
max = Max(max, currentMax); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static int EditDistance(string str1, string str2) | |
{ | |
int[,] distance = new int[str1.Length+1, str2.Length+1]; | |
for (int i = 0; i <= str1.Length; i++) | |
{ | |
distance[i, 0] = i; | |
} | |
for (int i = 0; i <= str2.Length; i++) | |
{ | |
distance[0, i] = i; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static int EditDistanceRecursive(string str1, string str2, int m, int n) | |
{ | |
if(m < 0 || n < 0 || | |
m >= str1.Length || | |
n >= str2.Length) | |
{ | |
throw new ArgumentOutOfRangeException(); | |
} | |
if(m == 0 && n == 0) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static double MinCost(double[,] cost, int m, int n) | |
{ | |
double[,] totalCost = new double[m+1, n+1]; | |
totalCost[0, 0] = cost[0, 0]; | |
for (int i = 1; i <= m; i++) | |
{ | |
totalCost[i, 0] = totalCost[i-1, 0] + cost[i, 0]; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private static string Expand(string str, int c1, int c2) | |
{ | |
int left = c1; | |
int right = c2; | |
while (left >= 0 && right < str.Length && str[left] == str[right]) | |
{ | |
left--; | |
right++; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static string LongestPalindrome(string str) | |
{ | |
var chars = str.ToCharArray(); | |
var dp = new bool[chars.Length, chars.Length]; | |
int longestBegin = 0; | |
int maxLength = 1; | |
for (int i = 0; i < chars.Length; i++) | |
{ | |
dp[i, i] = true; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static int Knapsack(IEnumerable<Tuple<int, int>> weightValue, | |
int capacity) | |
{ | |
var weights = weightValue.Select(t => t.Item2).ToArray(); | |
var values = weightValue.Select(t => t.Item1).ToArray(); | |
int[,] dp = new int[weightValue.Count()+1, capacity+1]; | |
//for 0 items total value is zero | |
for (int i = 0; i <= capacity; i++) | |
{ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static Tuple<int[], int[]> MergeSortedLists(IEnumerable<int> list1, | |
IEnumerable<int> list2) | |
{ | |
var arr1 = list1.OrderBy(i => i).ToArray(); | |
var arr2 = list2.OrderBy(i => i).ToArray(); | |
int j = 0; | |
for(int i = 0; i<arr1.Length; i++) | |
{ | |
if (arr1[i] > arr2[j]) | |
{ |