CareerCup

Another recursive option called with both strings and 0 (for s1Idx and s2Idx).

int countMatches(String str1, String str2, int s1Idx, int s2Idx) {

	if(s1Idx >= str1.length()) return 0;  

	int count = 0;
	for(int index=s2Idx; index<str2.length(); index++) {
	
		if(str1.charAt(s1Idx) == str2.charAt(index)) {
			if(str1.length()-1 == s1Idx) {
				count++;
			else
				count += findMatches(str1, str2, s1Idx+1, index+1);
		}
	}

	return count;
}

two ways of solving it:

The first is iterative and has a worst case of o(n^2)

void func(int[] buff) {
	
	int before, after = 0;
	for(int i=0; i<buff.length; i++) {
		for(int j=i+1; j<buff.length; j++) {
			after += buff[j];
		}

		int tmp = buff[i];
		buff[i] = before + after;
		before += tmp;
		after = 0;
	}
}

Second option is recursive and has a runtime of o(n)

int func(int before, int index, int[] buff) {
	if(index >= buff.length) return 0;

	int after = func(before + buff[index], index+1, buff);
	buff[index] = before + after;

	return after+buff[index];
}

1. assume the existence of a Hashtable<String, String> table that contains the mapping of a String number to String letter, e.g <"0", "A"> .... <"25", "Z">

2. assume the existence of a function:

private boolean isValid(String str) {
	return table.containsKey(str);
}

3. The requested function:

public int CountCombo(String str) {

	if(str.length <=0) return 0;

	int ones = 0;
	int twos = 0;

	ones = (isValid(str.substring(0,1)))?1:0 + CountCombo(str.substring(1));
	
	if(str.length>=2)
		twos = (isValid(0,2))?1:0 + CountCombo(str.substring(2));

	return ones + twos;
}

}

1. runtime is o(n)
2. we can save a bit by calculating the max possible value that
can be found which is the cube root of the number
3. Can be easily adjusted to store the findings and only print them
if there is more then one pair.

void FindPairs(int num) {

		int max = Math.pow(num, 1/3);
		int[] buff = new int[max];

		for(int index=0; indedx<=max; index++) {
			buff[index] = Math.pow(index, 3);
		}

		int start = 0;
		int end   = buff.length-1;

		while(start < end) {
			int sum = buff[start] + buff[end]
			if(sum == num) 
				System.out.println(buff[start] + " , " + buff[end]);
			else(sum < num)
				start++;
			else
				end--;
		}		
	}

This can be solved with a binary search tree, it might not be balanced but it's fine.

Step 1: build a BST
Step 2: evaluate the different depth from the root to the right side.
Left side does not count because they all represent elelents that
came after the root and are smaller.
Step 3: when returning in the recursion from the left side of a subnode, if
the right side depth is smaller (shorter list) then the left (longer list),
return the left list otherwise add current node to right list and return it.


Step 3 algorithm:

List<TreeNode> count(TreeNode node) {

		if(null == node) {
			List<TreeNode> list = new List<TreeNode>();
			return list;
		}
		
		List<TreeNode> right = count(node.right);
		List<TreeNode> left  = count(node.left);

		if(right.length >= left.length) {
			right.add(node);
			return right;
		else
			return left;
       }

convert the tree to a Stack by going from right to left and then pop k elements.

public TreeNode findK(TreeNode node, int k) {

	Stack<TreeNode> stk = new Stack<TreeNode>();
	fillStack(mode, stk);

	TreeNode ret = null;
	for(int index=0; index<k; index++)
		ret = stack.pop();

	return ret;
}

private void fillStack(TreeNode node, Stack<TreeNode> stk) {

	if(null == node)
		return;

	fillStack(node.right, stk);
	stk.push(node);
	fillStack(node.left, stk);	
}

Another approach is to build a binary search tree while adding the elements in the array from right to left (end to start). This works because:

1. Each time we go "down the tree" to the left all the elements in the tree above are larger than the current one so, add 1 + count the number of elements on the right side of the parent node.

2. When going "down the tree" to the right, the prev. element is small than the current one so don't count it.

3. For n elements we are traversing the tree which is max logN in height there for o(nlogn)

public int findMaxQaz(int[] buff) {

	int max = 0;
	int qaz = 0;

	// create the root
	TreeNode<int> root = new TreeNode(buff[buff.length-1]);
	TreeNode<int> node = root;

	for(int index=buff.length-2; index>=0; index--) {
		if(buff[index] < node.value) {
			qaz += countNodes(node.right);
			qaz += 1; // for current node
			if(node.left == null) {
				node.left = new TreeNode<int>(buff[indedx]);
				if(qaz > max)
					max = qaz;
			}
			else
				node = node.left;
		}
		else {
			if(mode.right == null) {
				node.right = node TreeNode<int>(buff[index]);
				if(qaz > max)
					max = qaz;
			}
			else
				node = node.right;
		}
	}

	return max;
}

private int countNodes(TreeNode node) {

	if(null == node)
		return 0;

	int left = countNodes(node.left);
	int right = countNodes(node.right);

	return left+right+1;
}

Since the it's not a complicated coding question, you are probably tested more on the stylle of coding, such as the return value.

public class Pair {
	public int min;
	public int max;

	public Pair() {
		min = Integer.MAX_VALUE;
		max = Integer.MIN_VALUE;
	}
}

public Pair findEdges(int[] buff) {
	Pair ans = new Pair();

	if(null == buff || 0 == buff.length)
		return ans;

	for(int index=0; index<buff.length; index++) {
		if(buff[index] > ans.max)
			ans.max = buff[index];

		if(buff[index] < ans.min)
			ans.mix = buff[index];
	}

	return ans;
}

it stores a cookie on your computer, it has some personal information + identifiers needed, if you sign out the cookie is deleted.

Since each row starts with 0's and followed by 1's you need to scan the rows according to column - worst case if will be O(MN) runtime

public int findRow(int[][] arr) {
		for (int col=arr[0].length; col++)
			for(int row=0; row<arr.length; row++)
				if(arr[row][col] == 1)
					return row;
		
		return -1;
	}

How about the following solution, it will run as long as we don't request K to be more then the number of all the possible combinations

public static ArrayList<Integer> firstKMin(int[] A, int[] B, int k) {

		ArrayList<Integer> list = new ArrayList<Integer>();
		
		int firstA=0;
		int nextA=1;
		int firstB=0;
		int nextB=1;

		list.add(A[firstA]+B[firstB]);
		int count=1;

		while(count<k) {
			if(A[firstA]+B[nextB] < B[firstB]+A[nextA]) {
				list.add(A[firstA]+B[nextB]);
				nextB++;
				if(nextB >= B.length) {
					firstA++;
					nextB=0;
				}
			} else {
				list.add(B[firstB]+A[nextA]);
				nextA++;
				if(nextA >= A.length) {
					firstB++;
					nextA=0;
				}
			
			}
			count++;					
		}
		
		return list;	
	}

Here is a dynamic programming solution, it can be optimized as some combinations are checked more then once.

However it allows you to do any combination of A, B, C and repeat them as many time as needed.

To run set low and high with initial value of 0 and min and max as the searched range.

public static boolean isBuidable(int low, int high, int min, int max) {
		
		if(low <= min && max <= high)
			return true;
		
		if(low > min) 
			return false;
		
		return isBuidable(low+300, high+310, min, max) ||
			   isBuidable(low+400, high+420, min, max) ||
			   isBuidable(low+500, high+515, min, max);
	}

anon is correct - private variables are not inherited, if you want them to be inherited and not accessed use protected instead.

public - inherited and accessible
protected - inherited and not accessible
private - not inherited and not accessible

We can utilize 4 main classes:

class User {
	String name;
	String email;
}

class Product {
	String name;
	int       id;
	int       amount;
	double price;
}

class Store {
	ArrayList<Product> inStock;
	ArrayList<Product> outStock;
	
	void add(Product) {...}       //adds new product to inStock
	void remove(Product) {...} //removes product from inStock and outStock
	void update(Product) {...}  //updates the product information such as 
                                                        //price/amount and sends notification when amount 
                                                        //change
}

class NotificationMgr {
	Hashmap<int, LinkedList<User>> waitingList;
	void register(User, Products[]);      //user registers for notifications
	void unregister(User, Products[]);  //user deregisters for notifications
               
              /*
	Use the Observer design pattern to receive the notifications when a product
               is moved from the outStock to inStock and send the notification to all registered
               users
              */
}

This wont work for everything, here are some examples it will fail for:
1. The array {-1,0} --> the mux product is 0, your code ignores 0
2. {-2,-1,-9} --> So the question is do we have to find a solution of consecutive numbers In the array or just select the best numbers to include. for the first option that will be {-1,-9} for the seconds it is {-2, -9}

But the question was about the product and not sum

I suggest a different approach - please tell me what I'm missing from the question.

Store is where the web services are directed at, it holds a hash table of the bands.
Getting a band takes an O(1) containing it takes O(#bands) space

public class Store {
	Hashtable<String, Band> bands;  //hash table - key is the band name
        
	public void play(String band, String song) {
            Band bReq = bands.get(band);
            bReq.playSong(song);
        }
  
        String topSong(String band) {
	    Band bReq = bands.get(band);
            return bReq.getTopSong();
        }
}

The Band class holds a sorted LinkedList in order to make seaching for a specific
song when requested by play faster - we can search for a song with binary search,
therefore it will only take O(log(#songs)) to find it and takes O(#songs) to contain.

The top song is always held be a separate reference so it can be retried and updated
within O(1) - updating takes O(1) because searching for it already took O(log(#songs))

public class Song {
	String name;
	String freq;
	String album; //not needed for this question

	public Song(String name) {
		this.name = name;
	 	this.freq    = 0;  //initial value
	}

	void playSong() {
		freq++;
		... //actions related to actual playing
	}
}

public class Band {
	LinkedList<Song> songs;
	Song                        topSong;

        void addSong(String name) { songs.add(new Song(name)); }
        void playSong(String name) { 
		Song s = songs.binarySearch(name);
		s.playSong();

		if(s.freq > topSong.freq)
			topSong = s;
	}

	String getTopSong() { return topSong.name; }
}

We can perhaps replace the LinkedList with something else, even another Hashtable<String, Song> where the key is the song name and the value is the Song class. In this case the size will not change but the search for the song can be O(1)

For an array with both positive and negative numbers we can notice that:
1. zero is to be ignored unless the array contains exactly 2 numbers {-v, 0}
2. Positive numbers are always wanted
3. Negative numbers are wanted as long as there is an even number of them
and in this case you want the smallest ones so to create the largest positive
product of them.

Because of the mixture you have to start by sorting them o(nlogn)
once sorted you can find the answer in a single scan of the sorted array while:
1. keeping track of the number negative numbers - ignore the biggest (closest to zero) negative number if there is an odd number of negative numbers.
2. Ignore 0 if possible (only one case require the use of 0)
3. Once reaching at the positive numbers continue to calculate till the end.