CareerCup

If the query is frequent, we can use a Trie to store the array of string. I omit the code of build Trie for simplify

struct Node {

	bool exist;
	Node *children[256];
};

Node *root;

bool dfs(Node *n, const string &s, int pos, int cnt) {
	if (cnt > 1)
		return false;
	if (pos == s.size())
		return cnt == 1;

	for (int i = 0; i < 256; ++i) {
		Node *c = n->children[i];
		if (c != nullptr) {
			if (s[pos] == i && dfs(c, s, pos + 1, cnt) ||
					s[pos] != i && dfs(c, s, pos + 1, cnt + 1))
				return true;
		}
	}
}

bool hasSimilar(const string &s) {
	return dfs(root, s, 0, 0);
}

void sort(int *src, int *dest, int lo, int hi, int *a, int *sp) {
	if (hi <= lo) {
		return;
	}
	int mid = lo + ((hi - lo) >> 1);
	sort(dest, src, lo, mid, a, sp);
	sort(dest, src, mid + 1, hi, a, sp);

	int pos = hi;
	int i = mid, j = hi;
	while (i >= lo && j > mid) {
		if (a[src[i]] < a[src[j]]) {
			dest[pos--] = src[j--];
		}
		else {
			sp[src[i]] += hi - j;
			dest[pos--] = src[i--];
		}
	}

	while (i >= lo) {
		sp[src[i]] += hi - mid;
		dest[pos--] = src[i--];
	}
	while (j > mid)
		dest[pos--] = src[j--];
}

int maxSurpasser(int *a, int n) {
	int *index = new int[n];
	int *sp = new int[n];
	int *buf = new int[n];
	memset(sp, 0, sizeof(int) * n);
	for (int i = 0; i < n; ++i)
		index[i] = i;
	memcpy(buf, index, sizeof(int) * n);

	sort(buf, index, 0, n - 1, a, sp);

	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, sp[i]);

	return ans;
}

struct Node {
	Node(int v) : val(v) {}

	int val;
	Node *left, *right;
};

int findClosestValue(Node *root, int x) {
	assert(root != nullptr);

	int ans;
	int diff = MAXI;
	while (root != nullptr) {
		if (root->val == x) {
			return x;
		}
		else if (root->val > x) {
			if (root->val -x < diff) {
				ans = root->val;
				diff = ans - x;
				root = root->left;
			}
		}
		else {
			if (x - root->val < diff) {
				ans = root->val;
				diff = x - ans;
				root = root->right;
			}
		}
	}

	return ans;
}

It's really a nice solution. I think it needn't to judge "a <= A[i] && A[i] <= b".

We can use dfs to solve this problem. Code as follows, assume that V is the number of vertex.

static const int V = 100010;

vcetor<int> G[V];
bool visited[V];

void dfs(int u, int par, int grand, vector<vector<int> > &ans) {
	visited[u] = true;
	for (int v : G[u]) {
		if (v == grand) {
			ans.push_back({u, par, grand});
		}
		else if (!visited[v])
			dfs(v, u, par, ans);
	}
}

vector<vector<int> > Triangles() {
	vector<vector<int> > ans;
	for (int i = 0; i < V; ++i) {
		if (!visited[i])
			dfs(i);
	}

	return move(ans);
}

It's really a nice solution, same with me. But it cannot handle uint32t, I think.

Provide another idea, we can process this problem like son.

struct Node {
	Node(const string &v) : val(v) {}
	
	string val;
	vector<Node*> sons;
};


void doMarshal(Node *root, string &data) {
	if (root == nullptr)
		return;
	data.push_back('{');
	data += root->val;
	data.push_back(':');
	for (Node *c : root->sons)
		doMarshal(c, data);
	data.push_back('}');
}

string Marshal(Node *root) {
	string data;
	doMarshal(root, data);
	return data;
}


Node *doUnmarshal(const string &data, string::size_type &pos) {
	if (pos >= data.size())
		return nullptr;
	++pos;
	string::size_type npos = data.find(':', pos);
	Node *root = new Node(data.substr(pos, npos - pos));

	pos = npos + 1;
	while (data[pos] != '}') {
		root->sons.push_back(doUnmarshal(data, pos));
	}
	++pos;
	return root;
}

Node *Unmarshal(const string &data) {
	string::size_type pos = 0;
	return doUnmarshal(data, pos);
}

We can use DP to solve this problem. Define dp[i][j] is the anwer for the first i numbers and the ith number is j, then we have dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 4]

int solve(int n) {

	vector<vector<int> > dp(n, vector<int>(10, 0));
	dp[0][0] = 0;
	for (int i = 1; i < 10; ++i)
		dp[0][i] = 1;

	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int k = 0; k <= j -4; ++k) {
				dp[i][j] += dp[i][k];
			}
		}
	}

	int ans = 0;
	for (int j = 0; j < 10; ++j)
		ans += dp[n - 1][j];

	return ans;
}

It's really a good problem

Maybe we use DP to solve it.

char dp[MAX][MAX][MAX];

vector<int> partition(const vector<int> &a) {
	int n = a.size();
	if (n < 2)
		return a;
	int m = n >> 1;

	int sum = 0;
	for (int x : a)
		sum += x;
	sum >>= 1;

	dp[0][0][0] = 1;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i && j <= m; ++j) {
			for (int k = 1; k <= sum; ++k) {
				if (dp[i - 1][j][k] > 0)
					dp[i][j][k] = 1;
				else if (dp[i - 1][j - 1][k] > 0)
					dp[i][j][k] = 2;
				else
					dp[i][j][k] = 0;
			}
		}
	}

	vector<int> ans;
	while (dp[n][m][sum] == 0)
		--sum;
	int val = dp[n][m][sum];
	while (val > 0) {
		if (val == 2) {
			ans.push_back(a[n - 1]);
			sum -= a[n - 1];
			val = dp[--n][--m][sum];
		}
		else {
			val = dp[--n][m][sum];
		}
	}

	return move(ans);
}

I agree with you. Here is my code.

class BIT {
public:
	BIT(int n) {
		len = n;
		a = new int[n + 1]();
	}

	~BIT() {
		free(a);
	}

	int sum(int i) {
		int ans = 0;
		while (i > 0) {
			ans += a[i];
			i -= i & -i;
		}
		return ans;
	}

	void add(int i, int val) {
		while (i <= len) {
			a[i] += val;
			i += i & -i;
		}
	}


private:
	int *a;
	int len;

};


class Light {
public:
	Light(int n) : bit(n + 1) {}

	bool isOn(int i) {
		return bit.sum(i) & 1;
	}

	void toggle(int start, int end) {
		bit.add(start, 1);
		bit.add(end + 1, -1);
	}

private:
	BIT bit;

};

I thought about the same solution, here is my code

int findLargsetCross(const vector<vector<int> > &matrix) {
	int m = matrix.size();
	if (m == 0)
		return 0;
	int n = matrix[0].size();
	if (n == 0)
		return 0;
	vector<vector<int> > H(m, vector<int>(n, 0)), V(m, vector<int>(n, 0));

	for (int j = 0; j < n; ++j) {
		int i = 0;
		while (i < m) {
			while (i < m && matrix[i][j] == 0)
				++i;
			int s = i;
			while (i < m && matrix[i][j] == 1)
				++i;
			for (int k = s; k < i; ++k)
				H[k][j] = i - s;
		}
	}
	for (int i = 0; i < m; ++i) {
		int j = 0;
		while (j < n) {
			while (j < n && matrix[i][j] == 0)
				++j;
			int s = j;
			while (j < n && matrix[i][j] == 1)
				++j;
			for (int k = s; k < j; ++k)
				V[i][k] = j - k;
		}
	}

	int ans = 0;
	for (int i = 1; i < m - 1; ++i) {
		for (int j = 1; j < n - 1; ++j) {
			if (matrix[i][j] == 1 && matrix[i - 1][j] == 1 && matrix[i + 1][j] == 1 &&
					matrix[i][j - 1] == 1 && matrix[i][j + 1] == 1)
				ans = max(ans, H[i][j] + V[i][j] - 1);
		}
	}

	return ans;
}

But I'm wonder that can the cross has multi row and multi column? If so, Maybe we can use a similar method to solve it

Hi, Sachin. You raised a very good question. I came up with a greedy algorithm as follows, and I used string to represent a large number. Please check me.

string solve(const string &a, const string &b) {
	if (a.size() < b.size())
		return "";
	if (a.size() > b.size()) {
		string ans = a;
		sort(ans.begin(), ans.end());
		return move(ans);
	}

	int st[256] = {0};
	for (char c : a)
		++st[c];

	string ans;
	ans.reserve(b.size());
	for (char c : b) {
		if (st[c] > 0) {
			ans.push_back(c);
			--st[c];
		}
		else {
			char x = c;
			while (++x <= '9' && st[x] == 0);
			if (x <= '9') {
				ans.push_back(x);
				--st[x];
				for (char y = '0'; y <= '9'; ++y) {
					while (st[y]-- > 0)
						ans.push_back(y);
				}
			}
			else {
				ans = "";
			}
			break;
		}
	}
	return move(ans);
}

I think this a DP problem. Define dp[i] is the number of paths from source to level i, then we have dp[i] = m * (dp[1] + dp[2] + ... + dp[i - 1]) = m * dp[i - 1] + m * (dp[1] + dp[2] + ... + dp[i - 2]) = m * dp[i - 1] + dp[i - 1] = (m + 1) * dp[i - 1]

Hi, technoapurva. The problem requires "sorted(initial_array) must equal sorted(array_after_executing_program) "

Hi, kyle. Because if L % x == 0, then x's factors must be L's factors, but the only factor of L is 3, so x is a power of 3

I think this problem is the same as "find the next(previous) integer with the same number of bit set", code as follows:

unsigned int Next(unsigned int x) {
	// test: x = 01101110
	int a = x & ~(x - 1); // a = 00000010
	int b = x + a;		  // b = 01110000
	int c = x & ~b;		  // c = 00001110
	int d = c / a >> 1;   // d = 00000011

	return b | d; // ans = 01110011
}

unsigned int Previous(unsigned int x) {
	// test: x = 01110011
	unsigned int a = x & ~(x - 1);         // a = 00000001
	unsigned int b = x + a;                // b = 01110100
	unsigned int c = x & b;				   // c = 01110000
	unsigned int d = (c & ~(c - 1)) >> 1;  // d = 00001000
	unsigned int e = ~x & b;	           // e = 00000100
	unsigned int f = d / e;				   // f = 00000010
	unsigned int g = e - 1;		           // g = 00000011

	return (c & ~(d << 1)) | d | f * g;	// ans = 01101110
}


unsigned int solve(unsigned int x) {
	unsigned int pre = Previous(x);
	unsigned int next = Next(x);

	return x - pre < next - x ? pre : next;
}

Since the number plus only one, we can simplify the code as follows:

void addOne(vector<int> &a) {
	int i = a.size() - 1;
	while (i >= 0 && a[i] == 9)
		a[i--] = 0;

	if (i < 0) {
		a.push_back(0);
		a[0] = 1;
	}
	else {
		++a[i];
	}
}

Yes, dre. Your solution are the same as me. Rob has raised a good question, you can try to solve it.

Thank you very much, Rob. You are right.

I just offer a thought, not yet optimized the code.

If epoch seconds as indices, maybe we can use "discrete coordinate" to reduce the memory usage. But in this case, we also need to sort the coordinates' array. If the coordinates' array is still large,we can divide the time duration into segments and process each segment. In this case, we need to read the file multiple times.

void* does not support arithmetic, maybe you mean this code:

void *alignAllocate(size_t size, size_t align) {
	int offset = sizeof(void*) + align - 1;
	void *rawPtr = malloc(size + offset);
	if (rawPtr == nullptr)
		return nullptr;

	char *ans = (char*)rawPtr + sizeof(void*);
	ans = (char*)(long(ans + align - 1) & ~(align - 1));
	*((void**)ans - 1) = rawPtr;

	return ans;
}

void alignFree(void *ptr) {
	void *rawPtr = *((void**)ptr - 1);
	free(rawPtr);
}

struct Node {

	Node(int v) : Val(v) {}

	int Val;
	vector<Node*> Children;
};


Node *nextChild(Node *root, Node *curChild) {
	if (curChild == nullptr) {
		return root->Children.empty() ? nullptr : root->Children[0];
	}
	else {
		int i = 0;
		int n = root->Children.size();
		for (; i < n && curChild != root->Children[i]; ++i);
		return i >= n - 1 ? nullptr : root->Children[i + 1];
	}
}

void PostOrder(Node *root) {
	stack<Node*> st;
	Node *pre = nullptr;

	while (root != nullptr || !st.empty()) {
		while (root != nullptr) {
			st.push(root);
			root = root->Children.empty() ? nullptr : root->Children[0];
		}

		root = st.top();

		Node *next = nextChild(root, pre);
		if (next == nullptr) {
			cout << root->Val << "";
			pre = root;
			st.pop();
		}
		root = next;
	}
	cout << endl;
}

I'm wonder that what is the post order of this tree?

0
/ | \
1 2 3
/ | \
4 5 6

It is a classic problem, we can use a cumulative array

static const int MAX = 111225;

int findHeighestMemoryUsageHour() {
	int usagePerHour[MAX] = {0};
	int start, end, usage;
	while (cin >> start >> end >> usage) {
		start -= 10000;
		end -= 10000;
		usagePerHour[start] += usage;
		usagePerHour[end + 1] -= usage;
	}

	for (int i = 1; i < MAX; ++i)
		usagePerHour[i] += usagePerHour[i - 1];

	int res = 0, maxUsage = 0;
	for (int i = 0; i < MAX - 1; ++i) {
		if (usagePerHour[i] > maxUsage) {
			res = i;
			maxUsage = usagePerHour[i];
		}
	}

	return res + 10000;
}

It's a simple DP problem

int NumberOfMatch(string s, string t)
{
	int m = s.size(), n = t.size(), *dp[2];

	dp[0] = new int[n](); dp[1] = new int[n](); dp[0][0] = s[0] == t[0] ? 1 : 0;

	for (int i = 1; i < m; ++i)
	{
		dp[i & 1][0] = dp[(i - 1) & 1][0] + (s[i] == t[0] ? 1 : 0);

		for (int j = 1; j < n; ++j) dp[i & 1][j] = dp[(i - 1) & 1][j] + (s[i] == t[j] ? dp[(i - 1) & 1][j - 1] : 0);
	}

	int ans = dp[(m - 1) & 1][n - 1];  delete[] dp[0]; delete[] dp[1];

	return ans;
}

It is a greedy problem

const int MAXW = 150;

int minCanoes(int A[], int n)
{
	sort(A, A + n);

	int ans = 0, lo = 0, hi = n - 1;

	while (lo < hi)
	{
		if (A[lo] + A[hi] <= MAXW) { ++lo; --hi; }

		else --hi;

		++ans;
	}

	if (lo == hi) ++ans;

	return ans;
}

This is a very classic problem, and a harder one is to find the biggest rectangle instead of square

We can use DP to solve this problem in O(n^2)

void longestSubArray(int A[], int n)
{
	int *dp[2]; for (int i = 0; i < 2; ++i) dp[i] = new int[n];

	int len = 0, s1 = 0, s2 = 0;

	for (int i = n - 1; i >= 0; --i)
	{
		dp[i & 1][i] = 0; dp[i & 1][n - 1] = 1;

		for (int j = n - 2; j > i; --j)
		{
			int tmp = (A[i] > A[j]) == (A[i + 1] > A[j + 1]) ? dp[(i + 1) & 1][j + 1] + 1 : 1;

			if (tmp > j - i) tmp = j - i;

			if (tmp > len)
			{
				len = tmp; s1 = i; s2 = j;
			}

			dp[i & 1][j] = tmp;
		}
	}

	if (len == 0)
	{
		cout << "no answer!" << endl;
	}

	cout << "first subarray: "; for (int i = s1; i < s1 + len; ++i) cout << A[i] << " "; cout << endl;

	cout << "second subarray: "; for (int i = s2; i < s2 + len; ++i) cout << A[i] << " "; cout << endl;
}

int nextSparserNumber(int x)
{
	int ans = 0, mask = 1; x += 1;

	while (x != 0)
	{
		while ((x & 1) == 0)
		{
			x >>= 1; mask <<= 1;
		}

		int cnt = 0;

		while ((x & 1) == 1)
		{
			++cnt; x >>= 1; mask <<= 1;
		}

		if (cnt > 1)
		{
			x += 1;
		}
		else
		{
			ans |= mask >> 1;
		}
	}

	return ans;
}

int longestPositiveSequence(int A[], int n)
{
	int ans = 0, cnt = 0;

	for (int i = 0; i < n; ++i)
	{
		if (A[i] > 0) ++cnt;

		else
		{
			ans = max(ans, cnt); cnt = 0;
		}
	}

	return ans;
}

string IntegerDivide(int num, int den, int n)
{
	if (num == MINI && den == -1) throw overflow_error("result overflowed");

	ll x = num, y = den; int sign = (x >> 31) == (y >> 31) ? 1 : -1;

	x = abs(x); y = abs(y);

	string integer = to_string(x / y * sign), decimal;

	unordered_map<int, int> st; x %= y;

	while (x != 0 && st.count(x) == 0 && decimal.size() < n)
	{
		st[x] = decimal.size(); x *= 10; decimal += to_string(x / y); x %= y;
	}

	if (x == 0)
	{
		decimal += string(n - decimal.size(), '0');
	}
	else if (st.count(x) != 0)
	{
		string tmp = decimal.substr(st[x]);

		while (decimal.size() < n) decimal += tmp;
	}

	while (decimal.size() > n) decimal.pop_back();

	return decimal.empty() ? integer : integer + "." + decimal;
}

void printAllCombination(const vector<string> &a)
{
	int n = a.size(), i = 0; string s(n, ' '); vector<int> index(n, -1);

	while (i >= 0)
	{
		++index[i];
		
		if (index[i] > 0)
		{
			while (index[i] < a[i].size() && a[i][index[i]] == a[i][index[i] - 1]) ++index[i];
		}

		if (index[i] < a[i].size())
		{
			s[i] = a[i][index[i]];

			if (i == n - 1) cout << s << endl;

			else ++i;
		}
		else index[i--] = -1;
	}
}

int *A, n, t;

void print(const vector<int> &a)
{
	for (int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;
}

void dfs(int i, int sum, vector<int> &a)
{
	if (sum == t)
	{
		do
		{
			print(a);
		}
		while (next_permutation(a.begin(), a.end()));

		return;
	}

	a.push_back(0);

	for (int j = i; j < n && sum + A[j] <= t; ++j)
	{
		a.back() = A[j]; dfs(j, sum + A[j], a);
	}

	a.pop_back();
}

void printPermutationsEqualtoSum(int A[], int n, int target)
{
	::A = A; ::n = n; t = target;

	sort(A, A + n);

	vector<int> a;

	dfs(0, 0, a);
}

int findMaxSteps(int n, int k)
{
	int ans = (n * (n + 1)) >> 1, x = (sqrt(8 * k + 1) - 1) / 2;

	return (x * (x + 1)) >> 1 == k ? ans - 1 : ans;
}

void print(const vector<int> &a)
{
	for (int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;
}

void dfs(int i, int cnt, int n, vector<int> &a)
{
	if (cnt == 0)
	{
		print(a); return;
	}

	if (n - i + 1 < cnt) return;

	a.push_back(i); dfs(i + 1, cnt - 1, n, a); a.pop_back();

	dfs(i + 1, cnt, n, a);
}

void printKSetOfN(int n, int k)
{
	assert(n > 0 && k > 0 && k <= n);

	vector<int> a;

	dfs(1, k, n, a);
}

It is just a segment prime seive

typedef long long ll;

bool is_prime_aux[1000001];
bool is_prime[100001];

ll segment_seive(ll a, ll b)
{
	for (ll i = 0; i * i <= b; ++i) is_prime_aux[i] = true;
	
	for (int i = 0; i <= b - a; ++i) is_prime[i] = true;

	for (ll i = 2; i * i <= b; ++i)
	{
		if (is_prime_aux[i])
		{
			for (ll j = 2 * i; j * j <= b; j += i) is_prime_aux[j] = false;

			for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) is_prime[j - a] = false;
		}
	}

	ll sum = 0;

	for (int i = 0; i <= b - a; ++i) sum += is_prime[i] ? a + i : 0;

	return sum;
}

I think the function prototype should be "ListNode *insert(ListNode *head, int value)", becuase it may modify the list's head

Is "1.2e10" legal?

vector<int> firstKthNumbers(int A[], int n, int k)
{
	assert(A != NULL && n > 0 && k > 0);

	unordered_map<int, int> st;

	for (int i = 0; i < n; ++i) ++st[A[i]];

	int *cnt = new int[n + 1]; memset(cnt, -1, sizeof(int) * (n + 1));

	for (auto &p : st) cnt[p.second] = p.first;

	vector<int> ans;

	for (int i = n; i >= 0 && k > 0; --i)
	{
		if (cnt[i] >= 0) { ans.push_back(cnt[i]); --k; }
	}

	return move(ans);
}

typedef pair<int, int> Node;

vector<int> *G; bool *onStack, *judge, *visited; int V;

void dfs(int u, int p, int d)
{
	visited[u] = true; onStack[u] = true; if (d != 2) judge[u] = false;

	++d;

	for (int v : G[u])
	{
		if (v != p && !onStack[v]) dfs(v, u, d);
	}

	onStack[u] = false;
}

vector<Node> findCriticalNodes(vector<int> G[], int V)
{
	::G = G; ::V = V;

	onStack = new bool[V]; judge = new bool[V]; visited = new bool[V];

	vector<Node> ans;

	for (int u = 0; u < V - 1; ++u)
	{
		memset(onStack, false, V); memset(judge, true, V); memset(visited, false, V);

		dfs(u, -1, 0);

		for (int v = 0; v < V; ++v)
		{
			if (visited[v] && judge[v]) ans.push_back(Node(u, v));
		}
	}

	return move(ans);
}

int minSwaps(int A[], int B[], int n)
{
	assert(A != NULL && B != NULL && n > 0);

	int ans = 0, rb = 1;

	for (int i = 0; i < n; ++i)
	{
		if (A[i] != B[i])
		{
			if (rb <= i) rb = i + 1;

			while (rb < n && A[rb] != B[i]) ++rb;

			if (rb >= n) throw logic_error("there is no solution");

			ans += rb - i; A[rb] = A[i]; ++rb;
		}
	}

	return ans;
}

string rangeOfNumbers(int A[], int n)
{
	assert(A != NULL && n > 0);

	set<int> st(A, A + n); string ans;

	while (!st.empty())
	{
		int s = *st.begin(), t = s;

		while (st.count(t + 1) > 0) st.erase(++t);

		st.erase(s);

		if (!ans.empty()) ans.push_back(',');

		ans += to_string(s);

		if (t != s)
		{
			ans += "-"; ans += to_string(t);
		}
	}

	return move(ans);
}

bool isLocal(int A[], int i)
{
	int x = A[i - 1] - A[i], y = A[i + 1] - A[i];

	return x >> 31 == y >> 31;
}

int findLocalMinOrMax(int A[], int n)
{
	assert(A != NULL && n > 0);

	int differ = abs(A[n - 1] - A[0]);

	if (differ >= n) throw logic_error("invalid input");

	if (differ == n - 1) throw logic_error("there is no local min or max");

	int offset = (n - 1 - differ) >> 1;

	return isLocal(A, offset) ?  A[offset] : A[n - 1 - offset];
}

This is the cognate problem of "caculate the number of inversion pair", as to
1 <= A[i] <= 100000, we can use the Binary Indexed Tree.

const int SIZE = 100001;

class BIT
{
public:
	BIT()
	{
		memset(a, 0, SIZE * sizeof(int));
	}

	void update(int i, int x)
	{
		while (i <= SIZE)
		{
			a[i] += x; i += i & -i;
		}
	}

	int query(int i)
	{
		int ans = 0;

		while (i > 0)
		{
			ans += a[i]; i -= i & -i;
		}

		return ans;
	}

private:
	int a[SIZE];

};

int Optimal(int A[], int n)
{
	assert(A != NULL && n > 0);

	BIT bit; int ans = 0;

	for (int i = n - 1; i >= 0; --i)
	{
		ans = max(ans, bit.query(A[i])); bit.update(A[i], 1);
	}

	return ans;
}

vector<string> wildcardMatch(string &s)
{
	int n = s.size(); vector<int> indexs; vector<string> ans;

	for (int i = 0; i < n; ++i) if (s[i] == '?') indexs.push_back(i);

	n = indexs.size();

	for (int mask = 0; mask < (1 << n); ++mask)
	{
		int tmp = mask;

		for (int i = 0; i < n; ++i, tmp >>= 1) s[indexs[i]] = (tmp & 1) ? '1' : '0';

		ans.push_back(s);
	}

	return move(ans);
}

typedef unordered_map<string, vector<string> > Tree;

typedef unordered_map<string, int> NumTable;

void calc(const string &s, Tree &st, NumTable &ans)
{
	if (ans.count(s) > 0) return;

	int cnt = 0;

	for (const auto &t : st[s])
	{
		calc(t, st, ans); cnt += ans[t] + 1;
	}

	ans[s] = cnt;
}

NumTable numOfEmployees(const unordered_map<string, string> &dic)
{
	NumTable ans; Tree st;

	for (auto &p : dic)
	{
		if (p.first == p.second) continue;

		st[p.second].push_back(p.first);
	}

	for (auto &p : st) calc(p.first, st, ans);

	return ans;
}

char findFirstUniqueCharacter(const string &s)
{
	unordered_set<char> st; map<int, char> index; map<char, int> rank;

	int cnt = 0;

	for (char c : s)
	{
		if (st.count(c) > 0)
		{
			if (rank.count(c) > 0)
			{
				int i = rank[c]; rank.erase(c); index.erase(i);
			}
		}
		else
		{
			st.insert(c); rank[c] = ++cnt; index[cnt] = c;
		}
	}

	return index.begin()->second;
}

pair<int, int> getPeriodOfMaxCount(int start[], int end[], int count[], int n)
{
	assert(start != NULL && end != NULL && count != NULL && n != 0);

	int minTime = *min_element(start, start + n), maxTime = *max_element(end, end + n), len = maxTime - minTime + 2;

	int *sum = new int[len]();
	
	for (int i = 0; i < n; ++i)
	{
		sum[start[i] - minTime] += count[i]; sum[end[i] - minTime + 1] -= count[i];
	}

	int maxCount = sum[0], s = 0, t = 0;

	for (int i = 1; i < len;)
	{
		sum[i] += sum[i - 1];

		if (sum[i] > maxCount)
		{
			maxCount = sum[i]; s = i;
			
			while (i < len - 1 && sum[++i] == 0);

			t = i - 1; sum[t] = maxCount;
		}
		else ++i;
	}

	delete[] sum;

	return make_pair(minTime + s, minTime + t);
}

int findFirstDuplicatedNumber(int A[], int n)
{
	int i = 0;

	while (i < n)
	{
		if (A[i] == i) ++i;
		
		else
		{
			if (A[i] == A[A[i]]) return A[i];

			else swap(A[i], A[A[i]]);
		}
	}

	return -1;
}

Suppose that we have a function that return a random number belong to internal [0,1), then we can draw a fuction as fllow:

void shuffle(int A[], int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int offset = random() * (n - i);
		swap(A[i], A[i] + offset);
	}
}