Q. Can you write an algorithm to swap two variables?
A.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| package algorithms;public class Swap { public static void main(String[ ] args) { int x = 5; int y = 6; //store 'x' in a temp variable int temp = x; x = y; y = temp; System.out.println("x=" + x + ",y=" + y); }} |
Q. Can you write code to bubble sort { 30, 12, 18, 0, -5, 72, 424 }?
A.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| package algorithms;import java.util.Arrays;public class BubbleSort { public static void main(String[ ] args) { Integer[ ] values = { 30, 12, 18, 0, -5, 72, 424 }; int size = values.length; System.out.println("Before:" + Arrays.deepToString(values)); for (int pass = 0; pass < size - 1; pass++) { for (int i = 0; i < size - pass - 1; i++) { // swap if i > i+1 if (values[i] > values[i + 1]) swap(values, i, i + 1); } } System.out.println("After:" + Arrays.deepToString(values)); } private static void swap(Integer[ ] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }} |
Q. Is there a more efficient sorting algorithm?
A. Although bubble-sort is one of the simplest sorting algorithms, it's also one of the slowest. It has the O(n^2) time complexity. Faster algorithms include quick-sort and heap-sort. The Arrays.sort( ) method uses the quick-sort algorithm, which on average has O(n * log n) but can go up to O(n^2) in a worst case scenario, and this happens especially with already sorted sequences.
Q. Write a program that will return whichever value is nearest to the value of 100 from two given int numbers?
A. You can firstly write the pseudo code as follows:
- Compute the difference to 100.
- Find out the absolute difference as negative numbers are valid.
- Compare the differences to find out the nearest number to 100.
- Write test cases for +ve, -ve, equal to, > than and < than values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| package chapter2.com;public class CloseTo100 { public static int <span class="IL_AD" id="IL_AD2">calculate</span>(int input1, int input2) { //compute the difference. Negative values are allowed as well int iput1Diff = Math.abs(100 - input1); int iput2Diff = Math.abs(100 - input2); //compare the difference if (iput1Diff < iput2Diff) return input1; else if (iput2Diff < iput1Diff) return input2; else return input1; //if tie, just return one } public static void main(String[ ] args) { //+ve numbers System.out.println("+ve numbers=" + calculate(50,90)); //-ve numbers System.out.println("-ve numbers=" + calculate(-50,-90)); //equal numbers System.out.println("equal numbers=" + calculate(50,50)); //greater than 100 System.out.println(">100 numbers=" + calculate(85,105)); System.out.println("<100 numbers=" + calculate(95,110)); } } |
Output:
+ve numbers=90
-ve numbers=-50
equal numbers=50
>100 numbers=105
<100 numbers=95
Q. Can you write a method that reverses a given String?
A.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class ReverseString { public static void main(String[ ] args) { System.out.println(reverse("big brown fox")); System.out.println(reverse("")); } public static String reverse(String input) { if(input == null || input.length( ) == 0){ return input; } return new StringBuilder(input).reverse( ).toString( ); }} |
It is always a best practice to reuse the API methods as shown above with the StringBuilder(input).reverse( ) method as it is fast, efficient (uses bitwise operations) and knows how to handle Unicode surrogate pairs, which most other solutions ignore. The above code handles null and empty strings, and a StringBuilder is used as opposed to a thread-safe StringBuffer, as the StringBuilder is locally defined, and local variables are implicitly thread-safe.
Some interviewers might probe you to write other lesser elegant code using either recursion or iterative swapping. Some developers find it very difficult to handle recursion, especially to work out the termination condition. All recursive methods need to have a condition to terminate the recursion.
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class ReverseString2 { public String reverse(String str) { // exit or termination condition if ((null == str) || (str.length( ) <= 1)) { return str; } // put the first character (i.e. charAt(0)) to the end. String indices are 0 based. // and recurse with 2nd character (i.e. substring(1)) onwards return reverse(str.substring(1)) + str.charAt(0); }} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class ReverseString3 { public String reverse(String str) { // validate if ((null == str) || (str.length( ) <= 1)) { return str; } char[ ] chars = str.toCharArray( ); int rhsIdx = chars.length - 1; //iteratively swap until exit condition lhsIdx < rhsIdx is reached for (int lhsIdx = 0; lhsIdx < rhsIdx; lhsIdx++) { char temp = chars[lhsIdx]; chars[lhsIdx] = chars[rhsIdx]; chars[rhsIdx--] = temp; } return new String(chars); }} |
No comments:
Post a Comment