• July 28
  • July 27
  • July 25
    • Jenkov’s concurrency tutorial (section 21-27)
    • Stanford CS 140 lecture: Processes and Threads.
    • To add: implement locks/ThreadPool to deepen understanding of concurrency.
    • https://leetcode.com/problems/sliding-window-maximum/#/description
      • Your attempt: have a maxPointer that tracks the index with maximum value. The very bad case, is when the whole array is decreasing, and so you need to linearly search for maxPointer every time. This makes it O(n^2) in that case, but on average it looks like O(n). (AC, 97.53%)
      • Some ideas from solution:
        • A two pass solution, where you split up the array into blocks of k. For each block, store the accumulating maximum from the left, and from the right. Given a length k interval, you can then split it into the right half of a block + the left half of an adjacent block. Just output the max( max of right half block, max of left half adjacent block)
        • A queueing solution. Use a queue to track the possible maximum indices.
          • If current index is i, keep polling head of queue until the index >= i – k + 1. This makes us focus on the index range [i-k+1, i]
          • We want to add nums[i]. Before we do so, poll from the back of the queue until nums[index] > nums[i]. This removes the elements in the queue that has no chance to be a max in any range.
          • Add nums[i] to the queue.
          • If the index is at least k-1, peek at the head of the queue – that would give you the max in the range [i-k+1, i].
    • https://www.hackerrank.com/challenges/the-story-of-a-tree
      • First attempt: brute force – try every node as root and see what happens – O(n^2) solution, 12.5% (other cases TLE)
      • Second attempt:
        • try first node as root, and get total number of right guesses/score.
        • Use an array to store the score for each node being used as root. Initialize score[first node] = score we found in last step.
        • Do BFS. In each round of BFS, use the child as the root node instead, and update the score for this new root node.
        • Go through the scores array once to count number of scores at least k.
        • This would be O(n) instead. (Passed)
    • https://www.hackerrank.com/challenges/sparse-arrays
      • What? Do you expect me to implement Hash map from scratch?
    • https://www.hackerrank.com/challenges/crush
      • Not hard to write a O(1) per operation, O(n) per query solution.
  • July 24
    • Jenkov’s concurrency tutorial (section 16-20)
    • Blog post
    • https://www.hackerrank.com/challenges/the-quickest-way-up
      • Your attempt: use recursion: try hitting the farthest point you can get to without hitting snake/ladder, and try all the snake/ladder you can reach in one roll.
      • Also track the visited vertices, in case there is a dead loop.
    • https://www.hackerrank.com/challenges/dijkstrashortreach
      • Classical Dijkstra – note that Java Priority Queue has O(n) runtime for remove – so don’t use Priority Queue to choose the next vertex to visit. Otherwise Test case 7 will TLE. (Naive linear search for minimum will pass test case 7)
    • Lookup fibonacci heap?
  • July 21
  • July 19
    • Hackerrank week of code 34 question 3:
      • Only pass half of the test cases, others TLE.
      • Without solutions it’s hard to see where my ideas can improve.
      • Track:
        • Naive O(n^2) per query solution: 5.97 points
        • Better O(n) per query solution: 20.31 points
        • What can I cache so that I can do better than O(n) per query? q >> n so presumably I should be caching things. Your O(n) per query solution depends on the pair, not the individual x,y though.
    • https://www.hackerrank.com/challenges/synchronous-shopping/problem
      • Failed. Don’t have any good ideas.
    • https://www.hackerrank.com/challenges/bfsshortreach
      • Trivial BFS
    • https://www.hackerrank.com/challenges/kruskalmstrsub
      • Read about Disjoint Set Data Structure and Kruskal’s algorithm – not hard to prove but still a little counter intuitive to me that naive greedy algorithm actually works.
      • Question is weird though – if you only care about minimizing sum of weights, then it doesn’t matter which smallest-weight edge you pick at every stage. The specification of which edge to choose is not tested at all any way.
    • https://www.hackerrank.com/challenges/even-tree/
      • Use any node as head of the tree. Assign leaf to have weight 1, and assign any parent to have weight 1 (for itself) + weights of all its children.
      • Greedy way is to chop off right above a parent (so that parent with its all children form a tree), if the parent’s weight is even.
      • Fairly certain this would work, because you are splitting out a minimum possible tree whenever possible.
      • Same solution as editorial.
  • July 18
  • July 17
  • July 16
  • July 15
    • https://www.hackerrank.com/challenges/richie-rich
      • Initial attempt:
        static String richieRich(String s, int n, int k){
        if( n == 0 ) return "-1";
        
        char[] arr = s.toCharArray();
        int count = 0; //number of wrong digits
        boolean[] correctDigit = new boolean[n/2];
        for(int i = 0; i < n/2; i++){
        if( arr[i] == arr[n-1-i] ) correctDigit[i] = true;
        else count++;
        }
        
        if( k < count ) return "-1";
        else{
        //initial update
        k -= count;
        for(int i = 0; i < n/2; i++){
        if( !correctDigit[i] ){
        if( arr[i] > arr[n-1-i] ) arr[n-1-i] = arr[i];
        else arr[i] = arr[n-1-i];
        }
        }
        //update from beginning, by replacing pairs by 9 whenever possible.
        int i = 0;
        while( k > 0 && i < n/2 ){
        if( !correctDigit[i] && arr[i] != '9' ){
        arr[i] = '9';
        arr[n-1-i] = '9';
        k--;
        } else if( correctDigit[i] && k > 1 && arr[i] != '9' ){
        arr[i] = '9';
        arr[n-1-i] = '9';
        k -= 2;
        }
        i++;
        }
        //handle the middle guy
        if( n%2 == 1 && k > 0 ) arr[n/2] = '9';
        return String.valueOf( arr );
        }
        }
    • https://www.hackerrank.com/challenges/sherlock-and-anagrams
      • Initial attempt:
         static int sherlockAndAnagrams(String s){
        Map<Map<Character, Integer>,Integer> substrFreq = new HashMap<>();
        
        char[] arr = s.toCharArray();
        int n = arr.length;
        int ans = 0;
        for(int l = 1; l < n; l++ ){
        substrFreq.clear();
        //initialize map
        Map<Character, Integer> freq = new HashMap<>();
        for(int i = 0; i < l; i++){
        freq.put( arr[i], freq.getOrDefault( arr[i], 0 )+1 );
        }
        substrFreq.put( freq, 1 );
        
        //walk through the substrings of length l
        for(int i = 0; i < n-l; i++){ //beginning of substrings that you will throw first char away
        freq = new HashMap<>( freq );
        if( freq.get( arr[i] ) == 1 ) freq.remove( arr[i] );
        else freq.put( arr[i], freq.get(arr[i]) - 1 );
        
        freq.put( arr[i+l], freq.getOrDefault(arr[i+l], 0 )+1 );
        substrFreq.put( freq, substrFreq.getOrDefault( freq, 0)+1 );
        }
        
        //increment answer
        for(int num : substrFreq.values() ){
        ans += num * (num-1) /2;
        }
        }
        return ans;
        }
    • https://www.hackerrank.com/challenges/bear-and-steady-gene
      • Your attempt:
        • Store the accumulative frequency of A,C,G,T up to i.
        • In particular, the last such array counts the frequency of A,C,G,T in whole array. If all of them equals n/4, return 0.
        • If not, this gives us the discrepancy vector between each alphabet and n/4. For each index i, we seek the smallest index > i such that the number of alphabets in this range, is bigger than the discrepancy vector in every component.
        • Since accumulative frequency is increasing in each component, we can do the last step by binary search.
        • The overall algorithm is O(n log n)
  • July 14
    • Four hackerrank problems (ixl)
    •  https://leetcode.com/problems/jump-game-ii/#/description
      • Your attempt: Clearly a range minimum query problem, trying to understand how segment tree can be used to solve it.
      • Not done
    • https://leetcode.com/problems/reverse-pairs/#/description
      • Your attempt: Keep [0,i] sorted so that we can binary search for the index/update answer. When we get to i+1, bubble down the latest element to make it sorted. O(n^2) (TLE)
      • Failed
      • Your idea is okay, as in you know that you should do something in [0,i] progressively to facilitate searching. Bad thing is bubble things down is too slow for this purpose – having some data structure would help.
        • Binary search tree would work, with average time O(log n) insertion and searching. This brings the average run time down to O(n log n). (Tried to implement naive unbalanced search tree – TLE)
        • Of course you may worry about unbalanced trees, so you can use any balanced binary search trees to make it actually O(n log n).
        • I don’t understand how Fenwick tree can be applied here.
  • July 12
    • https://www.hackerrank.com/challenges/sherlock-and-valid-string
    • https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/#/description
      • Your attempt: DP, track two double arrays: (Memory limit exceeded)
        • max profit, at most k transactions, holding at the end of n-th day ( bought but not sold yet is not counted as a transaction)
        • max profit, at most k transactions, not holding at the end of n-th day
      • Second attempt: to calculate the arrays at (k,n), only need data for (k, <n) and (k-1, <n) – so just two rows is fine, rather than int[k][n]; (Time limit exceeded)
      • Third attempt: clearly k <= n/2. also note that notHolding array doesn’t need to cache the last k at all. O(kn), all test cases passed but still TLE
      • Fourth attempt: note also that the precomputation you need for (k,n) depends on (k, n-1) or (k-1, n-1) – in particular the window n-k never increases. This means as you iterate j up to k, you only need to look up to (j, j + n-k) rather than up to n. TLE
      • Failed, nonetheless
      •  public int maxProfit(int k, int[] prices) {
         int n = prices.length;
         if( n == 0 ) return 0;
        
         k = Math.min( n/2, k );
         int[] holding = new int[n]; // max profit, for at most j transactions and holding at the end of n-th day, j up to k
         int[] notHolding = new int[n]; // max profit, for at most j transactions and not holding at the end of n-th day, j up to k
        
         //initialize
         int min = Integer.MAX_VALUE;
         for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n; i++){
         min = ( prices[i] &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; min ) ? prices[i] : min;
         holding[i] = -min;
         }
        
         int window = n-k;
         //recurrence
         for(int j = 1; j &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;= k; j++){
         int[] newHold = new int[n];
         newHold[0] = -prices[0]; // max profit, for at most k transactions and holding at the end of 0-th day = bought stock the first day
         for(int i = 1; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; j + window; i++ ){
         newHold[i] = Math.max( newHold[i-1], notHolding[i-1] - prices[i] );
         notHolding[i] = Math.max( holding[i-1] + prices[i], notHolding[i-1] );
         }
         holding = newHold;
         }
        
         return notHolding[n-1];
         }
      • After reading solution – key point is to handle the corner case k >= n/2, i.e. you can do any number of transactions directly. You don’t need DP for that!
    •  https://leetcode.com/problems/reverse-nodes-in-k-group/#/description
      • Your attempt: look ahead k dudes to see if reverse is necessary. If it is, use two pointers (one faster one slower) to swap next node one by one.
      •  public ListNode reverseKGroup(ListNode head, int k) {
         ListNode pre = new ListNode( 0 );
         pre.next = head;
        
         ListNode stopper = pre;
         while( stopper != null ){
         ListNode checker = stopper; //checker used to look ahead to see if there is k nodes remaining
         for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; k; i++ ){
         checker = checker.next;
         if( checker == null ) return pre.next;
         }
        
         ListNode tail = checker.next; // the supposedly "next" node; the initial value is the element right after the k elements we want to reverse order. In particular, the very first node in the block of k would have next pointing to this node
         ListNode mover = stopper.next; // start of the k-block
         for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; k; i++ ){
         ListNode tmp = mover.next;
         mover.next = tail; // adjust next node for our current target
         tail = mover; // move tail node
         mover = tmp; // move node
         }
         ListNode nextStopper = stopper.next; // the next stopper node in next while loop
         stopper.next = tail;
        
         stopper = nextStopper;
         }
        
         return pre.next;
         }
    • https://leetcode.com/problems/count-primes/#/description
      • Your attempt: basic sieve, using hashset (exceed memory)
      • Second attempt: basic sieve, using array
        public int countPrimes(int n) {
         if( n &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; 2) return 0;
        
         boolean[] composite = new boolean[n];
         int ans = 0;
         for(int i = 2; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n; i++ ){
         if( !composite[i] ){
         ans++;
         int count = 2*i;
         while( count &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n ){
         composite[count] = true;
         count += i;
         }
         }
         }
        
         return ans;
         }
      • Optimization: for inner loop you don’t need to start with 2*i, since for a composite number with the smallest prime factor p, the flag is set already if we start from p^2. This reduces number of operations.
    • https://leetcode.com/problems/find-largest-value-in-each-tree-row/#/description
      • Your attempt: bfs
      •  public List&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;Integer&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt; largestValues(TreeNode root) {
         if( root == null ) return new ArrayList&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;Integer&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;();
         Queue&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;TreeNode&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt; queue = new ArrayDeque&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;TreeNode&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;();
         queue.add( root );
        
         List&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;Integer&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt; ans = new ArrayList&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;Integer&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;();
         while(!queue.isEmpty()){
         int size = queue.size();
         int max = Integer.MIN_VALUE;
         for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; size; i++ ){
         TreeNode node = queue.poll();
        
         if( node.val &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt; max ) max = node.val;
        
         if( node.left != null ) queue.add( node.left );
         if( node.right != null ) queue.add( node.right );
         }
         ans.add( max );
         }
        
         return ans;
         }
  • July 11
    • https://leetcode.com/problems/reverse-words-in-a-string-iii/#/description
      • Your attempt: split the string by ” “, then reverse word by word.
      •  public String reverseWords(String s) {
        String[] splitWords = s.split(" ");
        
        StringBuilder sb = new StringBuilder();
        for( int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; splitWords.length; i++ ){
        char[] arr = splitWords[i].toCharArray();
        for(int j = arr.length-1; j &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;= 0; j--){
        sb.append( arr[j] );
        }
        
        if( i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; splitWords.length - 1 ) sb.append( " " );
        }
        return sb.toString();
        }
    • https://leetcode.com/problems/serialize-and-deserialize-binary-tree/#/description
      • Your attempt: it’s well known that binary tree can be reconstructed by preorder + inorder, for example.
        • This

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s