nil_dream
BAN USERJdev is using double locked mechanism for thread safe singleton object creation. However, compiler is free to assign value to 'object' variable before 'object' is initialized.
For instance, thread1 can create an instance of SingletonObject class but before it initializes it can preempted. So another thread2 can still find 'object' == null and try to create another instance of SingletonObject class.
To avoid that easiest way is to use synchronized method instead of block
Or we can create public member of class which is initialized when first time class is used.
public class SingletonObject{
public final static object = new SingletonObject();
private SingletonObject(){
// To avoid misuse of constructor
}
}
Hello
If i understood you problem correctly. You need to keep variance of B as stable as possible.
Variance - Distance of sample point from mean of sample space.
So you need to calculate the variance of each point in B from its mean. MAX(variances) will give you a threshold that you can start with.
Then insert each element of A into B and find out its mean and then variance of each sample point. Allow insertion of this element when variance is below your threshold.
It depends on how you want to calculate your variance. based on that us data structure will change
start with simple solutions -
1) we can use multi dimentional matrix with arrays in C, where each element indicates position of piece as 0 or 1. you can even implement one dimentional array and use it as 2 dimentional by using row size.
2) In Java we can use arrayList also for the same..
As it is 8*8 array, you dont need any advanced DS to lookup or insert into it..
Agreed.. O(n)
static int a1[] = {1,2,3,4,5,11,12};
static int a2[] = {2,3,4,5,6,7,8,9,10,11,15};
public static void main(String[] args) {
int length;
if(a1.length >= a2.length)
length = a2.length;
else
length = a1.length;
//
for(int i=0,j=0;i<length;){
if (a1[i] == a2[j]){
System.out.println(a1[i]);
i++;
j++;
}
else{
if(a1[i] < a2[j]){
i++;
}
else{
j++;
}
}
}
}
The logic -- find out smaller array.. for each element in smaller array lookup in larger array using binary search. so complexity will be O(nlgn)
Here is the working code--
public class findCommon {
/**
* @param args
*/
static int a1[] = {1,2,3,4,5,6};
static int a2[] = {2,3,4,5,6,7,8,9,10,11,15};
public static void main(String[] args) {
// larger one should be binary searched.
// add logic based on array length to iterate over smaller array and
// binary search larger array.
boolean found =false;
int i;
//complexity - O(nlgn)
for(i=0;i<a1.length;i++){
found = binarySearch(a1[i]);
if(found){
System.out.println(a1[i]);
found = false;
}
}
}
public static Boolean binarySearch(int num){
int start = 0;
int end = a2.length - 1;
int mid = start + end / 2;
//System.out.println(mid);
boolean found = false;
//binary search condition - Search continues till
// element not found AND start index < end index (means only on element left)
while(!found && start < end){
if(num == a2[mid])
found = true;
else
if(num < a2[mid]){
end = mid-1;
mid = (start + end) / 2;
}
else{
start = mid + 1;
mid = (start + end) / 2;
}
}
//compares the last element remaining. (condition useful for boundary elements)
if(num == a2[mid]){
found = true;
}
if(found){
//System.out.println("found at "+mid);
}
else{
//System.out.println("not found");
}
return found;
}
}
public static void main(String[] args) {
// Preparing random input
int input[] = new int[5];
Random r = new Random();
for(int i=0;i<5;i++){
input[i] = r.nextInt(10);
if(input[i] > 4)
input[i] = 0;
}
//int input[] = {0,2,2,2,1};
for(int i=0;i<5;i++){
System.out.print(input[i]+" ");
}
System.out.println("\n");
int j = 0,temp;
// Logic for pushing all zeros in place.
// If current element is 0 then, look for next non zero element and then swap with it.
// Worst case performance - O(n*n)
/*for(int i=0;i<input.length-1;i++){
if(input[i] == 0){
j = i + 1;
while(input[j] == 0 && j<input.length-1){
j++;
}
// Exchange
if(input[j] != 0){
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
//
}
}*/
//
// O(n) logic. First find first zeroIndex.
// now swap ZeroIndex with first nonZero index. "then increment zeroIndex"
while(input[j] != 0){
j++;
}
int zeroIndex = j;
for(int i=zeroIndex;i<input.length;i++){
if(input[i] == 0){
//zeroIndex = i;
}
else{
//swap
temp = input[i];
input[i] = input[zeroIndex];
input[zeroIndex] = temp;
zeroIndex++;
}
}
for(int i=0;i<5;i++){
System.out.print(input[i]+" ");
}
}
This O(N2) in worst case only when for each suffix., you have to search entire list before match found. Otherwise pruning will be veyr much effective..
- nil_dream March 08, 2013