CareerCup

Here is a question, why do we need to put the whole dictionary into the memory? The goal is to output all words that can be formed from s. From the example, we know that the order doesn't matter. So we only need to construct a hash map and store all four characters of s in it. And then read the dict from the stream and compare it with the characters in the hash map. I used another hash map. Since there are at most four characters for both strings, we don't need much extra space, do we?

However, if the question is, how to store the output words in an efficient data structure, I guess a trie should be a good one.

public static void validWords(String s, String dict) throws FileNotFoundException, IOException{
		BufferedReader br = new BufferedReader(new FileReader(dict));
		String currLine;
		Map<Character, Integer> sMap = new HashMap<Character, Integer>();
		for(int i = 0; i < s.length(); i++){
			char c = s.charAt(i);
			if(!sMap.containsKey(c))
				sMap.put(c, 1);
			else
				sMap.put(c, sMap.get(c) + 1);
		}
		Map<Character, Integer> word = new HashMap<Character, Integer>();
		while((currLine = br.readLine()) != null){
			if(currLine.length() > 4)
				continue;
			word.clear();
			boolean valid = true;
			for(int i = 0; i < currLine.length(); i++){
				char c = currLine.charAt(i);
				if(!sMap.containsKey(c)){
					valid = false;
					break;
				}
				if(!word.containsKey(c))
					word.put(c, 1);
				else
					word.put(c, word.get(c) + 1);
				if(word.get(c) > sMap.get(c)){
					valid = false;
					break;
				}
			}
			if(valid)
				System.out.println(currLine);
		}
		br.close();
	}

public static int longestSubstring(String s, int m){
		if(s == null || s.length() == 0 || m > s.length())
			return 0;
		Set<Character> unique = new HashSet<Character> ();
		int leftBound = 0;
		int max = 0;
		String rst = "";
		for(int i = 0; i < s.length(); i++){
			char c = s.charAt(i);
			if(!unique.contains(c)){
				if(unique.size() < m)
					unique.add(c);
				else{
					char last = s.charAt(i - 1);
					while(leftBound < i && s.charAt(leftBound) == last)
						leftBound++;
					char toRemove = s.charAt(leftBound);
					while(leftBound < i && s.charAt(leftBound) == toRemove)
						leftBound++;
					unique.remove(toRemove);
					unique.add(c);
				}
			}
			if(i - leftBound + 1 > max){
				max = i - leftBound + 1;
				rst = s.substring(leftBound, i + 1);
			}
		}
		System.out.println(rst);
		return max;
	}

This is a simple Greedy approach.

Sort the array. Start from the maximum, each day we add an element and subtract the number of candles needed. So given

2 2 2

Day 1: 2 - 1 = 1
Day 2: 1 + 2 - 2 = 1
Day 3: 1 + 2 - 3 = 0

public static int maxDays(int[] candles){
		if(candles == null || candles.length == 0)
			return 0;
		Arrays.sort(candles);
		int lit = candles[candles.length - 1] - 1;
		int count = 1;
		
		for(int i = candles.length - 2; i >= 0; i--){
			if(lit + (candles[i] - (count + 1)) < 0)
				break;
			lit += candles[i] - (++count);
		}
		return count;
	}

I am not sure if my approach is correct, but the idea is, since there are multiple threads executing, I use an integer releaseCount to check if all resources have been acquired. If it is, or if it is not at the top of the stack (according to the problem, all dependencies should be executed first), the current task should wait. When it comes to its turn, it will first schedule all of its dependencies and execute them first, then execute the current task. After executing the task, increment the releaseCount and let other task to acquire the resource.

public class TaskSchedulerParallel {
	Set<Task> executed;
	Stack<Task> scheduler;
	int releaseCount;
	//number of parallel nodes
	public TaskSchedulerParallel(int N){
		executed = new HashSet<Task>();
		scheduler = new Stack<Task>();
		releaseCount = N;
	}
	public synchronized void schedule(Task t) throws InterruptedException {
		scheduler.push(t);
		for(Task dep : t.GetDependencies()){
			if(!executed.contains(dep) && !scheduler.contains(dep))
				schedule(dep);
		}
		if(releaseCount == 0 || (!scheduler.isEmpty() && scheduler.peek() != t))
			t.wait();
		releaseCount--;
		scheduler.pop();
		t.Run();
		executed.add(t);
		releaseCount++;
	}
	

}

Well, I think one way to deal with cycles is to add another set inProcess, if we hit a cycle, i.e., the inProcess set has already had that element, just execute that element first.

public class TaskScheduler {
	Set<Task> executed;
	Set<Task> allTasks;
	Set<Task> inProcess;
	public TaskScheduler(Set<Task> tasks){
		allTasks = tasks;
		executed = new HashSet<Task>();
		inProcess = new HashSet<Task>();
	}
	public void schedule(Set<Task> allTasks){
		for(Task t : allTasks){
			if(executed.contains(t))
				continue;
			if(!inProcess.isEmpty() && inProcess.contains(t)){
				t.Run();
				inProcess.remove(t);
				executed.add(t);
				continue;
			}
			inProcess.add(t);
			schedule(t.GetDependencies());
			t.Run();
			inProcess.remove(t);
			executed.add(t);
		}
	}
}

public static int roles(Struct[][] board){
		if(board == null || board.length == 0 || board[0].length == 0 || board.length != board[0].length)
			return 0;
		int n = board.length;
		int[] roles = new int[n * n];
		for(int i = 0; i < n * n; i++){
			int x = i / n;
			int y = (x % 2 != 0) ? (n - 1 - i % n) : i % n;
			if(i < 6){
				roles[i] = board[x][y].s.equals("SU") ? Integer.MAX_VALUE / 2 : 1;
			}
			else{
				roles[i] = Integer.MAX_VALUE;
				for(int j = i - 6; j < i; j++)
					roles[i] = Math.min(roles[i], roles[j] + 1);
				if(board[x][y].s.equals("LU"))
					//in case the lower end of the ladder is the upper end of the
					//snake
					roles[i] = Math.min(ladder(board, x, y, roles),  roles[i]);
				else if(board[x][y].s.equals("SU"))
					roles[i] = Integer.MAX_VALUE / 2;
			}
		}
		
		return roles[n * n - 1];
	}
	private static int ladder(Struct[][] board, int x, int y, int[] roles){
		int n = board.length;
		int xc = board[x][y].x;
		return xc % 2 != 0 ? roles[xc * n + (n - 1 - board[x][y].y)]
					: roles[xc * n + board[x][y].y];
	}
	/**
	 * consists the string which represents the status of the square:
	 * "SU": snake upper side
	 * "SL": snake lower side
	 * "LU": ladder upper side
	 * "LL": ladder lower side
	 * as well as the coordinates of its corresponding end
	 * e.g., "SU", 1, 1 indicates the lower side of the snake is at x = 1, y = 1	
	 * @author shirleyyoung
	 *
	 */
	private static class Struct{
		String s;
		//the coordinate of the corresponding square
		int x;
		int y;
		public Struct(String s, int x, int y){
			this.s = s;
			this.x = x;
			this.y = y;
		}
	}

Actually it doesn't make much difference even if duplicates are allowed.

public char nextChar2(char[] list, char c) {
		if (list == null || list.length == 0)
			throw new IllegalArgumentException("Null or empty list!");
		int start = 0;
		int end = list.length - 1;
		if (c < list[0] || c >= list[list.length - 1])
			return list[0];
		while (start < end) {
			int mid = (start + end) / 2;
			if (c == list[mid]) {
				if (list[mid + 1] > c)
					return list[mid + 1];
				else 
					start = mid + 1;
			}
			else if (c < list[mid]) {
				end = mid - 1;
			}
			else
				start = mid + 1;
		}
		if (list[start] == c)
			return list[start + 1];
		return list[start];

}

Should separate numOfZero == 0 case and numOfZero == 1 case

public class SelfExcludingProduct {
	public int[] selfExcludingProduct (int[] input) {
		if (input == null) 
			throw new NullPointerException ("Null input array!");
		int[] productArray = new int[input.length];
		if (input.length == 0) 
			return productArray;
		int product = 1;
		int numOfZeros = 0;
		for (int i = 0; i < input.length; i++) {
			if (input[i] != 0)
				product *= input[i];
			else
				numOfZeros++;
			if (numOfZeros >= 2) {
				return productArray;
			}
		}
		for (int i = 0; i < input.length; i++) {
			if (numOfZeros == 0) {
				productArray[i] = product / input[i];
			}
			else {
				if (input[i] == 0) 
					productArray[i] = product;
				else
					productArray[i] = 0;
			}
				
		}
		
		return productArray;
			
	}

}

This question is very similar to the Text Justification on LeetCode. Unless I understand the problem wrong, this code works fine.

import java.util.ArrayList;


public class TextJustification {
	public ArrayList<String> fullJustify(String[] words, int L) {
        if (words == null)
            throw new NullPointerException("Null string array!");
        ArrayList<String> rst = new ArrayList<String> ();
        if (words.length == 0)
            return rst;
        int maxLength = words[0].length();
        for (int i = 0; i < words.length; i++) {
            maxLength = Math.max(maxLength, words[i].length()); 
        }
        if (maxLength > L)
            return rst;
            
        int prev_start = 0;
        int currSum = 0;
        int countWord = 0;
        for (int i = 0; i <= words.length; i++) {
            if (i == words.length || (currSum + words[i].length() + countWord > L)) {
                int totalSpace = L - currSum;
                String tmp = "";
                if (i == words.length || countWord == 1) {
                    for (int j = prev_start; j < i; j++) {
                        tmp += words[j];
                        if (j != i - 1)
                            tmp += " ";
                    }
                    tmp = appendSpace(tmp, L - tmp.length());
                }
                else {
                    int spaceEachWord = totalSpace / (countWord - 1);
                    int extraSpace = totalSpace % (countWord - 1);
                    for (int j = prev_start; j < i - 1; j++) {
                        tmp += words[j];
                        if (j != i - 1) {
                            tmp = appendSpace(tmp, spaceEachWord);
                            }
                        
                        if (extraSpace > 0) {
                            tmp += " ";
                            extraSpace--;
                        }
                    }
                    tmp += words[i - 1];
                }
                rst.add(tmp);
                if (i == words.length)
                    break;
                prev_start = i;
                currSum = words[i].length();
                countWord = 1;
            }
            else {
            currSum += words[i].length();
            countWord++;
            }
        }
        return rst;
        
    }
    private String appendSpace(String s, int space) {
        String rst = s;
        for (int i = 0; i < space; i++)
            rst += " ";
        return rst;
    }

}

Is it possible to do back tracking?

public class PossibleTriangle {
	public ArrayList<ArrayList<Integer>> possibleTriangle(int[] nums)
	{
		ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
		if (nums == null || nums.length == 0)
			return rst;
		ArrayList<Integer> triplets = new ArrayList<Integer>();
		Arrays.sort(nums);
		getTriangle(rst, triplets, nums, 0);
		return rst;
	}
	private void getTriangle(ArrayList<ArrayList<Integer>> rst, ArrayList<Integer> triplets, 
			int[] nums, int start)
	{
		if (triplets.size() == 3 && triplets.get(0) + triplets.get(1) > triplets.get(2))
			rst.add(new ArrayList<Integer> (triplets));
		for (int i = start; i < nums.length; i++)
		{
			if (i != start && nums[i] == nums[i - 1])
				continue;
			triplets.add(nums[i]);
			getTriangle(rst, triplets, nums, i + 1);
			triplets.remove(triplets.size() - 1);
		}
	}
	public void printList(ArrayList<ArrayList<Integer>> rst)
	{
		for (int i = 0; i < rst.size(); i++)
			System.out.println(rst.get(i));
	}

}