 July 28
 Basic Tree Traversal problems
 https://www.hackerrank.com/challenges/swapnodesalgo
 https://www.hackerrank.com/challenges/kittyscalculationsonatree
 Finding lowest common ancestor quickly?
 Basic Tree Traversal problems
 July 27
 https://www.hackerrank.com/challenges/detectwhetheralinkedlistcontainsacycle
 Standard Floyd cycle detection.
 Basic Tree Traversal problems
 https://www.hackerrank.com/challenges/treepreordertraversal
 https://www.hackerrank.com/challenges/treepostordertraversal
 https://www.hackerrank.com/challenges/treeinordertraversal
 https://www.hackerrank.com/challenges/treeheightofabinarytree
 https://www.hackerrank.com/challenges/treetopview
 https://www.hackerrank.com/challenges/treelevelordertraversal
 https://www.hackerrank.com/challenges/binarysearchtreeinsertion
 https://www.hackerrank.com/challenges/treehuffmandecoding
 LC Hard: https://leetcode.com/problems/editdistance/tabs/description
 Failed
 https://www.hackerrank.com/challenges/detectwhetheralinkedlistcontainsacycle
 July 25
 Jenkov’s concurrency tutorial (section 2127)
 Stanford CS 140 lecture: Processes and Threads.
 To add: implement locks/ThreadPool to deepen understanding of concurrency.
 https://leetcode.com/problems/slidingwindowmaximum/#/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 [ik+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 k1, peek at the head of the queue – that would give you the max in the range [ik+1, i].
 https://www.hackerrank.com/challenges/thestoryofatree
 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/sparsearrays
 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 1620)
 Blog post
 https://www.hackerrank.com/challenges/thequickestwayup
 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
 Jenkov’s concurrency tutorial (section 1115)
 Concurrency exercises: http://www.cs.carleton.edu/faculty/dmusican/cs348/java_multi/ (Homepage: http://www.cs.carleton.edu/faculty/dmusican/cs348w16/)
 https://www.hackerrank.com/challenges/thepowersum
 https://www.hackerrank.com/challenges/crosswordpuzzle
 Redo this again – although you solved it, this is certainly your weakest link.
 https://www.hackerrank.com/challenges/recursivedigitsum
 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/synchronousshopping/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 smallestweight 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/eventree/
 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.
 Hackerrank week of code 34 question 3:
 July 18
 https://leetcode.com/problems/theskylineproblem/#/description
 Use a sorted Map<Interval, Height>, where intervals would be disjoint (except on the border)
 When you add an interval, search for intervals such that your start <= interval end <= your end.
 For each interval, do intersection if necessary, and update height.
 For printing, go through each interval while tracking last height:
 If current height > last one, add (start, height) to the list; else keep going
 track the end of the last guy, and append (end, 0) at the end
 The idea should be correct, but your code is buggy.
 https://www.hackerrank.com/challenges/torqueanddevelopment
 Equivalent to finding number of connected components. Gave a dfs solution.
 https://www.hackerrank.com/challenges/gridlandmetro
 naive countdown latch solution.
 https://www.hackerrank.com/challenges/journeytothemoon
 size of each connected components. Still doable by dfs.
 Initially brute force compute sum of pairwise product of connected component size. That results in TLE in one test case, so change it to half of square of sum – sum of squares.
 https://leetcode.com/problems/theskylineproblem/#/description
 July 17
 Java Concurrency Exercises:
 Go back to https://leetcode.com/problems/jumpgameii/#/description
 Implemented Range Minimum Query using Segment tree – actually not that messy for implementation.
 Reference: http://www.geeksforgeeks.org/segmenttreeset1rangeminimumquery/
 There’s a much nicer O(n) greedy solution.
 https://www.hackerrank.com/contests/w34/challenges/onceinatram
 Should read how others write this later – this is precisely my weakness; I can write working but extremely messy code for this kind of thing.
 https://www.hackerrank.com/challenges/fraudulentactivitynotifications
 I still don’t understand what went wrong with previous solution – since it gave me WA rather than TLE. Nonetheless, implemented bucket sort solution anyway.
 https://www.hackerrank.com/challenges/hackerlandradiotransmitters
 Your attempt: sort. Start from the lowest element, set the center to be the farthest possible element that can still cover your current low. Increment counter and update.
 July 16
 https://www.hackerrank.com/challenges/quicksort3
 https://www.hackerrank.com/challenges/quicksort4
 https://www.hackerrank.com/challenges/countingsort4
 https://www.hackerrank.com/challenges/fraudulentactivitynotifications/problem
 Couldn’t pass test, not sure what’s happening.
 Failed
 https://www.hackerrank.com/challenges/lilyshomework/problem
 Couldn’t pass test for a long time – later realize that it doesn’t have to be sorted ascendingly – the other way can also happen.
 https://leetcode.com/problems/maximumaveragesubarrayii/#/description
 Brute force does work actually, lmao.
 Official solution uses binary search – very nice!
 July 15
 https://www.hackerrank.com/challenges/richierich
 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 &amp;amp;amp;amp;amp;amp;amp;lt; n/2; i++){ if( arr[i] == arr[n1i] ) correctDigit[i] = true; else count++; } if( k &amp;amp;amp;amp;amp;amp;amp;lt; count ) return "1"; else{ //initial update k = count; for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;lt; n/2; i++){ if( !correctDigit[i] ){ if( arr[i] &amp;amp;amp;amp;amp;amp;amp;gt; arr[n1i] ) arr[n1i] = arr[i]; else arr[i] = arr[n1i]; } } //update from beginning, by replacing pairs by 9 whenever possible. int i = 0; while( k &amp;amp;amp;amp;amp;amp;amp;gt; 0 &amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp; i &amp;amp;amp;amp;amp;amp;amp;lt; n/2 ){ if( !correctDigit[i] &amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp; arr[i] != '9' ){ arr[i] = '9'; arr[n1i] = '9'; k; } else if( correctDigit[i] &amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp; k &amp;amp;amp;amp;amp;amp;amp;gt; 1 &amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp; arr[i] != '9' ){ arr[i] = '9'; arr[n1i] = '9'; k = 2; } i++; } //handle the middle guy if( n%2 == 1 &amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp; k &amp;amp;amp;amp;amp;amp;amp;gt; 0 ) arr[n/2] = '9'; return String.valueOf( arr ); } }
 Initial attempt:
 https://www.hackerrank.com/challenges/sherlockandanagrams
 Initial attempt:
static int sherlockAndAnagrams(String s){ Map&amp;amp;amp;amp;amp;amp;amp;lt;Map&amp;amp;amp;amp;amp;amp;amp;lt;Character, Integer&amp;amp;amp;amp;amp;amp;amp;gt;,Integer&amp;amp;amp;amp;amp;amp;amp;gt; substrFreq = new HashMap&amp;amp;amp;amp;amp;amp;amp;lt;&amp;amp;amp;amp;amp;amp;amp;gt;(); char[] arr = s.toCharArray(); int n = arr.length; int ans = 0; for(int l = 1; l &amp;amp;amp;amp;amp;amp;amp;lt; n; l++ ){ substrFreq.clear(); //initialize map Map&amp;amp;amp;amp;amp;amp;amp;lt;Character, Integer&amp;amp;amp;amp;amp;amp;amp;gt; freq = new HashMap&amp;amp;amp;amp;amp;amp;amp;lt;&amp;amp;amp;amp;amp;amp;amp;gt;(); for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;lt; 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 &amp;amp;amp;amp;amp;amp;amp;lt; nl; i++){ //beginning of substrings that you will throw first char away freq = new HashMap&amp;amp;amp;amp;amp;amp;amp;lt;&amp;amp;amp;amp;amp;amp;amp;gt;( 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 * (num1) /2; } } return ans; }
 Initial attempt:
 https://www.hackerrank.com/challenges/bearandsteadygene
 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)
 Your attempt:
 https://www.hackerrank.com/challenges/richierich
 July 14
 Four hackerrank problems (ixl)
 https://leetcode.com/problems/jumpgameii/#/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/reversepairs/#/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/sherlockandvalidstring
 https://leetcode.com/problems/besttimetobuyandsellstockiv/#/description
 Your attempt: DP, track two double arrays: (Memory limit exceeded)
 max profit, at most k transactions, holding at the end of nth day ( bought but not sold yet is not counted as a transaction)
 max profit, at most k transactions, not holding at the end of nth day
 Second attempt: to calculate the arrays at (k,n), only need data for (k, <n) and (k1, <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, n1) or (k1, n1) – in particular the window nk never increases. This means as you iterate j up to k, you only need to look up to (j, j + nk) 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 nth day, j up to k int[] notHolding = new int[n]; // max profit, for at most j transactions and not holding at the end of nth 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;lt; n; i++){ min = ( prices[i] &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; min ) ? prices[i] : min; holding[i] = min; } int window = nk; //recurrence for(int j = 1; j &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 0th day = bought stock the first day for(int i = 1; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; j + window; i++ ){ newHold[i] = Math.max( newHold[i1], notHolding[i1]  prices[i] ); notHolding[i] = Math.max( holding[i1] + prices[i], notHolding[i1] ); } holding = newHold; } return notHolding[n1]; }
 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!
 Your attempt: DP, track two double arrays: (Memory limit exceeded)
 https://leetcode.com/problems/reversenodesinkgroup/#/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;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 kblock for(int i = 0; i &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/countprimes/#/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;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;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;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/findlargestvalueineachtreerow/#/description
 Your attempt: bfs

public List&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;gt; largestValues(TreeNode root) { if( root == null ) return new ArrayList&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;gt;(); Queue&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;gt; queue = new ArrayDeque&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;gt;(); queue.add( root ); List&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;gt; ans = new ArrayList&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;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;lt; size; i++ ){ TreeNode node = queue.poll(); if( node.val &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/reversewordsinastringiii/#/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;lt; splitWords.length; i++ ){ char[] arr = splitWords[i].toCharArray(); for(int j = arr.length1; j &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;lt; splitWords.length  1 ) sb.append( " " ); } return sb.toString(); }
 https://leetcode.com/problems/serializeanddeserializebinarytree/#/description
 Your attempt: it’s well known that binary tree can be reconstructed by preorder + inorder, for example.
 This
 Your attempt: it’s well known that binary tree can be reconstructed by preorder + inorder, for example.
 https://leetcode.com/problems/reversewordsinastringiii/#/description
Advertisements