CareerCup

boolean FindWord(char[][] keyboard, int N, String word) {
    	
    	boolean[][] isVisited = new boolean[N][N];
    	for (int r=0; r<N; r++) {
    		for (int c=0; c<N; c++) {
    			isVisited[r][c] = true;
    			boolean ret = FindWordRecursive(keyboard, isVisited, N, r, c, word, 1);
    			isVisited[r][c] = false;
    			if (ret) {
    				return true;
    			}
    		}
    	}
    	
    	return false;
    }
    
    boolean FindWordRecursive(char[][] keyboard, boolean[][] isVisited, int N, int r, int c, String word, int offset) {
    	
    	if (offset == word.length()) {
    		return true;
    	}
    	
    	for (int i=-1; i<=1; i++) {
    		for (int j=-1; j<=1; j++) {
    			
    			int r1 = r+i;
    			int c1 = c+j;
    			if (r1>=0 && r1<N && c1>=0 && c1<N && !isVisited[r1][c1]) {
    				isVisited[r1][c1] = true;
    				boolean ret = FindWordRecursive(keyboard, isVisited, N, r1, c1, word, offset+1);
    				isVisited[r1][c1] = false;
    				if (ret) {
    					return true;
    				}
    			}
    		}
    	}
    	
    	return false;

}

O(N)

int CountCommons(const vector<string> &words)
{
	int hist_size = 'z'-'a'+1;
	vector<int> hist(hist_size, 0);

	for (int i=0; i<words.size(); i++)
	{
		const string &word = words[i];
		vector<int> word_hist(hist_size, 0);
		
		for (int j=0; j<word.size(); j++)
			word_hist[word[j]-'a']++;
		
		for (int j=0; j<hist_size; j++)
		{
			if (word_hist[j]>0)
				hist[j]++;
		}
	}

	int ret = 0;
	for (int i=0; i<hist_size; i++)
	{
		if (hist[i] == words.size())
			ret++;
	}

	return ret;

}

public static void PrintBFS(Node root) {
	
	if (root == null) {
		return;
	}
	
	List<Node> curLevelNodes = new ArrayList<>();
	curLevelNodes.add(root);
	
	while (!curLevelNodes.isEmpty()) {
		List<Node> nextLevelNodes = new ArrayList<Node>();
		for (Node node : curLevelNodes) {
			System.out.print(String.valueOf(node.data) + ' ');
			if (node.left != null) {
				nextLevelNodes.add(node.left);
			}
			if (node.right != null) {
				nextLevelNodes.add(node.right);
			}
		}
		System.out.println();
		curLevelNodes.clear();
		curLevelNodes.addAll(nextLevelNodes);
	}

}

public static Node Flip(Node root) {

	if (root == null) {
		return null;
	}
	
	if (root.left == null) {
		return root;
	}
	
	Node flippedRoot = Flip(root.left);
	root.left.left = root;
	root.left.right = root.right;
	return flippedRoot;

}

In this problem three results are possible:
(1) First player wins.
(2) Second player wins.
(3) No winner.

Lets define two recursive functions:
(1) CanWin(int destNumber)
(2) IsLost(int destNumber)

Also because numbers in range 1-N are not re-usable we should hold boolean array with states. From here implementation in very simple. I coded it in C++.

bool CanWin(int destNumber);
bool IsLost(int destNumber);

vector<bool> isAvailable;
bool CanIWin(int maxChoosableInteger, int desiredTotal)
{
	//Initially all integers are available.
	isAvailable.resize(maxChoosableInteger, true);
	return CanWin(desiredTotal);
}

bool CanWin(int destNumber)
{
	for (int i=isAvailable.size()-1; i>=0; i--)
	{
		int num = i+1;

		if (!isAvailable.at(i))
			continue;

		if (destNumber <= num)
			return true;

		isAvailable.at(i) = false;
		bool isOpponentLost = IsLost(destNumber - num);
		isAvailable.at(i) = true;

		if (isOpponentLost)
			return true;
	}

	return false;
}

bool IsLost(int destNumber)
{
	for (int i=isAvailable.size()-1; i>=0; i--)
	{
		int num = i+1;

		if (!isAvailable.at(i))
			continue;

		if (destNumber <= num)
			return false;

		isAvailable.at(i) = false;
		bool canOpponentWin = CanWin(destNumber - num);
		isAvailable.at(i) = true;

		if (canOpponentWin)
			return true;
	}

	return false;
}

Simple recursion. First call with weight=1

public int depthSum (List<NestedInteger> input, int weight) 
{ 
	if (input == null) {
		return 0;
	}
	
	int sum = 0;
	for (NestedInteger elem : input)
	{
		if (elem.isInteger()) {
			sum += weight * elem.getInteger();
		} else {
			sum += depthSum(elem.getList(), weight+1);
		}
	}
	
	return sum;

}

Algorithm: Iterating over array, detecting sequences of same value and for each sequence find longest palindrome around it in bottom->up method.
Comlexity: O(N^2) in worst case.

int FindMaxPalindromeSubseqLen(int arr[], int N)
{
	int maxLen = 1;
	for (int i=0; i<N-1; i++)
	{
		int j=i;
		while (j<N && arr[j+1] == arr[i])
			j++;

		if (j>i)
		{
			int L = GetPalindromeLen(arr, N, i, j);
			maxLen = max(maxLen, L);
			i = j+1;
		}
	}

	return maxLen;
}

int GetPalindromeLen(int arr[], int N, int s, int e)
{
	while (s>0 && e<N-1 && arr[s-1] == arr[e+1])
	{
		s--;
		e++;
	}

	return e-s+1;

}

bool IsNumber(string s)
{
	int N = s.length();
	bool metDot = false;
	for (int i=0; i<N; i++)
	{
		char c = s[i];
		if (c < '0' || c > '9') //Not digit
		{
			if (i == 0 && (c == '-' || c == '+'))
				continue;

			if (i > 0 && i < N-1 && c == '.' && !metDot)
			{
				metDot = true;
				continue;
			}

			return false;
		}
	}

	return true;

}

Similar to Victor solution

void PrintAllTriangles(int A[], int N)
{

	//A[k] < A[i] + A[j]

	//Naturally solution is O(N^3) but we can do little optimization by presorting at O(NlogN)
	sort(A, A+N);
	
	for (int i=0; i<N-2; i++)
	{
		//A[i] < A[j] + A[k] always true for sorted array and j,k>i
		for (int j=i+1; j<N-1; j++)
		{
			//A[j] < A[i] + A[k] always true for sorted array and k>j
			int k=j+1;
			while (A[k] < A[i] + A[j] && k<N)
			{
				cout << A[i] << "," << A[j] << "," << A[k] << endl;
				k++;
			}
		}
	}

}

private static void PrintAll(List<List<String>> in, String comb, int depth)
    {
        if (depth == in.size()) {
            System.out.println(comb);
        }
        else {
            List<String> lst = in.get(depth);
            for (String s : lst) {
                PrintAll(in, comb + ' ' + s, depth+1);
            }
        }
    }

Dynamic programming. O(N^2)

int MaxGold(int pots[], int s, int e)
{
	if (s > e)
		return 0;
	
	if (s == e)
		return pots[s];

	int opt1 = pots[s] + MaxGold(pots, s+2, e);
	int opt2 = pots[s] + MaxGold(pots, s+1, e-1);
	int opt3 = pots[e] + MaxGold(pots, s, e-2);
	int opt4 = pots[e] + MaxGold(pots, s+1, e-1); //Partly duplicate of opt2.

	return max(max(opt1, opt2), max(opt3, opt4));

}

It is throttling problem.

double qps = 1; //Max throughput allowed.
double allowance = qps;

bool IsAllowed(double dt) //dt in seconds, since last call
{
	allowance += dt * qps;
	if (allowance > qps)
		allowance = qps; //throttling

	if (allowance < 1)
		return false;
	else
	{
		allowance -= 1;
		return true;
	}
}

//Number of inversions problem implementation 0(NlogN)
//Modified mergesort.
//Preallocating temp buffer same size as data.
int InvNum(int *pdata, int *ptemp, int s, int e)
{
	if (s == e)
		return 0;

	int mid = (s + e) / 2;

	int inv = InvNum(pdata, ptemp, s, mid);
	inv += InvNum(pdata, ptemp, mid+1, e);

	int ileft = s, iright = mid+1, itemp = 0, inv_merge = 0;
	while (ileft <= mid && iright <= e)
	{
		if (pdata[ileft] <= pdata[iright])
		{
			ptemp[itemp++]=pdata[ileft++];
			inv+=inv_merge;
		}
		else
		{
			ptemp[itemp++]=pdata[iright++];
			inv_merge++;
		}
	}

	while (iright <= e)
	{
		ptemp[itemp++]=pdata[iright++];
		inv_merge++;
	}

	while (ileft <= mid)
	{
		ptemp[itemp++]=pdata[ileft++];
		inv+=inv_merge;
	}

	copy(ptemp, ptemp+itemp, pdata+s);
	return inv;
}

public Node FindKthRecursive(Node n, int k)
    {
        if (k > n.data)
            return null;

        while (n.left != null && n.left.data >= k)
            n = n.left;

        if (n.left != null)
            k -= n.left.data;

        if (--k == 0)
            return n;
        else
            return FindKthRecursive(n.right, k);
    }

    public Node FindKthIterative(Node n, int k)
    {
        if (k > n.data)
            return null;

        while (true)
        {
            while (n.left != null && n.left.data >= k)
                n = n.left;

            if (n.left != null)
                k -= n.left.data;

            if (--k == 0)
                return n;

            n = n.right;
        }
    }

Unfortunately I don't understand what is the difference between N and 2N case. Below 2 general solutions: 1 recursive, 1 iterative.

//Recursive solution O(N!)
//cumSum in first call equals 0
//dstSum is N or 2N
bool FindSubsetRecursive(int dstSum, int cumSum, int *pData, int N)
{
	if (N == 0)
		return false;

	if (N == 1)
		return ((cumSum + *pData) % dstSum == 0) ? true : false;

	for (int i=0; i<N; i++)
	{
		if (FindSubsetRecursive(dstSum, cumSum + pData[i], pData+i+1, N-i-1))
			return true;
	}

	return false;
}

//Iterative solution O(N * 2^N) 
bool FindSubsetIter(int dstSum, int *pData, int N)
{
	for (int i=1; i<(1<<N); i++)
	{
		int tmp = i, sum = 0, cnt = 0;
		while (tmp > 0)
		{
			sum += (tmp&1) * pData[cnt++];
			tmp = tmp >> 1;
		}

		if (sum % dstSum == 0)
			return true;
	}

	return false;
}

Very nice solution. Simple implementation complexity: Time-O(N), Space O(logN)
Code:

class Node
{
    public Node left = null; //Can also serve as previos and head in double linked list
    public Node right = null; //Can also serve as next and tail in double linked list
    public int data = 0;

    public Node()
    {

    }

    //Time: O(N), Space: O(log(N))
    private Node Parse2LL(Node node)
    {
        if (node == null)
            return null;

        Node ret_list = new Node();

        Node left_list = Parse2LL(node.left);
        Node right_list = Parse2LL(node.right);

        if (left_list != null) {
            left_list.right.right = node;
            ret_list.left = left_list.left;
        }
        else {
            ret_list.left = node;
        }

        node.left = left_list;

        if (right_list != null) {
            right_list.left.left = node;
            ret_list.right = right_list.right;
        }
        else {
            ret_list.right = node;
        }

        node.right = right_list;

        return ret_list;
    }

    //Time: 0(N), Space: 0(1)
    public void FindCoeffs(Node node, int sum)
    {
        if (node == null) {
            System.out.println("Not found");
            return;
        }

        Node list = Parse2LL(node);
        Node head = list.left;
        Node tail = list.right;
        while (head != tail)
        {
            if ((head.data + tail.data) < sum) {
                tail = tail.left;
            } else if ((head.data + tail.data) > sum) {
                head = head.right;
            } else {
                System.out.println(String.format("Found {0}+{1}={2}.", head.data, tail.data, sum));
                return;
            }
        }
    }