Skip to content

Instantly share code, notes, and snippets.

View monkeylyf's full-sized avatar

Yifeng Liu monkeylyf

  • Google
  • Bay area
View GitHub Profile
/**USACO_Fraction_Decimal.
To find the first digit, we can calculate 30/8 = 3. Then we know the
result is 0.3xxxx...
2. To find the second digit, we first minus 3/8 by 0.3, which is 3/8 - 3/10
= (3*10 - 3*8) / 8*10 = 6/80. Note that since we only want to calculate the
next digit, we can multiply 6/80 by 10, which gives 6/8. Then we treat 6/8
as a new fraction, and repeat step 1. The first digit of 6/8 is 7, which means
6/8 = 0.7xxxx, i.e. 3/8 = 0.37xxxx
3. The above steps are repeated until numerator is 0, or a repeating sequence
import os
import sys
import time
def count_line(filepath, buf_size=1024*1024):
""""""
f = open(filename)
lines = 0
read_f = f.read # loop optimization
@monkeylyf
monkeylyf / gist:7723562
Created November 30, 2013 19:42
hackerran
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
from collections import defaultdict
rl = sys.stdin.readline
def bounded_knapsack(best, X):
dp = [ 0 ] * 5011
@monkeylyf
monkeylyf / gist:6888122
Created October 8, 2013 17:16
closest 2d point pair
# given n points in euclidean space.
# Find two points with the closest distance.
import operator
class Point():
def __init__(self, x, y):
"""Init"""
@monkeylyf
monkeylyf / gist:6426462
Created September 3, 2013 16:49
BST to DLL
class Convert_BST_to_DLL {
public static void main(String[] args) {
// Test case 1.
TreeNode root = new TreeNode(10);
root.left = new TreeNode(8);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(9);
root.right = new TreeNode(15);
root.right.left = new TreeNode(14);
@monkeylyf
monkeylyf / gist:5724823
Created June 6, 2013 20:50
cut tree hackerrank
import sys
rl = sys.stdin.readline
n, k = map(int, rl().strip().split())
tree = [ [] for _ in range(n + 1) ]
root = [ True for _ in range(n + 1) ]
res = 0
debug = True
@monkeylyf
monkeylyf / gist:5708258
Created June 4, 2013 18:26
oop deck of cards
/*Deck_of_Cards
career cup
Design the data structures for a generic deck of cards Explain how you would
subclassit to implement particular card games
*/
class Deck_of_Cards {
public static void main(String[] args) {
BlackJackCard a = new BlackJackCard(1, 1);
import operator
import sys
from collections import defaultdict
rl = sys.stdin.readline
T = int(rl().strip())
@monkeylyf
monkeylyf / gist:5614043
Created May 20, 2013 18:06
leetcode 4sum
public static void solve(int[] arr, int target) {
// Init vars.
int n = arr.length, head, tail, sum, i, j, a, b;
ArrayList<int[]> indexes;
ArrayList<Integer> pairs = new ArrayList<Integer>();
HashMap<Integer, ArrayList<int[]>> dict = new HashMap<Integer, ArrayList<int[]>>();
HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
// Hashing pairs: sum/index.
for (i = 0; i < n - 1; ++i) {
@monkeylyf
monkeylyf / gist:5580342
Created May 14, 2013 22:54
pogo_stick test large
import sys
rl = sys.stdin.readline
T = int(rl())
def is_reachable(x, y, steps):
euclidea_dis = abs(x) + abs(y)
abs_dis = (steps + 1) * steps / 2