sundeepblue

bool comp(string s1, string s2) {
	if((s1+s2).compare(s2+s1) < 0) return true;
	return false;
}

// cannot handle the case when exist 0
string get_smallest_number(vector<int> &nums) {
	if(nums.empty()) return "";
	string res = "";
	vector<string> strs;

sundeepblue

// key idea: use max heap not min heap!!!! And the max heap is declared using less<int> for priority_queue
// maybe confusing
// time: build heap O(k), scan the rest n-k numbers takes O((n-k)logk),
// so, overall, time is O(nlogk), space is k.

// idea 2: use quick selection algorithm

vector<int> get_min_k_numbers(vector<int> &A, int k) {
	if(k >= A.size()) return A;
	vector<int> res;

sundeepblue

void place_odd_before_even(int A[], int n) {
	if(n <= 1) return;
	int left = 0, right = n-1;
	while(left < right) {
		while(left < right && A[left]%2 != 0) left++;
		while(left < right && A[right]%2 == 0) right--;
		if(left < right)
			swap(A[left++], A[right--]);
	}
}

sundeepblue

void delete_node(TreeNode **head, TreeNode *p) {
	if(*head == NULL || p == NULL) return;
	if(*head == p) {
		delete p;
		p = NULL; // necessary
		*head = NULL;
		return;
	}
	if(p->next != NULL) {
		TreeNode *nxt = p->next;

sundeepblue

// key idea: first, go k-1 step.

ListNode* get_last_kth_node(ListNode *head, int k) {
	if(!head) return NULL;
	if(k == 0) return NULL;
	ListNode *p = head;
	// run k-1 steps
  for(int i=0; i<k-1; i++) {
  	if(p->next == NULL) return NULL;
  	p = p->next;

sundeepblue

void in_order(TreeNode *root) {
	if(!root) return;
	stack<TreeNode*> s;
	TreeNode *curr = root;
	//s.push(curr);
	while(true) {
		if(curr) {
			s.push(curr);
			curr = curr->left;
		}

sundeepblue

// ====================== a good concise version ===================== 4/30/2014 ==
// ================================================================================

bool is_letter(char c) { return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'; }

int count_words(const string& s) {
    int i = 0, N = s.size(), count = 0;
    while(i < N) {
        while(i < N && !is_letter(s[i])) i++;
        if(i == N) break;

sundeepblue

// http://learn.hackerearth.com/question/168/in-a-string-replace-all-occurrence-of-the-given-pattern-to-x/
/*
In a string replace all occurrence of the given pattern to 'X'

Replace all occurrence of the given pattern to 'X'.
For example, given that the pattern="abc", replace "abcdeffdfegabcabc" with "XdeffdfegX". Note that
multiple occurrences of abc's that are contiguous will be replaced with only one 'X'.
*/

sundeepblue

bool canInterleave(char *a, char *b, char *c) {
	if(*a == '\0' && *b == '\0' && *c == '\0') return true;
	if(*a == *b) {
		if(*a == *c) return canInterleave(a+1, b, c+1) || canInterleave(a, b+1, c+1);
		else return false;
	}
	if(*a == *c) return canInterleave(a+1, b, c+1);
	if(*b == *c) return canInterleave(a, b+1, c+1);
}

sundeepblue

// in pre-order
void serialize_btree(TreeNode *root, string &s) {
	if(!root) {
		s += '#';
		return;
	}
	s += to_string(root->data);
	serialize_btree(root->left, s);
	serialize_btree(root->right, s);