ducalpha’s gists

ducalpha / _vimrc

Created April 22, 2014 04:34

.vimrc on Windows

	set nocompatible
	source $VIMRUNTIME/vimrc_example.vim
	source $VIMRUNTIME/mswin.vim
	behave mswin

	set diffexpr=MyDiff()
	function MyDiff()
	let opt = '-a --binary '
	if &diffopt =~ 'icase' \| let opt = opt . '-i ' \| endif
	if &diffopt =~ 'iwhite' \| let opt = opt . '-b ' \| endif

ducalpha / t_confidence_interval.py

Created May 11, 2014 03:50

compute t-distribution confidence interval

	from scipy.stats import t
	import numpy

	def sampleStdev(samples):
	mean = numpy.mean(samples)
	squareSamples = [ numpy.power(x - mean, 2) for x in samples]
	sumSqr = numpy.sum(squareSamples)
	sampleStdev = numpy.sqrt(sumSqr / (len(samples) - 1))
	return sampleStdev

ducalpha / point_of_max_overlap.cpp

Last active October 23, 2015 05:47 — forked from ducss2015/point_of_max_overlap.cpp

Find the point of max overlap, given a number of intervals

	/*You are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
	*/
	#include <cstdio>
	#include <sstream>
	#include <fstream>
	#include <map>
	#include <vector>

	using namespace std;

ducalpha / Find_one_char_diff_string.cpp

Created October 23, 2015 15:18

Find one-character-different string in an array of strings

	/*Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths.
	Ex: Given string
	banana
	and array is [bana, apple, banaba, bonanza, banamf]
	and the output should be true as banana and banaba are one character difference.
	banana1, banan
	http://www.careercup.com/question?id=5760697411567616
	*/
	#include <my_epi/common.h>
	struct TrieNode {

ducalpha / find_subarray_closest_to_k.cpp

Last active December 18, 2015 12:49

find a subarray that contains the largest sum < k

	/* Given an array of integers A and an integer k, find a subarray that contains the largest sum, subject to a constraint that the sum is less than k?
	*/
	pair<int, int> FindSubarrayClosestToK(const vector<int>& a, int k) {
	pair<int, int> range{0, -1};

	if (a.empty()) return range;

	map<int, int> sum_to_idx;
	int sum = 0;
	int min_diff = k;

ducalpha / find_subarray_equal_to_k.cpp

Created December 18, 2015 13:12

Given an array of integers A and an integer k, find a subarray whose sum is k

	/* Given an array of integers A and an integer k, find a subarray whose sum is k */
	typedef pair<int, int> Range;
	Range FindSubarrayWithSum(const vector<int>& a, int k) {
	Range result{ -1, -1};
	if (a.empty())
	return result;
	unordered_map<int, int> sum_to_idx;
	int sum = 0;
	sum_to_idx.emplace(sum, -1); // cumulative sum at -1 is 0
	for (int i = 0; i < a.size(); ++i) {

ducalpha / longest_nondecreasing_subsequence.cpp

Last active December 18, 2015 14:33

Find longest increasing/nondecreasing subsequence in an array

	/* Find longest increasing/nondecreasing subsequence in an array */
	int LongestIncreasingSubsequence(const vector<int>& a) {
	if (a.empty()) return 0;
	vector<int> ends; // endpoint of active array
	ends.emplace_back(a[0]);
	for (int i = 1; i < a.size(); ++i) { //? ++i or i++
	auto it = lower_bound(ends.begin(), ends.end(), a[i]);
	if (it != ends.end()) {
	*it = a[i];
	} else {

ducalpha / find_longest_subarray_closest_to_k.cpp

Created December 18, 2015 14:36

find longest subarray closest/equal to k

	pair<int, int> FindSubarrayClosestToK(const vector<int>& a, int k) {
	pair<int, int> range{0, -1};

	if (a.empty()) return range;

	map<int, int> sum_to_idx;
	int sum = 0;
	int min_diff = k;
	sum_to_idx.emplace(0, -1); // S[-1] = 0 so push 0, -1 here!
	for (int i = 0; i < a.size(); ++i) {

ducalpha / is_valid_schedule.cpp

Created January 4, 2016 00:27

Check valid schedule

	struct Meeting {
	int start, end;
	};
	struct CompareMeeting {
	bool operator()(const Meeting& a, const Meeting& b) const {
	if (a.start == b.start) return a.end < b.end;
	return a.start < b.start;
	}
	};
	bool IsValidSchedule(vector<Meeting> meetings) {

ducalpha / find_min_time_period.cpp

Created January 4, 2016 00:29

	int FindMinTimePeriod(const vector<int>& tasks, int K) {
	unordered_map<int, int> task_to_last_time;
	int cur_time = 0;
	for (int i = 0; i < tasks.size(); ++i) {
	int cur_task = tasks[i];
	auto it = task_to_last_time.find(cur_task);
	if (it != task_to_last_time.end()) {
	cur_time = max(cur_time, it->second + K + 1);
	it->second = cur_time;
	} else {

Duc Bui ducalpha