CareerCup

Solutions can be done in

O(n)

or

O(log(n))

For first row we can use binary search to find the ending of 0 or starting of 1. for next row we can continue from the last row since we only need to find the lower (i.e. left side of the current index of 1.

What I did is find max for each row and column per iteration so I don't need to come back for that particular row or column again, complexity for iteration will be O(row+col)

Then in

getMax()

method I have used one treeSet to store row/column data in sorted manner. complexity for this function is O(n) for iteration and complexity of treesort.

Here is my code:

package ramesh.solutions;

import java.util.Set;
import java.util.TreeSet;

public class MaxMultiplicationFinderr {

	public static int findMax(int[][] arr, int k) {
		int max = Integer.MIN_VALUE;
		System.out.println("Max at begining: " + max);
		
		max = Math.max(max, getMax(arr, 0, 0, k));
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, Math.max(getMax(arr, 1, i, k), getMax(arr, 2, i, k)));
		}
		return max;
	}

	public static int getMax(int[][] arr, int isRow, int rowNum, int k) {
		int maxMul = Integer.MIN_VALUE;
		Set<Integer> sortedSet = new TreeSet<Integer>();

		for (int i = 0; i < arr.length; i++) {
			switch (isRow) {
			case 0:
				sortedSet.add(arr[i][i]);
				break;
			case 1:
				sortedSet.add(arr[rowNum][i]);
				break;
			case 2:
				sortedSet.add(arr[i][rowNum]);
				break;
			default:
				break;
			}
		}

		if (sortedSet.size() < k)
			return maxMul;

		Integer[] a = sortedSet.toArray(new Integer[0]);
		int arrLent = a.length;
		maxMul = a[arrLent - 1] * a[arrLent - 2] * a[arrLent - 3] * a[arrLent - 4];
		return maxMul;
	}

	public static void main(String[] args) {
		
		int[][] array = {
	            {1, 2, 0, -1 ,4},
	            {3, 1, 2, 4, 6},
	            {0, 6, 3, 1, 4},
	            {1, 3, 2, 0, 7},
	            {2, 0, 3, 2, 9}};
		System.out.println("Final Max: "+findMax(array, 4));
		
	}
}

As it is not clearly mentioned that either we have to check complete circular or inner circular list. so have to detect any circular relation exist in linkedlist.
We can use HashMap to store each node using this logic.

Object obj = new Object;
if(!map.contains(node))
	map.put(node,obj);
else 
	return true;

It is not explained what kind of list it is.
encase it is a java list u can use simply

Collections.sort(list);

Note: object must have implemented Comparable interface. if not then we can use

Collections.sort(list,comparator);

I am curious about how get has O(n) complexity, don't we need to traverse through the keys sho it should be O(n), isn't it ?