San Song Daddy :)

Question: http://www.lintcode.com/en/problem/kth-largest-element/ Find K-th largest element in an array. You can swap elements in the array. Answer: class Solution { public: /* * @param n: An integer * @param nums: An array * @return: the Kth largest element */ inline void qsort(vector<int> &nums, int left, int right) { if (left >= right) return; int mid = nums[(left + right)/2]; int l = left; int r = right; while (l < r) { while(nums[l] < mid) ++l; while(nums[r] > mid) --r; if (l >= r) break; nums[l] = nums[l] + nums[r]; nums[r] = nums[l] - nums[r]; nums[l] = nums[l] - nums[r]; ++l; --r; } if (l == r) l++; if (left < r) qsort(nums, left, l - 1); if (l > left) qsort(nums, r + 1, right); } int kthLargestElement(int n, vector<int>

Question: http://www.lintcode.com/en/problem/house-robber-iii/ The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Answer: ~~~c++ class Solution { public:     int houseRobber3(TreeNode* root) {         unordered_map<TreeNode*, int> m;         return dfs(root, m);     }     int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {         if (!root) return 0;         if (m.count(root)) return m[root];         int val = 0;         if (root->left) {             val += dfs(root->left->left, m) + dfs(root->left->right,

Question: http://www.lintcode.com/en/problem/house-robber-ii/ After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. Answer: ~~~c++ class Solution { public:      /*      * @param nums: An array of non-negative integers.      * @return: The maximum amount of money you can rob tonight      */     int houseRobber2(vector<int> nums) {         if (nums.size() <= 1)             return nums.empty() ? 0 : nums[0];         vector<int> nums_inf = nums;         vector<int> nums_inl = nums;         nu

Question: http://www.lintcode.com/en/problem/house-robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. Answer: time:O(N) ~~~c++ class Solution { public:     /*      * @param A: An array of non-negative integers      * @return: The maximum amount of money you can rob tonight      */     long long houseRobber(vector<int> &A) {         size_t as = A.size();         if (as == 0)           return 0;         if (as == 1)           return A[0];         if (as == 2)           return max(A[0], A[1]);         vector<long long&

knapsack problem Question: give two integer n and m, select rand numbers from 1,2,3,...,n-1, n,  let the sum of the combination is equal to  m. print out all possible combinations. Examples: n = 8 m = 10 8 2 7 3 7 2 1 6 4 6 3 1 5 4 1 5 3 2 4 3 2 1 Answer: #include <iostream> #include <vector> using namespace std; void printNumbersWithSum(int n, int m, vector<int>& numbers) {   if (m <= 0 || n <= 0)     return;   if (m == n) {     for (int number : numbers)       cout << number << " ";     cout << n << endl;   }   numbers.push_back(n);   printNumbersWithSum(n-1, m - n, numbers);   numbers.pop_back();   printNumbersWithSum(n-1, m, numbers); } int main() {   vector<int> numbers;   int n, m;   cin >> n >> m;   printNumbersWithSum(n, m, numbers);   return 0; }

Question: Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area. Example For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 4 . Answer: #include <cstdlib> #include <ctime> #include <iostream> #include <vector> using namespace std; int maxSquarea(vector<vector<int> >& matrix) {   int m = matrix.size();   int n = matrix[0].size();   vector<vector<int> >  matrix_flag = matrix;   int r = 0;   for (int i = 0; i < m; i++)     for (int j = 0; j < n; j++)       matrix_flag[i][j] = 0;   for (int i = 0; i < m; i++) {     for (int j = 0; j < n; j++) {       if (matrix[i][j] == 0)         continue;       if (matrix_flag[i][j] == 1)         continue;       int k = 1;       while (1) {         bool all1 = true;         int ii = i + k;         int jj;         for (jj = 0; jj <= k && ii < m && j+jj

#include <cstdlib> #include <iostream> #include <ctime> using namespace std; /* 0~9, a~z, A~z */ void randstring(int n, char* s) {   int fn = rand() % n;   if (fn <= n/2)     fn = (n+1) / 2;   for (int i = 0; i < fn; i++) {     int t = rand() % 3;     char c;     if (t == 0)       s[i] = '0' + (rand()%10);     else if (t == 1)       s[i] = 'a' + (rand()%26);     else       s[i] = 'A' + (rand()%26);   }   for (int i = fn; i < n; i++) {     s[i] = s[rand()%fn];   } } int main() {   srand(time(0));   int n = 20;   char* s = new char[n+1];   s[n] = '\0';   randstring(n, s);   cout << s << endl;   int n2 = (n+1)*2 + 1;   char* ns = new char[n2];   ns[0] = '$';   ns[1] = '#';   int j;   int i;   for (i = 0, j = 2; i < n; i++) {     ns[j] = s[i];     ns[++j] = '#';     j++;   }   ns[j] = '#';   ns[n2-1] = '\0';   cout << ns << endl;   int* p = new int[n2];   for (i = 0

Question: Find the minimum larger node in binary search tree for a giving node. Answer: struct BSTreeNode { BSTreeNode* pLeft; BSTreeNode* pRight; BSTreeNode* pParent; int value; }; BSTreeNode* findMinLarge(BSTreeNode* node) { if (!node) return 0; if (Node* result = node->pRight) { while (result && result->pLeft) { result = result->pLeft; } return result; } if (node->pParent == 0) { return 0; } if (node->pParent->pLeft == node) return node->pParent; BSTreeNode* parent = node->pParent; BSTreeNode* pparent = parent->pParent; while (1) { if (pparent && pparent->pLeft == parent) { return pparent; } if (!pparent) break; parent = pparent; pparent = parent->pParent; } return 0; }

Question: struct NODE { NODE* pLeft; NODE* pRight; char chValue; }; e.g. preorder traversal : a b d c e f inorder traversal : d b a e c f Answer: include using namespace std; struct NODE { NODE* pLeft; NODE* pRight; char chValue; }; void PrintPreOrder(NODE* pRoot) { if (!pRoot) return; cout << pRoot->chValue; PrintPreOrder(pRoot->pLeft); PrintPreOrder(pRoot->pRight); } void PrintInOrder(NODE* pRoot) { if (!pRoot) return; PrintInOrder(pRoot->pLeft); cout << pRoot->chValue; PrintInOrder(pRoot->pRight); } void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) { if (pPreOrder == 0 || pInOrder == 0) return; NODE* pTemp = new NODE; pTemp->pLeft = 0; pTemp->pRight = 0; pTemp->chValue = *pPreOrder; if (pRoot == 0) pRoot = pTemp; if (nTreeLen == 1) return; char pOrgInOrder = pInOrder; char pLeftEnd = pInOrder; int nTempLen = 0; while (*pPreOrder != *pLeftEnd) { nTempLen++; if (nTem

Question: An array has N numbers, move each elements to right for K steps. time limit : O(N) e.g. abcd1234 move 4 steps turns out 1234abcd Answer: void Reverse(int* arr, int b, int e) { for (; b < e; b++, e--) { int temp = arr[e]; arr[e] = arr[b]; arr[b] = temp; } } void RightShift(int* arr, int N, int K) { K %= N; Reverse(arr, 0, N - K - 1); Reverse(arr, N-K, N-1); Reverse(arr, 0, N-1); }

Question: Find the smallest k elements Answer: void findkmin(int *array, int len, int k) {   int* kmin = new int[k];   if (len <= k) {     for (int i = 0; i < len; i++)       kmin[i] = array[i];   }   else {     for (int i = 0; i < len; i++) {       int j;       for (j = 0; j < ((i < k) ? i : k); j++) {         if (kmin[j] > array[i])           break;       }       if (j < k) {         for (int m = k-1; m > j; m--)           kmin[m] = kmin[m-1];         kmin[j] = array[i];       }     }   }   for (int i = 0; i < k; i++)     cout << kmin[i] << " ";   cout << endl;   delete [] kmin; }

Question: Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. some numbers are negative. Time Complexity: O(n) Answer: void maxsumofsubarray(int* array, int len) { int curMax = 0; int mi = -1; int mj = -1; int max; bool max_init = false; for (int i = 0; i < len; i++) { if (curMax <= 0) { curMax = array[i]; mi = i; mj = i; } else { curMax += array[i]; } if (!max_init || max < curMax) { max = curMax; mj = i; max_init = true; } } for (int i = mi; i <= mj; i++) { cout << array[i] << " "; } cout << endl; cout << " max sub array sum is " << max << endl; }

Question: Transform the binary search tree into a sorted two-way linked list. do not use recursion. do not create any new node, only adjust the pointer to point. 10 / \ 6 14 / \ / \ 4 8 12 16 -->> 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; Answer: inline BSTreeNode* eleminateMinNode(BSTreeNode** tree) { BSTreeNode* treeHead = tree; if (!treeHead) return 0; BSTreeNode treeHeadParent = 0; while (treeHead->m_pLeft) { treeHeadParent = treeHead; treeHead = treeHead->m_pLeft; } if (treeHeadParent) treeHeadParent->m_pLeft = treeHead->m_pRight; if (treeHead == *tree) *tree = treeHead->m_pRight; return treeHead; } inline BSTreeNode* eleminateMaxNode(BSTreeNode** tree) { BSTreeNode* treeHead = tree; if (!treeHead) return 0; BSTreeNode treeHeadParent = 0; while (treeHead->m_pRight) { treeHeadParent = treeHead; treeH