y so serious
BAN USERpublic class AlternateSign {
static int negative;
static int positive;
private static void alter(int[] a,int index){
if(index>=a.length)
return;
if(a[index]<0 && a[index+1]>0)
{
negative--;
positive--;
alter(a,index+2);
}
else
{
if(negative==0 || positive==0)
return;
else{
for(int i=index+2;i<a.length;i++){
if(a[index]<0 && a[index+1]>0)
break;
if(a[index]>0 && a[i]<0)
{
int t=a[i];
a[i]=a[index];
a[index]=t;
}
if(a[index+1]<0 && a[i]>0)
{
int t=a[i];
a[i]=a[index+1];
a[index+1]=t;
}
}
negative--;
positive--;
alter(a,index+2);
}
}
}
public static void main(String[] args){
int[] ar=new int[]{-1,-2,4,-2,-6,5,6,-3,9,-8,-5,};
for(int i=0;i<ar.length;i++)
{
if(ar[i]<0)
negative++;
else
positive++;
}
alter(ar,0);
for(int i=0;i<ar.length;i++)
System.out.print(ar[i]+" ");
}
}
If looking for perfect ans:
Here it is...:)
It is O(n^2) if u dig a bit.
public class AlternateSign {
static int negative;
static int positive;
private static void alter(int[] a,int index){
if(index>=a.length)
return;
if(a[index]<0 && a[index+1]>0)
{
negative--;
positive--;
alter(a,index+2);
}
else
{
if(negative==0 || positive==0)
return;
else{
for(int i=index+2;i<a.length;i++){
if(a[index]<0 && a[index+1]>0)
break;
if(a[index]>0 && a[i]<0)
{
int t=a[i];
a[i]=a[index];
a[index]=t;
}
if(a[index+1]<0 && a[i]>0)
{
int t=a[i];
a[i]=a[index+1];
a[index+1]=t;
}
}
negative--;
positive--;
alter(a,index+2);
}
}
}
public static void main(String[] args){
int[] ar=new int[]{-1,-2,4,-2,-6,5,6,-3,9,-8,-5,};
for(int i=0;i<ar.length;i++)
{
if(ar[i]<0)
negative++;
else
positive++;
}
alter(ar,0);
for(int i=0;i<ar.length;i++)
System.out.print(ar[i]+" ");
}
}
I think it asks as to return only single object every time:
public class OnlyOneObject {
static OnlyOneObject obj;
static int count=0;
public static OnlyOneObject getIt(){
if(count==0)
{
obj=new OnlyOneObject();
count++;
return obj;
}
else
return obj;
}
public static void main(String[] args){
System.out.println(getIt().hashCode());
System.out.println(getIt().hashCode());
}
}
Java code:
public class SharedQueue implements Runnable{
static int size=5;
static int[] queue=new int[size];
static int putAt=0;
static int deleteAt=0;
static int numElements=0;
static int id=0;
static Delete del;
static Add add;
public void run(){
Random r=new Random();
if(r.nextInt(2)==0)
add.add(r.nextInt());
else
del.delete();
}
public static void main(String[] args)
{
SharedQueue q=new SharedQueue();
del=new Delete(q);
add=new Add(q);
Thread[] t=new Thread[50];
for(int i=0;i<50;i++)
{
t[i]=new Thread(q);
t[i].start();
}
}
}
class Delete{
static SharedQueue q;
public Delete(SharedQueue q)
{
this.q=q;
}
public int delete()
{
int num;
synchronized(q){
while(q.numElements==0){
try {
q.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
synchronized(this)
{
num = q.queue[q.deleteAt];
if(q.deleteAt<q.size-1)
q.deleteAt++;
else
q.deleteAt=0;
}
synchronized(q){
q.numElements--;
System.out.println("deleted "+num+" "+q.numElements);
q.notifyAll();
}
return num;
}
}
class Add{
static SharedQueue q;
public Add(SharedQueue q)
{
this.q=q;
}
public void add(int x)
{
synchronized(q){
while(q.numElements==q.size){
try {
q.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
synchronized(this){
if(q.putAt==q.size-1)
q.putAt=0;
else
q.putAt++;
q.queue[q.putAt]=x;
}
synchronized(q){
q.numElements++;
System.out.println("added "+x+" "+q.numElements);
q.notifyAll();
}
}
}
If previous term of sequence is even:
let it be x
next multiple of 2=2^(x+1)
power of 5 till now: log(x)/log(5)
next multiple of 5 = 5^(power of 5 till now+1)
find which 1 is small.
Do the converse for previous term is multiple of 5..:)
Simple use an integer count:
Reader:
{
if(count>=0) //inside critical section
count++;
}
//reader is reading file
{
count--;
notifyAll(); //inside critical section
}
Writer:
will write only if count==0;
count=-1;
Working code:
public class ReaderWriter implements Runnable{
static int count=0;
static Reader r;
static Writer w;
public void run(){
Random ran=new Random();
if(ran.nextInt(2)==1)
r.read();
else
w.write();
}
public static void main(String[] args)
{
ReaderWriter rw=new ReaderWriter();
r=new Reader(rw);
w=new Writer(rw);
Thread[] t=new Thread[20];
for(int i=0;i<20;i++){
t[i]= new Thread(rw);
t[i].start();
}
}
}
class Writer{
ReaderWriter r;
public Writer(ReaderWriter r){
this.r=r;
}
public void write(){
synchronized(r){
while(r.count!=0){
try {
r.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
r.count=-1;
}
try {
TimeUnit.MILLISECONDS.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//writing file
synchronized(r){
r.count=0;
System.out.println("Written file"+" "+r.count);
r.notifyAll();
}
}
}
class Reader{
ReaderWriter r;
public Reader(ReaderWriter r){
this.r=r;
}
public void read()
{
synchronized(r){
while(r.count==-1){
try {
r.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
r.count++;
}
try {
TimeUnit.MICROSECONDS.sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//reading file
synchronized(r){
r.count--;
System.out.println("Read file"+" "+r.count);
if(r.count==0)
r.notifyAll();
}
}
}
Seems its viral...:)
As mentioned it can be solved by fibonacci.
Suppose steps are :
_ a1 a2 a3 a4 a5 ..........an_
f(n)=f(n-1)+f(n-2)
f(n-1)------frog simply goes to a1 and we are left with subproblem to find number of solutions for a2 a3 a4 a5 ....an
f(n-2)------frog can jump a1 and goes to a2,now the left subproblem is a3 a4 a5.....an
Seems its viral...:)
As mentioned it can be solved by fibonacci.
Suppose steps are :
_ a1 a2 a3 a4 a5 ..........an_
f(n)=f(n-1)+f(n-2)
f(n-1)------frog simply goes to a1 and we are left with subproblem to find number of solutions for a2 a3 a4 a5 ....an
f(n-2)------frog can jump a1 and goes to a2,now the left subproblem is a3 a4 a5.....an
Working code:
Use the function
a[i][j]+max(a[i-1][j],a[i][j+1]);
public class CoinsCollect {
static int[][] coins={{1,5,3},{4,5,2}};
static int rows=2;
static int columns=3;
private static int max(int i,int j)
{
if(i<0 || j>=columns)
return 0;
else
return coins[i][j]+Math.max(max(i-1,j),max(i,j+1));
}
public static void main(String[] args)
{
System.out.println(max(rows-1,0));
}
}
Couldn't comment to @nihaldps so writing a new post.
fmax --maximum element in the array.
smax --second maximum element in the array.
Your solution fails for all negative elements in the array. So always initialise fmax and smax with a[0].
Suppose,a[0] is the greatest element in the array then,the number of comparisions that your code does is 2(n-1).Since from index=1 to n-1 every element will be compared to fmax and then to smax also.
This question can have a better solution.
We can find the fmax in n-1 comparisions.
For finding the second maximum element, we are sure that at any point of time second maximum element should have been compared with maximum element.So if somehow we can keep information that which all elements have been compared with maximum elements. We can find maximum of those which would be the second maximum element.
Prepare a decision tree as follows,
Compare a0 with a1, a2 with a3, a4 with a5......and so on.
then keep on going with winners among those.
We come to know that number of elements which get compared with maximum element is log(n) ------height of decision tree.
So now we can compute max from these in log(n)-1 comparisions.
So total no. of comparisions= n-1+log(n)-1=n+logn-2
I think the solution is really nice and the complexity is O(n).
Please point out if you find any mistakes.
Since the number to choosen is random number about which we have to partition the array.On an average we can assume that,choosing this random number leads to two arrays with half no. of elements every time.
And for worst case we can assume that we only found the nth element when we had only a single element in the array.
Suppose that there are k elements initially,
Initially,
k elements -----to partition we need k comparisions which leads to 2 arrays of k/2 elements.
k+k/2 (k/2 comparisions in the array of k/2 elements)
k+k/2+k/4 (k/4 comparisions for array of k/4 elements)
k+k/2+k/4+k/8+........k/2(power i) ,where k=2(power i) since we assumed that we found nth element when we had only single element in array
k(1+1/2+1/4+1/8+.....1/2(power i))
k(1-1/2(power i)/(1-1/2)
2k(2(power i)-1)/2(power i)
2k(2(power i)-1)/k
2(k-1)
O(k)
generally O(n),where n is size of problem
Suppose we have a matrix
- y so serious June 15, 2014A B C D E
A 1 1 1 0 0
B 1 1 1 0 0
C 1 1 1 0 0
D 1 1 1 1 0
E 1 1 1 0 1
Here Mat[x][y]=1, represents x knows y. So, the vertical column of A, B and C, has all 1's so they are a favourite group. Instead of matrix we can represent this vertical columns by bitsets.
If a new person is added to the party simple, simply add his knowings to this bitset and compute the cardinality. If the cardinality is equal to the total no. of people in the party then this person is in favourite group.