Igor
BAN USERimport java.lang.*;
import java.util.*;
class WordBreak {
public static void main(String[] args){
Set<String> dic = new HashSet<>();
dic.add("i");
dic.add("like");
dic.add("sam");
dic.add("sung");
dic.add("samsung");
dic.add("mobile");
dic.add("ice");
dic.add("cream");
dic.add("icecream");
dic.add("man");
dic.add("go");
dic.add("mango");
Set<List<String>> answers = test("ilikesamsung", new ArrayList<>(), dic);
System.out.printf("Total answers %s\n", answers.size());
for(List<String> list : answers){
for(String word: list){
System.out.printf("%s ", word);
}
System.out.println();
}
}
private static Set<List<String>> test(String input, List<String> path, Set<String> dic){
Set<List<String>> result = new HashSet<>();
if(input.length() > 0){
for(int i = 1; i <= input.length(); i++){
String prefix = input.substring(0, i);
if(dic.contains(prefix)){
path.add(prefix);
result.addAll(test(input.substring(i), new ArrayList<>(path), dic));
}
}
}else{
result.add(path);
}
return result;
}
}
Create Set<List<Node>>
Iterate over all children of the given input Node.
For each:
Check if it was visited before. (Hashtable, Node->Boolean), skip if it was.
If it was not create a new List<Node> and insert the Node into it. insert the List<...> into Set<List<Node>>
Iterate over all children of the Node, for each discovered ChildNode check if it was visited before. (Hashtable, Node->Boolean), skip if it was. If it's not add into the List<Node>, mark as visited.
Print Set<List<Node>>
private static int[] getMaxSubArray(int[] array) {
int max = array[0];
int maxSoFar = max;
int maxSoFarBegin = 0;
int maxSoFarEnd = 0;
for (int i = 1; i < array.length; i++) {
max = Math.max(array[i], max + array[i]);
maxSoFar = Math.max(maxSoFar, max);
if (maxSoFar == max) {
maxSoFarEnd = i;
if (max == array[i]) {
maxSoFarBegin = i;
}
}
}
return new int[]{maxSoFarBegin, maxSoFarEnd, maxSoFar, aaa(array)};
}
public class MultiPutBoundedQueue {
private LinkedList list;
private int maxCapacity;
private final Lock lock = new ReentrantLock();
private final Condition readCondition = lock.newCondition();
private final Condition writeCondition = lock.newCondition();
private final Condition writeCondition2 = lock.newCondition();
private volatile int countDownLatch;
private volatile boolean spaceAvailable = true;
public void init(int capacity) {
assertCapacity(capacity);
list = new LinkedList();
maxCapacity = capacity;
}
private void assertCapacity(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException("Capacity must be positive number");
}
public Object get() throws InterruptedException {
assertInitialized();
lock.lock();
try {
while (list.size() == 0) {
readCondition.await();
}
Object o = list.remove();
if (countDownLatch > 0) {
countDownLatch--;
}
System.out.println("[-1] Read 1, " + list.size());
if (countDownLatch == 0) {
writeCondition2.signalAll();
}
return o;
} finally {
lock.unlock();
}
}
public void put(Object obj) throws InterruptedException {
multiput(Arrays.asList(obj));
}
public void multiput(List objs) throws InterruptedException {
assertInitialized();
assertOverCapacity(objs); // if objs.size() > maxCapacity
lock.lock();
try {
while (!spaceAvailable) {
writeCondition.await();
}
if (list.size() + objs.size() > maxCapacity) {
countDownLatch = list.size() + objs.size() - maxCapacity;
while (countDownLatch > 0) {
spaceAvailable = false;
writeCondition2.await();
}
spaceAvailable = true;
}
list.addAll(objs);
System.out.println(String.format("[%s] Added %s, ", Thread.currentThread().getName(), objs.size()) + list.size());
writeCondition.signalAll();
readCondition.signalAll();
} finally {
lock.unlock();
}
}
private void assertOverCapacity(List objs) {
if (objs.size() > maxCapacity) {
throw new IllegalArgumentException("Max number of items is: " + maxCapacity);
}
}
private void assertInitialized() {
if (list == null) {
throw new IllegalStateException("MultiPutBlockingBoundedQueue has not been initialized with .init(...)");
}
}
public static void main(String[] args) throws Exception {
final MultiPutBoundedQueue multiPutBoundedQueue = new MultiPutBoundedQueue();
multiPutBoundedQueue.init(10);
Thread put = new Thread(new Runnable() {
@Override
public void run() {
try {
int counter = 0;
while (true) {
Thread.currentThread().setName("+1/" + counter++);
multiPutBoundedQueue.put("");
Thread.sleep(1000);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread mput = new Thread(new Runnable() {
@Override
public void run() {
try {
int counter = 0;
while (true) {
Thread.currentThread().setName("+5/" + counter++);
multiPutBoundedQueue.multiput(Arrays.asList(1, 2, 3, 4, 5));
Thread.sleep(1000);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread read = new Thread(new Runnable() {
@Override
public void run() {
Thread.currentThread().setName("-1");
try {
while (true) {
multiPutBoundedQueue.get();
Thread.sleep(1000);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
put.start();
mput.start();
read.start();
}
}
You guys are nuts! :-)
Problem explicitly states scale of the problem - facebook/twitter, so you should rightfully expect millions of events per hour. You should also understand that topics freq chart has a long-long tail. Keeping these millions of tags in RAM (all these heap-based solutions) would kill you. Storing them on disk is an option (DB based solutions) but then computing and retrieving them would be an offline job with certain latency.
I guess the most appropriate solution is any of the streaming counting algorithms - see sticky sampling or lossy counting for instance.
class MultiPutBlockingBoundedQueueImpl<E> implements MultiPutBlockingBoundedQueue<E> {
private E[] buffer;
private int position;
@Override
public void init(int capacity) throws Exception {
if (buffer != null) {
throw new IllegalStateException("Already initialized");
} else if (capacity <= 0) {
throw new IllegalArgumentException("Capacity must be positive number");
} else {
buffer = (E[]) new Object[capacity];
}
}
@Override
public E get() throws Exception {
if (buffer == null) {
throw new IllegalStateException("Not initialized");
}
synchronized (buffer) {
while (position == 0) {
buffer.wait();
}
position--;
return buffer[position + 1];
}
}
@Override
public void put(E obj) throws Exception {
multiput(new ArrayList<E>(){{add(obj);}});
}
@Override
public void multiput(List<E> objs) throws Exception {
if (buffer == null) {
throw new IllegalStateException("Not initialized");
}
synchronized (buffer) {
while (position >= buffer.length - 1 - objs.size()) {
buffer.wait();
}
for (E obj : objs) {
position++;
buffer[position] = obj;
}
buffer.notifyAll();
}
}
}
Replcarton941, Android test engineer at 8x8
My name is Lilly. I grew up in Somerset and currently live in the US. One desire that has always ...
Reparlenekraft8, How to book a seat on Southwest airlines flight at Absolute Softech Ltd
I am a coding specialist from MD,USA.I’m indifferent to most items on the planet.Participated in creating ...
- Igor April 12, 2016