Technical interviews: String and array
Question1:
Design an algorithm to find all pairs of integers within an array which sum to a specified value
package com.hong.stringAndArray; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Set; /** * @author HongQing * */ public class TwoElementsSum { //Running time is O(N*logN). public static Map<Integer, Integer> subsums(int[] intArray, int sum) { Map<Integer, Integer> sumPairs = new HashMap<Integer, Integer>(); Arrays.sort(intArray); //O(N*logN) running time. int startIndex = 0; int endIndex = intArray.length - 1; while(startIndex < endIndex) //O(N) running time. { if(intArray[startIndex] + intArray[endIndex]== sum) { sumPairs.put(intArray[startIndex], intArray[endIndex]); startIndex++; } else if(intArray[startIndex] + intArray[endIndex] < sum) { startIndex++; } else { endIndex--; } } return sumPairs; } //Test cases public static void main(String[] args) { int[] intArray = {-4, -3, -7, 0, 8, 1, 3, 54 , 11, 15, 19, 32}; int sum = 16; Map<Integer, Integer> result = subsums(intArray, sum); Set<Map.Entry<Integer, Integer>> resultPairs = result.entrySet(); for(Map.Entry<Integer, Integer> pair : resultPairs) { System.out.printf("%d + %d = %d\n",pair.getKey(), pair.getValue(), sum ); } } }
Question2:
Design an algorithm to check if two strings are anagrams.
package com.hong.stringAndArray; import java.util.Arrays; import java.util.HashMap; /** * @author HongQing * */ public class AnagramsValidator { //Running time depends on Arrays.sort() which most likey is O(N*logN). public static boolean checkBySorting(String string1, String string2) { char[] str1 = string1.toCharArray(); char[] str2 = string2.toCharArray(); Arrays.sort(str1); Arrays.sort(str2); return Arrays.equals(str1,str2); } //Running time is O(N), but a little bit more complex. public static boolean checkByMap(String string1, String string2) { if(string1.length() != string2.length() ) return false; HashMap<Character, Integer> charsMap = new HashMap<Character, Integer>(); for(int i = 0; i < string1.length(); i++) { if(charsMap.containsKey(string1.charAt(i))) { charsMap.put(string1.charAt(i), charsMap.get(string1.charAt(i))+1); } else { charsMap.put(string1.charAt(i), 1); } } for(int i = 0; i < string2.length(); i++) { Object count = charsMap.get(string2.charAt(i)); if(null == count) { return false; } else if( (Integer) count > 1){ charsMap.put(string2.charAt(i), (Integer)count - 1); } else { charsMap.remove(string2.charAt(i)); } } return charsMap.isEmpty(); } public static void main(String [] args) { String[][] stringPairs = { {"Hello", "Heoll"}, {"TestTest","TTeesstt"}, {"Helloo","Hello"}, }; for(int i = 0; i < stringPairs.length ; i++) { if(checkByMap(stringPairs[i][0], stringPairs[i][1])) { System.out.println(stringPairs[i][0] + " and " + stringPairs[i][1] + " are anagrams."); } else { System.out.println(stringPairs[i][0] + " and " + stringPairs[i][1] + " are not angrams."); } } } }
Question3:
Design an algorithm to rotate an N x N matrix 90 degrees. Try to design an in place rotation algorithm.
Example:
Input:
3 2 1
3 2 1
3 2 1
Output:
3 3 3
2 2 2
1 1 1
package com.hong.stringAndArray; /** * @author HongQing * */ public class MatrixRotation { public static void rotateMatrix(int[][] dataMatrix ) { int rows = dataMatrix.length; int cols = dataMatrix[0].length; for(int i = 0; i < rows/2; i++) { int head = i; int tail = cols - i - 1; for(int j = head; j < tail; j++) { int offset = j - head; int top = dataMatrix[head][j]; //Rotate left to top. dataMatrix[head][j] = dataMatrix[tail-offset][head]; //Rotate bottom to left. dataMatrix[tail-offset][head] = dataMatrix[tail][tail-offset]; //Rotate right to bottom. dataMatrix[tail][tail-offset] = dataMatrix[j][tail]; //Rotate top to right. dataMatrix[j][tail] = top; } } } /* * Example: * 222 312 * 111 ==> 312 * 333 312 * */ public static void main(String[] args) { int[][] matrix = { {3,3,3}, {1,1,1}, {2,2,2}, }; System.out.println("Th original matrix:"); printMatrix(matrix); rotateMatrix(matrix); System.out.println("The matrxi after rotation:"); printMatrix(matrix); } public static void printMatrix(int[][] matrix) { for(int i = 0; i < matrix.length; i++) { for(int j = 0; j < matrix[0].length; j++) { System.out.print(matrix[i][j]); } System.out.println(); } } }
Question4:
You're given an array containing both positive and negative integers. Write a program to find the continuous sub-array with the largest sum in O(N) running time, return the sum and subarray.
package com.hong.stringAndArray; /** * @author HongQing * */ public class ArraySum { //Input: The original array has at least one positive element. //Output: The array has three elements, first element is the largest sum of the continuous subarray, second element is starting index of the // subarray, third one is ending index of the subarray. public static int[] maxSubArray(int[] array) throws Exception { if(array == null || array.length == 0) throw new Exception("Empty array exception."); int results[] = new int[3]; int maxSum = 0; int start = 0; int end = 0; int sum = 0; int tempStart = 0; for(int i = 0; i < array.length; i++) { sum += array[i]; //Swaps maxSum with current sum and update starting and ending index. if(sum > maxSum ) { maxSum = sum; start = tempStart; end = i; } if( sum <= 0 ) //If sum is less than or equals to zero, reset sum and temporary starting index. { sum = 0; tempStart = i + 1 > array.length ? array.length : i+1; } } results[0] = maxSum; results[1] = start; results[2] = end; return results; } public static void main(String[] args) { int[] results; int[] target = { 1, 3, -1, -9, 15, -7, 8, -78, 12}; try { results = maxSubArray(target); System.out.printf("Sum is %d which starts at index %d and ends at index %d ",results[0], results[1], results[2]); } catch(Exception e) { e.printStackTrace(); } } }