CodeTips

import java.util.Arrays; public class QuickSort { int [] data ; public void quicksort( int [] nums) { if (nums == null || nums. length == 0 ) return ; data = nums; sort( 0 , nums. length - 1 ); } private void sort( int left, int right) { if (right <= left) return ; int pivot = partition(left, right); sort(left, pivot - 1 ); sort(pivot + 1 , right); } /** * put all the numbers that are smaller than pivot to the left * **/ int partition( int left, int right) { int pivot = data [right]; int startIndex = left; for ( int i = left; i < right; i++) { //all the nums on the left of startIndex are smaller than pivot //the number at startIndex is >= pivot if ( data [i] < pivot) { swap(startIndex++, i); } } // put the pivot to the right position swap(startIndex, right); r...

/**  * The read4 API is defined in the parent class Reader4.  *     int read4(char[] buf);  */ public class Solution extends Reader4 {     /**      * @param buf Destination buffer      * @param n   Number of characters to read      * @return    The number of actual characters read      */     // we need to save unused characters in a queue     // e.g. if we read 4 characters when calling read4, but we only need 2     // we save the 2 remaining characters in remain, we can use the remaining 2 chars first     // when next time the read(buf, n) is called     Queue<Character> remain = new LinkedList<>();       public int read(char[] buf, int n) {         int i = 0;         // check the remain queue first         while ...

class Solution {     public boolean isAlienSorted(String[] words, String order) {         int n = words.length;         Map<Character, Integer> orderMap = new HashMap<>();         for (int i = 0; i < order.length(); i++) {             orderMap.put(order.charAt(i),i);         }         for (int i = 0; i < n - 1; i++) {             if (!isSorted(words[i], words[i + 1], orderMap)) {                 return false;             }         }         return true;     }     boolean isSorted(String first, String two, Map<Character, Integer> map) {         int len1 = first.length();         int len2 = two.length();   ...

Yes, there is a Hashtable class in Java. Right, Hashtable with a lowercase t. 1. First difference. They inherit from different classes.  Hashtable is based on Dictionary class. HashMap is implemented based on the Map interface since Java 1.2. See the code below. public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {...} public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, Cloneable, Serializable {...} HashMap   extends the abstract class AbstractMap and implement the  Map interface: public abstract class AbstractMap<K, V> implements Map<K, V> {...} 2. The methods in Hashtable are synchronized，but the methods in HashMap are not synchronized by default. In multi-thread situations，we can use Hashtable.  If we choose to use HashMap, we need to handle the synchronization. 3. In Hashtable, no null value for keys ...

Purdue CS408 Software Testing Midterm 2018 Why test generation is difficult to automate? Unfortunately, automated test generation is infeasible in general because defining test oracle is mainly a manual process. What is testing oracle? test oracle is the procedure that determines if a test fails or passes. Test Gen -> Test Run -> Debugging -> Back to Test Gen Test gen Test run Stop Condition – # of bugs identified (graph should be reducing), coverage, Mutation Testing Test case id important level   L1 critical, if fail, can’t continue anything else L2 functional L3 usability The “law of conservation of bugs”: The number of bugs remaining in a large system is proportional to the number of bugs already fixed. Ripple Effect There is a high probability that the efforts to remove the defects may have actually added new defects The maintainer tries to fix problems without fully understanding the ramifications of th...

Given an array with n numbers, with n - 1 comparisons, we are able to find the smallest number in the array. After we find out the minimum number of the array, we only need n - 2 comparisons to find out the second smallest element in the array. Because there are n - 1 remaining elements. Can we do better than this? The answer is YES. The algorithm works as follows. See the image below. 1) Split the array into groups of two. 2) Get the smaller one out of the two. 3) Keep comparing until we find out the minimum. There are n - 1 comparisons to find out the minimum of the array. 4) Note that the second smallest element is among the elements that were compared with the minimum in the comparison tree. There are lgn elements that are compare with the smallest element. See the double circled elements in the image. Now lgn -1 comparisons are needed to find the smallest value out of the lgn values. The total comparisons  are n - 1 + lgn - 1 = n + lgn - 2.