random
BAN USERWhat are sizes of the lists? If words.size() is considerably smaller than part.size(), we could take the following approach.
1. Build a trie of all the words in parts. We can do this in O(P.L) time, where L is the average length of the of words in parts, and P, the number of elements in parts. We can maintain the index of the word in the parts array as a value in the leaf node representing the part word.
2. While building the trie above, we could determine the min (m) and max (M) length of any word in parts.
3. For each word in words, generate substrings of size S where m <= S <= M, and lookup each
such substring in the trie constructed in 1 above. Pick the longest substring that's found in the trie.
If there's a tie, pick the one that has the smallest index (we stored in the trie in 1 above)
Why not use an interval tree, with the tree nodes storing lists of pairs of the form <Interval,count_of_toggles_done_to_the_interval>.
On each toggle operation on (i,j), follow the interval tree construction algorithm to locate/create the node where the new interval can be added. If the interval has already been toggled, we'd discover it, and therefore increment the toggle_counter. Otherwise,we'd just insert the pair <(i,j),1>. This can be achieved in log(n) time, where n is the current size of the interval tree.
isOn(i) would then just be an interval tree lookup for enumerating all the intervals that contain i. We can then sum up the toggle_counters of the intervals in that intersection list, and return (sum%2 != 0) (since the bulbs were initially all off)
public static String expand(String s){
System.out.println(" Expanding String --> "+s);
Map<Integer,Integer> bracesPairIdxs = new HashMap<Integer,Integer>();
Stack<Integer> lastOpenBraceIndx = new Stack<Integer>();
int indx = 0;
for(char ch : s.toCharArray()){
if(ch == '['){
lastOpenBraceIndx.push(indx);
}else if(ch == ']'){
bracesPairIdxs.put(lastOpenBraceIndx.pop(),indx);
}
indx++;
}
System.out.println("bracesPairIdxs --> "+bracesPairIdxs);
return expandInternal(s,0,s.length()-1,bracesPairIdxs);
}
public static String expandInternal(String s,int start,int end, Map<Integer,Integer> bracesPairIdxs){
StringBuffer output = new StringBuffer();
int numRepeatToken = 0;
int indx = start;
while(indx <= end){
char ch = s.charAt(indx);
if(isNumber(ch)){
numRepeatToken = numRepeatToken*10 + ch - '0';
}else{
if(ch == '['){
String expandedToken = expandInternal(s,indx+1,bracesPairIdxs.get(indx)-1,bracesPairIdxs);
int count = 0;
while (count < numRepeatToken ){
output.append(expandedToken);
count++;
}
indx = bracesPairIdxs.get(indx)+1;
numRepeatToken = 0;
continue;
}else if(ch == ']'){
// we should not hit this condition
}else{
output.append(ch);
}
}
indx++;
}
return output.toString();
}
public class Semaphore {
private final int MAX_SLOTS = 10;
private int empty_slots = MAX_SLOTS;
public void down() {
synchronized (this) {
while (empty_slots == 0) {
try {
wait();
} catch (InterruptedException ex) {
}
}
empty_slots--;
}
}
public void up() {
synchronized (this) {
if (empty_slots < MAX_SLOTS) {
empty_slots++;
}
notifyAll();
}
}
}
Longest path in a DAG. Assuming there are no cycles in the directed graph formed by treating each title as a node , and each adjacency defined by the connectivity property described in the problem.
- random May 01, 2018