Technical interviews: Miscellaneous
Question1:
Write a program to swap two numbers in place without any temporary variables
package com.hong.misc; /*** * @author HongQing * */ public class InPlaceSwap { public static void swapByArithmetic(int[] numbers) throws Exception { if(numbers == null || numbers.length != 2) throw new Exception("Requires two numbers to perform swapping"); //Let numbers[0] = 10 and numbers[1] = 4 numbers[0] = numbers[1] - numbers[0]; // 10 - 4 = 6 ==> numbers[0] = 6 numbers[1] = numbers[1] - numbers[0]; // 10 - 6 = 4 ==> numbers[1] = 4 numbers[0] = numbers[1] + numbers[0]; // 4 + 6 = 10 ==> numbers[0] = 10, done! } public static void swapByBitOpt(int[] numbers) throws Exception { if(numbers == null || numbers.length != 2) throw new Exception("Requires two numbers to perform swapping"); //Let numbers[0] = 10 and numbers[1] = 4, we are only focus on the last byte of number to analyze the swapping. numbers[0] = numbers[0] ^ numbers[1]; // 0000 1010 ^ 0000 0100 = 0000 1110 ==> numbers[0] = 0000 1110 numbers[1] = numbers[0] ^ numbers[1]; // 0000 1110 ^ 0000 0100 = 0000 0100 ==> numbers[1] = 0000 1010 numbers[0] = numbers[0] ^ numbers[1]; // 0000 1110 ^ 0000 1010 = 0000 0100 ==> numbers[0] = 0000 0100, done! } //Simple tests. public static void main(String[] args) { int[] numbers1 = {10, 4}; int[] numbers2 = {25, 50}; try { //Swap numbers1. System.out.printf("Before swaping number1[0]=%d and number1[1]=%d ", numbers1[0], numbers1[1] ); System.out.println(); swapByArithmetic(numbers1); System.out.printf("After swaping number1[0]=%d and number1[1]=%d ", numbers1[0], numbers1[1] ); System.out.println(); //Swap numbers2. System.out.printf("Before swaping number1[0]=%d and number1[1]=%d ", numbers2[0], numbers2[1] ); System.out.println(); swapByArithmetic(numbers2); System.out.printf("After swaping number1[0]=%d and number1[1]=%d ", numbers2[0], numbers2[1] ); System.out.println(); } catch(Exception e) { e.printStackTrace(); } } }
Question2:
Write a program to compute a fibonacci number.
package com.hong.misc; /** * @author HongQing * */ public class Fibonacci { //Recursive solution is easy, but running time is exponential, try to avoid this implementation. //Pre-condition: number >= 0; public static int fibRec(int number) { //Base condition. if(number == 0 || number == 1) return number; else return fibRec(number - 1) + fibRec(number - 2); } //Iterative way achieves O(N) running time.(underlying technique is dynamic programming.) //pre-condition: number >= 0; public static int fibDynamic(int number) { if( number < 2) return number; int a = 0; int b = 1; int result = a + b; //Handles number == 2 case. for(int i = 2; i < number; i++) //If number > 2, program will step into for loop. { a = b; b = result; result = a + b; } return result; } public static void main(String[] args) { //If you un-comment the following line of code and run it, the application will take long time get the result. //System.out.println(fibRec(1000)); //Iterative version will give you the result in one second. System.out.println( fibDynamic(1000)); } }
Question3:
Given a sorted array of strings mixed with empty strings, write a method to find the index of a given string.
Example:
find "beer" in ["apple" , "" , "" , "beer" , "" , "dream", "" , "" ,
, "" , "fruit" , "", "world"];
output: 3
package com.hong.misc; /** * @author HongQing * */ public class StringBinarySearch { /** * Loops through strings to find the target string. Running time is O(N). * Output: index of target at the array, or -1 target string is not found. */ public static int findIterative(String[] strings, String target) { for(int i = 0; i < strings.length; i++) { if(target.equals(strings[i])) return i; } return -1; } /** * Slightly more complicated than normal binary search, since the program needs to take * mixed empty strings into consideration. * If the program hits an empty string, it will keep iterative looping toward the end of the array, * until the program hits a non-empty string, then binary search operation will be performed. * * The worst running time is O(N), but the expected running time is O(log*N). */ public static int binarySearch(String[] strings, String target, int start, int end) { //Base case, the target string is not found. if( start > end) return -1; int middle = (start + end) / 2; if(strings[middle].equals(target))//Lucky! { return middle; } int tempMiddle = middle; if(strings[middle].isEmpty())//The worst scenario, the program hits an empty string. { tempMiddle = searchNonEmptyString(strings, start, end, middle); if(tempMiddle == -1) return -1; } //search the right side of the first encountered non-empty string. if(target.compareTo(strings[tempMiddle])> 0) { return binarySearch(strings, target, tempMiddle + 1, end); } //search the left of the first encountered non-empty string . else if(target.compareTo(strings[tempMiddle]) < 0) { return binarySearch(strings, target, start, tempMiddle - 1); } else { //After skipping all the empty strings, we found the target string. return tempMiddle; } } public static int searchNonEmptyString(String[] strings, int start, int end, int middle) { int temp = middle; while(temp <= end) { if(!strings[temp].isEmpty()) return temp; temp++; } // The right side of the middle string is full of empty strings, temp = middle; while(temp >= start) //Search the left side of the middle. { if(!strings[temp].isEmpty()) return temp; temp--; } //string array is full of empty strings. return -1; } public static void main(String[] args) { String[] strings = {"apple", "", "", "", "", "beer", "", "fruit", "", "", "hello", "", "world", "", ""}; //output: 0 System.out.println(binarySearch(strings, "apple", 0, strings.length -1 )); //output: 10 System.out.println(binarySearch(strings, "hello", 0, strings.length -1 )); //output: -1 System.out.println(binarySearch(strings, "zebra", 0, strings.length -1 )); } }
