CareerCup

class DiceRoll {
	public static void main(String [] args) {
		int n = 5; // Number of dia
		int m = 5;// Number of faces in a dice 
		int X = 21;
		int [][] mem = new int[n + 1][m + 1];
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < m + 1; j++) {
				mem[i][j] =	 -1;
			}
		}
		System.out.println(getCount(m, n, X, mem));

	}

	public static int getCount(int m, int n, int X, int [][] mem) {
		if(n == 0 && X == 0) {
			return 1;
		}
		else {
			if (m <= 0 || n <= 0 || m * n < X) {
				return 0;
			}
			else {
				if (mem[n][m] != -1) {
					return mem[n][m];
				}
				int count = 0;
				for (int i = 0; i * m  + (n - i) <= X && n - i >= 0; i++) {
					count += getCount(m - 1, n - i, X - i * m, mem);
				}
				mem[n][m] = count;
				return count;
			}
		}
	}
}

A trie to optimize space.

public int getClosestValue(Node n, int value) {
		if (value > n.value) {
			if (n.right == null) {
				return n.value;
			}
			else {
				int subClosest = getClosestValue(n.right, value);
				if (Math.abs(subClosest - value) > Math.abs(n.value - value)) {
					return n.value;
				}
				return subClosest;
			}
		}
		else {
			if (n.left == null) {
				return n.value;
			}
			else {
				int subClosest = getClosestValue(n.left, value);
				if (Math.abs(subClosest - value) > Math.abs(n.value - value)) {
					return n.value;
				}
				return subClosest;
			}
		}
	}

We have a central server which will talk to each of the computers in the network containing the log files. Let's say there are n such computers.

Lets objectify each entry in the network of computers containing the log as <url, count, computer_id> where computer_id is the id of these individual computers.

class Entry {
	String URL,
	int count,
	String computer_id
}

We are going to solve this problem with map-reduce with minimal network data.

Map-step
-------------
Each of the log computers create a max heap (sorted on count) for all the URLs.

Reduce Step:
-----------------
The central server can ask a given computer, the top of the stack. Lets call this function as

function Entry getTopEntry(computer_id)

The central server can also ask a given computer to get the count for a given URL

function int getCount(computer_id, URL)

The central server has two heaps -
- one max-heap of size n (lets call this current_max_heap) containing the one (the top) entry from each log-computers. We also store the sum of all the entries' count in a variable and keep it updated.
- one min-heap of size k (lets call this k_min_heap) containing the current top k elements across all servers. At the end the reduce step, this heap will contain the required k entries

The idea:
Initialization: We initialize the current_max_heap with the first entry from each of the log computers (by polling their individual max_heaps).
We now get the top entry from the current_max_heap and add it to the k_min_heap. Before adding we need to update the entry's count so that it is equal to the count of that entry's URL across all the log-computers, which can be done by asking the count for a URL from all the log-computers) Every time an entry is removed from current_max_heap, we get the top entry from the computer's max-heap to which this entry belonged. We do it k times, so that the k_min_heap has k entries.
At any time, if the top element of the k_min_heap's count is less than the sum of the count's for element in current_max_heap), there is a possibility that the top URLs for all the computer's are same and when added-up they will be higher than this top-entry. So, we continue to move elements from current_max_heap to k_min_heap, till this condition is no longer true.

Here is the code running on the server:

// declare current_max_heap;
// declare k_min_heap;
int current_max_count = 0;
// Initialize the 
for (int i = 0; i < n; i++) {
	Entry entry = getTopEntry(computer_id);
	current_max_heap.add(entry);
	current_max_count += entry.count;
}
do {
	Entry top = current_max_heap.poll();
	Entry new_top  = getTop(top.computer_id);
	current_max_heap.add(new_top);
	current_max_count = current_max_count - top.count + new_top.count;
	current_max_heap.add();
	for (int i = 0; i < n; i++) {
		entry.total_count += getCount(i, top.URL);
	}
	if (k_min_heap.size() < k) {
		k_min_heap.add(entry);
	}
	else {
		if (k_min_heap.peek().count < entry.count) {
			k_min_heap.poll();
			k_min_heap.add(entry);
		}
	}
while(k_min_heap.size() != k || k_min_heap.peek().count <= current_max_count);

The class can contain a static list of the weak-references of all the objects instantiated for the class. Whenever a function which modifies the state is called for an object, the object can call a corresponding static function in the class, which in turn, can call the same function for all the other existing (not garbage collected) objects for that class.

This works - O(n) solution.

int maxDifference(int [] array) {
		if (array.length <= 1) {
			System.out.println("Size of the array should be greater than 1");
			System.exit(1);
		}
		int currentMaxDiff = array[1] - array[0];
		int currentMin = array[0] < array[1] ? array[0] : array[1];
		for (int i = 2; i < array.length; i++) {
			if (array[i] - currentMin > currentMaxDiff) {
				currentMaxDiff = array[i] - currentMin;
			}
			if (currentMin > array[i]) {
				currentMin = array[i];
			}
		}
		return currentMaxDiff;
	}

The following code prints K, as well as the list of integers whose square leads to N.

import java.lang.Math;

class SumOfIntegerSquares {
	int N;
	int [] memArray;
	int [] tracker;

	public static void main(String [] args) {
		new SumOfIntegerSquares().printAsSumOfIntegerSquares(2000);
	}

	public void printAsSumOfIntegerSquares(int N) {
		this.N = N;
		memArray = new int[N + 1];
		tracker = new int [N + 1];
		int K = getK(N);
		System.out.println("K = " + K);
		printNumbers(N);
	}

	private void printNumbers(int N) {
		if (tracker[N] == N) {
			System.out.print((int)(Math.sqrt(N)) + ", ");
		}
		else {
			printNumbers(tracker[N]);
			printNumbers(N - tracker[N]);
		}
	}

	private int getK(int n) {
		//System.out.println("N = " + n);
		if (memArray[n] != 0) {
			return memArray[n];
		}
		int sqrtN = (int)Math.sqrt(n);
		//System.out.println("Sqrt = " + sqrtN);
		if (n == sqrtN * sqrtN) {
			memArray[n] = 1;
			tracker[n] = n;
		}
		else {
			int minimum = Integer.MAX_VALUE;
			int minI = 0;
			for (int i = 1; i < n; i++) {
				int temp = getK(i) + getK(n- i);
				if (temp < minimum) {
					minimum = temp;
					minI = i;
				}
			}
			memArray[n] = minimum;
			tracker[n] = minI;
		}
		return memArray[n];
		
	}


}

Currently the getRandom() function is O(n). We can reduce it to O(log n) if we sort the tuples in order of non-decreasing weights and then do binary search.

import java.util.Scanner;
import java.util.List;
import java.util.LinkedList;

class WeightedProbability {
	public static void main (String [] args) {
		Scanner s = new Scanner(System.in);
		List<Tuple> tuples = new LinkedList<Tuple>();
		int totalWeight = 0;
		Tuple tuple;
		do {
			tuple = readTuple(s);
			totalWeight += tuple.weight;
			tuples.add(tuple);
		} while (!tuple.isLastTuple());
		// Remove the last tuple from the set
		for (int i = 0; i < 100; i++) {
			getRandom(tuples, totalWeight);
		} 

	}
	
	public static Tuple readTuple(Scanner s) {
		Tuple t = new Tuple();
		t.num = s.nextInt();
		t.weight = s.nextInt();
		return t;
	}

	public static int getRandom(List<Tuple> tuples, int totalWeight) {
		int rand = (int)(Math.random() * totalWeight);
		System.out.println("rand = " + rand);
		int i = 0;
		Tuple t = null;
		while (rand >= 0) {
			t = tuples.get(i);
			rand -= t.weight;
			i++;
		}
		System.out.println("Number = " + t.num);
		return t.num;
	}
}

class Tuple {
	int num;
	int weight;

	boolean isLastTuple() {
		if (num == 0 && weight == 0) {
			return true;
		}
		return false;
	}
}

This algorithm modifies the input matrix. If we don't want to modify the input, we can use another matrix to keep track of already visited neighbors.

class Countries {
	public static void main (String [] args) {
		int [][] matrix = {{1, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}};
		System.out.println("Number of countries = " + getNumOfCountries(matrix));
	}

	public static int getNumOfCountries(int [][] matrix) {
		int currentColor = -1;
		int numOfCountries = 0;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if (matrix[i][j] != -1) {
					colorNeighbors(i, j, matrix);
					numOfCountries++;
				}
			}
		}
		return numOfCountries;
	}

	public static void colorNeighbors(int i, int j, int [][] matrix) {
		int color = matrix[i][j];
		matrix[i][j] = -1;
		for (int m = -1; m <= 1; m++) {
			for (int n = -1; n <= 1; n++) {
				if (m + i >= 0 && n+ j >= 0 && m + i < matrix.length && n + j < matrix[m + i].length) {
					if (matrix[m + i][n + j] == color) {
						colorNeighbors(m + i, n + j, matrix);
					}
				}
			}
		}
	}
}

class OneArrayTwoStack {
	private int[] array;
	// index points to the last pushed element
	private int index1; // 1 is for left stack
	private int index2;

	public OneArrayTwoStack(int size) {
		if (size <= 0) {
			System.err.println("Size should be greater than 0");
			System.exit(1);
		}
		array = new int[size];
		index1 = -1;
		index2 = array.length;
	}

	public boolean isStack1Empty() {
		if (index1 == -1) {
			return true;
		}
		return false;
	}

	public boolean isStack2Empty() {
		if (index2 == array.length) {
			return true;
		}
		return false;
	}

	public boolean pushOnStack1(int value) {
		if(isStack1Full()) {
			throw new Exception("Stack is full!");
		}
		array[index1++] = value;
	}

	public boolean pushOnStack2(int value) {
		if (isStack2Full()) {
			throw new Exception ("Stack is full!");
		}
		array[index2--] == value;
	}

	public int popFromStack1() {
		if (isStack1Empty()) {
			throw new Exception ("Stack is empty");
		}
		return array[index1--];
	}

	public int popFromStack2() {
		if (isStack2Empty()) {
			throw new Exception ("Stack is empty");
		}
		return array[index2++];
	}

	public int peekIntoStack1() {
		if (isStack1Empty()) {
			throw new Exception ("Stack is empty");
		}
		return array[index]1;	
	}

	public int peekIntoStack2() {
		if (isStack2Empty()) {
			throw new Exception ("Stack is empty");
		}
		return array[index2];
	}

	public boolean isStack1Full() {
		return isArrayFull();
	}

	public boolean isStack2Full() {
		return isArrayFull();
	}

	private boolean isArrayFull() {
		if (index1 + 1 == index2) {
			return true;
		}
		return false;
	}
}

public class DigitOccurrance {
	public static void main (String [] args) {
		int d = 6;
		int k = 501;
		int max = 0;
		int numOfDigits = getNumOfDigits(k);
		int lastMax = 0;
		for (int i = 0; i < numOfDigits; i++) {
			lastMax = max;
			max = max * 10 + 9;
		}
		System.out.println(max);
		System.out.println("The desired num = " + findNum(lastMax + 1, max, d, k, numOfDigits));
	}

	public static int findNum(int start, int end, int d, int k, int numOfDigits) {

		int mid = (start + end) / 2;
		System.out.println("Calling for start = " + start + " end = " + end);

		int midNumOfOccurrances = getNumOfOccurrances(mid, d, numOfDigits);
		if (start == end) {
			if (midNumOfOccurrances == k) {
				return mid;
			}
			else {
				System.err.println("Wrong input!");
				System.exit(1);
			}
		}
		if (midNumOfOccurrances < k) {
			return findNum(mid + 1, end, d, k, numOfDigits);
		}
		else {
			return findNum(start, mid, d, k, numOfDigits);
		}
	}

	public static int getNumOfOccurrances(int num, int digit, int numOfDigits) {
		int [] array = new int[numOfDigits];
		int count = 0;
		for (int i = 0; i < numOfDigits; i++) {
			int x = (int)(num / Math.pow(10, i)) % 10;
			count = x * i * (int)Math.pow(10, i - 1);
			if (i > 0) {
				count += array[i - 1];
			}
			else {
				count = 0;
			}
			if (x == digit) {
				count += num % Math.pow(10, i);
			}
			if (x > digit) {
				count += Math.pow(10, i);
			}
			array[i] = count;
		}
		return count;
	}

	// Given k, we establish a upper limit on the required number.
	public static int getNumOfDigits(int k) {
		if (k == 0) {
			return 0;
		}
		int n = 1;
		while (n * Math.pow(10, n - 1) < k) {
			n++;
		}
		return n;
	}

}

Since t is time elapsed, it is constantly changing, Hence, the F(t, c) will also be ever-changing. So, every time we need to remove an element from cache, we would need to evaluate F(t, c) and get the least and remove that. That makes it O(n).

Instead if t is the timestamp when the element was added, it can be done in O(1) using Priority Queues.

import java.util.LinkedList;
import java.util.Queue;

class BinaryTreeRows {
	public static void main (String [] args) {
		Node root = new Node(8);
		root.left = new Node(1);
		root.left.left = new Node(3);
		root.left.left.left = new Node(4);
		root.left.left.left.right = new Node(3);
		root.left.right = new Node(6);
		root.left.right.right = new Node(2);
		root.right = new Node(9);
		root.right.left = new Node(-1);
		root.right.right = new Node(6);

		printTree(root);
	}

	public static void printTree(Node node) {
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(node);
		boolean newLevel = true;
		int levelCount = 0, currentCount = 0;
		while (queue.size() != 0) {
			if (newLevel == true) {
				System.out.println("\n");
				newLevel = false;
				levelCount = queue.size();
				currentCount = 0;
			}
			Node element = queue.poll();
			System.out.print(element.value + "\t");
			if (element.left != null) {
				queue.offer(element.left);
			}
			if (element.right != null) {
				queue.offer(element.right);
			}
			currentCount++;
			if (currentCount == levelCount) {
				newLevel = true;
			}
		}
	}
}

class Node {
	Node left;
	Node right;
	int value;
	Node (int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

import java.util.Stack;

class SubsetSumZero {
	public static void main (String [] args) {
		int [] set = {8, 3, 5, 1, -4, -8, 0};
		Stack<Integer> tracker = new Stack<Integer>();
		int runningSum = 0;
		DFS(0, set, runningSum, tracker);
	}

	public static void DFS(int index, int[] array, int runningSum, Stack<Integer> tracker) {
		if (index == array.length) {
			if (runningSum == 0 && tracker.size() > 0) {
				System.out.println("Subset = " + tracker);
			}
			return;
		}
		tracker.push(array[index]);
		DFS(index + 1, array, runningSum + array[index], tracker);
		tracker.pop();
		DFS(index + 1, array, runningSum, tracker);
	}

}

Haha.. my code was almost the same. Great minds think alike !! :) I also did not bother to implement findCenter or check for base cases (null etc)..

Here is a full implementation. It expects a file containing list of words as command line argument. The implementation uses Trie and PriorityQueue.

// Implement a T9 Dictionary
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Comparator;

public class T9Dictionary {

	Trie trie;

	public static void main (String [] args) {
		if (args.length != 1) {
			System.err.println("There should only be one and only one command line argument.");
		}
		BufferedReader reader = null;
		try {
			reader = new BufferedReader(new FileReader(args[0]));
		}
		catch (FileNotFoundException e) {
			System.err.println("File not found");
			return;
		}
		
		List<String> words = new ArrayList<String>();
		String str;
		try {
			while ((str = reader.readLine()) != null) {
				words.add(str.toLowerCase());
			}
		}
		catch (IOException e) {
			System.err.println("Some error while reading file");
			System.exit(1);
		}
		

		T9Dictionary t9Dict = new T9Dictionary();
		t9Dict.createTrie(words);

		System.out.println("Enter the numeric string to search: ");
		Scanner s = new Scanner(System.in);
		String numString = s.nextLine();

		List<String> suggestions = t9Dict.getSuggestions(numString);
		System.out.println("Suggestions: ");
		if (suggestions != null) {
			for (String word : suggestions) {
				System.out.print(word + "\t");
			}
		}
		else {
			System.out.println("No suggestions");
		}

	}

	public T9Dictionary() {
		trie = new Trie();
	}

	private void createTrie(List<String> words) {
		for (String word : words) {
			trie.add(word);
		}
	}

	// Returns the first three suggestion based on the string passed.
	public List<String> getSuggestions(String numString) {
		List<String> results = trie.search(numString);
		if (results != null) {
			return results.subList(0, Math.min(3, results.size()));
		}
		return null;
	}
}

class Trie {
	Node node;
	Trie[] children;

	// Create an empty trie
	Trie() {
		node = new Node();
		children = new Trie[8];
	}

	void add(String str) {
		char [] chrs = str.toCharArray();
		Trie node = this;
		for (int i = 0; i < chrs.length; i++) {
			int index = getNodeIndexFromChar(chrs[i]);
			if (node.children[index] == null) {
				node.children[index] = new Trie();
			}
			node = node.children[index];
		}
		node.node.addWord(str);
	}

	// The str passed should be a string with digits only between (2 to 9)
	List<String> search(String str) {
		System.out.println("Searching for " + str);
		List<String> list = null;
		Trie trie = this;
		char[] chrs = str.toCharArray();
		for (char chr : chrs) {
			if (chr < '2' || chr > '9') {
				System.err.println("Wrong search string: " + str);
				return null;
			}
			else {
				trie = trie.children[getNodeIndexFromNumChar(chr)];
				if (trie == null) {
					System.out.println("No matching string found.");
					return null;
				}
			}
		}
		if (!trie.node.isLeafNode()) {
			System.out.println("Node found but not a leaf node.");
		}
		else {
			PriorityQueue<Word> pq = trie.node.pq;
			list = new ArrayList<String>();
			List<Word> wordList = new ArrayList<Word>();
			int size = pq.size();
			for (int i = 0; i < 3 && i < size; i++) {
				Word word = pq.poll();
				list.add(word.word);
				wordList.add(word);
			}
			for (Word word : wordList) {
				pq.offer(word);
			}
		}
		return list;
	}

	 int getNodeIndexFromChar(char ch) {
	 	if (ch == 'a' || ch == 'b' || ch == 'c') {
	 		return 0;
	 	}
	 	if (ch == 'd' || ch == 'e' || ch == 'f') {
	 		return 1;
	 	}
	 	if (ch == 'g' || ch == 'h' || ch == 'i') {
	 		return 2;
	 	}
	 	if (ch == 'j' || ch == 'k' || ch == 'l') {
	 		return 3;
	 	}
	 	if (ch == 'm' || ch == 'n' || ch == 'o') {
	 		return 4;
	 	}
	 	if (ch == 'p' || ch == 'q' || ch == 'r' || ch == 's') {
	 		return 5;
	 	}
	 	if (ch == 't' || ch == 'u' || ch == 'v') {
	 		return 6;
	 	}
	 	if (ch == 'w' || ch == 'x' || ch == 'y' || ch == 'z') {
	 		return 7;
	 	}
	 	return -1;
	 }

	 int getNodeIndexFromNumChar(char chr) {
	 	return chr - '0' - 2;
	 }
}

class Node {
	public static WordComparator comp = new WordComparator();
	private boolean isLeaf;
	PriorityQueue<Word> pq;

	Node () {
		isLeaf = false;
	}

	public boolean isLeafNode() {
		return isLeaf;
	}

	public void addWord(String str) {
		if (this.isLeaf == false) {
			this.isLeaf = true;
			WordComparator comp = new WordComparator();
			pq = new PriorityQueue<Word>(10, comp);
		}
		// Check if the word is in the queue, if yes, increase its frequency
		Word w = new Word(str, 1);
		for (Word word : pq) {
			if (word.word.compareTo(str) == 0) {
				pq.remove(word);
				word.frequency++;
				w = word;
				break;
			}
		}
		pq.offer(w);
	}
}

class Word{
	int frequency;
	String word;

	Word (String word, int frequency) {
		this.word = word;
		this.frequency = frequency;
	}
}

class WordComparator implements Comparator<Word>{
	public int compare(Word w1, Word w2) {
		return w2.frequency - w1.frequency;
	}
}

Complete code with test cases:

class Node {

	Node left;
	Node right;
	int value;

	Node(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

public class BinaryTreeComparator {
	public static void main(String [] args) {
		Node master1 = new Node(6);
		master1.left = new Node(5);
		master1.right = new Node(12);
		master1.left.left = new Node(4);
		master1.left.right = new Node(7);
		master1.right.left = new Node(8);
		master1.right.right = new Node(10);

		Node master2 = null;
		Node master3 = new Node(10);

		Node subtree1 = null;
		Node subtree2 = new Node(10);
		Node subtree3 = new Node(5);
		subtree3.left = new Node(4);
		subtree3.right = new Node (7);

		System.out.println("Master1 and Subtree1: " + checkSubTree(master1, subtree1));
		System.out.println("Master1 and Subtree2: " + checkSubTree(master1, subtree2));
		System.out.println("Master1 and Subtree3: " + checkSubTree(master1, subtree3));
		System.out.println("Master2 and Subtree1: " + checkSubTree(master2, subtree1));
		System.out.println("Master2 and Subtree2: " + checkSubTree(master2, subtree2));
		System.out.println("Master2 and Subtree3: " + checkSubTree(master2, subtree3));
		System.out.println("Master3 and Subtree1: " + checkSubTree(master3, subtree1));
		System.out.println("Master3 and Subtree2: " + checkSubTree(master3, subtree2));
		System.out.println("Master3 and Subtree3: " + checkSubTree(master3, subtree3));

		Node master4 = master1;
		master4.left.left.left = new Node(1);

		System.out.println("Master4 and Subtree1: " + checkSubTree(master4, subtree1));
		System.out.println("Master4 and Subtree2: " + checkSubTree(master4, subtree2));
		System.out.println("Master4 and Subtree3: " + checkSubTree(master4, subtree3));
	}

	public static boolean checkSubTree(Node master, Node sub) {
		return (compareTrees(master, sub) || 
			(master != null && master.left != null && checkSubTree(master.left, sub)) || 
			(master != null && master.right != null && checkSubTree(master.right, sub)));
	}

	public static boolean compareTrees(Node masterTree, Node subTree) {
		// Subtree is allowed to be null
		if (subTree == null) {
			return true;
		}
		// Master cannot be null, if subtree is null. 
		else if (masterTree == null) {
			return false;
		}
		// At this point, both the trees are non-null.
		if (masterTree.value != subTree.value) {
			return false;
		}
		return (compareTrees(masterTree.left, subTree.left) && compareTrees(masterTree.right, subTree.right));
	}
}

You applied the formula wrong, for a single(n = 1) digit number, the occurrence of any digit (0 to 9) is 1 * 10 ^ (0) = 1;
For a 2 digit number (10 to 99), occurrence = 2 * 10 = 20
For a 3 digit number (100 to 990), occurrence = 3 * 100 = 300 and so on. You should be able to easily verify this.

That is right, that's why whatever celebrity you find in the end, you need to verify if that person is indeed a celebrity. The first part of algorithm establishes that the rest of n - 1 person are not celebrities and that this person might be a celebrity, which you can verify (or reject) in O(n) time.

Can be solved in O(n) time, both recursively and iteratively. Here is an iterative version:

import java.util.Scanner;

class NumToString {
	public static void main (String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("Enter the Number-string");
		String str = s.nextLine();
		char [] cArray = str.toCharArray();
		int [] array = new int[str.length()];
		for (int i = 0; i < array.length; i++) {
			if (cArray[i] >= '0' && cArray[i] <= '9') {
				array[i] = cArray[i] - '0';
			}
			else {
				System.err.println("Wrong input. Exiting...");
			}
		}
		int [] memArray = new int[array.length + 1];
		memArray[array.length] = 1;
		memArray[array.length - 1] = 1;
		for (int i = array.length - 2; i >= 0; i--) {
			if (array[i] > 2 || array[i] == 0 || (array[i] == 2 && array[i + 1] > 5)) {
				memArray[i] = memArray[i + 1];
			}
			else {
				memArray[i] = memArray[i + 1] + memArray[i + 2];
			}
		}
		System.out.println("Number of strings possible = " + memArray[0]);
	}
}

Let Occurrence(d, k) returns a number in which digit d occurs k-th time, then the desired range is (Occurrence(d,k), Occurrence(d, k + 1)).

Also, the formula for total number of occurrence of any digit in all the n-digit numbers is given by n * 10^(n - 1).

Based on this two information, we can find the desired range.

In the end we need to verify if the celebrity even exists or not. (Consider a scenario where no-one knows each other). If it does not exist, return -1.

public int findCelebrity() {
		int celebrity = 0;
		for (int i = 1;  i < N; i++) {
			if (knows(celebrity, i)) {
				celebrity = i;
			}
			else if (knows(i, celebrity)) {
				// No need to do anything here.
			}
			else if (i + 1 < N) {
				// None of them are celebrity, lets select a new one.
				celebrity = i + 1;
				i++; // Increment the counter as none of these two are celebrity.
			}
		}
		boolean noCelebrity = false;
		// We need to confirm if the celebrity is correct or not.
		for (int i = 0; i < N; i++) {
			if (!knows(i, celebrity) || (i != celebrity && knows(celebrity, i))) {
				noCelebrity = true;
			}
		}
		if (noCelebrity) {
			return -1;
		}
		return celebrity;
	}

Using recursion to continue looking for the string and a 2D boolean array to track of the visited indices.

import java.util.Scanner;

class Ruzzle {
	public static void main(String [] args) {
		char [][] board = {{'S', 'T', 'F', 'M'}, {'R', 'U', 'N', 'G'}, {'T', 'A', 'M', 'N'}, {'E', 'O', 'N', 'I'}};
		Scanner s = new Scanner(System.in);
		String str = s.nextLine();

		boolean [][] tracker = new boolean[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				tracker[i][j] = false;
			}
 		}

		boolean found = false;

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (board[i][j] == str.charAt(0)) {
					tracker[i][j] = true;
					if (lookForNextCharacter(board, tracker, str, i, j, 1)) {
						found = true;
						break;
					}
					tracker[i][j] = false;
				}
			}
			if (found) {
				break;
			}
		}

		if (found) {
			System.out.println("String found");
		}
		else {
			System.out.println("String not found");
		}
	}

	public static boolean lookForNextCharacter(char[][] board, boolean[][] tracker, String str, int x, int y, int index) {
		if (index == str.length()) {
			return true;
		}
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i != 0 || j != 0) {
					// First check is that the index should exist
					if (isIndexValid(x + i, y + j, tracker, board, str.charAt(index))) {
						tracker[x + i][y + j] = true;
						if (lookForNextCharacter(board, tracker, str, x + i, y + j, index + 1)) {
							return true;
						}
						tracker[x + 1][y + 1] = false;
					}
				}
			}
		}
		return false;
	}

	public static boolean isIndexValid(int x, int y, boolean[][] tracker, char [][] board, char chr) {
		if (x >= 0 && x < 4 && y >= 0 && y < 4 && tracker[x][y] != true && board[x][y] == chr) {
			return true;
		}
		return false;
	}
}

Reverse sentence and then each word in the sentence

import java.util.Scanner;

class InPlaceReverse {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("Enter the string: ");
		String sentence = s.nextLine();
		sentence = reverseSentence(sentence);
		System.out.println("Reversed string = " + sentence);
	}

	public static String reverseSentence(String sentence) {
		char [] array = sentence.toCharArray();
		reverse(array, 0, sentence.length()	 - 1);
		int lastIndex = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == ' ') {
				reverse(array, lastIndex, i - 1);
				lastIndex = i + 1;
			}
		}
		return new String(array);
	}

	public static void reverse(char[] str, int start, int end) {
		while (end > start) {
			char charStart = str[start];
			str[start] = str[end];
			str[end] = charStart;
			end--;
			start++;
		}
	}
}

Here is my take to this:

import java.util.List;
import java.util.LinkedList;

class Sudoku2X2 {
	public static void main (String[] args) {
		int[][] array = {{0, 0, 0, 0}, {3, 0, 4, 0}, {0, 2, 0, 0}, {0, 0, 0, 0}};
		SudokuBoard board = new SudokuBoard(array);
		if (!board.isBoardValid()) {
			System.err.println("The input board is not valid. Exiting..");
			System.exit(1);
		}
		List<SudokuBoard> boards = getAllValidBoards(0, 0, board);
		System.out.println("Number of boards = " + boards.size());
		for (int i = 0; i < boards.size(); i++) {
			System.out.println("Board " + i + ":");
			boards.get(i).print();
		}
	}

	public static List<SudokuBoard> getAllValidBoards(int x, int y, SudokuBoard board) {
		LinkedList<SudokuBoard> boards = new LinkedList<SudokuBoard>();
		if (x >= SudokuBoard.SIZE || y >= SudokuBoard.SIZE) {
			boards.add(board);
		}
		else {
			if (!board.isEmpty(x, y)) {
				int x1 = x + 1;
				int y1 = y;
				if (x1 == SudokuBoard.SIZE) {
					x1 = 0;
					y1 ++;
				}
				boards.addAll(getAllValidBoards(x1, y1, board));
			}
			else {
				for (int i = 0; i <= SudokuBoard.SIZE; i++) {
					if (board.isMoveValid(x, y, i)) {
						SudokuBoard tempBoard = board.clone();
						tempBoard.move(x, y, i);
						int x1 = x + 1;
						int y1 = y;
						if (x1 == SudokuBoard.SIZE) {
							x1 = 0;
							y1 ++;
						}
						boards.addAll(getAllValidBoards(x1, y1, tempBoard));
					}
				}
			} 
		}
		return boards;
	}

}

class SudokuBoard {
	public static final int SIZE = 4;

	private int board[][];
	private int validator[];

	public SudokuBoard() {
		board = new int[SIZE][SIZE];
		validator = new int[SIZE];
	}

	public SudokuBoard(int[][] array) {
		board = array;
		validator = new int[SIZE];
	}

	public boolean isBoardValid() {
		for (int i = 0; i < SIZE; i++) {
			if (!validateRow(i) || !validateColumn(i) || !validateSquare(i%2, i/2)) {
				return false;
			}
		}
		return true;
	}

	public boolean isEmpty(int x, int y) {
		return (board[x][y] == 0);
	}

	public boolean isBoardComplete() {
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				if (board[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}

	public void move(int x, int y, int move) {
		board[x][y] = move;
	}

	public boolean isMoveValid(int x, int y, int move) {
		if (x < 0 || y < 0 || move < 1 || x >= SIZE || y >= SIZE || move > SIZE) {
			return false;
		}
		else if (board[x][y] != 0) {
			return false;
		}

		board[x][y] = move;

		if (validateRow(x) && validateColumn(y) && validateSquare(x/2, y/2)) {
			board[x][y] = 0;
			return true;
		}
		board[x][y] = 0;
		return false;
	}

	private boolean validateRow(int row) {
		if (row < 0 || row >= SIZE) {
			return false;
		}
		resetValidator();
		for (int i = 0; i < SIZE; i++) {
			int element = board[row][i];
			if (element == 0) {
				continue;
			}
			if (validator[element - 1] != 0) {
				return false;
			}
			else {
				validator[element - 1] = 1;
			}
		}
		return true;
	}

	private void resetValidator() {
		for (int i = 0; i < SIZE; i++) {
			validator[i] = 0;
		}
	}

	private boolean validateColumn(int column) {
		if (column < 0 || column >= SIZE) {
			return false;
		}
		resetValidator();
		for (int i = 0; i < SIZE; i++) {
			int element = board[i][column];
			if (element == 0) {
				continue;
			}
			if (validator[element - 1] != 0) {
				return false;
			}
			else {
				validator[element - 1] = 1;
			}
		}
		return true;
	}

	private boolean validateSquare(int sqRow, int sqColumn) {
		if (sqRow < 0 || sqColumn < 0 || sqRow >= 2 || sqColumn >= 2) {
			return false;
		}
		int startX = sqRow * 2; 
		int startY = sqColumn * 2;
		resetValidator();
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				int element = board[i][j];
				if (element == 0) {
					continue;
				}
				if (validator[element - 1] != 0) {
					return false;
				}
				else {
					validator[element - 1] = 1;
				}
			}
		}
		return true;
	}

	public SudokuBoard clone() {
		int board[][] = new int[SIZE][SIZE];
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				board[i][j] = this.board[i][j];
			}
		}
		return new SudokuBoard(board);
	}

	public void print() {
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
	}
}

I have used LinkedList to store the result, but we can also use a HashMap. LinkedList would have been better if the worst case was O(log(n)). Implementation wise, HashMap would have been easier.

The worst case will always be O(n), but the average case would be O(log(n)). My assumption is that the native LinkedList.addAll implementation in Java is O(1). If it is not, we can write our own implementation.

import java.util.LinkedList;

class BinarySearchCount {

	private int [] sortedArray;

	class Count {
		Count (int num, int count) {
			this.num = num;
			this.count = count;
		}
		int num;
		int count;
	}
	
	public BinarySearchCount(int [] sortedArray) {
		this.sortedArray = sortedArray;
	}

	public LinkedList<Count> getCount(int start, int end) {
		LinkedList<Count> array;
		if (this.sortedArray[start] == this.sortedArray[end]) {
			array = new LinkedList<Count>();
			Count count = new Count(this.sortedArray[start], end + 1 - start);
			array.add(count);
		}
		else {
			LinkedList<Count> leftList = this.getCount(start, start + (end-start)/2);
			LinkedList<Count> rightList = this.getCount(start + (end-start)/2 + 1, end);
			if (leftList.getLast().num == rightList.getFirst().num) {
				leftList.getLast().count += rightList.getFirst().count;
				rightList.remove();
			}
			leftList.addAll(rightList);
			array = leftList;
		}
		return array;
	}

	public static void main (String [] args) {
		// Testing the algorithm.
		int array[] = {1, 1, 3, 3, 3, 9, 9, 9, 11, 11, 13};
		BinarySearchCount bscTest = new BinarySearchCount(array);
		LinkedList<Count> result = bscTest.getCount(0, array.length - 1);
		for (Count count : result) {
			System.out.println(count.num + ": " + count.count);
		}


	}

}