CareerCup

this is a backTracking algo. Maintain an arrayList and keep replacing pairs with the character.
If you dont get the solution, loop for the next element pair.
If nothing happens, then return -1.

import java.io.*;
import java.util.*;

class GFG {
	public static void main (String[] args) {
		String input = "ABACB";
		//String dict[] = {"AB,C","AC,B","BC,A"};
		String dict[] = {"AB,C","CC,B","BB,B"};
		System.out.println(findLen(input,dict));
	}
	
	static int findLen(String input, String dictionary[]) {
	    HashMap<String,Character> map = new HashMap<>();
	    
	    for(String dict : dictionary) {
	        String str = dict.substring(0,2);
	        String revStr = "" + dict.charAt(1) + dict.charAt(0);
	        map.put(str,dict.charAt(3));
	        map.put(revStr,dict.charAt(3));
	        //System.out.println(str + " " + revStr);
	    }
	    
	    ArrayList<Character> backTrack = new ArrayList<>();
	    for(int i=0; i<input.length(); i++){
	        backTrack.add(input.charAt(i));
	    }
	    
	    int len = findLenUtil(map,backTrack);
	    
	    return len;
	    
	}
	
	static int findLenUtil(HashMap<String,Character> map, ArrayList<Character> backTrack) {
	    
	    for(Character ch : backTrack) {
	        System.out.print(ch + " ");
	    }
	    System.out.println();
	    
	    if(backTrack.size() == 1)
	        return 0;
	    
	    for(int i=0; i<backTrack.size()-1; i++) {
	        char ch1 = backTrack.get(i);
	        char ch2 = backTrack.get(i+1);
	        //System.out.println(ch1 + " " + ch2);
	        
	        String str = "" + ch1 + ch2;
	        if(map.containsKey(str)) {
	            char replace = map.get(str);
	            backTrack.set(i,replace);
	            backTrack.remove(i+1);
	            
	            int len = findLenUtil(map,backTrack);
	            if(len != -1) {
	                return len + 1;
	            }
	            else {
	                backTrack.set(i,ch1);
	                backTrack.add(i+1,ch2);
	            }
	        }
	    }
	    return -1;
	}
}

Have a hashMap<String, ArrayList<String>>
Key is the move 1,2 or 2,3 or 2,1 etc. And the ArrayList will have the list of employees doing that move.
Fill this hashMap.
Then iterate through the hashMap from the top. Check if there is a key with reverse of move in the map.
If there is then, keep matching and removing from the arrayLists till one of them becomes empty.

import java.io.*;
import java.util.*;

public class BuildingSwap {
    
    public static void main(String[] args) {
        String [] input = {"John,1,2","Dan,2,3","Mary,2,1","Eli,3,2","Sam,1,3","Tarly,3,2",
                           "Joey,1,2","Emma,2,3","Stone,2,3","Snow,2,1"};
        ArrayList<String> swaps = findSwaps(input);
        System.out.println(swaps);
    }
    
    static ArrayList<String> findSwaps (String input[]) {
        
        HashMap <String,ArrayList<String>> map = new HashMap<>();
        ArrayList<String> swaps = new ArrayList<>();
        
        for(String emp : input) {
            String move = emp.substring(emp.length()-3);              // will give the moves like 1,2
            if(map.get(move) == null) {
                ArrayList<String> arr = new ArrayList<>();
                arr.add(emp.substring(0,emp.length()-4));
                map.put(move,arr);
            }
            else
                map.get(move).add(emp.substring(0,emp.length()-4));
        }
        
        
        for(Map.Entry<String,ArrayList<String>> entry : map.entrySet()) {
            String move = entry.getKey();
            ArrayList<String> emps = entry.getValue();
            
            String revMove = getReverse(move);
            
            if(map.containsKey(revMove)) {
                ArrayList<String> revEmps = map.get(revMove);
                while(emps.size() > 0 && revEmps.size() > 0) {
                    String emp1 = emps.get(0);
                    String emp2 = revEmps.get(0);
                    swaps.add(new String(emp1 + " & " + emp2));
                    emps.remove(emp1);
                    revEmps.remove(emp2);
                }
            }
        }
        
        return swaps;
    }
    
    static String getReverse(String move) {
        return new String(move.charAt(2) + "," + move.charAt(0));
    }
}

Let the input matrix be called input[][].
Have another matrix of same size called num[][].
copy the first row and first column from input[][] to num[][].
Then update the num matrix such that num[i][j] should hold the number of continuous 1s in that column j if the input[i][j] == 1.
if input[i][j] == 0, then num[i][j] = 0.
Now look for odd numbers in num[][] greater than 1.
Lets say you find 3, then go up one step and check if the left and right are non zero.
If yes, then the size of plus is 1.
Now, keep looking for odd numbers greater than 3.
If you found 5, check again for left and right of two places up.
Then look for 7.. and so on.

complexity : O(n2)

Java solution :

//Algo:
1st part: Use BFS to find the distance from the input random coordinate to the nearest door.
2nd part: Insert all the door coordinates with distance 0 into the queue. Now run BFS.
We are doing this because we want the distance to be updated from all directions. Spreading the gossip from all sources. :)
Maintain a third 2D array which will hold the distances. Then return this distance array.

import java.io.*;
import java.util.*;

class Coordinate {
    int x,y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Array {
    public static final int grid[][] = {
        {2, 1, 2, 1, 2, 2, 2},
        {2, 0, 2, 0, 0, 0, 2},
        {2, 0, 0, 0, 2, 0, 2},
        {2, 2, 0, 2, 0, 0, 2},
        {2, 0, 0, 0, 0, 0, 2},
        {2, 2, 2, 0, 0, 0, 2},
        {2, 2, 2, 2, 2, 2, 2}};

    static final int moves[][] = {{1,0,-1,0},
                                  {0,1,0,-1}};

	public static void main (String[] args) {
		System.out.print(getMinDist(grid,2,3));
	}
	
	static int getMinDist(int grid[][], int m, int n) {
	    if(grid[m][n] == 2)
	        return -1;
	   
	    if(grid[m][n] == 1)
	        return 0;
	        
	    int visited[][] = new int[grid.length][grid[0].length];
	    
	    int dist = getMinDistUtil(grid,m,n,visited);
	    return dist;
	}
	
	static int getMinDistUtil(int grid[][], int m, int n, int visited[][]) {
	    
	    visited[m][n] = 1;
	    
	    Queue<Coordinate> queue = new LinkedList<>();
	    queue.add(new Coordinate(m,n));
	    
	    // get neighbors and add to queue if valid
	    while(!queue.isEmpty()) {
	        
	        Coordinate coor = queue.poll();
	        
	        int dist = visited[coor.x][coor.y];
	        System.out.println("dist : " + dist + " x,y " + coor.x + "," + coor.y);
	        
	        if(grid[coor.x][coor.y] == 1)
	            return (dist - 1);
	       
	        for(int i=0; i<moves[0].length; i++) {
	            int X = coor.x + moves[0][i];
	            int Y = coor.y + moves[1][i];
	            System.out.println("X,Y : " + X + "," + Y);
	            if(X >= 0 && X < grid.length &&
	               Y >= 0 && Y < grid[0].length && 
	               grid[X][Y] != 2 && visited[X][Y] == 0) 
	            {
	                   visited[X][Y] = dist + 1;
	                   queue.add(new Coordinate(X,Y));
	            }
	        }
	    }

	    return -1;
	}
}

import java.io.*;

class Array {
	public static void main (String[] args) {
		int arr[][] = {{0,0,0,1,1,1},
		               {0,0,1,1,1,1},
		               {0,0,0,0,0,0},
		               {0,0,1,1,1,1}};
		findMaxRow(arr);
	}
	
	static void findMaxRow(int arr[][]) {
	    int index = arr[0].length - 1;
	    for(int i=0; i<arr.length; i++){
	        while(arr[i][index] == 1) {
	            index--;
	        }
	    }
	    for(int i=0; i<arr.length; i++){
	        if(arr[i][index+1] == 1)
	            System.out.println(i);
	    }
	}
}

Use LinkedHashMap to preserve the order of characters.

import java.io.*;
import java.util.*;

class GetFirstUniqueChar {
	public static void main (String[] args) {
		String str = "abcdeabc";
		Map<Character,Integer> map = new LinkedHashMap<>();
		for(int i=0 ; i<str.length(); i++) {
		    if(map.get(str.charAt(i)) != null) {
		        int num = map.get(str.charAt(i));
		        map.put(str.charAt(i),num+1);
		    }
            else
                map.put(str.charAt(i),1);
		}
		
		for(Map.Entry<Character,Integer> entry : map.entrySet()) {
		    if(entry.getValue() == 1) {
		        System.out.println(entry.getKey());
		        return;
		    }
		}
		
	}
}

This is similar to the shuffle debts feature in Splitwise.com
Here is a Java solution :

import java.io.*;
import java.util.*;

public class SplitWise {
	public static void main (String[] args) {
		int input[] = {1,9,13,-14,-2,-7};
		shuffleDebts(input);
	}
	
	static void shuffleDebts(int debts[]) {
	    
	    Comparator<friendDebtPair> compMax = new maxComparator();
	    Queue<friendDebtPair> maxHeap = new PriorityQueue<friendDebtPair>(1,compMax);
	    
	    Comparator<friendDebtPair> compMin = new minComparator();
	    Queue<friendDebtPair> minHeap = new PriorityQueue<friendDebtPair>(1,compMin);
	    
	    for(int i=0; i<debts.length; i++)
	    {
	        if(debts[i] >= 0)
	            maxHeap.add(new friendDebtPair(i,debts[i]));
	        else
	            minHeap.add(new friendDebtPair(i,debts[i]));
	    }
	    
	    while(maxHeap.size() > 0 && minHeap.size() > 0) {
	        friendDebtPair giver = maxHeap.peek();
	        friendDebtPair receiver = minHeap.peek();
	        int balance = giver.debt + receiver.debt;
	        
	        if(balance > 0) {
	            System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(receiver.debt));
	            maxHeap.poll();
	            giver.debt = balance;
	            maxHeap.add(giver);
	            minHeap.poll();
	        }
	        else if(balance < 0) {
	            System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(giver.debt));
	            maxHeap.poll();
	            minHeap.poll();
	            receiver.debt = balance;
	            minHeap.add(receiver);
	        }
	        else {
	            System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(receiver.debt));
	            maxHeap.poll();
	            minHeap.poll();
	        }
	    }
	    
	}
}

class friendDebtPair {
    int friend;
    int debt;
    friendDebtPair(int f, int d) {
        friend = f;
        debt = d;
    }
}

class maxComparator implements Comparator<friendDebtPair> {
    public int compare(friendDebtPair f1, friendDebtPair f2) {
        return(f2.debt - f1.debt);
    }
}

class minComparator implements Comparator<friendDebtPair> {
    public int compare(friendDebtPair f1, friendDebtPair f2) {
        return(f1.debt - f2.debt);
    }
}

Output:

2->3:13
1->5:7
1->4:2
0->3:1