CareerCup

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)

vector<int> minCoin(vector<int> base, int total) {
	sort(base.begin(), base.end());
	vector<int> rec(total+1, 0);
	vector<int> coin(total + 1, 0);
	for (int i = 1; i <= total; ++i) {
		int localMin = INT_MAX-1;
		int candcoin = 0;
		for (auto cand : base) {
			if (i - cand < 0) continue;
			if (rec[i - cand] + 1 < localMin) {
				candcoin = cand;
				localMin = rec[i - cand] + 1;
			}
		}
		rec[i] = localMin;
		coin[i] = candcoin;
	}
	if (rec[total] == INT_MAX - 1) return vector<int>();
	vector<int> ret;
	while (total) {
		ret.push_back(coin[total]);
		total -= coin[total];
	}
	return ret;
}

Playable version at

ideone.com/GfxnF8

Prefix 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.

No 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

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

this solution is O(n)? Try 121314151617181910 this kind of string. You are talking about O(n^3) with that substring comparison * each character * each next occurrence.

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".

Additive 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. Ill-formed 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;
}

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 non-negligible 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...

Greedy 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 counter-examples.
Always keep in mind that set sum problem is a NPC problem. All the DP algorithm posted here are psuedo-polynomial time solutions since when the number of bits used to represent target value increases, the time-space complexity increases exponentially. For more details, also google "set sum problem pseudo polinomial".
Coin-change 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 top-down 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 bottom-up 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

love-oriented.com/pack/

. Playable version for the above four methods can be found at:

ideone.com/KQ2lhU

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

Yes it can. Each time you find a candidate, if it has the same length as the global optimal solution, just use a stack or a vector or whatever kind of container to store it.

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;
}

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, i-1]
		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;
}

What do you mean by saying "broken key digit"? I don't even understand what this question is talking about. Should

numeric_limits<typename>::max()

and

numeric_limits<typename>::min()

suffice?

So many "for"s and "if-else"... 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;
}

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();
}

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.

Basic 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;
}

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) bottom-up 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, j-1] 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;
		}
	}
}

Brute force method. N^3

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;
}

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);
}

105/(10+5) is time. loc of A + time*velocity of A is where they will meet. Third grade math.

If I am asked this kind of questions during an interview, I'll just sigh and walk out. You are not trying to recruit a smart a** but an engineer.

This is not vanilla kadane. Check case: {-1,-2,1000,-1}. Your algorithm returns 1000. But the questions states that the min number of elements in the resulting subarray must be at least 2. In this case, you should return 1000 + (-1) = 999.

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

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;
}

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;
}

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;
}

* 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 << ' ';
	}
}

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;
}

return min(abs(30*hour - 5.5*min), 360 - abs(30*hour - 5.5*min));

3rd grade math.

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 row-major order or column-major 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->i-1] / 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;
}

I don't think they mentioned any kind of "jump over" actions. Besides, jump size is measured by how many times you've jumped instead of how many blocks you have jumped.

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;
}

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 well-ordered 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 well-ordered as 1<5<9)