CareerCup

C++

int* ArrangePeople(int height[], int front[], int n)
{
	for(int i = 0; i < n; i++)
	{
		int temp = height[i];
		for(int j = i; j > front[i]; j--)
		{
			height[j] = height[j-1];
		}
		height[front[i]] = temp;
	}
	for(int i = 0; i < n; i++)
		cout<<height[i]<<" ";
	return height;
}

int heights[5] ={5,4,3,2,1};
int rank[5] ={0, 1, 0, 1, 2};
ArrangePeople(heights, rank, 5);
output: 3 2 1 5 4

in C++, dynamic programming

int Calc(int **V, int v[], int r[], int i, int j, int n)
{
	if(V[i][j]!=0)
		return V[i][j];
	if(i > j)
		return 0;
	else
	{
		V[i][j]=max(Calc(V,v,r,i,j-1,n),Calc(V,v,r,max(i,j+r[j]-n+1), j-r[j]-1, n) + v[j]);
		return V[i][j];
	}
}

int bomb(int v[], int r[], int n)
{
	int** V = new int*[n]; //V[i][j] means the max sum of value from i to j;
	for(int i = 0; i < n; i++)
	{
		V[i] = new int[n];
		memset(V[i], 0, sizeof(int)*n);
		V[i][i] = v[i];
	}
	return Calc(V,v,r,0,n,n);
}

in C++ code, dynamic programming

int LongestPalindrome(string file)
{
	int length = file.length();
	vector<vector<int>> start;
	for(int i = 0; i < length; i++)
	{
		start.push_back(vector<int>());
	}
	start[0].push_back(0);
	int maxLength = 1;
	for(int i = 1; i < length; i++)
	{
		start[i].push_back(i);
		if(file[i-1] == file[i])
			start[i].push_back(i-1);
		for(int j = 0; j < start[i-1].size(); j++)
		{
			int preS = start[i-1][j]-1;
			if(preS>=0)
			{
				if(file[preS] == file[i])
				{
					start[i].push_back(preS);
				}
			}
		}
		int temp = *max_element(start[i].begin(), start[i].end());
		if( temp > maxLength)
			maxLength = temp;
	}
	return maxLength;
}

in c++ code

void columeInExcel(int number)
{
	string dic=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	vector<char> result;
	while(number)
	{
		int low = number%26;
		int high = number/26;
		if(high == 1 && low == 0)
		{
			result.push_back('z');
			break;
		}
		result.push_back(dic[low]);
		number = high;
	}
	for(int i = result.size()-1; i>=0; i--)
		cout << result[i];
	cout << endl;
}

in C++ code

bool concatenateString(string strs[], int n)
{
	int tail[26]={0};
	int count = 0;
	for(int i = 0; i < n; i++)
	{
		tail[strs[i][strs[i].size()-1]-'a']++;
		tail[strs[i][0]-'a']--;
	}
	for(int i = 0; i < 26; i++)
	{
		count += abs(tail[i]);
	}
	if(count == 2)
		return true;
	else
		return false;
}

in C++ code

int FindNumber(int numbers[], int sequence, int start, int end)
{
	if(sequence == start || sequence == end)
		return numbers[sequence];
	int m = numbers[sequence];
	int l = start, r= end;
	while(l < r)
	{
		while(numbers[l]>m)l++;
		while(numbers[r]<m)r--;
		int temp = numbers[l];
		numbers[l] = numbers[r];
		numbers[r] = temp;
	}
	if(sequence >= l) return FindNumber(numbers, sequence, l, end);
	else return FindNumber(numbers, sequence, start, r);
}

int FindMedianNumber(int numbers[], int n)
{
	return FindNumber(numbers, 4, 0, 9);
}

int numbers[9] = {9,2,4,3,8,5,7,6,1};
cout<< FindMedianNumber(numbers, 9);

C++ code solution

void printCharacter(int startX, int startY, int endX, int endY)
{
	int x = endX - startX;
	int direction[4];//right, left, down,up
	if(x < 0)
		direction[1] = -1*x;
	else
		direction[0] = x;
	int y = endY-startY;
	if(y< 0)
		direction[3] = -1*y;
	else direction[2] = y;
	while(direction[0]-->0) cout<<"l";
	while(direction[1]-->0) cout<<"r";
	while(direction[2]-->0) cout<<"d";
	while(direction[3]-->0) cout<<"u";
	cout<<'!';
}


void printMovieName(string name, int n)
{
	int startX = 0; 
	int startY = 0;
	int endX = 0;
	int endY = 0;
	int n = 5;
	for(int i= 0; i < name.size(); i++)
	{
		char charecter = name[i];
		int value = charecter-'a';
		endX = value%n;
		endY = value/n;
		printCharacter(startX, startY, endX, endY);
		startX = endX;
		startY = endY;
	}
}

printMovieName("up", 5)

C++

#include<hash_map>
#include<string>
#include<list>
#include<set>
#include<stack>
using namespace std;

class Relation { 
public:
	string parent; 
	string child; 
public:
	Relation(string parent, string child) { this->parent = parent; this->child = child;} 
};

class TreePrinter { 
public:
	
	
	static void printTree(list<Relation> rs) { 
		hash_map<string, set<string>> myNodes;
		set<string> headers;
		list<Relation>::iterator it = rs.begin();
		for(; it != rs.end(); it++)
		{
			hash_map<string, set<string>>::iterator temp = myNodes.find(it->parent);
			if(temp != myNodes.end())
			{
				temp->second.insert(it->child);
			}
			else
			{
				headers.insert(it->parent);
				set<string> child;
				child.insert(it->child);
				myNodes.insert(pair<string, set<string>>(it->parent,child));
			}
			temp = myNodes.find(it->child);
			if(temp != myNodes.end())
			{
				headers.erase(it->child);
			}
			else if(temp == myNodes.end())
			{
				set<string> child;
				myNodes.insert(pair<string, set<string>>(it->child,child));
			}
		}
		stack<string> printSequece;
		int count = 1;
		//
		for(set<string>::iterator elem = headers.begin(); elem != headers.end(); elem++)
		{
			printSequece.push(*elem);
		}
			while(!printSequece.empty())
			{
				string current = printSequece.top();
				printf("line %d, %s\n",count++, current.c_str());
				printSequece.pop();
				set<string> childs = myNodes[current];
				for(set<string>::iterator child= childs.begin(); child != childs.end(); child++)
				{
					printSequece.push(*child);
				}

			}
	

	} 
};

n*logn + n