CareerCup

def string_period(msg):
    for k in range(1, len(msg)):
        if msg == (msg[k:] + msg[:k]):
            break
    return msg[:k]

def compute_distance(w,q):
    assert len(w) == len(q)
    dist = 0
    for k in range(len(w)):
        if w[k] != q[k]:
            dist = dist +1
    return dist

def miss_splell(words, query):
    result = []
    for w in words:
        if len(w) == len(query):
            dist = compute_distance(w, query)
            if dist == 1:
                result.append(w)
            if len(result) == 3:
                break
    return result

Implemented as DFS via recurrent function. Each we passe a message 'msg' and a pointer 'k'. If msg[k] is the dollar sign, this char is replaced by a digit from the 'digit_set' and the recuurent function is called with the modified message and increased pointer k+1.

The complexity of the soution is O(2^k) in time and O(n^k) in memory where k is # of dollars and n is # of digits.

def replace_dollar(msg):
    results = []
    digit_set = set(list(msg.replace('$','')))
    _replace_dollar(msg, 0,results, digit_set)
    return results


def _replace_dollar(msg, k, results, digit_set):
    if k == len(msg):
        results.append(msg)
    elif msg[k] != '$':
        _replace_dollar(msg, k+1, results, digit_set)
    else:
        for digit in digit_set:
            _replace_dollar(replace_at_k(msg, k, digit), k+1, results, digit_set)

def replace_at_k(msg, k, digit):
    return msg[:k] + digit + msg[k+1:]

The problem can be viewed as a graph problem. "Given the graph, determine if the graph is bipartite". In other words, is it possible to color the graph using two colors such that no nodes with the same color are connected? Proposed solution assumes that the graph is connected:

(i) using the pairs, construct a graph G
(ii) chose any node as a source node
(iii) starting from the source node, perform BFS, at each step, color the neighbors, toggle the color. If a neighbor is already colored with different color, the graph is not bipartite, return None
(iv) group nodes by color and return two sets

class Bipartite:

    def __init__(self, G):
        self.G = G
        self.st = {}

    def test(self, src):
        if (self._is_bipartite(src)):   return self._split()
        else:                           return None

    def _is_bipartite(self, src):
        q = deque()
        q.append(src)           # enqueue source

        color = 0               # initial color label
        while not q.empty():
            curr = q.pop()
            if st.has_key(curr):
                continue        # skip node
            self.st[curr] = color

            for node in G.neighbours(curr):
                if not st.has_key(node):
                    q.append(node)
                else if self.st[node] == color:
                        return False
            color = color^1     # toggle color label

        return True

    def _split(self):
        A = set()
        B = set()
        for node in st.keys():
            if st[key]:     A.add(node)
            else:           B.add(node)
        return A,B

|x-y| is not minimized hence not correct solution...

How to you minimize the distance |x-y|? A am afraid this is not a solution.

Hi Mehrdad, that is certainly true and it looks good. What remains now is to minimize |x-y|. Sorry I edited the task right after I posted it, I forgot to write the minimization condition.

I like the trick with two's complement (x & -x), awesome :)

Hi Mehrdad, that is certainly true and it looks good. What remains now is to minimize |x-y|. Sorry I edited the task right after I posted it, I forgot to write the minimization condition.

I like the trick with two's complement (x & -x), awesome :)

Hi JeffD,
(i) For example 2 1 1 1 1 2 the algorithm will work as follows:
2 1 1 1 1 2
2 (1+1) (1+1) 2
2*2*2*2 = 16

However we can do better:
2 1 1 1 1 2
(2+1) 1 1 ( 1+2)
(2+1) (1+1) (1+2)
3*2*3 = 18

Hence you are right Jeff, the algorithm is NOT correct.

(ii) In sake of braces, you never get something like 1(2) since the while loop inserts '*'.

So the question is, how to fix the algorithm and is it feasible to slove this task in O(N) linear time?

The problem can be solved recursively or iteratively, there are two problems to solve:
(i) How to reduce the problem to smaller one
(ii) In which order to pick operand couples
(iii) How to chose between multiplication and addition

First, notice that without loss of generlity we can pick any two adjacent numbers, perform desired operation and replace the two numbers with the result, which forms a new reduced problem. For instance, let have a sequence of bumbers "a,b,c,d,e", let pick a couple b,c, hence the new reduced problem is a, x, d, e where x=(b '*' or '+' c).

Second, notice that since interers are positive, the only case when an addition is benefical is only when at least one member of the couple equals '1', otherwise multiplication yields the same or greater result.

Third, notice tha we wont to first get rid of '1' using addition, than it remains only to perform multiplication. If the '1' has two neighbours, it is benefical to sum it with the lower neighbour. To illustrate this consider example below:
Correct: 3,1,2 -> 3*(1+2)=9
Incorrect: 3,1,2->(3+1)*2 = 8

The algorithm sketch may look like this:

1) Reduce problem by geting rid of '1's by addition with lower neighbour
2) Multiply all remaining elements.

What remains is to print the expression to the standart output. The sample code may look like as follows:

public int findMax(int[] a) {
	if (a.length>1) {
		System.out.println(a[0]);
		return a[0];		
	}
	Node<Integer> la = new Node<Integer>();
	Node<String>   sa = new Node<String>();
	for (int k=0; k<a.length; k++) {
		la.add(a[k]);
		sa.add(""+a[k]);
	}
	getRidOfOnes(la, sa);

	/* Multiplication - no '1's left */
	res = 1;
	while(true) {
		res *= la.val;
		System.out.print(ls.val);
		if(!la.isLast()) 	System.out.print("*");
		else 			break;
		la = la.next;
		ls = ls.next;
	} 
	System.out.println();
	return res;	
}
private void getRidOfOnes(Node<Integer> curra, Node<String> currs) {
	while(curra != NULL) {
		if(curra.val != 1) {	
			curra = curra.next;
			currs = currs.next;
			continue;
		}
		if (!curra.isFirst() && !curra.isLast()) { 		// has both neighbours
			if(curra.prev.val>curra.next.val) 	addWithNext(curra, currs);
			else 							addWithPrev(curra, currs);
		}
		else if (curra.isFirst() && !curra.isLast()) 		// has only right neighbour
			addWithNext(curra, currs)
		else if (curra.isLast() && !curra.isFirst()) 		// has only left neighbour
			addWithPrev()
		curra = curr.next;
	}
}

private void addWithNext(Node<Integer> curra, Node<String> currs) {
	curra.val += curr.next.val;
	curra.next = curra.next.next;
	currs.val += "("+curr.val+"+"+curr.next.val+")";
	currs.next = curra.next.next;
}

private void addWithPrev(Node ...) {...}

Notice that the Node class is a custom doubly linked list datastructure.

You are absolutely right ydu525. I will edit the code. Thank you!

Sure, it could be anything. I have experienced a question of type 'how would you collect phone numbers from ~10M if=ox XML files'. The good answer was grep or sed, the red flag was to implement your own code.

Notice that this problem is very similar to the lever-order tree traversal. This problem can be implemented by a queue.
The only difference is that while in odd levels we traverse left to right in the even layers me traverse right to left. We will traverse the the tree while keeping track of even/odd layer. This will affect the order we put the nodes on the queue.

The interviewer is probably interested if you can use bash instead of coding something already implemented very well If this is the case than I would reply something like:

find temp/reg -name '*.c'

The goal is to count a number of connected components in a graph. The problem can be solved by BFS or DFS. Let consider a BFS solution. For simplicity, let assume that the land is represented as a 'boolean[][] map' array and let assume that we can modify it. The solution may look like this:

Initiate a counter to zero
(i) Start at the top left corner of the map, find a land element ('true') and put its coordinates in a queue.
(ii) Dequeue an element and unmark it in the map as 'false'
(iii) Add its adjacent land neighbours to the queue
(iv) If the queue is not empty go to (ii) otherwise increment counter and continue with (i);
Return counter

A sample code is shown below:

public class Components{
	public static int count(boolean[][] map) {
		int M = map.length;
		int N = map[0].length;
		int cnt = 0;
		
		for (int i=0; i<M; i++)
			for (int j=0; j<N; j++)
				if(map[i][j]) {
					visit(new Coord(i,j));
					cnt++;
				}
		return cnt;
	}
	private static visit(boolean[][] map, Coord curr) {
		Queue<Coord> q = new Queue<Coord>();
		q.add(curr);
		
		do {
			curr = q.remove();
			map[curr.i][curr.j] = 0;
			for (c : adj(curr)) 	q.add(c);
		}
		while(!q.isempty());
		return;
	}
	private static Iterable<Coord> adj(boolean[][] map, Coord curr) {
		int M = map.length;
		int N = map[0].length;
		LinkedList<Coord> lst = new LinkedList<Coord>();
		
		for (int i = curr.i-1; i <= curr.i+1;  i++)
			for (int j = curr.j-1; j <= curr.j+1;  j++)
				if (i>=0 && i<M && j>=0 && j<N && map[i][j])
					lst.add(new Coord(i,j));
		return lst;
	}
	
}

Now try it without arithmetic operators.

The direction of the question was finally to create an output stream that is the subtraction of streams. String buffer is fine just for illustration. Good job!

Are you sure about this? "swap(A[i], A[i] + offset)" You have a bug in your code...

Given an integer array 'a' of the length 'N' the problem can be solved as follows:
For each 'i' in 0 to N-1:
(i) generate a random number 'k' that is betweem 'i' and N-1
(ii) swap elements a[i] and a[k]

public static void shuffle(int[] a) {
	int N = a.length;

	for (int i = 0; i < N; i++) {
		int k = i + random()*(N-i)  	// random in (i, N-1)
		int aux = a[i];
		a[i] = a[k];
		a[k] = aux;
	}
}

This algorithm yields in a uniform shuffling, hence all possible permutations are equally possible.

No, it should be a max heap. If you have a bunch of stars in the heap and new one is coming, say it is the one closest to the earth, which one you replace? It make sense to replace the star that has the maximal distance, because it is no longer useful.

Imagine that we would like to print all subsets. Then each integer from array 'int a[]' is member of the subset or not. This can be solved recursively by passing two additional arguments 'int lo' and 'String accum'. Given the index 'lo' we either add a[lo] to an accumulation string or not, increment 'lo' and perform recursive call. We stop and print the 'accum' string as soon as 'lo' is equal to the length of 'a'.

Now, given problem is essentially the same except one modification of the base case. We print the string if and only if its length is equal to 'k', the length of the subset.

A sample code is shown below:

public static void print(int K, int N) {
	int[] a = new int[N];
	for (int k=0; k<N; k++) 	a[k] = k+1;

	print(a, K, 0, "");
}

private static void print(int[] a, int K, int lo, String s) {
	if (s.length() == K)	System.out.println("'" + s + "'");
	if (s.length() >= K)	return;
	if (a.length == lo)		return;

	print(a, K, lo+1, s);
	print(a, K, lo+1, s+a[lo]);
}

I would propose modified quick sort as follows:
(i) Shuffle array
(ii) Select pivot
(iii) Partition the array and get rank of the pivot
(iv) If rank is 'k' done otherwise go to (ii) and repeat on sub array

public static int findRank(int x[], int rnk) {
	int a = new int[x.length];
	// Defensive copy, avoid side effect on x
	for (int k=0; k < x.length; k++) 	
		a[k] = x[k];

	shuffle(a);
	return findRank(a, rnk, 0, a.length-1);
}
private static int findRank(int a[], rnk, int lo, int hi) {
	int mid = partition(a, lo, hi);

	if (rnk < mid) 	return findRank(a, rnk, lo, mid-1);
	if (rnk > mid) 	return findRank(a, rnk, mid+1, hi);

	return a[mid];
}
private static int partition(int[] a, int lo, int hi) {
	int p = a[lo];
	int i = lo;
	int j = hi+1;

	while (true) {
		while (a[++i] <= p) 	if (i == hi) 	break;
		while (a[--j] >  p) 	if (j == lo) 	break;
		if (i >= j) 	break;
		swap(a, i, j);
	}

	swap(a, lo, j);
	return j;
}

The methods swap and shuffle are omitted for brevity. The algorithm is probabilistic guaranteed of O(N) with the worse case quadratic performance.

I know there exist an algorithm for median which has guaranteed worse case performance O(N), maybe this algorithm can be modified and used. It would be nice if someone post and explain this solution.

@zsalloum, No but notice +"" which yields the String.

I would propose the solution via heap. Since sorting all stars and keep the first million is not feasible (O N log N) one can use a heap which yields O(N log K) where K is a short list size. Notice that we are not even asked to return these stars in sorted order.

Let's try to design an algorithm:
(i) Use a max heap (or max Priority queue if you will)
(ii) Fill the heap with first one million values
(iii) Comapre each new value with the top of heap
a) if bigger do nothing
b) if smaller replace top of the heap
Finally, the heap contains top 1 million closest stars. A sample code is shown below:

public Star[] findClosest(Star[] sky, int K) {
	PriorityQueue<Star> pq = new PriorityQueue<Star>();

	int N = sky.length;
	if (N <= K) 	return sky;

	for (int k = 0; k < k; k++)
		pq.add(sky[k]);

	for (int k = K; k < N; k++) {
		Star mystar = sky[k];
		if ( less(mystar, pq.peek()) ) {
			pq.remove();
			pq.add(mystar);
		}
	}

	return(Star[]) pq.toArray();
}

private boolean less(Comparable a, Comparable b) {
	return a.compareTo(b) < 0;
}

public class Star implements Comparable<Star> {
	public int id;
	public float dst;

	public int compareTo(Star other) {
		if (this.dst > other.dst) 	return 1;
		if (this.dst < other.dst) 	return -1;
		return 0;
	}
}

I would propose the following: If the binary tree is BST, at any given node as a root, it has the following properties:
(i) The left most node in the right subtree is greater or equal to the root.
(ii) The right most node in the left subtree is less than a root.

Given the root of a binary tree one can recursively check for these two properties. A sample code is shown below:

public static boolean isBST(Node root) {
	return checkLeft(root, root.val) && checkRight(root, root.val);
}

private static boolean checkRight(Node x, int val) {
	if (x == null) 	return true;
	if (x < val)	return false;
	return checkRight(x.right, val);
}

private static boolean checkLeft(Node x, int val) {
	if (x == null) 	return true;
	if (x >= val)	return false;
	return checkLeft(x.right, val);
}

This task can be solved by a recursive algorithm. Let assume that the input array 'a' contains unique integers 1-9 and we are give a target value 'x'. Notice that when we use one number from 'a', lets say number 'y = a[j]', we have to solve exactly the same problem with the new target value 'x_new = x - y'.

Hence, we can solve the task recursively while checking for two basecases: (i) target value is zero which means sums to original target value or (ii) target value is less than zero which means does not sum to the original target value. The last thing is to keep track of the values used so far and if the basecase (i) occurs push the string on the stack. Finally, we return th stack of strings to the client.

A sample code is shown below:

private static Stack<String> out;

public static Iterable<String> sumsTo(int[] a, int x) {
	out = new Stack<String>();
	sumsTo(a, x, "");
	return out;
}

private static void sumsTo(int[] a, int x, String accum) {
	if (x == 0)	 		out.add(accum);
	if (x <= 0) 		return;

	for (int k = 0; k < a.length; k++)
		sumsTo(a, x-a[k], accum + a[k]);
}

One should clarify with the interviewer how the code should behave if zero is contained in 'a' which may yield an infinite numer of permutations. If the numbers in a[] are not unique one can handle duplicate permutations via symbol table (Hash or Tree Map).

Go for top coder arena, SRM Div 2 problems 250-1000pts and Div 1 problems 200-500pts. If you are able to solve it using a piece of paper paper and a pen within 35min then you are very close to the bar. Good luck!

Hi Marcello! Could you think about some super simple code that builds the tree given the binary image? Maybe that would be tough during the interview given the fact you only have about 40min and whiteboard only. The method signature would be something like this:

public static QuadNode buildQuadTree(boolean[][] img);

When I read the problem to me it was obvious that I have some extra information about the numbers a,b and c, its max and min values, and interviewer wants me to take advantage of this extra information. Otherwise the problem would be just to find median of five integers [ a b c d e f] which is far less interesting task and maybe something the interviewer does not want.

Quadtree is a tree with branching factor of four. In this context it is probably used for dividing screen space recursively into four quadrants. The important question is 'how and what for we will use it for'? Now I am guessing, I think that we will deal with the case when there is a binary picture given and we want to zoom out (or scale down) the image by factors of two.
Lets design the node, each node:
(i) will contain four links to children
(ii) will contain color
(iii) will contain portion of white pixels in its sub-tree
(iv) if node is a leaf, its number of white pixels will be either 0 or 1;

Then the query 'numberOfPixelsGivenColor' will be straightforward. The datastructure may look like this:

public class QuadNode {
	boolean col;
	int nwhite;
	QuadNode[] children;

	public QuadNode(boolean col) {
		this.col = col;
		this.nwhite = 0;
		this.children = new QuadNode[4];
	}

	public void addChild(QuadNode node, int k) {
		this.children[k] = node;
		this.nwhite += node.nwhite;
	}

	public int nwhite() { return this.nwhite; }
}

I am not sure this is exactly what interviewer was asking for.

The second problem:
Comparing to the first problem we are now also given 'min' and 'max'. Notice that min and max are actually two of the input integers a,b and c. One can use two important properties of the bitwise XOR operator:
a) If we XOR two identical numbers we get zero.
b) If we XOR any number with zero we get identity.

The solution is then to XOR all values. A sample code is shown below:

public static int median(int a, int b, int c, int min, int max) {
	return a^b^c^min^max;
}

Example: Let say that min = c, max = b then it follows
a^b^c^min^max = a^(b^max)^(c^min) = a^0^0 = a

The first problem: Maybe it is too simple but I would propse the following solution:

public static int median(int a, int b, int c) {
	if ( (a <= b && b <= c) || (c <= b && b <= a) ) 	return b;
 	if ( (b <= a && a <= c) || (c <= a && a <= b) ) 	return a;
	return c;
}

The question is how the function should behave if the input does not contain unique integers.

The key question is if it is a single or multiple query. If multiple queries are expected than I would propose @zsalloum's solution with a hash map:
OFFLINE:
(i) Create a hash map, key - numeronym, val - List of strings, full words
(ii) For each word from dictionary, comute its numeronym and use it as a key
and add it to the hash map.
ONLINE:
(i) use the given numeronym as a key
(ii) return a list of words from hash map.

Offline O(N) time complesity, online O(1) amortized.

Another solution would be to use a trie:
Dictionary is represented as a trie. Than you traverse trie from 'h' at three levels down and than to 'e' in order to find complete words matching the numeronym. This method may be not optimal for large dictionaries.

I would propose the following solution:

public static String makeNumeronym(String s) {
	if (s == null || s.length() < 3) 	return s;
	int N = s.length();
	return s.charAt(0) + (N-2) + s.charAt(N-1) + "";
}

Btw, isn it that marcus -> m4s? Is it something the interviewer expected?

It looks like your code is not working, did you test it? :)

Let's first solve simplified problem: Let assume that we are only interested if there exist a solution such that 'target' integer can be expressed by combination of given integers in array 'a', operators '+ - * /' and braces '( )'. For instance, given integers 30 2 2 and a target value 16 then 16 = (2+30)/2, however there is no solution if the target value was 8.

Notice that if you remove two numbers from the array 'a' of the length N, apply an operator to these values and append the new value to the array 'a', you obtain a new array of the length N-1. Now you have to solve exactly the same problem as in the beginning, however with reduced size to N-1.

Hence the problem can be solved recursively, in each recursive call try all pairs from 'a' with all operators, while reducing the problem. Eventually the array contains a single integer, the base case. If the integer is equal to the target value we are done : the target value can be expressed as valid mathematical expression composed of given operators, braces and by given N integers. Otherwise we have to explore different branch of the tree.

There are two important remarks:
1) Let assume that non-integer division is not allowed
2) Division operator is not symmetric, hence in general x/y != y/x
This must be carefully handled in the code.

Finally, to solve the original problem we have to modify the recursive algorithm such that it will be able to keep track of the expression. This can be implemented via linked list of strings.

A sample code is shown below:

public static String decompose(int[] a, int target) {
	LinkedList<Integer> x = new LinkedList<Integer>();
	LinkedList<String> expr = new LinkedList<String>();
	for (Integer y : a) {
		x.addLast(y);
		expr.addLast(y+"");
	}

	return decompose(x, expr, target);
}

private static String decompose(LinkedList<Integer> x, LinkedList<String> expr, int target) {
	if (x.size() == 1) { 			// Base case
		if (x.get(0) == target) 	return (expr.get(0)+" = "+target);
		else 						return null;
	}

	for (int i = 0; i<x.size(); i++) {
		for (int j = i+1; j<x.size(); j++) {
			int a = x.get(j);
			int b = x.get(i);
			
			String ae = exp.get(j);
			String be = exp.get(i); 
			
			for (int k=0; k<5; k++) {
 				// Copy of the integer list
				LinkedList<Integer> xnew = new LinkedList<Integer>() ;
				for (Integer y : x) { xnew.addLast(y); }
				xnew.remove(j); xnew.remove(i);
 				// Copy of the expression string list
				LinkedList<String> exprnew = new LinkedList<String>();
				for (String s : expr) { exprnew.addLast(s); }
				exprnew.remove(j); exprnew.remove(i);
 				// Handling division and zero
				if ( k==3 && (b==0 || a%b != 0)) 	continue;
				if ( k==4 && (a==0 || b%a != 0)) 	continue;
				// Applying operator
				int res = applyOperator(a, b, k);
				xnew.addFirst(res);	
				// Merging expression strings 
				String e = stringOperator(ae, be, k);
				exprnew.addFirst(e);
				
				String ans = decompose(xnew, exprnew, target);
				if (ans != null)					return ans;
			}
		}
	}
	return null;
}

private static int applyOperator(int a, int b, int k) {
	switch (k) {
		case 0: 	return a+b;
		case 1: 	return a-b;
		case 2: 	return a*b;
		case 3:     return a/b;
	}
	return b/a;
}

private static String stringOperator(String ae, String be, int k) {
	if (ae.matches(".+[-+*/].+"))	ae = "(" + ae + ")";
	if (be.matches(".+[-+*/].+"))	be = "(" + be + ")";

	switch (k) {
		case 0: 	return ae + "+" + be;
		case 1: 	return ae + "-" + be;
		case 2: 	return ae + "*" + be;
		case 3: 	return ae + "/" + be;
	}
	return be + "/" + ae;
}

Notice that division is handled by two cases: 'k=3' for 'a/b' and 'k=4' for b/k. Indeed it works, example:
input: 4, [5 7 13 169]
output: (7+(169/13))/5 = 4

Good point Rahul, not only 'aux' must be zero but also 'k' must exceeds length of at least one string. Bug fixed, thank you!

I would prose the following solution:
(i) Extract k-th digits from the end of the strings (if index exceeds dimension return '0').
(ii) Sum these digits and the carry
(iii) Compute resulting digit as modulo 2
(iv) Compute new carry as inreger division by 2
(v) Do until digits and carry are all zero.

A sample code is shown below:

public static String sumBinary(String a, String b) {
	int carry = 0;
	StringBuffer sb = new StringBuffer();
	int k = 0;
	while (true) {
		int da = getChar(a, k) - '0'; 	// extract digit
		int db = getChar(b, k) - '0';
		int aux = da + db + carry;
		if ( aux == 0 && !(k<a.length() && k<b.length()) )			
				break;
		sb.append(aux%2);
		carry = aux/2;
		k++;
	}

	return sb.reverse().toString();
}
private static char getChar(String s, int k) {
	int idx = s.length()-1-k;
	return (idx >= 0)?s.charAt(idx):'0';
}

This is too heavy code, it can be done with just few lines. It would be a red flag during interview.

I would propose the following solution:
(i) iterate through the elements of the array
(ii) keep track of the longest positive sequence

A sample code is shown below:

public static void findPosSeq(int a[]) {
	int N = a.length;
	int maxIdx = -1;
	int maxLen = -1;
	int len = -1; 
	int idx = -1;;
	boolean flag = false;

	for (int k = 0; k < N; k++) {
		if (a[k] > 0) {
			if (flag == true) {	
				len++;
			}
			else {
				len = 1;  // new sequence
				idx = k;
				flag = true;
			}
		}
		else {
			flag = false;
			if (len > maxLen) {
				maxLen = len;
				maxIdx = idx;
			}
		} 	
	}
	
	if (maxLen > 0) 	
		System.out.println("Length "+maxLen+", starting index "+maxIdx);
	else
		System.out.println("No positive sequence detected.")
	
}

The algoritnm is O(N) time and O(1) space complexity. After modification it should work also with stream.

@ ninhnnsoc, babesh, Dhaya: Thank you guys for useful comments! As you suggested I've modified a line of code such that we first remove 'y' and then check for 'sum-y'. As @babesh pointed out, the code handles only distinct keys.

The string may contain non alphabet charecters or upper case...

Assuming that a string is ASCII I would propose the following solution:

(i) 	Create histogram whit 128 bins initiated to zero and create counter
(ii) 	Initiate left/right pointers to 1st and 2nd char in a string
(iii)	Move right pointer if substring contains less or equal 'm' unique characters
	Move left pointer if substring containc more than 'm' unique characters
(iv) 	Keep track of the longest substring

The solution should be O(N) time O(1) memory. A sample code is shown below:

public static String longestSubstring(String s, int m) {
	int N = s.length();
	int[] h = new int[128];
 	int cnt = 0;
	int left = 0, right = 0;
	int from = 0, to = 0;
	
	while (left < N && right < N) {
		if (cnt <= m) {
			char c = s.charAt(right++);
			if (h[c]++ == 0) 		cnt++;
		}
		else {
			char c = s.charAt(left++);
			if (h[c]-- == 0) 		cnt--;
		}

		if (to - from < right-left ) {
			from = left;
			to = right;
		}
	}
	
	return s.substring(from, to);
}

"Sort the array first" means O(N log N) time complexity.

I would propose the following:
Let's say that array int[] a can fit into the memory

(i)  	use all numbers as a key and put it in a set
(ii) 	for each j in length a[]
                compute x = sum - a[j]
                if x is in the set
                        print pair a[j], x
                        remove x from the set

The the set construction is O(N), query to the set, if implemented via hash, is O(1) amortized and finally last loop is O(N)

A sample code is shown below:

public static void printPairs(int a[], int sum) {
	HashSet<Integer> st = new HashSet<Integer>();
	
	for (int x : a)
		st.add(x);
	
	for(int y : a) {
		st.remove(y);
		if (st.contains(sum-y)) {
			System.out.println(y + ", " + (sum-y));
			st.remove(sum-y);
		}
	}
}

Notice that since the number is removed from the set, all possible pairs are printed only once. Notice also that this code works only for distinct integer values in the array.

Oh, tooo bad we can not edit any more. I got the question wrong.

Sorry to everyone, don't kill me :)

The problem is essentially checking an element existence in a set. One can use a lookup table implemented via HashSet. Given the collection of names one first build a the lookup table which takes O(N) time. Then the query is just to check if a given value is present in the lookup table which is O(1) amortized time.

A sample code is show below:

public class NameFinder {
	HashSet<String> st;

	public NameFinder (String[] names) {
		st = new HashSet<String>();
		for (String s : names)
			st.add(s.toLowerCase().trim());
	}
	
	public boolean query(String name) {
		boolean bin = st.contains(name.toLowerCase().trim());
		if (bin == true) 		System.out.println("YES");
		else 			System.out.println("NO");
		return bin;
	}
}

I guess that asking this type of question the interviewer wants us to work us with singly linked list. One can use two pointers 'head' and 'tail' pointing to a head and tail of the linked list. Then the process would be (i) link tail.next to head and (ii) update head, update tail, (iii) set tail.next to null to avoid circular list. A sample code is shown below:

public void reverseList(Node list) {
	if (list == null || list.next == null) 		return;
	int N=1;
	Node head = list;
	Node tail = list;

	while(tail.next != null) { 	// get tail and list length
		N++;
		tail = tail.next;
 	}

	for (int k = 0; k < N-1; k++) {
		tail.next = head;
		head = head.next;
		tail = tail.next;
		tail.next = null;
	}
	
	list = head;
}

public class Node {
	public Node next;
	public int val;
}

True, by mistake I took natural log, hence 312 vs. 297 bits. I saved only 15 bits.