CareerCup

package com.practice.algo.and.ds.graph;

/*
A company's organizational structure is represented as
        1: 2, 3, 4
        In the above employees with id 2, 3 and 4 report to 1
        Assume the following hierarchy.
        1: 2, 3, 4
        3: 5, 6, 7
        5: 8, 9, 10
        Given an employee Id, return all the employees reporting to him directly or indirectly
*/

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

public class Graphs_CareerCup_EmployeeReporting {


    public static void main(String[] args) {
        Map<Integer,List<Integer>> empMap = new HashMap<>();
        empMap.put(1, Arrays.asList(2,3,4));
        empMap.put(3, Arrays.asList(5,6,7));
        empMap.put(5, Arrays.asList(8,9,10));
        empMap.put(9, Arrays.asList(11,12,13));
        Graphs_CareerCup_EmployeeReporting o = new Graphs_CareerCup_EmployeeReporting();
        System.out.println(o.getReportees(empMap,3));
    }

    public List<Integer> getReportees(Map<Integer,List<Integer>> empMap,int manager){
        List<Integer> result = new ArrayList<>();
        getReporteesHelper(result,empMap,manager);
        return result;
    }

    private void getReporteesHelper(List<Integer> result, Map<Integer, List<Integer>> empMap, Integer manager) {
        List<Integer> reportees = empMap.get(manager);
        if(reportees==null)
            return;
        for (Integer i: reportees) {
            result.add(i);
            getReporteesHelper(result,empMap,i);
        }
    }

}

public class CareerCup_Amazon_FindGivenNumberInTree {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode root = new TreeNode(0);
		TreeNode o1 = new TreeNode(1);
		TreeNode t2 = new TreeNode(1);
		TreeNode t3 = new TreeNode(3);
		TreeNode f4 = new TreeNode(4);
		TreeNode f5 = new TreeNode(4);
		TreeNode s6 = new TreeNode(6);
		TreeNode s7 = new TreeNode(7);
		TreeNode e8 = new TreeNode(8);
		TreeNode n9 = new TreeNode(9);

		root.left = o1;
		root.right = t2;

		o1.left = t3;
		o1.right = f4;
		
		t2.left = f5;
		t2.right = s6;
		
		t3.left = s7;
		t3.right = e8;
		f5.left = n9;

		CareerCup_Amazon_FindGivenNumberInTree o = new CareerCup_Amazon_FindGivenNumberInTree();
		o.hasNumberInTree(root,149);
	}
	public boolean hasNumberInTree(TreeNode root,Integer n){
		List<Integer> nL = new ArrayList<>();
		
		while(!(n<10)){
			int nR = n%10;
			n = n/10;
			nL.add(0,nR);
		}
		nL.add(0,n);
		
		return hasNumberInTreeHelper(root,nL,-1,0,0);
	}
/*	ex: 
	     3 
	  4     5 
	6   7  8  9*/

	
	public boolean hasNumberInTreeHelper(TreeNode root,List<Integer> nL,int previosLevel,int level,int i){

		if(root==null)
			return false;
		
		if(root.val == nL.get(i)){
			if(previosLevel==-1)
				previosLevel = level;
			else if(level-previosLevel>1)
				return false;
			previosLevel = level;
			i=i+1;			
		}
		if(i==nL.size()){
			return true;
		}
		
		if(hasNumberInTreeHelper(root.left, nL,previosLevel,level+1,i) || hasNumberInTreeHelper(root.right, nL,previosLevel,level+1,i))
			return true;
		
		return false;
	}

}

package com.practice.algo.and.ds.bitmanipulation;

public class BitMask {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[][] arr = {{0,0,0,1},{1,1,1,1},{0,0,1,1},{0,1,1,1}};
		int n = 1;
		for(int i =0;i<3;i++){
			n |=(n<<1);
		}
		int count = Integer.MIN_VALUE;
		for(int i=0;i<arr.length;i++){
			String str = "";
			for(int j=0;j<arr.length;j++){
			str+=arr[i][j];
			}
			int c= Integer.bitCount(Integer.parseInt(str, 2) & n);
			if(c > count){
				count = c;
			}
			
		}
		System.out.println(count);
	}

}

Below line is giving ClassCastException for the one dimensional array

Object obj1[] = (Object[]) cls.cast(obj);

Thanks Tim for an amazing solution. Thats what I was looking for.

I wan to know if this can be solved by set of equations or BFS ?
Here I am not concerned with this particular input but generic input and moves.

Any specific algorithms...or implementation to solve this. BFS or Equations ?

String str = "111100";
String str2 = "000100";
String str3 = "000010";
int kk=0;
for(int i=str.length()-1;i>=0;i--){

if(str.charAt(i)=='1'){
a = a | (1<<kk);
}

kk=kk+1;
System.out.println(a);
}
kk=0;
int b=0;
for(int i=str2.length()-1;i>=0;i--){

if(str2.charAt(i)=='1'){
b = b | (1<<kk);
}

kk=kk+1;
System.out.println(b);
}
kk=0;
int c=0;
for(int i=str3.length()-1;i>=0;i--){

if(str3.charAt(i)=='1'){
c = c | (1<<kk);
}

kk=kk+1;
System.out.println(c);
}
System.out.println(c);
int aa[] = {a,b,c};
int N=3;
int M=6;
int K=5;
for(int i=1;i<(1<<N);i++){
int r =0;
for(int j=0;j<N;j++){
if((i & (1<<j)) !=0){
r = r | aa[j];
}
}
if(K==Integer.bitCount(r)){
System.out.println("found");
break;
}
}

how ll you get 0 and 1

What about doing bit masking and chcking set bits if they add upto required sum.

When we have use some personaised object (not String,Integer etc which already implements these functions)as a key in Hash related data structures i.e. HashMap,TreeMap, HashSet etc then for correct implementation of this key, We need to implement these functions.
It is good practice to implement both these functions together.

Please verify my solution. I could solve it by BruteForce only. Any algorithm can be applied on this? Experts please help

package com.tc.graphs;

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

public class RectangleBorderOnes {

	/**
	 * @param args
	 */
	
	Set<Integer> t = new TreeSet<Integer>();
	
	int[][] array = { { 1, 1, 1, 1, 1 },		    { 1, 1, 1, 1, 0 },		    { 1, 1, 1, 1, 0 },		    { 0, 0, 1, 0, 0 } };
	
	
	private void addEdge(int start,int end){
		array[start][end] = 1;
	}
	
	private int calculate(){
		
		for(int row=0;row<array.length;row++){
			for(int colum=0;colum<array[row].length-1;colum++){
				//System.out.println(row + "" +colum);
				if((array[row][colum]==1)){
				for(int columCol=colum+1;columCol<array[row].length;columCol++){
					//System.out.println(colum + "" + columCol);
					int flag = 0;
						for(int i=colum;i<=columCol;i++){
							if(array[row][i]==0){
								flag=0;	
								break;
							}else {
								flag=1;	
							}
						}
						if(flag==1){
							checkOnes(row,colum,columCol);
						}
						
					
					}
				}else{
				//		break;
					}
				}
				
				
			}
			
		
		Object[] result = t.toArray();
		return (Integer)result[result.length - 1];
	}
	
	private void checkOnes(int row,int colum,int columCol) {
		// TODO Auto-generated method stub
		// Now we got the width
		int width = columCol - colum + 1;
		
		for(int i = row+1;i<array.length;i++){
			int flag = 1;
			
			for(int k = row+1;k<=i;k++){
				if(array[k][colum]==0 ||  array[k][columCol]==0){
					flag=0;	
				}
			}
			
			if(flag==1){
				int cc=1;
				for(int j = colum+1;j<=columCol-1;j++){
					if(array[i][j]==0){
						cc=0;
					}
				}
					if(cc==1){
						//System.out.println("rectangle Completed");
						int area = (i-row+1)*(columCol-colum+1);
						//System.out.println(area);
						t.add(area);
					}
				}
			}
		}
		
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		RectangleBorderOnes r = new RectangleBorderOnes();
		

		
		int res = r.calculate();
		System.out.println(res);
		
		
		
	}

}