program to find permutations

import java.util.ArrayList;
import java.util.List;

public class Permutation {

public static void permuteString(List permutations,
String beginningString, String endingString) {

String output = beginningString + endingString;
if (endingString.length() <= 1) {
permutations.add(output);
} else {
for (int i = 0; i < endingString.length(); i++) {
try {
String newString = endingString.substring(0, i)
+ endingString.substring(i + 1);

permuteString(permutations, beginningString
+ endingString.charAt(i), newString);

} catch (StringIndexOutOfBoundsException exception) {
exception.printStackTrace();
}
}
}
}

public static void main(String[] args) {
List permutations = new ArrayList();
permuteString(permutations, "", "123456789");
for (String string : permutations) {
// System.out.println(output);
int first = Integer.parseInt(string.substring(0, 4));
int second = Integer.parseInt(string.substring(4, 5));
int third = Integer.parseInt(string.substring(5, 9));
if ((first * second) == third) {
System.out.println(string + "-->true");
}
}
}
}

Program to rotate a matrix

//for(int i=0; i less than n-1 ; i++){
//for(int j=0;jless than n-i-1;j++){
//int temp = a[n-j][n-i];
//a[n-j][n-i] = a[i][j];
//a[i][j] =temp;
//}
//}

Good Ques n their solutions

Q : reverse a string without using any loops (use recursion)

A : public static String Reverse(String strParam) {

if (strParam.length() == 1) {
return strParam;
} else {
return Reverse(strParam.substring(1)) + strParam.substring(0, 1);
}
}

Q: Write a algorithm to find out the substring in a string and find out the number of occurrences also
A: public static void findSubString(String input, String subStr) {
int occurance = 0;
int inp_len = input.length();
int sub_len = subStr.length();

for (int i = 0; i < inp_len; i++) {
System.out.println("Scanning Character : " + input.charAt(i));

int charsmatched = 0;

if (input.charAt(i) == subStr.charAt(0)) {
charsmatched++;

for (int k = 1; k < sub_len; k++) {

if ((i < (inp_len - sub_len)) && (input.charAt(i + k) == subStr.charAt(k))) {
charsmatched++;
}

if (charsmatched == sub_len) {
occurance++;
System.out.println("Substring found : " + occurance + " times");
}
}
}
}

System.out.println("Total ocurances : " + occurance);
}

Q: 4. Find out the nth number in a fibonnaci series.
A:
public static long fibonacci(int n) {
long sum = 0;

if (n < 0) {
System.out.println("Enter a positive number");
} else if (n == 0) {
sum += 0;

return sum;
} else if (n == 1) {
sum += 1;
} else {
sum = fibonacci(n - 1) + fibonacci(n - 2);
}

return sum;
}

Q: 5. Sentence is given , u have to reverse words

A: public static void rvrsWords(String input) {
System.out.println("Original : " + input);

String output = " ";

if (input != null) {
String[] array = input.split(" ");
int len = array.length;

for (int i = 0; i < (len / 2); i++) {
String temp = array[i];
array[i] = array[len - i - 1];
array[len - i - 1] = temp;
output = " " + array[i];
}

System.out.println("Reversed Array : ");

for (int i = 0; i < (len); i++) {
System.out.println(array[i] + " ");
}
}
}

A 2 : private static String reverseString(String string) {
String reverse="",temp="";

for(int i=0;ichar c= string.charAt(i);
if(c==' ' && temp.length()>0){
reverse = temp + " " + reverse;
temp="";
}else{
temp += c;
}
}
reverse = temp + " " + reverse;
return reverse;
}

Q: Given array A[i] = i+1 for i = 0 to N-1
create array O[i] = product of all elements of array A except A[i] for i = 0 to N-1

eg: for N = 3, O[2] = A[0]*A[1]
O[1] = A[0]*A[2] (we cant multiple with A[1])



package geeks.threads;

public class Product {

public static void main(String[] args) {
int n =5;

int[] a= new int[n] ;
for(int i = 0 ; i < n ; i++) {
a[i] = i+1;
System.out.println(a[i]);
}

Product p = new Product();
p.product(a, 3);

}

public void product(int[] a, int x ) {
int product = 1;
for(int i = 0; i < a.length ; i++) {
if(!(i ==x)) {
product *= a[i];
}
}
System.out.println("Product is : "+ product);
}


}

NexTag Questions:

1. There are 100 hundred doors numbered 1, 2, 3 ,4 ,..... 100 n one person is standing in front of each of them. Initially all are in open state.'
1 goes n closes all the doors
2 goes n flips the state of all doors numbered 2,4,6, ....
3 foes n flips the state of all doors numbered 3,6,9,. ...

What would be the state of each door after al the persons have flipped the doors ..

Ans : All doors which are squares f any number wil be closed(or open .. not sure ) coz wen we see their factors , same number appears
twice ,, this problem is related to number of factors

Q: We have an array in which numbers are sorted.
Given a number k, we need to find a pair of numbers from the numbers present in the array such that their difference is k
in least time ..
Ans :
Complexity : O(n logn)
As we know the difference, we ll start from first element and add k to it and then search for k in the remaining array.
we can apply binarry search on the remaining elements as we know they are sorted.

Q : Write algo to find all possible permutations of a given character array e.g for a String abcdef
A string of n characters will have n! permutaions.

Q: Write algo to reverse all words given in a String. in O(n)

Q:What are volatile variables are why are they used ?
Ans : The answer to this is realted to persistence in java. Volatile variables are not persisted in DB.
e.g. lets say we have three variables v1,v2 and v3.
Out of these , V3 is volatile.
So everytime a user makes changes to these variables , changes made to only v1 and v2 will be persisted, but v3 wont be.

Q: How can you find out a loop in a Liked list ?
Ans : It can be done by using two pointers .... one would move ahead by one node n other by two nodes., but in this case , if number of elements in the loop is large ,
it would take a lot of time ... we would keep looping into the loop ..
so to handle this, we should associate a variable with each node n set it wen we traverse the node , if during traversal, we encounter
a node which has already been traversesd, then we have found the loop.

Q: We have an array having numbers in increasing order but they are repeated e.g. 1,1,1,3,3,3,5,5,9,9,9
Find all unique numbers.

Ans : I used integer array in this for output, but ArrayList should be used instead as it would be more space efficient as we donot know
the number of elements in output. THis had to be done in O(n) complexity.

Apart from this, there were a number of java questions in written test.. which were quite tricky..like finding output
and which of the following statements are correct etc.

They asked basic java questions n examples of inner classes , Threads , static variables, overriding was their favourite ques
Solve SCJP ques for this ...

Very very good puzzle .. asked in Adobe interview

Q :Three containers of 15,10 and 6 ltrs capacity. Initially its in configuration (15,0,0). Make it to configuration (0,8,5).

Sol :

15 10 6
15 0 0
9 0 6
9 6 0
3 6 6
3 10 2
3 10 0
13 0 0
7 0 6
7 6 0
1 6 6
1 10 2
11 0 2
11 2 0
5 2 6
5 8 0
0 8 5