bluesunxu’s gists

bluesunxu / kthelem_1.cpp

Last active December 10, 2015 01:48

Find kth smallest element under O(k)

	int findKthElem(int arr1[], int m, int arr2[], int n, int k)
	{
	assert(k>0 && k<=(m+n));
	int i=0, j=0;

	while(true)
	{
	if(i==m)
	return arr2[j+k-1];
	if(j==n)

bluesunxu / preIn.cpp

Created December 21, 2012 05:16

Generate a binary tree from its inorder and preorder sequence

	// inorderMap maps from value to its inorder index (no dup value in tree)
	// pre changes in each recursive call, pre[0] is alway the next root value
	// l is the left index of the inorder range we investigate in current call
	// r is the right index of the inorder range
	Node* buildPreIn(map<int, int> inorderMap, int pre[], int l, int r) {
	// terminate condition l < r
	// when l==r, we still need to proceed and create the leaf node
	if (l > r) return NULL;

	int curValue = pre[0];

bluesunxu / longestdupsubstring.cpp

Created December 19, 2012 19:40

Find the longest sub string that occurs more than once.

	class trie_node {
	public:
	trie_node* child[256];
	trie_node() {
	for(int i=1; i<256; ++i)
	child[i] = NULL;
	};
	};

	// return value is the length of the dup sub string

bluesunxu / longest_nodup_substr.cpp

Created December 19, 2012 05:07

Find longest sub string without duplicate character.

	int lengthOfLongestSubstring(string s) {
	if(s.empty()) return 0;
	int len = s.length();
	int arr[256];
	for(int i=0; i<256; ++i)
	arr[i] = -1;
	int curStart = 0, curLen = 1;
	int maxLen = 1;
	for(int i=0; i<len; ++i) {
	if(arr[s.at(i)] < curStart)

bluesunxu / regexp_match.cpp

Created December 18, 2012 05:39

Match a regular expression (including '.' and '*' using dynamic programming

	bool canMatch(char a, char b)
	{
	return (a == b \|\| b == '.');
	}

	bool isMatch(const char s, const char p) {
	int lS = strlen(s);
	int lP = strlen(p);
	vector<vector<bool> > F(lS + 1, vector<bool>(lP + 1));
	F[0][0] = true;

bluesunxu / lca_bst.cpp

Created December 18, 2012 05:16

Find the Lowest Common Ancestor in a Binary Search Tree

	node* LCA_BST(node* root, node* c1, node* c2) {
	if(!c1 \|\| !c2)
	return NULL;
	node* cur = root;
	while(cur) { // returns NULL if root is NULL
	// cur key larger than both keys, LCA in the left subtree
	if(cur->key > c1->key && cur->key > c2->key)
	cur = cur->left;
	// cur key smaller than both keys, LCA in the right subtree
	else if(cur->key < c1->key && cur->key < c2->key)

bluesunxu / icsl_2.cpp

Created December 18, 2012 03:57

Insertion to a cyclic sorted list given a pointer to a random node in the list.

	node* icsl_2(node* head, node* n) {
	if(!head) {
	// list is empty, set head to the new node.
	return (head = n->next = n);
	}

	node* cur=head;
	node* prev;

	do {

bluesunxu / version_control

Created December 17, 2012 22:43

test

	Test version control
	v1, v2

bluesunxu / icsl_1.cpp

Created December 17, 2012 22:01

Insertion into a cyclic sorted list with known head pointer of the smallest element

	node* icsl_1(node* head, node* n) {
	if(!head) {
	// list is empty, set head to the new node.
	return (head = n->next = n);
	}

	node* cur=head;
	node* prev;

	// the new element is less than the smallest in the list