CareerCup

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Set;
import java.util.HashSet;

public class KSortedArrayIterator implements Iterator
{
	//use priority queue to maintain the values in order
	Queue<Value> pq;
	List<Integer[]> kSortedList;
	boolean removeDuplicates;
	//to remove duplicates
	Set<Integer> set;
	public KSortedArrayIterator(List<Integer[]> kSortedList, boolean removeDuplicates)
	{
		this.pq = new PriorityQueue<Value>(10, new Value(0,0,0));
		this.kSortedList = kSortedList;
		this.removeDuplicates = removeDuplicates;
		this.set = new HashSet<>();
		if(this.kSortedList!=null && !this.kSortedList.isEmpty())
		{
			for(int i=0;i<this.kSortedList.size();i++)
			{
				Integer[] arr = this.kSortedList.get(i);
				int index = 0;
				while(this.removeDuplicates && index < arr.length && set.contains(arr[0]))
					index++;
				if(index < arr.length)
				{
					pq.offer(new Value(arr[index], i, index));
					if(this.removeDuplicates)
						set.add(arr[index]);
				}
			}
		}
	}

	public static void main(String[] args)
	{
		List<Integer[]> list = new ArrayList<>();
		Integer[] a = new Integer[]{1, 2, 3, 4, 7, 9 };
		Integer[] b = new Integer[]{3, 5, 6, 8, 10};
		Integer[] c = new Integer[]{1, 2, 3};
		list.add(a);
		list.add(b);
		list.add(c);
		KSortedArrayIterator k = new KSortedArrayIterator(list, false);
		while(k.hasNext())
		{
			//System.out.println(k.pq);
			System.out.println(k.next());
		}
	}

	public Object next()
	{
		Value v = pq.poll();
		Integer[] a = kSortedList.get(v.arrIndex);
		int index= v.elementIndex+1;

		while(this.removeDuplicates && index < a.length && set.contains(a[index]))
		{
			index++;
		}
		if(index < a.length)
		{
			pq.offer(new Value(a[index], v.arrIndex, index));
			if(this.removeDuplicates)
				set.add(a[index]);
		}
		return v.val;
	}

	public boolean hasNext()
	{
		return !this.pq.isEmpty();
	}
}

class Value implements Comparator<Value>
{
	int val;
	int arrIndex;
	int elementIndex;

	public Value(int val, int arrIndex, int elementIndex)
	{
		this.val = val;
		this.arrIndex = arrIndex;
		this.elementIndex = elementIndex;
	}

	@Override
	public int compare(Value a, Value b) 
	{
    	return Integer.compare(a.val, b.val);
	}	

	@Override
	public String toString()
	{
		return this.val+"|"+this.arrIndex+"|"+this.elementIndex;
	}
}

import java.util.Arrays;
public class SquaredSortedList
{
	public static void main(String args[])
	{
		SquaredSortedList s = new SquaredSortedList();
		int[] nums = {-7, -2, -1, 1, 6};
		int[] res = s.getSquaredSortedList(nums);
		System.out.println(Arrays.toString(res));
	}

	public int[] getSquaredSortedList(int[] nums)
	{
		int lo = 0;
		int hi = nums.length-1;

		int[] res = new int[nums.length];
		int k = nums.length-1;
		while(lo <= hi)
		{
			long lo2 = nums[lo] * nums[lo];
			long hi2 = nums[hi] * nums[hi];

			if(lo2>=hi2)
			{
				res[k] = (int)lo2;
				lo++;
				k--;
 			}
 			else if(lo2<hi2)
 			{
 				res[k] = (int)hi2;
 				hi--;
 				k--;
 			}
		}
		return res;
	}

}

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class ValidBinaryTree
{
	public static void main(String args[])
	{
		ValidBinaryTree v = new ValidBinaryTree();

		Node n3 = new Node(3);
		Node n2 = new Node(2);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		Node n1 = new Node(1);
		n2.left = n4;
		n2.right = n5;

		n1.left = n2;
		n1.right = n3;

		List<Node> list = new ArrayList<>();
		list.add(n3);
		list.add(n2);
		list.add(n4);
		list.add(n5);
		list.add(n1);

		System.out.println(v.isValid(list));
	}

	public boolean isValid(List<Node> list)
	{
		//create a freqMap
		Map<Integer, Integer> freqMap = new HashMap<>();
		for(Node node : list)
		{
			//if the node is not present in the map
			//add the node
			if(!freqMap.containsKey(node.val))
			{
				freqMap.put(node.val, 1);
			}
			else
			{
				//if the node is present 
				//then decrease the frequency my 1
				freqMap.put(node.val, freqMap.get(node.val)-1);
			}
			//similarly for the left and right child
			if(node.left!=null)
			{
				if(!freqMap.containsKey(node.left.val))
				{
					freqMap.put(node.left.val, 1);
				}
				else
				{
					freqMap.put(node.left.val, freqMap.get(node.left.val)-1);
				}
			}

			if(node.right!=null)
			{
				if(node.right!=null && !freqMap.containsKey(node.right.val))
				{
					freqMap.put(node.right.val, 1);
				}
				else
				{
					freqMap.put(node.right.val, freqMap.get(node.right.val)-1);
				}
			}

		}

		int count = 0;
		//count the elements in the freq map with frequency not equal to
		for(Map.Entry<Integer, Integer> entry : freqMap.entrySet())	
		{
			if(entry.getValue()!=0)
				count++;
		}
		System.out.println(count);
		return count==1;
	}
}

class Node
{
	Node left;
	Node right;

	int val;
	Node(int val)
	{
		this.val = val;
	}
}

public class FixBst
{
	public static void main(String args[])
	{
		TreeNode root= new TreeNode(3);
		root.left = new TreeNode(1);
		root.right = new TreeNode(6);
		root.left.right = new TreeNode(2);
		root.right.left = root.left.right;

		FixBst f = new FixBst();
		f.print(root);
		f.fix(root, Integer.MIN_VALUE, Integer.MAX_VALUE, null);
		System.out.println();
		f.print(root);

	}

	public void fix(TreeNode root, int min, int max, TreeNode parent)
	{
		if(root==null)
			return;
		if(root.val > min && root.val <= max)
		{
			fix(root.left, min, root.val, root);
			fix(root.right, root.val, max, root);
		}
		else
		{
			if(parent.left.val == root.val)
				parent.left = null;
			else if(parent.right.val == root.val)
				parent.right = null;
		}
	} 

	private void print(TreeNode root)
	{
		if(root==null)
			return;

		print(root.left);
		System.out.print(root.val+"\t");
		print(root.right);
	}
}

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
		this.val = val;
	}
}

import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;

public class MaxConsecutiveNumbersinBinaryTree
{
	public static void main(String args[])
	{
		MaxConsecutiveNumbersinBinaryTree m = new MaxConsecutiveNumbersinBinaryTree();
		TreeNode root = new TreeNode(90);
		root.left = new TreeNode(1);
		root.left.left = new TreeNode(2);
		root.left.left.left = new TreeNode(5);
		root.left.left.right = new TreeNode(4);
		root.left.left.left.left = new TreeNode(99);
		root.left.left.left.right = new TreeNode(100);

		root.right = new TreeNode(66);
		root.right.left = new TreeNode(67);
		root.right.left.left = new TreeNode(68);

		Set<List<Integer>> list = new HashSet<>();

		m.dfs(root, null, new ArrayList<Integer>(), list);

		System.out.println(list);

	}

	public void dfs(TreeNode root, TreeNode parent, List<Integer> l, Set<List<Integer>> list)
	{
		if(root == null)
		{
			list.add(l);
			return;
		}

		if(parent==null)
		{
			l.add(root.val);
		}
		else if(Math.abs(root.val - parent.val)==1)
		{
			l.add(root.val);
		}
		else if(Math.abs(root.val - parent.val)!=1)
		{
			list.add(l);
			l = new ArrayList<>();
			l.add(root.val);
		}
		dfs(root.left, root, l, list);
		dfs(root.right, root, l, list);
	}
}

class TreeNode
{
	TreeNode left;
	TreeNode right;

	int val;

	TreeNode(int val)
	{
		this.val = val;
	}
}

import java.util.*;

public class GeneratePasswords
{
	public static void main(String args[])
	{
		GeneratePasswords g = new GeneratePasswords();
		System.out.println(g.generate("Password"));
	}

	public Set generate(String s)
	{
		Set<String> set = new HashSet<>();
		helper(s, 0, set);
		return set;
	}

	private void helper(String s, int index, Set<String> set)
	{
		if(index>=s.length())
		{
			set.add(s);
			return;
		}
		if(s.charAt(index)=='a')
		{
			helper(s.substring(0,index)+"@"+s.substring(index+1), index+1, set);
			helper(s, index+1, set);
		}
		else if(s.charAt(index)=='s')
		{
			helper(s.substring(0,index)+"$"+s.substring(index+1), index+1, set);
			helper(s, index+1, set);
		}
		else
		{
			helper(s, index+1, set);
		}
	}
}

import java.util.*;
public class MatrixToTree
{
	public static void main(String args[])
	{
		int[][] mat = {{0, 1, 0, 0, 0},
						{0, 0, 1, 0, 0},
						{0, 0, 0, 1, 0},
						{0, 0, 0, 0, 1},
						{0, 0, 0, 0, 0}};
		MatrixToTree  m = new MatrixToTree();
		TreeNode root = m.create(mat);
		m.print(root);

	}

	public TreeNode create(int[][] mat)
	{
		Map<Integer, TreeNode> map = new HashMap<>();

		for(int i=0;i<mat.length;i++)
		{
			for(int j=0;j<mat[i].length;j++)
			{
				if(mat[i][j]==1)
				{
					helper(i, j, map);
				}
			}
		}

		int root = findRoot(mat);
		return map.get(root);
	} 


	private void helper(int p, int c, Map<Integer, TreeNode> map)	
	{
		TreeNode parent = map.getOrDefault(p, new TreeNode(p));
		TreeNode child = map.getOrDefault(c, new TreeNode(c));

		parent.children.add(child);
		map.put(p, parent);
		map.put(c, child);
	}


	private int findRoot(int[][] mat)
	{
		for(int col = 0; col<mat[0].length; col++)
		{
			boolean isRoot = true;
			for(int row = 0; row<mat.length; row++)
			{
				if(mat[row][col]==1)
				{
					isRoot = false;
					break;
				}
			}
			if(isRoot)
				return col;
		}
		return -1;
	}

	private void print(TreeNode root)
	{	
		Queue<TreeNode> next = new LinkedList<>();
		Queue<TreeNode> curr = null;
		next.offer(root);

		while(!next.isEmpty())
		{
			curr = next;
			next = new LinkedList<>();

			while(!curr.isEmpty())
			{
				TreeNode temp = curr.poll();
				System.out.print(temp.val+"\t");
				for(TreeNode child: temp.children)
				{
					next.offer(child);
				}
			}
			System.out.println();
		}
	}
}


class TreeNode
{
	int val;
	List<TreeNode> children;

	TreeNode(int val)
	{
		this.val= val;
		children = new ArrayList<>();
	}

	public String toString()
	{
		return val+ ": "+children;
	}
}

import java.util.*;
public class SimplifyDebt
{
	public static void main(String[] args)
	{
		Graph g = new Graph();
		g.addTransaction(1, 2, 400);
		g.addTransaction(2, 3, 200);
		g.addTransaction(3, 1, 100);
		g.addTransaction(3, 4, 200);
		g.addTransaction(4, 1, 100);
		g.addTransaction(3, 5, 1000);
		System.out.println(g);
		SimplifyDebt s= new SimplifyDebt();
		Graph newG = s.simplify(g);
		System.out.println(newG);
	}


	public Graph simplify(Graph g)
	{
		Map<Integer, Integer> map = solve(g);
		PriorityQueue<Node> inq = new PriorityQueue<>(10,new Comparator<Node>(){
			public int compare(Node a, Node b)
			{
				return Integer.compare(b.owe, a.owe);
			}
		});

		PriorityQueue<Node> outq = new PriorityQueue<>(10, new Comparator<Node>(){
			public int compare(Node a, Node b)
			{
				return Integer.compare(a.owe, b.owe);
			}
		});
		System.out.println(map);
		for(Map.Entry<Integer, Integer> entry: map.entrySet())
		{
			if(entry.getValue()<0)
				outq.offer(new Node(entry.getKey(), entry.getValue()));
			else
				inq.offer(new Node(entry.getKey(), entry.getValue()));
		}
		System.out.println(inq);
		System.out.println(outq);
		return evaluate(inq,outq);
	}

	private Graph evaluate(PriorityQueue<Node> inq, PriorityQueue<Node> outq)
	{
		Graph g = new Graph();
		while(!inq.isEmpty() && !outq.isEmpty())
		{
			Node in = inq.poll();
			Node out = outq.poll();
			int owe = (out.owe * -1)>in.owe?in.owe:(out.owe*-1);
			g.addTransaction(out.to, in.to, owe);
			int sum = in.owe+out.owe;
			if(sum < 0)
			{
				outq.add(new Node(out.to, sum));
			}
			else if(sum >0)
			{
				inq.add(new Node(in.to, sum));
			}
		}
		return g;
	}

	private Map<Integer, Integer> solve(Graph g)
	{
		Map<Integer, Integer> tempMap = new HashMap<>();
		for(Integer from: g.map.keySet())
		{
			for(Node node : g.map.get(from))
			{
				tempMap.put(from, tempMap.getOrDefault(from, 0)-node.owe);
				tempMap.put(node.to, tempMap.getOrDefault(node.to, 0)+node.owe);
			}

		}
		return tempMap;
	}

}

class Graph
{
	Map<Integer, List<Node>> map;

	public Graph()
	{
		this.map = new HashMap<>();
	}

	public void addTransaction(int from, int to, int owe)
	{
		List<Node> list = map.getOrDefault(from, new ArrayList<Node>());
		list.add(new Node(to, owe));
		map.put(from, list);
	}

	public String toString()
	{
		return this.map.toString();
	}
}

class Node
{
	int to;
	int owe;

	Node(int to, int owe)
	{
		this.to = to;
		this.owe = owe;
	}

	public String toString()
	{
		return this.to+":"+owe;
	}
}

import java.util.Set;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Comparator;

public class NodeMaxDifference
{
	PriorityQueue<TreeNode> maxq = null;
	PriorityQueue<TreeNode> minq = null;
	int diff = Integer.MIN_VALUE;

	public NodeMaxDifference()
	{
		this.maxq = new PriorityQueue<>(10, new Comparator<TreeNode>(){
			public int compare(TreeNode a, TreeNode b)
			{
				return Integer.compare(b.val, a.val);
			}
		});

		this.minq = new PriorityQueue<>(10, new Comparator<TreeNode>(){
			public int compare(TreeNode a, TreeNode b)
			{
				return Integer.compare(a.val, b.val);
			}
		});
	}

	public static void main(String[] args)
	{
		NodeMaxDifference n = new NodeMaxDifference();
		
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);

		root.left.left = new TreeNode(9);
		root.right.left = new TreeNode(7);

		n.dfs(root);

		System.out.println(n.diff);
	}

	public void dfs(TreeNode node)
	{
		helper(node);
	}

	private void helper(TreeNode root)
	{
		if(root==null)
			return;

		maxq.offer(root);
		minq.offer(root);

		if(maxq.peek().val - minq.peek().val > diff)
			diff = maxq.peek().val - minq.peek().val;

		helper(root.left);
		helper(root.right);

		maxq.remove(root);
		minq.remove(root);	
		
	}
}

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
		this.val = val;
	}

	@Override
	public boolean equals(Object o)
	{
		if(o instanceof TreeNode)
		{
			TreeNode temp = (TreeNode)o;
		 	if(this==null && temp == null)
		 		return true;
		 	if(this==null || temp== null)
		 		return false;
		 	return this.val == temp.val;
		}
		else
		{
			return false;
		}
	}

	@Override
	public int hashCode()
	{
		return (this.val+"").hashCode();
	}

	public String toString()
	{
		return this.val+"";
	}
}

import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;

public class BalanceSumBinaryTree
{
	public static void main(String[] args)
	{
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(1);

		root.right.left = new TreeNode(1);
		
		BalanceSumBinaryTree b = new BalanceSumBinaryTree();
		System.out.println(b.isBalance(root));
		System.out.println(b.allBalanceNodes(root));
	}

	public boolean isBalance(TreeNode root)
	{
		if(root==null)
			return true;

		int left = helper(root.left);
		int right = helper(root.right);

		return left==right;
	}

	private int helper(TreeNode root)
	{
		if(root==null)
			return 0;
		int left = helper(root.left);
		int right = helper(root.right);

		return left + root.val + right;
	}

	public List<TreeNode> allBalanceNodes(TreeNode root)
	{
		Queue<TreeNode> next = new LinkedList<>();
		Queue<TreeNode> curr;
		next.offer(root);
		
		List<TreeNode> res = new ArrayList<>();

		while(!next.isEmpty())
		{
			curr = next;
			next = new LinkedList<>();

			while(!curr.isEmpty())
			{
				TreeNode temp = curr.poll();
				if(isBalance(temp))
					res.add(temp);

				if(temp.left!=null)
					next.offer(temp.left);
				if(temp.right!=null)
					next.offer(temp.right);
			}
		}
		return res;
	}
}

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
		this.val = val;
	}

	public String toString()
	{
		return this.val+" ";
	}
}

public class MatrixToLinkedList
{
	public static void main(String[] args)
	{
		int[][] mat = { { 1, 2, 3 }, 
				        { 4, 5, 6 },
				        { 7, 8, 9 } };

		MatrixToLinkedList m = new MatrixToLinkedList();
		Node node = m.createLinkedList(mat);

		System.out.println(node.val+" : "+node.right.val+" : "+node.down.val+" : "+ node.right.right.val);
	}

	public Node createLinkedList(int[][] mat)
	{
		return helper(mat, 0, 0);
	}

	private Node helper(int[][] mat, int i, int j)
	{
		if(isSafe(mat, i, j))
		{
			Node node = new Node(mat[i][j]);
			node.right = helper(mat, i, j+1);
			node.down = helper(mat, i+1, j);
			return node;
		}
		return null;
		
	}

	public boolean isSafe(int[][] mat, int row, int col)
	{
		if(row < 0|| row >= mat.length || col<0 || col>= mat[row].length)
			return false;
		return true;
	}


}

class Node
{
	int val;
	Node down;
	Node right;

	Node(int val)
	{
		this.val = val;
	}
}

import java.util.Set;
import java.util.HashSet;

public class LongestRepeatingSubstring
{
	public static void main(String[] args)
	{
		LongestRepeatingSubstring l = new LongestRepeatingSubstring();
		System.out.println(l.find("banana"));
		System.out.println(l.find("abcdefg"));
		System.out.println(l.find("aaaaaaa"));
		System.out.println(l.find(""));
	}

	public String find(String s)
	{
		String max = "";
		String localMax = "";
		for(int i=1;i<s.length();i++)
		{
			localMax = helper(s, i);
			if(localMax.length()>max.length())
				max = localMax;
		}
		return max;
	}	

	private String helper(String s, int windowSize)
	{
		String res = "";
		Set<String> set = new HashSet<>();
		for(int i=0;i<s.length()-windowSize+1;i++)
		{
			String temp = s.substring(i, i+windowSize);
			if(set.contains(temp))
			{
				res = temp;
			}
			else
			{
				set.add(temp);
			}
		}
		return res;
	}

}

import java.util.Stack;
import java.util.Arrays;

public class NextHigher
{
	public static void main(String[] args)
	{
		int[] a = {10, 5, 2, 1, 4, 6, 7};
		//int[] a = {1, 2, 3};
		//int[] a = {5, 4, 3, 2, 1};
		//int[] a = {1, 1, 1};
		NextHigher n = new NextHigher();
		System.out.println(Arrays.toString(n.populateNextHigher(a)));
	}	

	public int[] populateNextHigher(int[] a)
	{
		Stack<Integer> stack = new Stack<>();
		int[] res = new int[a.length];
		for(int i = a.length-1;i>=0;i--)
		{
			if(stack.isEmpty())
			{
				stack.push(a[i]);
				res[i] = a[i];
			}
			else
			{
				while(!stack.isEmpty() && stack.peek()<a[i])
					stack.pop();
				if(!stack.isEmpty())
					res[i] = stack.peek();
				else
					res[i] = a[i];
				stack.push(a[i]);
			}
		}
		return res;
	}
}

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.List;
public class KMaximumNumbers
{
	PriorityQueue<Integer> pq;
	int capacity;
	KMaximumNumbers(int k)
	{
		pq = new PriorityQueue(k);
		this.capacity = k;
	}

	public static void main(String[] args)
	{	
		KMaximumNumbers k = new KMaximumNumbers(3);
		int[] a = {0, 10, 7, 1, 3, 4, 9, 5};
		for(int i = 0;i<a.length;i++)
		{
			k.add(a[i]);
			System.out.println(k.findKMax());
		}
	}

	public void add(int a)
	{
		if(pq.size()>=this.capacity && pq.peek() < a)
		{
			pq.poll();
			pq.add(a);	
		}
		else if(pq.size() < this.capacity)
			pq.add(a);

	}

	public List<Integer> findKMax()
	{
		List<Integer> list = new ArrayList<>(pq);
		return list;
	}
}

import java.util.Arrays;
public class ElementsLessThanOrEqual
{
	public static void main(String[] args)
	{
		int[] a = {0, 1, 7};
		int[] b = {1};

		ElementsLessThanOrEqual e = new ElementsLessThanOrEqual();
		e.find(a, b);
	}

	public int[] find(int[] a, int[] b)
	{
		Arrays.sort(b);
		int[] c = new int[a.length];
		for(int i=0;i<a.length;i++)
		{
			c[i] = findHelper(a[i], b);
			System.out.println(Arrays.toString(c));		
		}
		return c;
	}

	public int findHelper(int a, int[] b)
	{
		int lo = 0;
		int hi = b.length-1;

		while(lo <=  hi)
		{
			int mid = lo + (hi-lo)/2;
			if(b[mid]<=a)
			{
				int p = mid;
				while(p<b.length && b[p]<=a)
					p++;
				return p;
			}
			else
			{
				hi = mid-1;
			}
		}
		return -1;
	}

}

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

public class CheeseMaze
{
	public static void main(String args[])
	{
		int width = 10;
		int height = 20;

		int[][] cheeseCells = { { 5, 3 }, { 4, 3 }, { 7, 11 } };
		int[][] blockCells = { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } };
		int[] anotherPerson = { 8, 17 };

		CheeseMaze c = new CheeseMaze();
		int[][] grid = c.createGrid(width, height, cheeseCells, blockCells, anotherPerson);
		Result result = c.findCheese(grid, anotherPerson);

		System.out.println(result);
		
	}

	public Result findCheese(int[][] grid, int[] anotherPerson)
	{
		boolean[][] visited = new boolean[grid.length][grid[0].length];
		return findCheeseHelper(grid, visited, anotherPerson);
	}

	private Result findCheeseHelper(int[][] grid, boolean[][] visited, int[] anotherPerson)
	{
		int[] x = {0, 0, -1, 1};
		int[] y = {-1, 1, 0, 0};

		Queue<Integer[]> next = new LinkedList<>();
		Queue<Integer[]> curr = null;
		next.offer(new Integer[]{0,0});
		int stepsCount = 0;
		int globalStepsCount = 0;
		int cheeseCount  = 0;
		int[] lastCheese = new int[2];
		while(!next.isEmpty())
		{
			curr = next;
			next = new LinkedList<>();

			while(!curr.isEmpty())
			{
				Integer[] temp = curr.poll();
				if(!visited[temp[0]][temp[1]])
				{
					visited[temp[0]][temp[1]] = true;
					if(grid[temp[0]][temp[1]]==2)
					{
						globalStepsCount += stepsCount;
						stepsCount = 0;
						cheeseCount++;
						lastCheese[0] = temp[0];
						lastCheese[1] = temp[1];
						next = new LinkedList<>();
						curr = new LinkedList<>();
					}
					for(int i=0;i<x.length;i++)
					{
						int r = temp[0] + x[i];
						int c = temp[1] + y[i];

						if(isSafe(grid, r, c, visited, anotherPerson))
						{
							next.offer(new Integer[]{r, c});
						}
					}
				}
			}
			stepsCount++;
		}

		System.out.println(cheeseCount + " : "+ stepsCount + " : "+globalStepsCount);
		Result r = new Result();
		r.totalSteps  = Math.abs(lastCheese[0]-anotherPerson[0])+Math.abs(lastCheese[1]-anotherPerson[1]) + globalStepsCount;
		r.cheeseCount = cheeseCount;
		return r;
	}

	private boolean isSafe(int[][] grid, int row, int col, boolean[][] visited, int[] anotherPerson)
	{
		//System.out.println(row + " : " + col );
		if(row < 0 || 
			row >= grid.length ||
			col < 0 ||
			col >= grid[row].length ||
			grid[row][col]==0 || 
			visited[row][col] ||
			(row==anotherPerson[0]&&col==anotherPerson[1]))
		{
			return false;
		}
		return true;
	}


	private int[][] createGrid(int width, 
								int height, 
								int[][] cheeseCells, 
								int[][] blockCells,
								int[] anotherPerson)
	{
		int[][] grid = new int[width][height];
		
		for(int i=0;i<grid.length;i++)
		{
			Arrays.fill(grid[i], 1);
		}

		for(int i=0;i<cheeseCells.length;i++)
		{
			grid[cheeseCells[i][0]][cheeseCells[i][1]] = 2;
		}

		for(int i=0;i<blockCells.length;i++)
		{
			grid[blockCells[i][0]][blockCells[i][1]] = 0;
		}
		grid[anotherPerson[0]][anotherPerson[1]]=3;
		for(int i=0;i<grid.length;i++)
		{
			System.out.println(Arrays.toString(grid[i]));
		}

		
		return grid;
	}
}

class Result
{
	int totalSteps;
	int cheeseCount;

	public String toString()
	{
		return "totalSteps: "+ totalSteps + " cheeseCount: " + cheeseCount;
	}
}

Seems like Google PageRank Algorithm

public int helper(int n, String p)
	{
		if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111 && Integer.parseInt(p)%n==0)
			return Integer.parseInt(p);
		else if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111)
			return Math.min(helper(n, p+"0"),helper(n, p+"1"));
		return Integer.MAX_VALUE;

}