petko.ivanov
BAN USERpublic class LongestSequenceOfOne {
public static int arr[][] = {
{0, 0, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 1, 0},
{0, 0, 1, 0, 0},
{1, 1, 1, 1, 1}};
//can only move to the right OR down
public static int point(int row,int column,int countSoFar){
if (row>=arr.length || column>=arr[row].length) return countSoFar; //outside
if (arr[row][column]==0) return countSoFar; // cant move on 0
return Math.max(point(row, column + 1, countSoFar + 1), point(row + 1, column, countSoFar + 1));
}
public static void main(String[] args) {
int max = 0, row=-1, column=-1;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
int maxTemp = point(i, j, 0);
if (maxTemp>max){
max = maxTemp;
row = i;
column = j;
}
}
}
System.out.println(max+" at ("+row+","+column+")");
}
}
Output : 8 at (1,0)
- petko.ivanov September 22, 2014public class StringBuilderThreadSafety {
public static void myMethodSafe(StringBuilder sb, String name){
sb = new StringBuilder(sb.toString());
sb.append(" ").append(name);
System.out.println(sb.toString());
}
public static void myMethodUnSafe(StringBuilder sb,String name){
sb.append(" ").append(name);
System.out.println(sb.toString());
}
public static void main(String[] args) {
final StringBuilder sb = new StringBuilder("foo: ");
for (int i = 0; i < 10; i++) {
final int finalI = i;
new Thread(){
public void run(){
myMethodUnSafe(sb, ""+ finalI);
}
}.start();
}
}
}
It all depends what happens inside that method.
It could be either way.
Unsage output :
foo: 1 0
foo: 1 0
foo: 1 0 2
foo: 1 0 2 3
foo: 1 0 2 3 4
foo: 1 0 2 3 4 5
foo: 1 0 2 3 4 5 6
foo: 1 0 2 3 4 5 6 8
foo: 1 0 2 3 4 5 6 8 7
foo: 1 0 2 3 4 5 6 8 7 9
Safe Output:
foo: 0
foo: 6
foo: 4
foo: 5
foo: 3
foo: 2
foo: 1
foo: 7
foo: 8
foo: 9
public class ParallelCount {
static final int SINGLE_SLEEP = 50;
static int getCount(String s) {
try {
Thread.sleep(SINGLE_SLEEP);
} catch (InterruptedException e) {
e.printStackTrace();
}
return (int) (Math.random()*100.);
}
public static void main(String[] args) throws Exception{
boolean isMultiThreaded = true;
for(int i=0;i<10;i++) {
long start = System.currentTimeMillis();
if (!isMultiThreaded) {
int count = getCount("ds1");
if (count < 100) count = count + getCount("ds2");
if (count < 100) count = count + getCount("ds3");
if (count < 100) count = count + getCount("ds4");
if (count < 100) count = count + getCount("ds4");
}else {
final int[] counts = new int[5];
Thread[] t = new Thread[5];
for (int j = 0; j < 5; j++) {
final int finalJ = j;
t[j] = new Thread() {
public void run() {
counts[finalJ] = getCount("ds" + finalJ);
}
};
t[j].start();
}
int count = 0;
for (int j = 0; j < 5; j++) {
t[j].join();
count += counts[j];
if (count >= 100) break;
}
}
System.out.println("Total time = " + (System.currentTimeMillis() - start));
}
}
}
The total time is the time it takes to make one call even if you dont need all the results. Output (from multithreaded run) :
Total time = 53
Total time = 54
Total time = 54
Total time = 53
Total time = 53
Total time = 54
Total time = 52
Total time = 53
Total time = 52
Total time = 52
public class ReverseLinkedList {
static class Node{
Object value;
Node next;
Node(Object value){
this.value = value;
}
Node next(Node next){
this.next = next;
return next;
}
@Override
public String toString() {
return "Node(" +value +")+>"+(next!=null?next.toString():"|");
}
}
static class SingleLinkedList{
Node head;
void reverse(){
Node cur=head, prev=null;
while(cur!=null){
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
head=prev;
}
}
public static void main(String[] args) {
SingleLinkedList l = new SingleLinkedList();
l.head = new Node(1);
l.head.next(new Node(2)).next(new Node(3)).next(new Node(4)).next(new Node(5));
System.out.println(l.head);
l.reverse();
System.out.println(l.head);
}
}
Output:
Node(1)+>Node(2)+>Node(3)+>Node(4)+>Node(5)+>|
Node(5)+>Node(4)+>Node(3)+>Node(2)+>Node(1)+>|
import java.util.Arrays;
public class SimilarArrays {
static int[] arr1 = { 3, 5, 2, 5, 2, 15}, arr2 = { 2, 3, 5, 5, 2, 15};
public static void main(String[] args) {
System.out.println(new Stats(arr1).equals(new Stats(arr2)));
}
//NB - assumes very bounded natural numbers
static class Stats{
int [] counter = new int[10];
Stats(int [] arr){
for(int i : arr){
if (counter.length<=i){
counter = Arrays.copyOf(counter, i+1);
}
counter[i]++;
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Stats stats = (Stats) o;
if (!Arrays.equals(counter, stats.counter)) return false;
return true;
}
@Override
public int hashCode() {
return counter != null ? Arrays.hashCode(counter) : 0;
}
}
}
The interesting thing is you can kind of reproduce the random behavior if you put a Thread.sleep(1). This will cause it to sometimes go into an infinite wait OR sometimes print out the result.
- petko.ivanov September 09, 2014Precalculate all slopes between any 2 points - O(n^2)
Then within each list of points with the same slope see if 2 corresponding perpendicular lines exist.
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FindSquaresIn2D {
static class Point{
double x,y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
if (Double.compare(point.x, x) != 0) return false;
if (Double.compare(point.y, y) != 0) return false;
return true;
}
@Override
public int hashCode() {
int result;
long temp;
temp = Double.doubleToLongBits(x);
result = (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public String toString() {
return "{" +x +"," + y +'}';
}
}
static class Line{
Point a,b;
Line(Point a, Point b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "{" + a +"|" + b +'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Line that = (Line) o;
return (this.a.equals(that.a) && this.b.equals(that.b) ||
this.a.equals(that.b) && this.b.equals(that.a));
}
@Override
public int hashCode() {
return (int) (a.x*a.y+b.x*b.y);
}
}
static List<Point> all = Lists.newArrayList(
new Point(0,0),new Point(0,2),new Point(1,1),new Point(1,-1),
new Point(2,2),new Point(2,0),new Point(2,1),
new Point(1,2), new Point(1.1,2.7), new Point(-1,-1)
);
public static void main(String[] args) throws InterruptedException {
Map<Double,Set<Line>> m = Maps.newHashMap();
for (int i = 0; i < all.size()-1; i++) {
Point a = all.get(i);
for (int j = i+1; j < all.size(); j++) {
Point b = all.get(j);
if (a.equals(b)) continue ;
Double slope = checkForNegativeExtremes( (a.y - b.y) / (a.x - b.x) );
Set<Line> l = m.get(slope);
if (l==null){
m.put(slope, l = Sets.newHashSet());
}
l.add(new Line(a, b));
}
}
for(Double slope : Lists.newArrayList( m.keySet())){
Set<Line> lTmp = m.get(slope);
if (lTmp==null || lTmp.size()<=1) continue ;
Double slopePerpendicular = checkForNegativeExtremes(-1. / slope);
Set<Line> perpendiculars = m.remove(slopePerpendicular);
if (perpendiculars==null || perpendiculars.size()<=1) continue ;
List<Line> l = Lists.newArrayList(lTmp);
for (int i = 0; i < l.size()-1; i++) {
Line l1 = l.get(i);
for (int j = i+1; j < l.size(); j++) {
Line l2 = l.get(j);
if (perpendiculars.contains(new Line(l1.a,l2.a)) && perpendiculars.contains(new Line(l1.b,l2.b))
// just in case we got them crossed here try the other way too.
|| perpendiculars.contains(new Line(l1.a,l2.b)) && perpendiculars.contains(new Line(l1.b,l2.a))){
System.out.println(l1.a+" "+l1.b+" "+l2.a+" "+l2.b+" form a square");
}
}
}
}
Thread.sleep(1000);
System.exit(0);
}
private static Double checkForNegativeExtremes(Double slope) {
if (slope.isInfinite() || slope.equals(-0.0)){
slope = Math.abs(slope); // this handles horizontal and perpendicular lines, dont want to differential between 0. and -0.
}
return slope;
}
}
Output :
{0.0,0.0} {2.0,0.0} {0.0,2.0} {2.0,2.0} form a square
{1.0,1.0} {2.0,1.0} {2.0,2.0} {1.0,2.0} form a square
{0.0,0.0} {1.0,1.0} {1.0,-1.0} {2.0,0.0} form a square
Output for 1k pots :
- petko.ivanov September 24, 20147726
brute took 454
7711
algo took 0
N.B. The fast algo is pretty damn close and very fast but it's not accurate. Times are in milliseconds.