CareerCup

We can use a hashtable to record last complete time of every task:

def getCompleteTime(tasks, waitBetweenRepeatedTask):
	time = 0	# clock
	record = {}	# record[t] represents last time t is done
	for t in tasks:
		if t in record and time - record[t] < waitBetweenRepeatedTask:
			# wait the cooldown
			time = record[t] + waitBetweenRepeatedTask
		# execute t
		time += 1
		# update record
		record[t] = time
	return time

# tests
tasks = [1, 2, 3, 4]
k = 3
print(getCompleteTime(tasks, k))

tasks = [1, 2, 1, 4]
k = 3
print(getCompleteTime(tasks, k))

tasks = [1, 1, 1, 1]
k = 3
print(getCompleteTime(tasks, k))

tasks = [1, 2, 3, 1, 3, 2, 4, 1]
k = 4
print(getCompleteTime(tasks, k))

We may add a flag for each node whether its children have been visited, like this:

void PostOrderTraverse(Node* root)
{
	if(!root) return;
	
	typedef pair<Node*, bool> PNB;
	stack<PNB> st;
	st.push(PNB(root, false));
	while(!st.empty()){
		PNB& x = st.top();
		if(x.second){//x's children have been visited, time to visit x
			cout << x.first->val;
			st.pop();
		}
		else{//x's children have not been visited, do them first
			x.second = true;//change the flag
			for(Node* p : x.first->children){//add children to stack
				st.push(PNB(p, true));
			}
		}
	}
}

@Scott
I agree with the thought. You may need to check f[j-1] before taking it into account, what if f[j-1] is Integer.MAX_VALUE.
Code in python:

import math

def sliceIntoMultiplesOf5(s):
	def isPowerOf5(s):
		x = int(s, 2)
		n = int(math.log2(x) / math.log2(5))
		return 5 ** n == x

	# initialize
	n = len(s)
	f = [-1] * n
	# dp
	for i in range(n):
		if isPowerOf5(s[:i+1]):
			f[i] = 1
			continue
		for j in range(i):
			# pieces do not start with 0
			if f[j] == -1 or s[j+1] == '0' or not isPowerOf5(s[j+1:i+1]):
				continue
			if f[i] == -1:
				f[i] = f[j] + 1
			else:
				f[i] = min(f[i], f[j] + 1)
	# result
	return f[n-1]


# test case
strList = [
"101101101",
"1111101",
"110011011",
"1000101011",
"111011100110101100101110111" 
]

for s in strList:
	print(sliceIntoMultiplesOf5(s))

In sorted array, we can locate any number in O(logn) time. By finding the first the target's first position and last position, we can count its occurrence in O(logn) time.
If we can use C++ standard library <algorithm>, then the answer is simple:

int count_in_sorted_array(int arr[], int n, int x)
{
    return upper_bound(arr, arr + n, x) - lower_bound(arr, arr + n, x);
}

If we are not supposed to use library, the subfunctiones go like this:

def lower_bound(arr, x):
	"""
	return the first position in the sorted arr, on which the value is no smaller than x
	return len(arr) if no such value exists
	"""
	if not arr:
		return 0

	# check front
	l = 0
	if arr[0] >= x:
		return 0

	# check back
	r = len(arr)
	if arr[r-1] < x:
		return r

	# binary search, keep arr[r] >= x and arr[l] < x
	while l + 1 < r:
		m = (l + r) // 2
		if arr[m] >= x:
			r = m
		else:
			l = m
	return r

def upper_bound(arr, x):
	"""
	return the first position in the sorted arr, on which the value is larger than x
	return len(arr) if no such value exists
	"""
	if not arr:
		return 0

	# check front
	l = 0
	if arr[0] > x:
		return 0

	# check back
	r = len(arr)
	if arr[r-1] <= x:
		return r

	# binary search, keep arr[r] > x and arr[l] <= x
	while l + 1 < r:
		m = (l + r) // 2
		if arr[m] > x:
			r = m
		else:
			l = m
	return r

def count_in_sorted_array(arr, x):
	return upper_bound(arr, x) - lower_bound(arr, x)

# test case
arr = [1, 1, 2, 3, 3, 3, 4, 5]
print(count_in_sorted_array(arr, 1))
print(count_in_sorted_array(arr, 2))
print(count_in_sorted_array(arr, 3))
print(count_in_sorted_array(arr, 4))
print(count_in_sorted_array(arr, 5))

@Lake096
If still wants a solution with O(1) memory in modulo M, the best I can see is O(NM) time, applying the same rules as above code: 1st run place those with reminder 0, 2nd with reminder 1, the M-1 times with reminder M-2.
If we can use O(N) memory, using a hashtable we can fix it with O(N) time.

Python code with explanation:

def SortByModulo3(arr):
	n = len(arr)
	# in first run place all numbers with reminder 0
	nex = 0
	for i in range(n):
		if arr[i] % 3 == 0:
			arr[nex], arr[i] = arr[i], arr[nex]
			nex += 1
	# in second run place all numbers with reminder 1
	for i in range(nex, n):
		if arr[i] % 3 == 1:
			arr[nex], arr[i] = arr[i], arr[nex]
			nex += 1

# test case
arr = [1, 2, 3, 4, 5]
SortByModulo3(arr)
print(arr)

If we do not take letter repetition into account, then a permutation method will almost do all the work. If we can use a library function, the C++ next_permutation function is good enough.

A row means all those nodes with the same depth ? Level traverse using a queue ?

We might also keep a record of the second best choice when making a decision:

TreeNode* findMaxLessThanOrEqualTo(TreeNode* p, int x, TreeNode* pSecondBest = NULL)
{
	if(p == NULL) return pSecondBest;
	if(p->val == x) return p;

	if(p->val > x) return findMaxLessThanOrEqualTo(p->left, x, pSecondBest);
	else if(pSecondBest != NULL && pSecondBest->val > p->val){
		return findMaxLessThanOrEqualTo(p->right, x, pSecondBest);
	}
	else return findMaxLessThanOrEqualTo(p->right, x, p);
}

The problem is just to build the staff tree and print it as a directory?

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;

public class CompanyTree {
	private static String levelPrefix = "    ";
	private HashMap<Integer, Employ> staff = new HashMap<Integer, Employ>();
	
	class Employ{
		private int id;
		private String name;
		private int superiorId;
		private Set<Integer> subordinateIds;
		
		public Employ(int id, String name, int superiorId){
			this.id = id;
			this.name = name;
			this.superiorId = superiorId;
			this.subordinateIds = null;
		}
		public int getId(){
			return id;
		}
		public String getName(){
			return name;
		}
		public int getSuperiorId(){
			return superiorId;
		}
		public void addSubordinate(int id){
			if(subordinateIds == null)
				subordinateIds = new HashSet<Integer>();
			subordinateIds.add(id);
		}
		public void showTeam(int level){
			for(int i = 0; i < level; ++i) System.out.print(levelPrefix);
			
			Employ e = staff.get(id);
			System.out.println(e.getName());
			
			if(subordinateIds != null){
				Iterator<Integer> iter = subordinateIds.iterator();
				while(iter.hasNext()){
					Integer ID = iter.next();
					staff.get(ID).showTeam(level + 1);
				}
			}
		}
	}
	
	private void setTeams(){
		Iterator<Entry<Integer, Employ>> iter = staff.entrySet().iterator();
		while(iter.hasNext()){
			Entry<Integer, Employ> entry = iter.next();
			Employ superior = staff.get(entry.getValue().getSuperiorId());
			if(superior != null) superior.addSubordinate(entry.getKey());
		}
	}
	public void addEmploy(int id, String name, int superiorId){
		staff.put(id, new Employ(id, name, superiorId));
	}
	public void show(){
		setTeams();
		
		Iterator<Entry<Integer, Employ>> iter = staff.entrySet().iterator();
		while(iter.hasNext()){
			Entry<Integer, Employ> entry = iter.next();
			Employ e = entry.getValue();
			if(e.getSuperiorId() == -1)	e.showTeam(0);
		}
	}
	
	public static void main(String[] args) throws IOException{
		String filePath = "input.txt";
		BufferedReader br = new BufferedReader(new FileReader(filePath));
		
		String line;
		CompanyTree company = new CompanyTree();
		while((line = br.readLine()) != null){
			String[] arr = line.split(" +");
			if(arr[2].equals("Null")) company.addEmploy(Integer.parseInt(arr[0]), arr[1], -1);
			else company.addEmploy(Integer.parseInt(arr[0]), arr[1], Integer.parseInt(arr[2]));
		}
		
		company.show();
	}
}

@Anonymous, it's to figure out how many ways there are to decode the number string into a legal letter string.

DP formula:
if s[i] == 0, dp[i] = 0
else if s[i] <= 2 && s[i+1] <= 6, dp[i] = dp[i+1] + dp[i+2]
else dp[i] = dp[i+1]
Code in C++:

int getWaysToDecode(const string& text){
        //check if head decodable
        if(text.empty() || text[0] == '0') return 0;
        //if single character
        if(text.size() == 1) return 1;
        
        int len = text.size(), i;
        int* dp = new int[len + 1];
        //check if memory allocation failed
        if(dp == NULL) return -1;
        dp[len] = 1;
        dp[len-1] = text[len-1] > '0';
        for(i = len-2; i >= 0; --i){
            if(text[i] > '0'){
                //we can decode text[i] as a one-code word
                dp[i] = dp[i+1];
                //try to decode text[i,i+1] as a two-code word
                if(text[i] <= '2' && text[i+1] <= '6') dp[i] += dp[i+2];
            }
            else dp[i] = 0;
        }
        //free memory before return
        len = dp[0];
        delete[] dp;
        return len;
    }

The thought is backtrace, following is code in C with easy-to-understand comments:

#include <stdio.h>
#define MAX_PAIR  20

void printAllPairs(char s[], int left, int right, int pair)
{
//check if all '(' and ')' have been used up
    if(left == pair && right == pair){
        s[left + right] = '\0';
        puts(s);
        return;
    }
//try to let current position be '('    
    if(left < pair){
        s[left + right] = '(';
        printAllPairs(s, left + 1, right, pair);
    }
//try to let current position be ')' 
    if(left > right){
        s[left + right] = ')';
        printAllPairs(s, left, right + 1, pair);
    }
}

int main()
{
    char s[MAX_PAIR * 2 + 1];
    int  pair = 10;
    
    printAllPairs(s, 0, 0, pair);
    return 0;
}

We may use DP, following is code in Java:

public class RegularMatcher {
	private static boolean isMatching(char a, char b){
		return a == b || b == '?' || a == '?';
	}
	private static boolean isMatching(String text, String patten){
		int tlen = text.length(), plen = patten.length();
	/* step 1: allocate memory to store states */
		boolean[][] dp = new boolean[tlen + 1][plen + 1];//all false initially
	/* step 2: initialize */
		dp[tlen][plen] = true;
	/* step 3: DP */
		for(int i = tlen - 1; i >= 0; --i){
			char t = text.charAt(i);
			for(int j = plen - 1; j >= 0; --j){
				char p = patten.charAt(j);
				if(p != '*')
					dp[i][j] = isMatching(t, p) && dp[i+1][j+1];
				else
					dp[i][j] = isMatching(t, patten.charAt(j-1)) && 
					           (dp[i+1][j+1] || dp[i+1][j]);
			}
		}
	/* step 4: return result */
		return dp[0][0];
	}
	public static void main(String[] args){
		System.out.println(isMatching("abcd", "ab?d"));
		System.out.println(isMatching("abccdddef", "ab?*f"));
		System.out.println(isMatching("abccd" , "ab?*ccd"));
	}
}

We may divide the problem into two parts:
(1)mix each subtree according to the colors of nodes
(2)try to concetrate those nodes whose children have same color.
Following is Code in C:

/*********************** definitions **************************/
#define SCREEN_DIVISION	4
enum Color{
	unknown,
	white,
	black	
};
typedef struct ScreenNode{
	Color color;
	struct ScreenNode* child[SCREEN_DIVISION];
} ScreenNode;
/********************** general function ***********************/
int isLeaf(const ScreenNode* p)
{
	if(!p) return false;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(p->child[i]) return 0;
	}
	return 1;
}
void freeChildren(ScreenNode* parent)
{
	if(!parent) return;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(parent->child[i]){
			free(parent->child[i]);
			parent->child[i] = NULL;
		}
	}
}
ScreenNode* cloneScreen(const ScreenNode* p)
{
	if(!p) return NULL;

	ScreenNode* t = (ScreenNode*)malloc(sizeof(ScreenNode));
	t->color = p->color;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		t->child[i] = cloneScreen(p->child[i]);
	}
	return t;
}
/******************* get overlapped screen *********************/
ScreenNode* mixLeafWithTree(const ScreenNode* leaf, const ScreenNode* tree)
{
	if(leaf->color == Color.black) return cloneScreen(leaf);
	else return cloneScreen(tree);
}
ScreenNode* overlap(const ScreenNode* a, const ScreenNode* b)
{
	if(!a) return cloneScreen(b);
	if(!b) return cloneScreen(a);

	if(isLeaf(a)) return mixLeafWithTree(a, b);
	if(isLeaf(b)) return mixLeafWithTree(b, a);

	ScreenNode* p = (ScreenNode*)malloc(sizeof(ScreenNode));
	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		p->child[i] = overlap(a->child[i], b->child[i]);
	}
	return p;
}
/********************* concentrate subscreen *********************/
int canBeConcentrated(const ScreenNode* parent)
{
/* In given condition: all children are leaves && all children has same color */
	if(parent->child[0] && !isLeaf(parent->child[0])) return parent;
	for(i = 1; i < SCREEN_DIVISION; ++i){
		if(!parent->child[0]) continue;
		if(isLeaf(parent->child[i]) ||
		   parent->child[i]->color != parent->child[i-1]->color
		) return 0;
	}
	return 1;
}
Color getConcentratedColor(const ScreenNode* parent)
{
/* In given condition: parent's color is first child's color */
	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(parent->child[i]) return parent->child[i]->color;
	}
	return Color.unknown;
}
ScreenNode* concentrate(ScreenNode* p)
{
	if(!p || isLeaf(p)) return p;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		p->child[i] = concentrate(p->child[i]);
	}
	if(canBeConcentrated(p)){
		p->color = getConcentratedColor(p);
		freeChildren(p);
	}
	return p;
}

/********************** interface to outside ***********************/
ScreenNode* getOverlappedScreen(const ScreenNode* a, const ScreenNode* b)
{
	return concentrate(overlap(a, b));
}

Code in C++:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main()
{
    int n, digit;
    vector<int> digitFactors;
    
    while(cin >> n){
        if(n < 0) cout << "-1";
        else if(n < 10) cout << n;
        else{
            digitFactors.clear();
            for(digit = 9; n > 1 && digit > 1; ){
                if(n % digit == 0){
                    n /= digit;
                    digitFactors.push_back(digit);
                }
                else --digit;
            }
            if(n > 1) cout << "-1";
            else copy(digitFactors.rbegin(), digitFactors.rend(), 
                      ostream_iterator<int>(cout, ""));
        }
        cout << "\n";
    }
    
    return 0;
}

Could you please explain the problem a little more, perhaps by giving the best strategy for the example given ?

Code in C:

#include <stdio.h>

/*
 * src is the source string which containing target to be replaced
 * offset is where to start this replace action in source string
 * target is target character to be found and replaced
 * candidate is an array of all substitutes
 * n is the size of candidate array
 */
void permutateReplace(char* src, int offset, char target,
                      const char candidate[], int n
)
{
//step 1: find the first target start from offset
    for(; src[offset]; ++offset){
        if(src[offset] == target) break;
    }
//step 2: if found, use candidate to replace it, else print the result out
    if(src[offset]){
        //try to replace target with every candidate
        int i = 0;
        for(; i < n; ++i){
            src[offset] = candidate[i];
            permutateReplace(src, offset + 1, target, candidate, n);
        }
        //restore site
        src[offset] = target;
    }
    else puts(src);
}

int main()
{
    char src[] = "a?b?c?";
    char target = '?';
    char candidate[] = {'0', '1'};
    
    permutateReplace(src, 0, target, candidate, sizeof(candidate)/sizeof(char));
    
    return 0;
}

In BT we have to search every path to get the final result, because we do not know any info about subtrees. But in BST, as long as we find a path meeting the requirement we can stop the searching process:
(0)say now we encounter node p, with its value being p->value, then we perform targetSum -= p->value.
(1)If targetSum < 0 now
our first choice would be going on with the left subtree, because:
if a path exists along the left subtree, it must be shorter than any possible path along the right, since all nodes at left is smaller than those at right.
If there is no such path along the left, then we check p->value, if it is negative, then we go on searching right subtree,
else we stop current searching because all nodes at right(larger than p->value) is positive, which can not have a negative sum.
(2)If targetSum > 0 now
similar with (1), yet our first choice would be going on with right subtree, because:
if the path exists along the right subtree, it must be shorter than any possible path along the left, since all nodes at right is greater than those at left.
If there is no such path along the right, then we check p->value, if it is positive, then we go on searching left subtree,
else we stop current searching because all nodes at left(smaller than p->value) is negative, which can not have a positive sum.
(3)If targetSum = 0 now
if p is not a leaf, then current path is a dead end, no need to search deeper;
else the shortest path is found!
Following is code in C++:

struct TreeNode
{
	int value;
	TreeNode* left;
	TreeNode* right;
};
int getShortestPathWithSumInBST(TreeNode* root, int sum)
{
	if(root == NULL) return -1;

	int res;
	if(helper(root, sum, 0, res)) return res;
	return -1;
}
bool helper(TreeNode* p, int sum, int prevLen, int& res)
{
	sum -= p->value;
	++prevLen;
	if(sum < 0){
		return p->left != NULL && helper(p->left, sum, prevLen, res) ||
	    	   p->value < 0 && p->right != NULL && helper(p->right, sum, prevLen, res);
	}
	else if(sum > 0){
	    return p->right != NULL && helper(p->right, sum, prevLen, res) ||
	    	   p->value > 0 && p->left != NULL && helper(p->left, sum, prevLen, res);
	}
	else{
		if(p->left != NULL || p->right != NULL) return false;
		res = prevLen;
		return true;
	}
}

#include <stdio.h>

char* removeSingleOccurrence(char* s, char c)
{
    int i = 0, pos = 0, cnt;
    while(s[i]){
        //if not c then append s[i] to s[pos]
        if(s[i] != c) s[pos++] = s[i++];
        else{
            //count how many times c occurs repeatedly
            cnt = 1;
            for(++i; s[i] && s[i] == c; ++i, ++cnt) ;
            //if times > 1 append c to s[pos] cnt times
            if(cnt > 1){
                for(; cnt; --cnt) s[pos++] = c;
            }
        }
    }
    s[pos] = '\0';
    return s;
}

int main()
{
    char s[] = "120jdvj00ncdnv000ndnv0nvd0nvd0";
    puts(removeSingleOccurrence(s, '0'));
    return 0;
}

@iroodaz, you are right, we can do swap just when tmp[j] != tmp[k].

What about bidirectional BFS:

#include <cstring>
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

bool containSameCharacters(const string& a, const string& b)
{
	if(a.size() != b.size()) return false;
	
	int count[256], i, len = a.size();
	memset(count, 0, sizeof(count));
	for(i = 0; i < len; ++i) ++count[a[i]];
	for(i = 0; i < len; ++i){
		if(--count[b[i]] < 0) return false;
	}
	return true;
}
int getMinimumSwaps(const string& from, const string& to)
{
	if(!containSameCharacters(from, to)) return -1;
	if(from == to) return 0;

	unordered_map<string, int> fromMap, toMap;//record state already visited and 
											  //how many swaps need to transfrom into this state
	queue<string> fromQueue, toQueue;//states queue
	int level = 1;					 //how many swaps has been done

	string tmp;
	int i, j, k, n, len = from.size();
	unordered_map<string, int>::iterator iter;
	//initialize
	fromQueue.push(from);
	fromMap[from] = 0;
	toQueue.push(to);
	toMap[to] = 0;
	//binary BFS
	for(; !fromQueue.empty() && !toQueue.empty(); ++level){
		//extend state in fromQueue
		for(i = 0, n = fromQueue.size(); i < n; ++i){
			tmp = fromQueue.front();
			fromQueue.pop();
			for(j = 0; j < len; ++j){
				for(k = j+1; k < len; ++k){
					swap(tmp[j], tmp[k]);//try to swap tmp[j] with tmp[k]
					iter = toMap.find(tmp);//check if this state has been visited by 'to'
					if(iter != toMap.end()){
						cout << "fromMap["<< tmp << "]= " << level << endl;
						cout << "toMap[" << tmp << "]= " << iter->second << endl;
						return level + iter->second;
					}
					else if(fromMap.find(tmp) == fromMap.end()){//check if this state has been visited by 'from'
						fromQueue.push(tmp);
						fromMap[tmp] = level;
					}
					swap(tmp[j], tmp[k]);
				}
			}
		}
		//extend state in toQueue
		for(i = 0, n = toQueue.size(); i < n; ++i){
			tmp = toQueue.front();
			toQueue.pop();
			for(j = 0; j < len; ++j){
				for(k = j+1; k < len; ++k){
					swap(tmp[j], tmp[k]);//try to swap tmp[j] with tmp[k]
					iter = fromMap.find(tmp);//check if this state has been visited by 'from'
					if(iter != fromMap.end()){
						cout << "toMap[" << tmp << "]= " << level << endl;
						cout << "fromMap["<< tmp << "]= " << iter->second << endl;
						return level + iter->second;
					}
					else if(toMap.find(tmp) == toMap.end()){//check if this state has been visited by 'to'
						toQueue.push(tmp);
						toMap[tmp] = level;
					}
					swap(tmp[j], tmp[k]);
				}
			}
		}
	}

	return -1;//actually it never reaches here
}

int main()
{
	cout << getMinimumSwaps("kamal", "amalk");
	return 0;
}

Can we swap arbitrary two characters or just adjacent ones?

Say p is the pointer of the node with value being 50, pNew is the pointer of the node with value being 40. Then we can do like this:

pNew->next = p->next;
p->next = pNew;
p->val = 40;
pNew->val = 50;

The procedure can be divided into four steps:
(1)break up the list into the first half and the second half
(2)reverse the second half to use it as subtrahend
(3)minus each node of first half with each node of reverse of second half
(4)reverse the second half and connect it back to the first half's end
Complexity: time O(n), space O(1)
Following is C++ code:

struct ListNode{
	int val;
	ListNode* next;
};
/*
  minus each of node in first half with the symmetric one in the second half
*/
ListNode* minusSymmetricNode(ListNode* head)
{
	if(head == NULL) return NULL;
	if(head->next == NULL){
		head->val = 0;
		return head;
	}
//Step 1: use fast and slow pointer to break the list up at the (n + 1)/2 node
	ListNode* pFast = head->next, *pSlow = head;
	while(true){
		if(pFast == NULL) break;//now pSlow points to the last node of the first half
								//and length of first half = length of second half + 1
		if(pFast->next == NULL) break;//now pSlow points to the last node of the first half
									  //and length of first half = length of second half
		pSlow = pSlow->next;
		pFast = pFast->next->next;
	}
	//if total length is odd, we set middle node' value to zero!!!
	if(pFast == NULL) pSlow->val = 0;
	//now slow->next is the head of second half
	ListNode* pSecondHalf = pSlow->next;
	pSlow->next = NULL;
//Step 2: reverse second half and use it as subtrahend
	pSecondHalf = reverseList(pSecondHalf);
//Step 3: minus each node of first half with each node of reverse of second half
	minus(head, pSecondHalf);
//Step 4: reverse the second half and connect it to the first half's end
	pSlow->next = reverseList(pSecondHalf);

	return head;
}
ListNode* reverseList(ListNode* head)//reverse the list and return the new head
{
	if(head == NULL || head->next == NULL) return head;

	ListNode *pre = NULL, *next = NULL;
	for(; head != NULL; head = next){
		next = head->next;
		head->next = pre;
		pre = head;
	}
	return pre;
}
void minus(ListNode* minuend, ListNode* subtrahend)//minus each of minuend by each of subtrahend
{
	while(minuend != NULL && subtrahend != NULL){
		minuend->val -= subtrahend->val;
		minuend = minuend->next;
		subtrahend = subtrahend->next;
	}
}

Good idea. Need some fix though.

(1)Comparing the two refs using '!=' is comparing the two objects' addresses.
(2)Comparing the two refs using '>=' or '<=' is comparing the two integer values(auto unboxing).

The problem can be divided into two steps:
(1)find the first common ancestor of the two nodes
(2)find path from left node to ancestor, say it is leftPath,
find path from right node to ancestor, say it is rightPath,
then path = leftPath - ancestor + reverse(rightPath)
In implementation, we can combine those two steps together. Following is code in C++:

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode(int value) : val(value) left(NULL), right(NULL), parent(NULL) {}
};
bool getPath(vector<TreeNode*>& path, TreeNode* start, TreeNode* dest)
{
	path.clear();
//step 0: handling specail cases
	if(start == NULL || dest == NULL) return false;
	if(start == dest){//start is dest
		path.push_back(start);
		return true;
	}
	if(start->parent == NULL){//start is root
		getPathToRoot(path, dest);
		if(path.back() != start){//start and dest in different trees!
			path.clear();
			return false;
		}
		reversePath(path);
		return true;
	}
	if(dest->parent == NULL){//dest is root
		getPathToRoot(path, start);
		if(path.back() != dest){//start and dest in different trees!
			path.clear();
			return false;
		}
		return true;
	}
//step 1: find out two nodes' paths to root
	vector<TreeNode*> startToRoot, destToRoot;
	getPathToRoot(startToRoot, start);
	getPathToRoot(destToRoot, dest);
//step 2: find out the first common ancestor by finding the first common node of two lists
	size_t i, j, lenOfStart = startToRoot.size(), lenOfDest = destToRoot.size();
	if(lenOfStart < lenOfDest){
		i = 0;
		j = lenOfDest - lenOfStart;
	}
	else{
		i = lenOfStart - lenOfDest;
		j = 0;
	}
	for(; j < lenOfDest; ++i, ++j){
		if(startToRoot[i] == destToRoot[j]) break;//find common ancestor!
	}
	if(j == lenOfDest) return false;//start and dest in different trees!
//step 3: get fully path from start to dest
	path.assign(startToRoot.begin(), startToRoot.begin() + i);
	path.insert(path.end(), destToRoot.rbegin() + lenOfDest - 1 - j, destToRoot.rend());
	return true;
}
void getPathToRoot(vector<TreeNode*>& path, TreeNode* p)
{
	for(; p != NULL; p = p->parent) path.push_back(p);
}
void reversePath(vector<TreeNode*>& path)
{
	if(path.size() < 2) return;
	for(size_t i = 0, j = path.size() - 1; i < j; ++i, --j){
		TreeNode* tmp = path[i];
		path[i] = path[j];
		path[j] = tmp;
	}
}

Does the number dictionary like the given example only contain single-digit numbers?

Two steps:
(1)link each node with its next sibling(leftest sibling).
(2)print each level's nodes by finding the leftest node of each level then print all its siblings.
Code in C++:

void specificBFS(Node* root)
{
	if(root == NULL) return;
	//link every node with its leftest sibling
	root->foo = NULL;
	linkSibling(root);
	//print from leftest node of each level to all its siblings
	for(Node* p = root; p != NULL; ){
		printSiblings(p);
		if(p->left != NULL) p = p->left;
		else if(p->right != NULL) p = p->right;
		else p = findFirstNephew(p);
	}
}
void linkSibling(Node* p)//p has already linked with its next sibling
{
	if(p->left != NULL && p->right != NULL){
		p->left->foo = p->right;
		p->right->foo = findFirstNephew(p);
		//here link right child with its sibling first
		linkSibling(p->right);
		linkSibling(p->left);
	}
	else if(p->left != NULL){
		p->left->foo = findFirstNephew(p);
		linkSibling(p->left);
	}
	else if(p->right != NULL){
		p->right->foo = findFirstNephew(p);
		linkSibling(p->right);
	}
}
Node* findFirstNephew(Node* p)//find the leftest nephew
{
	for(Node* sibling = p->foo; sibling != NULL; sibling = sibling->foo){
		if(sibling->left != NULL) return sibling->left;
		if(sibling->right != NULL) return sibling->right;
	}
	return NULL;
}
void printSiblings(Node* p)//print all p's siblings
{
	for(; p != NULL; p = p->foo) printf("%d ", p->data);
}

It's not ANSI C, yet it works in GNU C where operations on void* is taken as char*. To make it meet ANSI, you may change that sentence to this:

res = compare((void*)((char*)arr + mid * size), pTarget);

How about this:

int binarySearch(void* arr, int size, int n, void* pTarget, int (*compare)(const void*, const void*))
{
	if(arr == NULL || n < 1) return -1;

	int left = 0, right = n - 1, mid, res;
	while(left <= right){
		mid = left + ((right - left) >> 1);
		res = compare(arr + (mid * size), pTarget);
		if(res == 0) return mid;
		else if(res < 0) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}

If white spaces are removed, then for any two pairs of parenthesis in the expression, there are 5 kinds of cases we need to take care of:
1.((exp)) such as ((a+b))
2.(exp(exp)) such as (a-(b+c))
3.((exp)exp) such as ((a+b)*c)
4.(exp(exp)exp) such as (a/(b-c)+d)
5.(exp)exp(exp) such as (a+b)/(c*d)
Only the first kind has redundant outside parenthesis, so all we need to do is find out the ocurrances of two pairs of parenthesis like the first kind.
Following is code in C++11:

#include <cctype>
#include <stack>
#include <vector>
#include <string>
#include <utility>
#include <iostream>
#include <unordered_map>
using namespace std;

void buildMapOfStringWithoutSpaces(string& s, unordered_map<int,int>& positionMap, const string& src)
{
	for(int k = 0, i = 0, len = src.size(); i < len; ++i){
		if(isspace(src[i])) continue;
		s.push_back(src[i]);
		positionMap[k++] = i;
	}
}
void remap(vector<pair<int,int> >& v, unordered_map<int,int>& positionMap)
{
	for(int i = 0, n = v.size(); i < n; ++i){
		v[i].first  = positionMap[v[i].first];
		v[i].second = positionMap[v[i].second];
	}
}
void findRedundantParenthesis(vector<pair<int,int> >& v, const string& exp)//exp has no spaces
{
	v.clear();
	if(exp.empty()) return;

	stack<int> st;
	for(int i = 0, len = exp.size(); i < len; ++i){
		if(exp[i] == '('){
			if(!st.empty() && exp[st.top()] == ')'){//previous right's pair has no reduntant
				st.pop();
				st.pop();
			}
			st.push(i);
		}
		else if(exp[i] == ')'){
			if(exp[st.top()] == ')'){//check if this pair is redundant
				int preRight = st.top();
				st.pop();
				int preLeft = st.top();
				st.pop();
				if(i == preRight + 1 && st.top() == preLeft - 1){//this pair is redundant
					v.push_back(make_pair(st.top(), i));
				}
			}
			st.push(i);
		}
	}
}

int main()
{
    vector<pair<int,int> > v;
    string expWithoutSpaces;
    unordered_map<int,int> positionMap;

    buildMapOfStringWithoutSpaces(expWithoutSpaces, positionMap, "((( a + b ) * (( c - d ))))");
    findRedundantParenthesis(v, expWithoutSpaces);
    if(!v.empty()){
        remap(v, positionMap);
        cout << "redundant parenthesis are at:\n";
        for(int i = 0; i < v.size(); ++i){
            cout << "(" << v[i].first << ", " << v[i].second << ")\n";
        }
    }

    return 0;
}

time complexity O(n), space complexity O(n)

If a[] is the inorder traverse of BST, which means a[] is sorted, and arr[][] gives the root of each subtree, we may rebuild the BST by divide and conquer:
arr[0][a.length-1] gives the root of the BST, locate it in a[] as a[k],
we divide the problem into two smaller ones:
(1)rebuild left BST with a[0, k-1] and arr[][]
(2)rebuild right BST with a[k+1, n-1] and arr[][]
Below is code in Java:

public TreeNode rebuild(int[] a, int[][] arr){
	return rebuild(a, 0, a.length - 1, arr);
}
private TreeNode rebuild(int[] a, int s, int e, int[][] arr){
	if(s == e) return new TreeNode(a[s]);

	int rootVal = arr[s][e];
	TreeNode root = new TreeNode(rootVal);
	int pos = Arrays.binarySearch(a, rootVal);
	if(pos > s) root.left = rebuild(a, s, pos - 1, arr);
	if(pos < e) root.right = rebuild(a, pos + 1, e, arr);
	return root;
}

Say these two sorted arrays are a[n] and b[m].
If n + m is odd, then the median should be the (n + m) / 2 smallest number in the merged array.
Else the median is the average of the (n + m - 1)/2 smallest and (n + m + 1)/2 smallest.
Now let's see how we can find the Kth(0, 1, ... n+m-1) number of two sorted arrays without merging them:
(0)say its possible range is a[i, j], middle index m = (i + j) / 2
(1)binary search for equal range of a[m] in b[], say it's [left, right), which means we can insert a[m] into b[] at index range [left, right] while keeping b[] sorted.
(2)If m + left > K, which means if the Kth item is in a[], it must be smaller than a[m] so it should be in range a[i, m-1];
Else if m + right < K, which means if Kth item is in a[], it must be larger than a[m] so it should be in range a[m+1, j];
Else a[m] is the Kth item.
(3)If i > j then the Kth item must be in b[], where we can surely find it by similar method as (1) and (2)
Due to dual binary search, this search process has complexity as log(n)*log(m)

There could be more than one array matching the requirement and we only need to find one. So we can make a great optimization to backtracing by placing the large value first, which has less possibilities:
(1)as soon as we can not place the large value, we stop the search process.
(2)by placing large value first we also cut off many search branches for smaller ones.
As an example, when length = 16, following code is much faster than the above one.

public class OrderMaker {
	private static boolean place(int n, int[] arr){
		if(n == 0) return true;
		for(int i = 0; i + n + 1 < arr.length; ++i){
			if(arr[i] == 0 && arr[i + n + 1] == 0){
				arr[i] = arr[i + n + 1] = n;
				if(place(n - 1, arr)) return true;
				arr[i] = arr[i + n + 1] = 0;
			}
		}
		return false;
	}
	public static int[] makeNumberDistanceEqualsToNumber(int length){
		int[] arr = new int[length];
		Arrays.fill(arr, 0);
		if(place(length >> 1, arr)) return arr;
		return null;
	}
	
	public static void main(String args[]){
		int[] arr = makeNumberDistanceEqualsToNumber(16);
		if(arr != null) System.out.println(Arrays.toString(arr));
		else System.out.println("Can not make such array");
	}

public static int getMinDistance(List<String> list, String A, String B){
    if(list == null || A == null || B == null) return -1;
    if(A.equals(B)) return 0;

    int minDistance = -1, indexOfA = -1, indexOfB = -1;
    for(int i = 0; i < list.size(); ++i){
        String word = list.get(i);
        if(word.equals(A)){
            if(indexOfB >= 0){
                minDistance = minDistance == -1 ? i - indexOfB : Math.min(minDistance, i - indexOfB);
            }
            indexOfA = i;
        }
        else if(word.equals(B)){
            if(indexOfA >= 0){
                minDistance = minDistance == -1 ? i - indexOfA : Math.min(minDistance, i - indexOfA);
            }
            indexOfB = i;
        }
    }
    return minDistance;
}

Exactly my thought, yet it it works only when the tree is a full binary sort tree. This is code in C++:

TreeNode* getNthNodeOfFullBST(int n, TreeNode* p, int height, TreeNode* parent, int parentIndex)
{
	//get the order of node p
	int index = p == parent->left ? parentIndex - (1 << height) : parentIndex + (1 << height);
	if(index == n) return p;
	return getNthNodeOfFullBST(n, n > index ? p->right : p->left, height - 1, p, index);
}
TreeNode* getNthNodeOfFullBST(TreeNode* pFullBST, int n)
{
	if(n < 1 || pFullBST == NULL) return NULL;

	//get height of the full BST
	int height = 0;
	TreeNode* p = pFullBST;
	for(; p->left != NULL; p = p->left) ++height;
	if(n > (1 << (height + 1))) return NULL;//there are less than n nodes at all
	
	//get the order of root
	int index = 1 << height;
	if(n == index) return pFullBST;
	return getNthNode(n, n > index ? pFullBST->right : pFullBST->left, height - 1, pFullBST, index);
}

private void traverseToRoot(List<Node> path, Node node){
	for(; node != null; node = node.parent){
		path.add(node);
	}
}
public Node commonAncestor(Node nodeOne, Node nodeTwo) 
{ 
	if(nodeOne == null || nodeTwo == null) return null;
	if(nodeOne == nodeTwo) return nodeOne;

	List<Node> pathOfOne = new ArrayList<Node>();
	traverseToRoot(pathOfOne, nodeOne);//get nodeOne's path from root
	List<Node> pathOfTwo = new ArrayList<Node>();
	traverseToRoot(pathOfTwo, nodeTwo);//get nodeTwo's path from root
	if(pathOfOne.size() > pathOfTwo.size(){//swap to make pathOfTwo longer
		List<Node> tmp = pathOfOne;
		pathOfOne = pathOfTwo;
		pathOfTwo = tmp;
	};
	for(int i = 0, j = pathOfTwo.size() - pathOfOne.size(); i < pathOfOne.size(); ++i, ++j){
		if(pathOfOne.get(i) == pathOfTwo.get(j)) return pathOfOne.get(i);
	}
	//if reaching here, it means nodeOne and nodeTwo are in different trees
	return null;
}

void makeWave(int arr[], int n)
{
	for(int i = 0; i < n; ++i){
		if(i & 1){//odd index should be smaller than after
			if(i + 1 < n && arr[i] > arr[i+1]) swap(arr[i], arr[i+1]);
		}
		else{//even index should be larger than after
			if(i + 1 < n && arr[i] < arr[i+1]) swap(arr[i], arr[i+1]);
		}
	}
}

We can find the different one in 3 comparations by following steps:
Divide these 8 coins into 4 groups

group[1] = [1,2]
group[2] = [3,4]
group[3] = [5,6]
group[4] = [7,8]

then

COMPARE group[1] with group[2]
if group[1] has the same weight with group[2]
	//now we know [1,2,3,4] are good
	COMPARE group[1] with group[3]
	if group[1] has the same weight with group[3]
		//now we know [1,2,3,4,5,6] are good
		COMPARE 1 with 7
		if 1 has same weight with 7, then 8 is fake
		else 7 is fake
	else
		//now we know the fake one is in [5,6] and whether if it's heavier or lighter!!!
		if group[1] is heavier than group[3]//the fake one is lighter
			COMPARE 6 with 7, the lighter one is fake
		else//the fake one is heavier
			COMPARE 6 with 7, the heavier one is fake
else
	//now we know [5,6,7,8] are good
	if group[1] is heavier than group[2]
		COMPARE group[1] with group[3]
		if group[1] has the same weight with group[3]
			//now we know the fake one is in [3,4] and the fake one is lighter
			COMPARE 3 with 4, the lighter is fake
		else//now we know the fake one is in [1,2] and the fake one is heavier
			COMPARE 1 with 2, the heavier is fake
	else
		COMPARE group[1] with group[3]
		if group[1] has the same weight with group[3]
			//now we know the fake one is in [3,4] and the fake one is heavier
			COMPARE 3 with 4, the heavier is fake
		else//now we know the fake one is in [1,2] and the fake one is lighter
			COMPARE 1 with 2, the lighter is fake

We know in BST root is bigger than all nodes in left subtree and is no larger than all nodes in right subtree. Thus, if the array is a post traversal of a BST, then arr[n-1] can divide the array into two parts arr[0, i) and arr[i, n-1), where
(1)each item in arr[0, i) is less than arr[n-1]
(2)each item in arr[i, n-1) is not less than arr[n-1]
(3)both arr[0, i) and arr[i, n-1) are post traversals of BSTs.

bool isPostTraversalOfBST(int arr[], int n)
{
	if(n < 2) return true;

	int i = 0;
	//try to find out the beginning of right subtree's traversal
	for(; arr[i] < arr[n-1]; ++i) ;
	//check if all arr[i,n-1) >= arr[n-1]
	for(int j = i + 1; j + 1 < n; ++j){
		if(arr[j] < arr[n-1]) return false;
	}
	//check if both two parts are post traversals of BSTs
	return isPostTraversalOfBST(arr, i) &&
		   isPostTraversalOfBST(arr + i, n - i - 1);
}

Though several insertion sequences can result into the same BST, a simple fact that can be concluded by observing is that:
as long as for any subBST the root is inserted before its subtrees, we can build the same BST after changing the insertion sequence.
It's like in the topological graph A->B and A->C, all we need to make sure is that A is done before B and C, while the order of B and C does not matter.

Now let's take the insertion sequence in the example of the problem,
the tree structure is like this:

4
     3      6
    1      5 7
     2

to build the same BST, all we need to maintain after changing the insertion sequence is such relative order:
4->3 and 4->6
3->1
1->2
6->5 and 5->7

To get all the insertion sequences that can result into given BST, we can
(1)recursively get all the insertion sequences of the subtrees
(2)merge subtrees' insertion sequence into one while keeping each sequence's relative order
(3)push the root's value into the merged sequence's front

code in C++:

#include <iostream>
#include <list>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int v):val(v), left(NULL), right(NULL){}
};
class BSTBuilder{
public:
    //insert value into BST, return false if already in the BST
    bool insertBST(TreeNode*& root, int value){
        if(root == NULL){
            root = new TreeNode(value);
            return true;
        }
        
        TreeNode* p = root;
        while(true){
            if(p->val == value) return false;
            if(p->val > value){
                if(p->left == NULL){
                    p->left = new TreeNode(value);
                    break;
                }
                else p = p->left;
            }
            else{
                if(p->right == NULL){
                    p->right = new TreeNode(value);
                    break;
                }
                else p = p->right;
            }
        }
        return true;
    }
    //build a BST taking arr[] as the insertion sequence
    TreeNode* buildBST(int arr[], int n){
        TreeNode* root = NULL;
        for(int i = 0; i < n; ++i) insertBST(root, arr[i]);
        return root;
    }
    //free memory allocated for BST
    void deleteBST(TreeNode*& root){
        if(root == NULL) return;
        
        deleteBST(root->left);
        deleteBST(root->right);
        delete root;
        root = NULL;
    }
};
class BSTRestorer{
private:
    typedef list<int> List;
    typedef list<List> ListList;
    typedef List::iterator Iter;
private:
    //insert value at front of each list in ll
    void insertAtFront(ListList& ll, int value){
        for(ListList::iterator iter = ll.begin(); iter != ll.end(); ++iter){
            iter->push_front(value);
        }
    }
    //insert r's each item into l, while keeping the relative order
    //and insert the merged list into all
    void insertWithRelativeOrder(ListList& all, List& l, Iter firstAvailable, List& r, Iter cur){
        if(cur == r.end()){
            all.push_back(l);
            return;
        }
        
        Iter tmp;
        int val = *cur++;
        for(; firstAvailable != l.end(); ++firstAvailable){
            tmp = l.insert(firstAvailable, val);
            insertWithRelativeOrder(all, l, firstAvailable, r, cur);
            l.erase(tmp);
        }
        tmp = l.insert(firstAvailable, val);
        insertWithRelativeOrder(all, l, firstAvailable, r, cur);
        l.erase(tmp);
    }
    //restore all the insertion sequences that result into the BST
    void restore(TreeNode* root, ListList& insertionSequence){
        if(root->left == NULL && root->right == NULL){
            insertionSequence.push_back(List());
            insertionSequence.back().push_back(root->val);
            return;
        }
        //get all insertion sequence of subtrees
        if(root->left != NULL && root->right != NULL){
            //get left subtree's and right subtree's insertion sequence
            ListList leftInsertionSequence, rightInsertionSequence;
            restore(root->left, leftInsertionSequence);
            restore(root->right, rightInsertionSequence);
            //combine insertion sequence of subtrees
            for(ListList::iterator iter = leftInsertionSequence.begin(); 
                iter != leftInsertionSequence.end();
                ++iter){
                for(ListList::iterator jter = rightInsertionSequence.begin(); 
                    jter != rightInsertionSequence.end();
                    ++jter){
                    insertWithRelativeOrder(insertionSequence, 
                                            *iter, 
                                            iter->begin(), 
                                            *jter,
                                            jter->begin()
                                            );
                }
            }
        }
        else restore(root->left != NULL ? root->left : root->right, insertionSequence);
        //root->val is the first item of a tree insertion sequence 
        insertAtFront(insertionSequence, root->val);
    }
public:
    //interface to outside
    void restoreBST(ListList& insertionSequence, TreeNode* root){
        insertionSequence.clear();
        if(root != NULL) restore(root, insertionSequence);
    }
};

int main()
{
    BSTBuilder builder;
    BSTRestorer restorer;
    list<list<int> > insertionSequence;
    int arr[] = {4, 3, 1, 2, 6, 5, 7}, n = sizeof(arr) / sizeof(arr[0]);
    
    //build BST according to the insertion sequence
    TreeNode* root = builder.buildBST(arr, n);
    //generate all insertion sequences of the BST
    restorer.restoreBST(insertionSequence, root);
    //print those insertion sequences
    for(list<list<int> >::iterator iter = insertionSequence.begin();
        iter != insertionSequence.end();
        ++iter){
        for(list<int>::iterator i = iter->begin(); i != iter->end(); ++i) cout << *i << ' ';
        cout << '\n';
    }
    //free memory
    builder.deleteBST(root);

    return 0;
}

Sorry man, but I don't think it works well for negative values. Think of such case: arr[] = {-1, 1} and threshold = 0. The result should be 1, but according to your algorithm:
(1)at first winleft = 0, winright = 0, winsum = arr[0] = -1.
(2)winsum < threshold, so we slide to right, ++winright.
(3)now winsum = winsum + arr[1] = 0 <= threshold, yet we can not slide to right any more, so there exists no such sequence.

Here we take comma, number and space as separators between words? If so, the thought would be: find out each word' front and back, then reverse it. Code in C:

int isSeparator(char c)
{
	return c == ',' || isdigit(c) || isspace(c);
}
void reverse(char* s, char* e)
{
	char c;
	for(; s < e; ++s, --e){
		c = *s;
		*s = *e;
		*e = c;
	}
}
char* reverseWord(char* s)
{
	if(s == NULL || *s == '\0') return s;

	char *head = s, *tail = s;
	while(1){
		//skip continuous separators till next word's front
		for(head = tail; *head != '\0' && isSeparator(*head); ++head) ;
		if(*head == '\0') break;
		//now head points to a word's front, we go on to find out the word's back
		for(tail = head + 1; *tail != '\0' && !isSeparator(*tail); ++tail) ;
		//now *tail == '\0' or *tail is a separator, so we reverse s[head,tail)
		reverse(head, tail - 1);
	}
	return s;
}

The thought is to split the number by billion, million and thousand. Code in C++:

#include <iostream>
#include <string>
using namespace std;

class NumberReader{
private:
    static const string digit[10];
    static const string teen[10];
    static const string ty[8];
private:
    string read(int n){// 0 < n < 1000
        string s;
        if(n > 99){
            s = digit[n / 100];
            s.append(" hundred");
            n %= 100;
            if(n > 0) s.append(" and ");
        }
        if(n == 0) ;
        else if(n < 10) s.append(digit[n]);
        else if(n < 20) s.append(teen[n - 10]);
        else{
            s.append(ty[n / 10 - 2]);
            n %= 10;
            if(n > 0){
                s.append("-");
                s.append(digit[n]);
            }
        }
        return s;
    }
public:
    string readUnsignedInt(unsigned int num){//0 <= num <= 4294967295
        if(num == 0) return "zero";
        
        string s;
        if(num > 999999999){
            s.append(read(num / 1000000000));
            s.append(" billion");
            num %= 1000000000;
            if(num > 0){
                s.append(" ");
                s.append(readUnsignedInt(num));
            }
        }
        else if(num > 999999){
            s.append(read(num / 1000000));
            s.append(" million");
            num %= 1000000;
            if(num > 0){
                s.append(" ");
                s.append(readUnsignedInt(num));
            }
        }
        else if(num > 999){
            s.append(read(num / 1000));
            s.append(" thousand");
            num %= 1000;
            if(num > 0){
                if(num > 100) s.append(" ");
                else s.append(" and ");
                s.append(readUnsignedInt(num));
            }
        }
        else s = read(num);
        
        return s;
    }
    string readInt(int num){// -2147483648 <= num < 2147483647
        if(num == 0) return "zero";
        
        string s;
        unsigned int n = num;
        if(num < 0) s = "negative ";
        s.append(readUnsignedInt(n));
        return s;
    }
};
const string NumberReader::digit[10] = {
    "zero",
    "one",
    "two",
    "three",
    "four",
    "five",
    "six",
    "seven",
    "eight",
    "nine"
};
const string NumberReader::teen[10] = {
    "ten",
    "eleven",
    "twelve",
    "thirteen",
    "fourteen",
    "fifteen",
    "sixteen",
    "seventeen",
    "eighteen",
    "nineteen"
};
const string NumberReader::ty[8] = {
    "tweenty",
    "thirty",
    "forty",
    "fifty",
    "sixty",
    "seventy",
    "eighty",
    "ninety"
};

int main()
{
    int num;
    NumberReader reader;
    
    while(cin >> num){
        cout << reader.readInt(num) << endl;
    }
    
    return 0;
}

There are at most 8 tasks and 8 servers, so the count of assignment is at most 8^8 = 2^24, which is not a very large size. Depth First Search could just work well.

private boolean schedule(int i, int[] need, int[] capacity)
{
	if(i >= need.length) return true;

	for(int k = 0; k < capacity.length; ++k){
		if(capacity[k] >= need[i]){
			capacity[k] -= need[i];
			if(schedule(i + 1, need, capacity)) return true;
			capacity[k] += need[i];
		}
	}
	return false;
}
public boolean schedule(int[] need, int[] capacity)
{
	//check if total capacity is enough 
	//check all can be scheduled
	return sumOfArray(capacity) >= sumOfArray(need) && schedule(0, need, capacity);
}

I'm sorry but I don't think the greed algorithm works well. Let's take the following case as an example:
server capacity[] = {4, 5}
task need[] = {2, 2, 2, 3}
Then according to your algorithm, the process will be:
(1)task[3] assign to server[0]
(2)task[2] assign to server[1]
(3)task[1] assign to server[1]
(4)task[0] can not be assigned, return false
while actually we can schdule them like this:
task[0] and task[1] => server[0]
task[2] and task[3] => server[1]

I suppose here one task's need can not split among several servers, so the following case should return false:
Server capacity limits: 1, 3
Task capacity needs: 4

(1)if size < 1000, unit is B
(2)if 1000 <= size < 10,000, result as "*.**K" is most accurate
(3)if 10,000 <= size < 100,000, result as "**.*K" is most accurate
(4)if 100,000 <= size < 1000,000, result as "***K" is most accurate
(5)if 1,000,000 <= size < 10,000,000, result as "*.**M" is most accurate
(6)if 10,000,000 <= size < 100,000,000, result as "**.*M" is most accurate
(7)if 100,000,000 <= size < 1000,000,000, result as "***M" is most accurate
(8)if size == 1000,000,000, result is "1G"
Code in C++:

string formatFileSize(unsigned int size)
{
	char s[8] = {0};
	
	if(size < 1000){
		sprintf(s, "%uB", size);
		return string(s);
	}
	else if(size < 10000) sprintf(s, "%.2fK", size * 1.0);
	else if(size < 100000) sprintf(s, "%.1fK", size * 1.0);
	else if(size < 1000000){
		sprintf(s, "%uK", (size - size % 1000)/1000);
		return string(s);
	}
	else if(size < 10000000) sprintf(s, "%.2fM", size * 1.0);
	else if(size < 100000000) sprintf(s, "%.1fM", size * 1.0);
	else if(size < 1000000000){
		sprintf(s, "%uM", (size - size % 1000000)/1000000);
		return string(s);
	}
	else return string("1G");

	return removeTailingDecimalZeros(string(s));
}
string removeTailingDecimalZeros(const string& num)
{
	size_t i = num.find('.'), j = num.size() - 1;
	if(i == string::npos) return num;//an integer without decimal point

	for(; j > i; --j){
		if(num[j] != '0') break;
	}
	if(j == i) ++j;//if num is 37.0000, the result will be 37.0
	return num.substr(0, j+1);
}