Looper
BAN USERSimple BFS
private static int dr[] = {-1, 0, 1, 0};
private static int dc[] = {0, 1, 0, -1};
public static int getArea(char[][] matrix, int row, int col) {
LinkedList<int[]> queue = new LinkedList<int[]>();
boolean[][] visited = new boolean[matrix.length][matrix.length];
int[] pair = {row, col};
queue.addFirst(pair);
visited[row][col] = true;
int area = 0;
char color = matrix[row][col];
while (!queue.isEmpty()) {
int[] point = queue.removeLast();
area++;
for (int i=0; i<dr.length; i++) {
int newR = point[0] + dr[i];
int newC = point[1] + dc[i];
if (newR < 0 || newC < 0 || newR >= matrix.length || newC >= matrix.length || visited[newR][newC] || matrix[newR][newC] != color) {
continue;
}
visited[newR][newC] = true;
int[] next = {newR, newC};
queue.addFirst(next);
}
}
return area;
This can be done in O(nlogn) where n is the length of the search string ( or the characters to use)
The key is to store the dictionary that makes it amenable to do O(1) lookups. Dictionary should be stores as a HashMap where key is sorted unique set of characters and the value is a linked list of all words in the dictionary that uses all those characters. The linked list must always be in descending order of word lengths.
Lookup: Just sort input characters, lookup in the HashMap and return the 1st word in the linkedlist - O( time to sort chars )
Inserting a new word in the dictionary: Sort chars of the word, remove redundant chars, lookup the linked list in the HashMap and insert the new word at the right spot in the LinkedList (so that we preserve the descending world length criteria) - O (time to sort chars) + O(number of words in that bucket)
Code
public class SortedDictionary {
private final Map<String, List<String>> dictionary;
public SortedDictionary() {
dictionary = new HashMap<String, List<String>>();
}
public static SortedDictionary create(String[] words) {
SortedDictionary dictionary = new SortedDictionary();
for (String word : words) {
dictionary.add(word);
}
return dictionary;
}
public void add(String word) {
String sortedString = getSortedString(word);
List<String> words = dictionary.get(sortedString);
if (words == null) {
words = new LinkedList<String>();
words.add(word);
} else {
insertAtSortedLocation(word, words);
}
dictionary.put(sortedString, words);
}
private void insertAtSortedLocation(String word, List<String> words) {
int index = 0;
for (String str : words) {
if (str.length() <= word.length()) {
words.add(index, word);
return;
}
index++;
}
words.add(word);
}
private String getSortedString(String str) {
char[] sorted = str.toLowerCase().toCharArray();
Arrays.sort(sorted);
StringBuffer result = new StringBuffer();
boolean firstChar = true;
char lastChar = ' ';
for (char c : sorted) {
if (firstChar || c != lastChar) {
lastChar = c;
firstChar = false;
result.append(c);
}
}
return result.toString();
}
public String search(String letters) {
String sortedString = getSortedString(letters);
List<String> list = dictionary.get(sortedString);
if (list == null) return null;
return list.get(0);
}
}
This can be broken into sub-problems. Here is the recurrence relation
LexicographicRank(A) = 1 (when A has just 1 char or if A is empty)
otherwise
LexicographicRank(A) = Rank(A.charAt(0), A) * LexicographicRank(A.substring(1))
Rank(char c, String A) = #(unique characters in A < c) + 1
e.g rank of C in "CDA" is 2
To make this work for extremely large matrices, you would replace recursion with an explicitly maintained stack or queue (rather than using the recursion stack). Instead of recursing you would add candidates to this data structure and keep popping them off and processing them till the stack is empty
- Looper October 30, 2012This is what is known as floodfill, an application of DFS. For each element in the array that is a 1 you attempt to recursively search all 4 neighbors for 1s, the search continues till you either hit the boundaries or see 0s. Also as and when you find 1s you make them 0s so that they are not counted again. Repeat this search for every element
Code
public static int countIslands(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int result = 0;
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
if (matrix[i][j] == 1) {
result++;
doFill(matrix, i, j);
}
}
}
return result;
}
public static void doFill(int[][] matrix, int row, int col) {
if (row < 0 || col < 0 || row >= matrix.length || col >=matrix[0].length || matrix[row][col] == 0) {
return;
}
matrix[row][col] = 0;
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
for (int i=0; i<dr.length; i++) {
doFill(matrix, row + dr[i], col + dc[i]);
}
}
Agree with Johnny's topological sort solution. Construct a graph whose nodes each represent one number slot. If the nodes of the graph ar a1, a2... an, ai -> ai+i (edge from i to i+1) if signature(i) = I and ai <- ai+1 (edge from i+1 to i) if signature(i)=D
Run the topological sort on all the nodes starting from the last node since you wish to have the last one be assigned the biggest value
Code:
public static int[] findLexicographicallyLowestPermutation(String signature) {
if (signature == null) return null;
int[] result = new int[signature.length() + 1];
int graph[][] = new int[signature.length() + 1][signature.length() + 1];
for(int i=0; i<graph.length; i++) for(int j=0; j<graph[i].length; j++) graph[i][j] = 0;
for(int i=0; i<signature.length(); i++) {
if (signature.charAt(i) == 'D') {
graph[i+1][i] = 1;
} else {
graph[i][i+1] = 1;
}
}
boolean visited[] = new boolean[signature.length() + 1];
int topValue = result.length;
for (int i=result.length-1; i>=0; i--) {
topValue = topSort(graph, visited, result, i, topValue);
}
return result;
}
public static int topSort(int[][] graph, boolean[]visited, int[] result, int n, int topValue) {
if (visited[n]) return topValue;
visited[n] = true;
for(int i=0; i<graph.length; i++) {
if (graph[n][i] != 0) {
topValue = topSort(graph, visited, result, i, topValue);
}
}
result[n] = topValue;
return topValue - 1;
}
Implementation using semaphores
public class BoundedBlockingQueue<T> {
private final List<T> queue;
private final Semaphore availableItem;
private final Semaphore availableSpace;
public BoundedBlockingQueue(int size) {
this.queue = new LinkedList<T>();
availableItem = new Semaphore(0);
availableSpace = new Semaphore(size);
}
public void add(T element) throws InterruptedException {
availableSpace.acquire();
boolean isAdded = false;
try {
synchronized (this) {
isAdded = queue.add(element);
}
} finally {
if (!isAdded) {
availableSpace.release();
} else {
availableItem.release();
}
}
}
public T remove() throws InterruptedException {
availableItem.acquire();
T element;
synchronized (this) {
element = queue.remove(queue.size() - 1);
availableSpace.release();
}
return element;
}
}
Very elegant solution!. Just one caveat.. In the case there there are 2 or more intervals sharing the same start or end values i.e a.start == b.start || a.end == b.end || a.start == b.end || a.end == b.start. In this case you would need to update the value for the key rather than just put it.
Must do something like this...
- Looper May 18, 2014