In Java, what is the difference between static, final, and const.

Full Question:

In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++).

const: static final. It defines a constant. Now we do not use const keyword any more.

final
Define an entity once that cannot be changed nor derived from later. More specifically: a final class cannot be subclassed, a final method cannot be overridden, and a final variable can occur at most once as a left-hand expression. All methods in a final class are implicitly final.

static
Used to declare a field, method or inner class as a class field. Classes maintain one copy of class fields regardless of how many instances exist of that class. static also is used to define a method as a class method. Class methods are bound to the class instead of to a specific instance, and can only operate on class fields. (Classes and interfaces declared as static members of another class or interface are actually top-level classes and are not inner classes.)

Read More [...]

Posted in Google Interview Question, Java, Java Const, Java Final, Java Static, MS interview Question, Programmer Interview Question, Software Engineer Interview Question

In Java, what is the difference between final, finally, and finalize?

Full Question:

In Java, what is the difference between final, finally, and finalize?

• final – Define an entity once that cannot be changed nor derived from later. More specifically: a final class cannot be subclassed, a final method cannot be overridden, and a final variable can occur at most once as a left-hand expression. All methods in a final class are implicitly final.
  Example.
  
  // final class
  public final class MyFinalClass {...}
  
  // final method
  public class MyClass {
     public final void myFinalMethod() {...}
  }
  
  //final variable
  public class Sphere {
     public static final PI = 3.141592653589793; // a constant
     public final double radius;
   
     Sphere(double r) {
        radius = r;
     }
  }
  
  
• finally – The finally block always executes when the try block exits, except System.exit(0) call. This ensures that the finally block is executed even if an unexpected exception occurs. But finally is useful for more than just exception handling — it allows the programmer to avoid having cleanup code accidentally bypassed by a return, continue, or break. Putting cleanup code in a finally block is always a good practice, even when no exceptions are anticipated.
  Example.
  
  try {
     System.out.println("Entering second try block");
     try {
        throw new MyException();
     } finally {
        System.out.println("finally in 2nd try block");
     }
  } catch (MyException e) {
     System.err.println("Caught MyException in 1st try block");
  } finally {
     System.err.println("finally in 1st try block");
  }
  
  Result:
     Entering second try block
     finally in 2nd try block
     Caught MyException in 1st try block
     finally in 1st try block
• finalize() – method helps in garbage collection. A method that is invoked before an object is discarded by the garbage collector, allowing it to clean up its state. Should not be used to release non-memory resources like file handles, sockets, database connections etc because Java has only a finite number of these resources and you do not know when the garbage collection is going to kick in to release these non-memory resources through the finalize() method.
  Example.
  
  protected void finalize() throws Throwable {
     try {
        close();
     } catch(Exception e) {
  
     } finally {
        super.finalize();
     }
  }

Read More [...]

Posted in Google Interview Question, Java, Java Final, Java Finalize, Java Finally, MS interview Question, Programmer Interview Question, Software Engineer Interview Question

Generate a Random Number Between 1 and 7, Given a Method that Generates a Random Number Between 1 and 5.

Full Question:

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

The given function, let's call rand(5), generates a random number between 1 to 5 in uniform manner. So, we can generate a random number from 1 to 5ⁿ in also uniform manner. For example, 25*(rand(5)-1) + rand(5) generates a random number between 1 to 125, and 5*(rand(5)-1)+rand(5) generates a random number between 1 to 25 uniformly. From this derivation, we can get a random number between 1 to 7 under uniform distribution.

public static void main(String args[]) {
Random g = new Random(1929304);
int N = 100000000;
int num[] = {0, 0, 0, 0, 0, 0, 0};

for(int i=0; i<N; i++ ) {
int j;
do {
j = 5*g.nextInt(5) + (g.nextInt(5)+1); // uniform between 1 and 25
} while(j>21); // uniform between 1 and 21
num[(j%7)]++; // uniform between 1 and 7 (0 and 6)
}

for(int i=0; i< 7; i++ )
System.out.println(i+1 + ": " + num[i]);
}

Following box shows results after a hundred million times try.

1: 14289981
2: 14288932
3: 14286841
4: 14284775
5: 14283995
6: 14285958
7: 14279518

Read More [...]

Posted in C, Google Interview Question, Interview Question, Java, MS interview Question, Programmer Interview Question, Programming, Random Number, Software Engineer Interview Question

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i].

Full Question:

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Simply, it can be solved in O(n²) time, by using double loop. For example,

int[] multiplicationExceptMe() {
int ret[N] = {1,};
for (int i=0; i < N; i++)
 for (int j=0; j < N; j++) {
  if(i != j)
     ret[i] *= A[j]
 }
return ret;
}

But, we have to solve in in O(n). The idea is to do multiply in both side (i.e. from start to end and from end to start) in each loop.

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;  
ret[n-1-i] = ret[n-1-i]*right;
//after multiplication, set new left and right value
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Obviously, it's O(n) time complexity.

Read More [...]

Posted in Big O, C, Google Interview Question, Interview Question, Java, MS interview Question, Programming, Time Complexity

Find All Permutations of the Letters in a Particular String

Permutations of string 'ABC' are:
ABC, ACB, BAC, BCA, CAB, CBA.

Taking the backtracking strategy, here is a solution. The program prints all permutation of the given string .It's assumed that NO same character in the string. So, the given string has same character, some redundant results are shown. You can avoid it by maintaining array to save permutations.

public static void main(String args[]) {
char[] input = {'A', 'B', 'C'};
permute(input, 0, input.length-1);
}

public static void swap(char[] str, int i, int j) {
char temp;

temp = str[j];
str[j] = str[i];
str[i] = temp;
}

public static void permute(char[] str, int start, int end) {
if (start == end)
System.out.println(str);
else {
for (int i=start; i<=end; i++) {
swap(str, start, i);
permute(str, start+1, end);
swap(str, start, i);
}
}
}

Read More [...]

Posted in C, Google Interview Question, Java, MS interview Question, Permutation, Programming

Multiplication of All Element in Array[N] except Array[i] without Divide Operation

Question:

• There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

It is from Google and Microsoft interview Question List. If you want to be hired, see the code. If we use divide operator (/), it's easy to solve in O(n). Multiply of all elements once, and divide into the value of A[i]. And we can implement division function without divide operator, but it may be not way to go. 

Here is a solution. Just define two variable, left and right to store multiplication results of left of A[i] and right of A[i]. We need just one loop of n and hence it's in O(n).

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;
ret[n-1-i] = ret[n-1-i]*right;
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Read More [...]

Posted in C, Google Interview Question, Java, MS interview Question, Programming

Implementing Division without Divide Operator

Implementing dividing operation is a popular interview question in programmer and software engineering job. When you're asked, of course you must not use divide (/) operator obviously.

Since Multiplication (Devision) is derived from Addition (Subtraction) mathematically, the dividing operation can be implemented using subtraction.

Following function implement the dividing operation. there're two way- using multiplication and subtraction. However, you should use subtraction because multiplication has same property of division. You know devision can be converted to multiplication, and vise versa.

public int divide(int numerator, int denominator) {
int result = 0;

if (numerator == 0)
return numerator;
else if (denominator == 0) {
System.out.println("Error: Divided by 0");
return ERROR;// define constant for ERROR Message
else {
int sign = numerator*denominator > 0? 1:-1;
if(numerator < 0)
numerator *= -1;
if(denominator < 0)
denominator *= -1;
/* using multiplication
while(true) {
result++;
if(result*denominator > numerator) {
result--;
break;
}
}
*/
//using subtraction
while (true) {
numerator = numerator - denominator;
if(numerator>=0)
result++;
else
break;
}

return (sign*result);
}
}

Read More [...]

Posted in C, Google Interview Question, implement Division, Interview Question, Java, Programming