XiaoPiGu
BAN USERPrefix trie is very brilliant though a little overkill. We will not have any case like 3343 as one character. Thus I feel prefix trie is not ideal here. Especially when you have case like 333333, 444444.
My code is not neat. Thus I will not present it here. Playable version @
ideone.com/CeIqWK
A map structure is used. Multiple key press on the same char is taken care off by modulo operation. The question itself never mentioned pressing 1 and pressing 0. As suggested by other fellow CCers, it is handled as numeric inputs.
 XiaoPiGu January 13, 2015No duplication allowed in the output. or else what is the meaning of this interview question?
Either set or manual duplication check can be used to eliminate duplicate. I am not talking about generate all possible outputs and then eliminate duplicates. Duplication checking is done while generating permutation.
void helper(string s, int i, vector<string> &res) {
if (i == s.size()  1) {
res.push_back(s);
return;
}
set<char> used;
for (int st = i; st < s.size(); ++st) {
if (used.count(s[st])) continue;
used.insert(s[st]);
swap(s[i], s[st]);
helper(s, i + 1, res);
swap(s[i], s[st]);
}
}
vector<string> perm(string s) {
if (!s.size()) return vector<string>();
vector<string> ret;
helper(s, 0, ret);
return ret;
}
Playble code at
ideone.com/umy4It

XiaoPiGu
January 12, 2015 Observe:
* If 263 is colorful then 362 is also colorful.
* Consider all substring ending at index i, for 362, when we are at 3, we have only one option: 3. When we are at 6, we have two options: 3*6 and 6. When we are at 2, we have three options: 2, 6*2 and 3*6*2. Notice how those options populate from one index to the next index. Once we have all those options, we simply use a set or map or whatever counting container to check duplication.
Since there are at least O(N^2) substrings, time complexity is at least O(N^2).
bool color(int num) {
if (num < 10) return true;
set<int> s;
vector<int> v;
while (num) {
int lastdigit = num % 10;
num /= 10;
for (auto &i : v) i *= lastdigit;
v.push_back(lastdigit);
for (auto i : v) {
if (s.count(i)) return false;
else s.insert(i);
}
}
return true;
}
Playable version at:
ideone.com/UxES9I

XiaoPiGu
December 31, 2014 Naive methods are easy to come up with. You can either store all possible substrings (n^2) and then do string compare to search consecutive duplicate substrings, or use hash map to store all possible start locations. Refer to the top post for the first method. For the second method:
bool validPassword(string password) {
/* Check string length and upper lower case stuff... omitted */
unordered_multimap<char, int> umm;
for (int i = 0; i < password.size(); ++i) {
if (i != 0 && password[i] == password[i  1]) return false;
if (umm.count(password[i])) {
auto range = umm.equal_range(password[i]);
for (auto it = range.first; it != range.second; ++it) {
int candstart = 2 * (*it).second  i + 1;
if (candstart < 0  password[candstart] !=\
password[(*it).second + 1])
continue;
int candlen = i  (*it).second;
if (password.substr(candstart, candlen) == \
password.substr((*it).second + 1, candlen))
return false;
}
}
umm.insert(make_pair(password[i], i));
}
return true;
}
Admit it, both methods have complexity O(n^3).
I really think we can do better than O(n^3).
I am referring to longest repeated substring problem. If we construct the suffix tree (in O(N) by Ukkomen algorithm, or O(N^2) naive method), then for all N^2 suffix substring pairs, with O(N) preprocess time, we can do longest common prefix inqury in O(1) time for one pair of suffix substring (by Harel and Tarjan's algorithm, refer to
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Introduction
), thus achieving O(N^2) time complexity.
This is a very interesting problem. Any thoughts and ideas, fellow CCers?
Just some thoughts.
1. You can only have one palindrome date in one year.
2. You might need more information from the interviewer, such as:
2.1 Do you need to consider leap year?
2.2 Do you need to consider 30/31 days per month?
2.3 Do you need to consider BC years?
2.4 Do you need to consider missing 0s? such as April 10, 2014 (4102014) or February 10, 2012 (2102012)?
2.5 Can year input ranges from 0000 to 9999? What is the lower and upper bound?
My brute force practice:
ideone.com/5MhTaq
I only outputed all palindrome date in 21st century without considering cases like "2102012".
 XiaoPiGu December 24, 2014Additive or not additive? Brute force method should be easy to come up with. But as said in other posts, we have the following optimizations and assumptions:
1. Number must have at least 3 digits.
2. Negative numbers? Negative numbers are not ok.
3. Illformed numbers such as 10102? 1 + 01 = 02, but we prefer not to consider this case now.
At the cost of string conversion, I found it easier to code after the number is converted to string. In C++, string to integer is stoi(), while integer to string is std::to_string(). Ill formed case is easier to check when string is used too.
Playable code at
ideone.com/kRN4IN
bool verify(string s1, string s2, string s3) {
// verify that s3 is the fibbonaci sequence of s1 and s2
while(s3.size()) {
string res = to_string(stoi(s1) + stoi(s2));
if (res.size() > s3.size()  s3.substr(0, res.size()) != res)
return false;
s1 = s2;
s2 = res;
s3 = s3.substr(res.size(), s3.size()  res.size());
}
return true;
}
bool additive(int num) {
if (num <= 100) return false;
string str = to_string(num);
for (int st1len = 1; st1len <= str.size()  2; ++st1len) {
for (int st2len = 1; st2len <= str.size()  st1len  1; ++st2len) {
string s1 = str.substr(0, st1len);
string s2 = str.substr(st1len, st2len);
if (s1.front() == '0'  s2.front() == '0') continue;
string s3 = str.substr(st1len + st2len, \
str.size()  st1len  st2len);
if (s3.front() == '0') continue;
if (verify(s1, s2, s3)) return true;
}
}
return false;
}

XiaoPiGu
December 20, 2014 Heap, complexity O(n*log3), almost linear
3 variables for 3 largest so far, complexity O(3n), linear with constant
Quick select, complexity O(2n). after select, need to sum all those nonnegligible elements.
Quick select using hoare partition:
int hoare(int A[], int st, int ed) {
if (st == ed) return st;
int left(st  1), right(ed + 1), key(A[st]);
while (1) {
while (A[++left] < key);
while (A[right] > key);
if (left < right) swap(A[left], A[right]);
else return right;
}
}
int select(int A[], int st, int ed, int k) {
if (k < st  k > ed) return 1;
if (st == ed) return A[st];
int pivot = hoare(A, st, ed);
if (pivot >= k) return select(A, st, pivot, k);
return select(A, pivot + 1, ed, k);
}
double averageWithout3Largest(int A[], int n) {
if (n <= 3) return 0;
select(A, 0, n  1, n  3);
int sum = 0;
int totalnum = n  3;
for (int i = 0; i < n  3; ++i) {
if (A[i] == 0) totalnum;
else sum += A[i];
}
return double(sum) / double(totalnum);
}
IMO, getting quick select right during an interview is hard enough though...
 XiaoPiGu December 19, 2014Greedy is not OK in this problem. Simple search "greedy coin change algorithm" and wiki will tell you greedy is not guaranteed to give you optimal solution. Refer to other posts for counterexamples.
Always keep in mind that set sum problem is a NPC problem. All the DP algorithm posted here are psuedopolynomial time solutions since when the number of bits used to represent target value increases, the timespace complexity increases exponentially. For more details, also google "set sum problem pseudo polinomial".
Coinchange problem, also known as knapsack problem, is frequently tested. A brute force method is always a good start.
Since we have unlimited number of each denomination coin, given a target value, and current coin we are considering, we can convert this problem to "how many coins that have equal value to the current coins can we take before we study the next coin", and the value ranges from 0 to target/current coin value. Now we have the following code:
int brutehelper(vector<int>& cand, int target, int i) {
int ret = INT_MAX;
if (target == 0) return 0;
if (target < 0  i < 0) return 1;
for (int repeat = 0; repeat <= target / cand[i]; ++repeat) {
int subproblem = brutehelper(cand, target  repeat*cand[i], i  1);
if (subproblem < 0) continue;
ret = min(ret, subproblem + repeat);
}
return (ret == INT_MAX) ? 1: ret;
}
If we think this problem in another way, that is, for the current coin, we either consider it as part of the target value, or we exclude it from the target value, and we will have another brute force version:
int brutehelper2(vector<int> &cand, int target, int i) {
if (target == 0) return 0;
if (target < 0  i < 0) return 1;
int cand1 = brutehelper2(cand, target, i  1); // don't keep current
int cand2 = brutehelper2(cand, target  cand[i], i);// keep current
if (cand2 >= 0) cand2 += 1;
if (cand1 < 0) return cand2;
if (cand2 < 0) return cand1;
return min(cand1, cand2);
}
It is easy to see that subproblems are overlapping, with some memoization, the second brute force method can be easily converted to topdown DP solution:
int dphelper(vector<int> &cand, int target, int i, vector<vector<int>>& memo) {
if (target == 0) return 0;
if (target < 0  i < 0) return 1;
if (memo[target][i] != 0) return memo[target][i];
int cand1 = dphelper(cand, target, i  1, memo);
int cand2 = dphelper(cand, target  cand[i], i, memo);
if (cand2 >= 0) ++cand2;
if (cand1 < 0) memo[target][i] = cand2;
else if (cand2 < 0) memo[target][i] = cand1;
else memo[target][i] = min(cand1, cand2);
return memo[target][i];
}
On the other hand, the first brute force method is ideal when constructing bottomup DP solution:
int bottomUpDp(vector<int>& cand, int target) {
if (target == 0) return 0;
if (target < 0  !cand.size()) return 1;
vector<vector<int>> memo(cand.size(), vector<int>(target+1, 0));
for (int val = 0; val <= target; ++val) {
memo[0][val] = val%cand[0] ? 1 : (val / cand[0]);
}
for (int i = 1; i < cand.size(); ++i) {
for (int val = 1; val <= target; ++val) { // the immediate value of target
int tmp = INT_MAX;
for (int repeat = 0; repeat <= val / cand[i]; ++repeat) {
if (memo[i  1][val  repeat*cand[i]] < 0) continue;
tmp = min(tmp, memo[i  1][val  repeat*cand[i]] + repeat);
}
memo[i][val] = (tmp == INT_MAX) ? 1 : tmp;
}
}
return memo[cand.size()  1][target];
}
More on knapsack problem, DP memory optimization can be found at
loveoriented.com/pack/
. Playable version for the above four methods can be found at:
ideone.com/KQ2lhU

XiaoPiGu
December 19, 2014 POJ1088
poj.org/problem?id=1088
(chinese). DFS with memoization.
int helper(int row, int col, vector<vector<int>> &grid, vector<vector<int>> &memo) {
if (memo[row][col] != 0) return memo[row][col];
// at least one step is possible, since the sequence can be
// only one element.
int up(0), down(0), left(0), right(0);
if (row > 0 && grid[row  1][col] == grid[row][col] + 1)
up = helper(row  1, col, grid, memo);
if (row < grid.size()  1 && grid[row + 1][col] == grid[row][col] + 1)
down = helper(row + 1, col, grid, memo);
if (col > 0 && grid[row][col  1] == grid[row][col] + 1)
left = helper(row, col  1, grid, memo);
if (col < grid[0].size()  1 && grid[row][col + 1] == grid[row][col] + 1)
right = helper(row, col + 1, grid, memo);
memo[row][col] = max(max(up, down), max(left, right)) + 1;
return memo[row][col];
}
The above code will only output the length of longest LIS from current coordinate. To get the full sequence, check full code at:
ideone.com/s4ILPd

XiaoPiGu
December 19, 2014 DP is definitely what they are looking for here in this question. My interpretation of the DP formula is kinda different. Since the snake only goes to right and down, thus we start the memoization table from the right down corner, and use the memoization table to record how long can the snake go if it starts from here. The DP formula is simple:
steps[i][j] = 1+max(steps[i+1, j], steps[i, j+1])
If i+1 or j+1 is out of bound, disregard that term. If i+1 and j+1 are all out of bound, set the second term in DP formula zero. Don't forget to check number continuity.
Playable code at
ideone.com/s7QdEs
vector<int> helper(vector<vector<int>> grid) {
if (!grid.size()  !grid[0].size()) return vector<int>();
int rowCount(grid.size()), colCount(grid[0].size());
vector<vector<int>> memo(colCount);
vector<int> ret;
for (int row = rowCount  1; row >= 0; row) {
for (int col = colCount  1; col >= 0; col) {
vector<int> right, down;
if (col + 1 < colCount && \
abs(grid[row][col + 1]  grid[row][col]) == 1)
right = memo[col + 1];
if (row + 1 < rowCount && \
abs(grid[row + 1][col]  grid[row][col]) == 1)
down = memo[col];
memo[col] = right.size() > down.size() ? right : down;
memo[col].push_back(grid[row][col]);
ret = ret.size() > memo[col].size() ? ret : memo[col];
}
}
reverse(ret.begin(), ret.end());
return ret;
}

XiaoPiGu
December 17, 2014 Sliding window is a good start. Since we are trying to find a consecutive range, instead of calculating (from i to j) we can try to solve another problem. We find (0>i) and (0>j) such that those two segments will sum up to value1 and value1+target. To facilitate O(1) data access for each elements, map structure is used. The following code assumes array value can be any integer number, and will output all possible segments if multiple segments meet the criteria. Complexity O(n), O(n).
Playable version at
ideone.com/H7JJX2
vector<pair<int, int>> findRange(int A[], int n, int target) {
unordered_multimap<int, int> um;
vector<pair<int, int>> ret;
for (int i(0), leftsum(0); i < n; ++i) {
if (i == 0) leftsum = A[0]; // left sum is sum[0, i]
else leftsum += A[i];
um.insert(make_pair(leftsum, i));
}
for (int i(0), leftsum(0); i < n; ++i) {
if (i == 0) leftsum = 0; // now leftsum is sum[0, i1]
else leftsum += A[i  1];
int targetsum = leftsum + target;
auto p = um.equal_range(targetsum);
for (auto st = p.first; st != p.second; ++st) {
if ((*st).second < i) continue;
//ret.push_back(make_pair(i, (*st).second));
ret.push_back(make_pair(i+1, (*st).second+1));
}
}
return ret;
}

XiaoPiGu
December 17, 2014 So many "for"s and "ifelse"... Just name a counter and follow the spiral path until the counter reaches n**2. That's it! btw, the input is wrong. Should use { "ilove", "dinte", "newep", "aivri", "maxec" }.
Playable code at:
ideone.com/sqWl30
pair<int, int> nextdir(pair<int, int> dir) {
if (dir == pair<int, int>{0, 1}) return pair<int, int>{1, 0};
else if (dir == pair<int, int>{1, 0}) return pair<int, int>{0, 1};
else if (dir == pair<int, int>{0, 1}) return pair<int, int>{1, 0};
else return pair<int, int>{0, 1};
}
vector<char> spiral(vector<string> matrix) {
vector<char> ret;
if (matrix.size() <= 0) return ret;
int row(0), col(0);
pair<int, int> dir{ 0, 1 };
for (int i = 0; i < matrix.size()*matrix.size(); ++i) {
ret.push_back(matrix[row][col]);
matrix[row][col] = 0; // dont forget this
row += dir.first; col += dir.second;
if (row < 0  col < 0  row == matrix.size()  \
col == matrix.size()  !matrix[row][col]) {
row = dir.first; col = dir.second;
dir = nextdir(dir);
row += dir.first; col += dir.second;
}
}
return ret;
}

XiaoPiGu
December 13, 2014 What's the meaning of this question? If user enters 818684, while you expect 18684, should we still return true since the computer only sees 164? Anyway, if that's what EPIC wants, we can come up with the following two ideas.
* We can either eliminate all faulty chars in expected string and do string compare,
* or compare two strings char by char. If faulty chars are found in expected string, skip.
Playable code at:
ideone.com/DtlAK2
bool checker(string actual, string expected, char fault) {
if (actual.size() > expected.size()) return false;
int actPt(0), expPt(0);
while (actPt != actual.size() && expPt != expected.size()) {
if (expected[expPt] == fault) {
++expPt;
continue;
}
if (actual[actPt] != expected[expPt]) return false;
++actPt, ++expPt;
}
while (expPt != expected.size() && expected[expPt] == fault) ++expPt;
return actPt == actual.size() && expPt == expected.size();
}

XiaoPiGu
December 12, 2014 Similar idea. Shorter code. n is string length.
void adjSwap(char src[], char dst[], int n) {
for (int cur = 0; cur < n; ++cur) {
if (src[cur] == dst[cur]) continue;
int ct = cur+1;
for (; src[ct] != dst[cur] && ct < n; ++ct);
for (; ct != cur; ct) {
swap(src[ct], src[ct  1]);
cout << src << endl;
}
}
}
The hard part is how to prove this is optimal. A similar problem is how to find how many swaps are necessary to convert one string to another using only adjacent swaps, which is also known as inversion count problem.
 XiaoPiGu December 12, 2014Basic recursive practice. Just don't forget 0 when n == 1.
Playable code:
ideone.com/OYUBa3
vector<int> helper(int n, int pre) {
if (n == 0) return vector<int>{pre};
vector<int> ret;
for (int i = pre % 10 + 1; i <= 9; ++i) {
auto tmp = helper(n  1, pre * 10 + i);
ret.insert(ret.end(), tmp.begin(), tmp.end());
}
return ret;
}
vector<int> gen(int n) {
if (n <= 0) return vector<int>();
auto ret = helper(n, 0);
if (n == 1) ret.push_back(0);
return ret;
}

XiaoPiGu
December 12, 2014 If you ever heard of Manacher's algorithm, then you will know that there is a O(N), O(N) solution out there.
Just to make my life easier, here is my O(N^2), O(N) bottomup DP code. No recursion. Idea is simple, if I want to check whether S[i>j] is a palindrome or not, i check: S.charAt[i] == S.charAt[j] and substring from i to j is less than 3 char long, or S[i+1, j1] is a palindrome.
Playable code at:
ideone.com/c2BXDf
void checkPalindrome(string s) {
if (s.size() < 3) return;
vector<bool> memo(s.size(), 0);
for (int i = s.size()  1; i >= 0; i) {
for (int j = s.size()  1; j >= i; j) {
if (s[i] == s[j] && (j <= i + 1  memo[j  1])) {
memo[j] = 1;
if (j  i + 1 >= 3)
cout << s.substr(i, j  i + 1) << endl;
}
else memo[j] = 0;
}
}
}

XiaoPiGu
December 11, 2014 This question needs to be clarified a little bit.
Have you ever considered the case when the user goes right, then down, then upright?
For this question, tt seems that only one direction is considered at a time, which greatly reduce the complexity of this problem. But the random walk case seems more fun to do (seems like a 3 dimensional DP problem I guess).
Anyway, with a bit memoization steps, this question is easy to solve. O(n^2), O(n).
Playable code at
ideone.com/qFgocO
int countHelper(vector<vector<char>>& matrix, char targetColor, pair<int, int> dir, int onepoint=3) {
if (!matrix.size()  !matrix[0].size()) return 0;
int rowcount(matrix.size()), colcount(matrix[0].size());
int ret = 0;
vector<vector<int>> count(rowcount, vector<int>(colcount, 0));
for (int col = colcount  1; col >= 0; col) { // col goes next
for (int row = rowcount  1; row >= 0; row) { // row goes first
if (matrix[row][col] != targetColor) continue;
// check the next one along the line.
count[row][col] = 1;
int nextrow(row + dir.first), nextcol(col + dir.second);
if (!(nextrow < 0  nextrow == rowcount  nextcol < 0  nextcol == colcount))
count[row][col] += count[nextrow][nextcol];
ret += (count[row][col] >= onepoint);
}
}
return ret;
}
bool winner(vector<vector<char>>& matrix) {
int red = countHelper(matrix, 'r', pair<int, int>{1, 1}) + \
countHelper(matrix, 'r', pair<int, int>{0, 1}) + \
countHelper(matrix, 'r', pair<int, int>{1, 1}) + \
countHelper(matrix, 'r', pair<int, int>{1, 0});
int black = countHelper(matrix, 'b', pair<int, int>{1, 1}) + \
countHelper(matrix, 'b', pair<int, int>{0, 1}) + \
countHelper(matrix, 'b', pair<int, int>{1, 1}) + \
countHelper(matrix, 'b', pair<int, int>{1, 0});
return red > black;
}

XiaoPiGu
December 11, 2014 Thanks for this question, I went back and reviewed GCD. :)
With GCD, this problem is quite simple. There is another hard problem: repeated decimal to fraction(medium), and fraction to repeated decimal(hard).
Code for this problem:
int gcd(int a, int b) { // make sure a > b
if (!(a%b)) return b;
return gcd(b, a%b);
}
pair<int, int> getIrreducibleFraction(double num) {
int denominator = 10000;
int numerator = denominator * num;
int cd;
cd = gcd(numerator, denominator);
numerator /= cd;
denominator /= cd;
return make_pair(numerator, denominator);
}

XiaoPiGu
December 10, 2014 Follow kadane's idea, this is my code.
This one dimensional DP problem has subproblem: Given maxsub[i], to generate largest subarray sum with at least two elements, we only consider: ``maxsub[i] + A[i]``. But to continue ``maxsub`` array, we consider both ``maxsub[i]+A[i]`` and ``A[i]``.
pair<int, int> maxSubArray(int A[], int n) {
if (n <= 1) return pair<int, int>{1, 1};
int ret(INT_MIN), localmax(A[0]);
int ed = 0;
for (int i = 1; i < n; ++i) {
if (ret < localmax + A[i]) {
ret = localmax + A[i];
ed = i;
}
localmax = max(localmax + A[i], A[i]);
}
int sum (A[ed]), st(ed);
do {
sum += A[st];
} while (sum != ret);
return make_pair(st, ed);
}
Playable code at
ideone.com/WMT6uZ

XiaoPiGu
December 10, 2014 8 lines of code. Reverse pascal triangle.
vector<vector<int>> revPascal(vector<int> v) {
vector<vector<int>> ret;
if (!v.size()) return ret;
vector<int> nxt;
for (int i = 0; i < v.size()  1; ++i)
nxt.push_back(v[i] + v[i + 1]);
auto ret2 = revPascal(nxt);
ret2.push_back(v);
return ret2;
}

XiaoPiGu
December 10, 2014 Matrix traversal. Another easy one. Don't care about odd N or even N, just count to N^2.
pair<int, int> nextDir(pair<int, int> dir) {
if (dir == pair<int, int>{0, 1}) return pair<int, int>{1, 0};
if (dir == pair<int, int>{1, 0}) return pair<int, int>{0, 1};
if (dir == pair<int, int>{0, 1}) return pair<int, int>{1, 0};
if (dir == pair<int, int>{1, 0}) return pair<int, int>{0, 1};
}
string spiral(vector<vector<char>> matrix) {
string ret;
if (!matrix.size()) return ret;
if (matrix.size() == 1) {
ret.push_back(matrix[0][0]);
return ret;
}
int row(0), col(matrix.size()  1);
pair<int, int> dir{ 0, 1 };
for (int i = 0; i < matrix.size()*matrix.size(); ++i) {
ret.push_back(matrix[row][col]);
matrix[row][col] = 0;
row += dir.first; col += dir.second;
if (row < 0  col < 0  row == matrix.size()  col == matrix.size()  !matrix[row][col]) {
row = dir.first; col = dir.second;
dir = nextDir(dir);
row += dir.first; col += dir.second;
}
}
return ret;
}

XiaoPiGu
December 09, 2014 I got to admit GK's idea is good. Like what he/she did, DFS+memoization is used.
Some modifications are applied in my code. If the range contains negative numbers, different cases need to be investigated. Other than that, nothing different from GK's code.
Playable code at
ideone.com/o6Qq4z
void stepGen(int pre, int low, int high, vector<int> &res) {
if (pre > high) return;
if (pre >= low && pre <= high) res.push_back(pre);
int lastdigit = pre % 10;
if (pre == 0) {
for (int st = 1; st <= 9; ++st) stepGen(st, low, high, res);
}
else {
if (lastdigit < 9) stepGen(pre * 10 + lastdigit + 1, low, high, res);
if (lastdigit > 0) stepGen(pre * 10 + lastdigit  1, low, high, res);
}
}
vector<int> step(pair<int, int> bound) { // call me
vector<int> res;
if (bound.first > bound.second) return res;
if (bound.first * bound.second < 0) {
stepGen(0, 0, bound.first, res);
for (auto &e : res) e *= 1;
stepGen(0, 1, bound.second, res); // here 1 is used as lower bound since 0 has been
// considered in negative part.
}
else {
if (bound.first < 0) {
stepGen(0, bound.second, bound.first, res);
for (auto &e : res) e *= 1;
}
else stepGen(0, bound.first, bound.second, res);
}
return res;
}

XiaoPiGu
December 09, 2014 * Negative numbers are not palindrome.
* The range is limited to integer range [0, INT_MAX].
bool checkPalindrome(int num, int base) {
string ret;
if (num == 0) return true;
while (num) {
ret.push_back(num % base + '0');
num /= base;
}
int low(0), high(ret.size()  1);
while (low < high)
if (ret[low++] != ret[high]) return false;
return true;
}
void twoTypePalindrome(pair<int, int> range) {
if (range.first > range.second  range.first < 0) return;
for (int num = range.first; num <= range.second; ++num) {
if (checkPalindrome(num, 10) && checkPalindrome(num, 8))
cout << num << ' ';
}
}

XiaoPiGu
December 09, 2014 Just want to make sure, "Disallowed digits can be up to 3, and can be included along with the phone number." You mean disallowed digits cannot be included along with the phone number, right?
* Phone number can start with 0.
* An allowed number can appear multiple times as long as they are not right next to each other.
* If there are multiple 4s, the resulting number must starts with 4. Other 4s follow the above rule.
Algorithm: DFS + pruning.
void helper(int i, int numdigits, set<int>& disallowed, vector<int>& pre, vector<vector<int>>& ret) {
if (i >= numdigits) {
ret.push_back(pre);
return;
}
for (int cand = 0; cand <= 9; ++cand) {
if (disallowed.count(cand)) continue;
if (pre.size() && pre.back() == cand) continue;
if (pre.size() && cand == 4 && pre.front() != 4) continue;
pre.push_back(cand);
helper(i + 1, numdigits, disallowed, pre, ret);
pre.pop_back();
}
}
vector<vector<int>> generate(int numdigits, set<int> disallowed) {
vector<vector<int>> ret;
if (numdigits == 0) return ret;
vector<int> pre;
helper(0, numdigits, disallowed, pre, ret);
return ret;
}

XiaoPiGu
December 09, 2014 This question is similar to question "Mountain point" (CC post id: 5165388048367616).
But this question is quite vague since:
0. How to convert a 2D image to 1D array? In rowmajor order or columnmajor order?
1. It never mentioned the exact definition of "adjacent pixels". (4 adjacent pixels? or 8?)
2. Are border points considered as edge pixels? (This is especially important when W or H is 1.)
3. Do we only consider positive difference or absolute difference? (Image a checker pattern. If absolute difference is used then all pixels are edge pixels.)
No 1, no 0, no duplicates allowed. For fast prod[i>j] calculation, do prod[0>n] / prod[0>i1] / reverseprod[j+1 > n]. O(n^2), O(n).
bool isColorful(int num) {
if (num == 0  num == 1) return true;
if (num < 0) return false;
// num to vector
vector<int> seq;
vector<bool> check(8, false);
// no 0, no 1, no duplicate
while (num) {
if (num % 10 == 0  num % 10 == 1  check[num % 10  2]) return false;
check[num % 10  2] = true;
seq.push_back(num % 10);
num /= 10;
}
int low(0), high(seq.size()  1);
while (low < high) swap(seq[low++], seq[high]);
// calc sequential prod and rev prod.
vector<int> seqprod(seq.size());
seqprod[0] = seq[0];
for (int i = 1; i < seq.size(); ++i) seqprod[i] = seqprod[i  1] * seq[i];
vector<int> revprod(seq.size());
revprod[seq.size()  1] = seq.back();
for (int i = seq.size()  2; i >= 0; i) revprod[i] = revprod[i + 1] * seq[i];
set<int> s;
for (int st = 0; st < seq.size(); ++st) {
for (int ed = st; ed < seq.size(); ++ed) {
// cal prod[st]*prod[st+1]*...*prod[ed]
int leftprod(1), rightprod(1);
if (st > 0) leftprod = seqprod[st  1];
if (ed < seq.size()  1) rightprod = revprod[ed + 1];
if (s.count(revprod[0] / leftprod / rightprod)) return false;
s.insert(revprod[0] / leftprod / rightprod);
}
}
return true;
}

XiaoPiGu
December 08, 2014 void bullsAndCows(string s1, string s2) {
if (!s1.size()  !s2.size()) {
cout << "A  " << s1 << " B  " << s2 << ", bulls  0, cows  0" << endl;
return;
}
bool* charset = new bool[256]();
for_each(s1.begin(), s1.end(), [charset](char c){charset[tolower(c)] = true; });
int bull(0), cow(0);
for (int i = 0; i < s2.size(); ++i) {
if (charset[tolower(s2[i])]) {
if (i < s1.size() && tolower(s1[i]) == tolower(s2[i])) ++bull;
else ++cow;
}
}
cout << "A  " << s1 << " B  " << s2 << ", bulls  " << bull << ", cows  " << cow << endl;
return;
}

XiaoPiGu
December 08, 2014 Goldbach's conjecture:
CCpost id: 5725570532900864, Write a function which takes a number as input, verify if is an even number greater than 2 and also print atleast one pair of prime numbers
Well ordered numbers:
CCpost id: 6284835370827776, you have a number of character sequences. Your task is to generate all possible wellordered word that can be generated by those numbers of given character sequences. And 12998668. Find all the possible passwords, given the length of the password and that it is a well ordered number (159 is wellordered as 1<5<9)
Open Chat in New Window
Just one quick reminder, you know there are 2 dollar bills and half dollar coin, which means the optimal solution for the question is actually not 1 five 4 ones and 3 quarters, but 1 quarter, 1 half dollar, 2 two dollar bills and 1 five dollar bill.
Greedy is definitely recommended for coin change problem using american coin system. But general problems need regular DP. A bottom DP solution is as follow (with traceback)
Playable version at
 XiaoPiGu January 13, 2015