CareerCup

I could use a modified dijkstra's algorithm. Initially we assign each entry to be 0 and 1 where there is a path from S to pi. And then we get the group of largest distance we have, and visit each of the points and try to modify the largest distance in our array so we have a new distance array from S to each node in our graph. This step is crucial, consider all situations we might encounter and you will find it is correct. Finally, when we will find our destination point would be the largest distance in the array if the point is a sink.

void intersection(vector<int> list1, vector<int> list2) {

	map<int, int> hashTable;
	map<int, int>::iterator it;
	for (int i=0; i<list1.size(); i++) {
		it = hashTable.find(list1[i]);
		if (it == hashTable.end()) hashTable.insert(pair<int, int>(list1[i], 1));
		else it->second++;
}
	for (int i=0; i<list2.size(); i++) {
	it = hashTable.find(list2[i]);
	if (it != hashTable.end() && it->second != 0) {
		it->second--;
		std::cout<<list2[i]<<endl;
}
}
}

since the integer has millions of digits, we can divide it by 1000 or more, and base on the remainder of 1000, we can use this remainder as an index of our pre-stored string-array to get the corresponding string, it sacrifices the memory for time.

void flip(char *bytes, int width, int height) {
	
	for (int h=0; h<height; h++) {
	int i = h*width;
	int j= h*(width+1)-1;
	while (i<j) {
		char t = bytes[i];
		bytes[i] = bytes[j];
		bytes[j] = t;
		i++; j--;
}
}
}

len/wid parameters mean how many pixels for a horizontal/vertical line?

using hash table to store the query body and occurrence, it can be done in O(n) time. And then keep a min heap of 10 capacity to find the top 10. If the new one is bigger than the top of our min heap, it can replace the min heap top and keep the min heap property in O(log10). The total time would be O(n+n*log10), at most O(n)

The condition in this problem is not enough. If the walking ways are limited to right and down, it can be achieved by DP, where M[i][j] = M[i+1][j] + M[i][j+1]. However, if it is allowed to walk in all direction, it would be solved by DFS with a visited history of all points, which is analog to a brutal force algorithm.

we can start from the dictionary. Basically, we would build a word tree that consists of all the dictionary words, and then go from our string to find whether there is a path in the word tree and the end of our string is actually an end of a dictionary word.

void phoneNumbers(const string &dialString, string prefix) {

	if (diaString.length() == prefix.length()) {
		std::cout<<prefix<<endl;
	return;
}
	for (int i=0; i<9; i++) 
		phoneNumbers(diaString, prefix+(‘0’+i));
}

string longestCommonSubsequence(string s1, string s2) {

	multimap<char, string> suffixTree;
	int longest = 0;
	string lstr = “”:
	for (int i=0; i<s1.length(); i++) {
		suffixTree.insert(pair<char, string>(s1[i], s1.substr(i)));
}
multimap<char, string>::iterator it;
for (int i=0; i<s2.length(); i++) {
	it = suffixTree.find(s2[i]);
	if (it == suffixTree.end()) continue;
	pair<multimap<char, string>::iterator, multimap<char, string>::iterator> range = suffixTree.equal_range(s2[i]));
	
	for (it = range.first; it != range.second; it++) {
	int p=0, q=i;
	while(p<it->second.length() && q<s2.length()) {
		if (it->second[p] != s2[q]) break;
		p++; q++;
}
if (longest < p) { longest = p; lstr = it->second.substr(0, p);}
} 
}
return lstr;
}

Once I got this done, I found that it was possible to get using dynamic programming with the following formula. 
	M[i, j] = max(M[i-1, j-1], M[i+1, j], M[i, j+1]) if (S1[i] == S2[j]) 
		  = max(M[i+1, j], M[i, j+1]) if (S1[i] != S2[j])
	M[i, j] refers to the ith position of S1 and jth position of S2

void subsequence(const int *list, int size) {
	
	if (size == 0 || size == 1)
		return;
	int *M = new int[size];
        int *Post = new int[size];
        for (int i=0; i<size; i++) {
	       M[i] = 1;
	       Post[i] = -1;
         }
	M[size-1] = 1;
        Post[size-1] = -1;
        int front = 0;
        int longest = 0;
        for (int i=size-2; i>=0; i--) {
		int max = 0;
                for (int j=i+1; j<size; j++) {
			if (list[j] >= list[i] && max < M[j]+1) {
				max = M[j]+1;
				Post[i] = j;
				if (longest < max) {
					longest = max;
					front = i;
                               }
                      }
               }
          }

          while(front != -1) {
	         cout <<list[front]<<endl;
	         front = Post[front];
           }
           delete M;
           delete F;
}

Sort on B first and then sort on A, it is a radix sorting

void sortString(string &word, const string &dictionary) {

	map<char, int> m;
	for (int i=0; i<word.size(); i++) {
	map<char, int>::iterator it = map.find(word[i]);
	if (it == map.end()) word.insert(pair<char, int>(word[i], 1));
	else it->second += 1;
}
int k = 0;
for (int i=0;i<dictionary.size()) {
	map<char, int>::iterator it = map.find(dictionary[i]);
	if (it != map.end()) {
		word.replace(word.begin()+k, it->second, dictionary[i]);
		k += it->second;
}
}
return;
}

int GetMutualMedian(int *A, int *B, int n, int m, int pos) {
	
if (n == -1) return B[pos];
if (m == -1) return A[pos];

int amid = pos/2 > n ? n : pos/2;
	int bmid = pos/2 > m ? m : pos/2;
	if (A[amid] > B[bmid]) {
		if (bmid == m) return GetMutualMedian(A, B, n, -1, pos-bmid);
		else return GetMutualMedian(A, B+bmid, amid, m-bmid, pos/2);
}
	else if (A[amid] < B[bmid]) {
		if (amid == n) return GetMutualMedian(A, B, -1, m, pos-amid);
		else return GetMutualMedian(A+amid, B, n-amid, bmid, pos/2);
}
	else {
		if (n >= pos/2 && m >= pos/2) return A[amid];
		else if (pos/2 > n) return GetMutualMedian(A, B, -1, m, pos-n);
		else (pos/2 > m) return GetMutualMedian(A, B, n, -1, pos-m);
	}
}

string sequence(const string &word, char &cur, int &index) {
	string ret = “”;
	if (word.length() == 0)
		return ret;
	if (index >= word.length())
		return ret;
	if (cur == word[index])
		ret += ‘!’;
	else {
		int curValue = (int)(cur-’a’+1);
		int destValue = (int)(word[index]-’a’+1);
		ret += string((curValue/5-destValue/5)>0 ? ‘u’ : ‘d’, (curValue/5-destValue/5));
		ret += string((curValue%5-destValue%5)>0 ? ‘l’ : ‘r’, (curValue%5-destValue%5));
		ret += ‘!’;
	}
	cur = word[index];
	index ++;
	if (index >= word.length())
		return ret;
	else return ret+sequence(word, cur, index);

}

Hi, basically, nothing should be modified for the original string, since the new char '\ooo' would be the same as the previous char.