CareerCup

Here are a couple of ways I would do it:

class SumOfTwoNumbers {
	public static void main(String... args) {
		int[] largearr = {5,9,1,100,5000,0};

		for (int i : largearr) {
			for (int j : largearr) {
				if ((i+j) == 10) {
					System.out.println(i + " " + j);
				}
			}
		}
	}
}

and

class SumOfTwoNumbers2 {
	public static void main(String... args) {
		int[] largearr = {5,9,1,100,5000,0};
		Set<Integer> allInts = new HashSet<Integer>();
		for (int i : largearr) {
			allInts.add(i);
		}

		for (int i : largearr) {
			int diff = 10-i;
			if (allInts.contains(diff)) {
				System.out.println(i + " " + diff);
			}
		}
	}
}

Please elaborate.

They may or may not be in order. No we do not know the total number of elements.

@Anon: Reservoir sampling works only if the data is statistically equally distributed. That was not mentioned.

I would think so. Please provide your algorithm.

That works for the first part of the question. The challenge is the second part which states there is not enough memory.

How about level order traversal and keep track of the max width.

I think you misunderstood the question.

Here's one implementation:

public class TrimMultipleSpaces {
	public String trim(String word) {
		char[] p = word.toCharArray();
		tr(p);
		return new String(p);
	}

	private void tr(char[] word) {
		boolean flag = false;
		for (int i = 0; i < word.length; i++) {
			if (word[i] == ' ' && flag) {
				bringInFront(word, i);
			} else if (word[i] == ' ' && !flag) {
				bringInFront(word, i);
				flag = true;
			} else {
				flag = false;
			}
		}
	}

	private void bringInFront(char[] word, int l) {
		for (int i = l; i < word.length; i++) {
			if (i + 1 < word.length - 1) {
				word[i] = word[i + 1];
			}
		}
	}

	public static void main(String[] args) {
		TrimMultipleSpaces obj = new TrimMultipleSpaces();
		System.out.println(obj.trim("   Hello   World   "));
	}
}

Using an adapter pattern might be useful.

Can you describe what you mean by "fall down" ?

A recursive implementation in Java:

package ws.abhis.algos.ds;

public class ArrayManipulation1 {
	public int countLastNumber(int[] arr) {
		int sizeOfArray = arr.length;
		int lastNumber = arr[sizeOfArray-1];
		int[] newArr = {};
		for (int i=0; i<arr.length-1; i++) 
			newArr[i] = arr[i];
		int[] positions = searchForNumber(newArr, lastNumber);
		return positions.length;
	}
	
	private int[] searchForNumber(int[] arr, int number) {
		int low = 0;
		int high = arr.length-1;
		int mid = (high-low)/2;
		int[] returnPositions = {};
		if (arr[mid] == number)
			returnPositions[0] = mid;
		else {
			//divide into left and right arrays
			int[] leftArray = {};
			for (int i=0; i<mid-1; i++) 
				leftArray[i] = arr[i];
			int[] rightArray = {};
			for (int i=mid+1, j=0; i<arr.length; i++, j++)
				rightArray[j] = arr[i];
			searchForNumber(leftArray, number);
			searchForNumber(rightArray, number);
		}
		return returnPositions;
	}
	
	public static void main(String args[]) {
		int[] defArr = {1,2,3,4,2,2,3,2};
		ArrayManipulation1 obj = new ArrayManipulation1();
		int cnt = obj.countLastNumber(defArr);
		System.out.println(cnt);
	}
}