javispute
BAN USERJava JEE developer
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
public class WildCardReplacer {
private Substitutor substritutor;
public WildCardReplacer() {
substritutor = new Substitutor();
}
public List<String> substituteWildChar(String strWithWildChar, String wildChar) {
Stack<String> stack = new Stack<String>();
stack.push(strWithWildChar);
String[] substitutedStr = null;
String strContainsWildChar = null;
List<String> stringlistRelacedWildCharList = new ArrayList<String>();
while (!stack.isEmpty()) {
strContainsWildChar = stack.pop();
if (strContainsWildChar.indexOf(wildChar) >= 0) {
substitutedStr = substritutor.substitute(strContainsWildChar, wildChar);
for (String sub : substitutedStr) {
stack.push(sub);
}
} else {
stringlistRelacedWildCharList.add(strContainsWildChar);
}
}
return stringlistRelacedWildCharList;
}
public static void main(String[] args) {
System.out.println(new WildCardReplacer().substituteWildChar("?001?00?", "?"));
}
}
class Substitutor {
private static Map<String, String[]> substituteStringMap = new HashMap<String, String[]>();
static {
String[] substituteChar = { "0", "1" };
substituteStringMap.put("?", substituteChar);
}
public String[] substitute(String srcStr, String wildChar) {
if (substituteStringMap.containsKey(wildChar)) {
String[] substituteChar = substituteStringMap.get(wildChar);
String[] substitutedStr = new String[substituteChar.length];
int indx = 0;
for (String schar : substituteChar) {
substitutedStr[indx++] = srcStr.replaceFirst("\\" + wildChar, schar);
}
return substitutedStr;
}
throw new RuntimeException(" Wild char :" + wildChar + " not supported!!");
}
}
I guess following is optimized code for finding prime..which is certainly not O(N^2)
import java.util.ArrayList;
import java.util.List;
public class PrimeFinder {
public int findNthPrime(int n) {
if (n < 0) {
throw new RuntimeException("Invalid argument :" + n);
}
List<Integer> primeNoList = new ArrayList<Integer>();
int primeNo = 2;
primeNoList.add(primeNo);
boolean iterateOverPrimeNoList = true;
int primeListCnt = 0;
int num = primeNo + 1;
int denominator = primeNo;
int primeCnt = 0;
while (primeCnt < n) {
System.out.println("main loop interation cnt : " + primeCnt);
primeListCnt = 0;
iterateOverPrimeNoList = true;
// check if next num is not divisible by all prime numbers which are
// less than equal to sqrt of num
while (primeListCnt < primeNoList.size() && iterateOverPrimeNoList) {
denominator = primeNoList.get(primeListCnt);
System.out.println("check num :" + num + " divisible by : " + denominator);
if (num % denominator == 0) {
num++;
primeListCnt = 0;
} else {
denominator = (primeListCnt + 1) < primeNoList.size() ? primeNoList.get(primeListCnt + 1) : denominator;
if (denominator <= Math.sqrt(num)) {
primeListCnt++;
} else {
iterateOverPrimeNoList = false;
}
}
}
primeCnt++;
primeNoList.add(num);
primeNo = num;
System.out.println(primeCnt + " nth Prime no:" + num + " found ");
num++;
}
System.out.println(primeNoList);
return primeNo;
}
public static void main(String[] args) {
System.out.println(new PrimeFinder().findNthPrime(10));
}
}
It could be done with small hack in println of Printstram :)
import java.io.PrintStream;
public class Program {
static {
PrintStream ps = System.out;
System.setOut(new PrintStream(ps){
public void println(boolean x) {
synchronized (this) {
super.println(!x);
}
}
});
}
public static void main(String args[]) {
TestA testObj = new TestA();
System.out.println(testObj.equals(testObj));
}
}
class TestA {
}
try to find 10000th or more prime no for comparison with other algos
- javispute April 14, 2014e.g.
long start = System.currentTimeMillis();
System.out.println(new PrimeFinder().findNthPrime(10000));
long end = System.currentTimeMillis();
System.out.println(" time 1: " + (end - start));
start = System.currentTimeMillis();
prime(10000); /*assuming ur code is in prime method*/
end = System.currentTimeMillis();
System.out.println(" time 2: " + (end - start));