Basic Unix commands (tbc)

Fairly generic reference: https://www.tjhsst.edu/~dhyatt/superap/unixcmd.html

  1. ls, for listing all files in a directory.
    1. ls -a | list all files
    2. ls lol* | list all files with name starting with lol
    3. ls -d lol* | list all files AND directories with name starting with lol
    4. ls -l | list files in long format
    5. ls -r | list in reverse order
  2. cd for changing directory
  3. rm for removal
    1. rm -f | remove a file forcefully (ignore non-existent files, and do not prompt before deleting)
    2. rm -i | remove a file, prompt before removal.
    3. rm -r | remove directories and their content recursively.
    4. rm -v | remove verbosely – listing all the paths that were removed.
  4. mv for move/rename
    1. mv source (multiple) dest | move files/directories from source to destination
    2. mv source target | rename file/directory from source to target; if target file already existed, it would be overwritten.
    3. mv -i | prompt before overwriting
    4. mv -f | no prompt before overwriting
    5. mv -u | overwrite only when source is newer than destination.
    6. mv -v | verbose
  5. more for looking at a file, one page at a time
  6. grep [option] pattern(regex) file
    1. grep -b | display line number in original file for each line
    2. grep -c | display number of matched lines in each file
    3. grep -l | display only the names of matching files
    4. grep -w | match whole word

Leetcode III

  • August 3
  • July 31
    • Disjoint Set
      • https://www.hackerrank.com/challenges/merging-communities
        • First attempt: Naive DisjointSet Implementation, with union by rank – in particular, need to go up the forest to find ancestor every time – O(log n) merge and O(log n) query. TLE for most cases.
        • Second attempt: Optimize by caching index to oldest ancestor. Lazy updates. TLE for most cases.
        • Third attempt: Go back to attempt 1, but use path compression as well. Used array list to track the visited nodes whose parents have to be updated. TLE for most cases.
        • Fourth attempt: Use recursion directly to do path compression. Passed.
        • Conclusion: it looks like the main reason I get TLE was that in merging, I didn’t return when the two sets already have same ancestor. The official solution doesn’t do union by rank or path compression at all.
      • https://www.hackerrank.com/challenges/components-in-graph
        • Strongly suspect that bfs would be fast enough as well, but nonetheless solved by disjoint set.
      • https://www.hackerrank.com/challenges/kundu-and-tree
        • Fairly straightforward, once you realize that you should think of red edges as non-existent edges, and that you are trying to count the number of unordered triples coming from three distinct connected components (only with the black edges).
  • July 30
    • Basic tree problems
    • Stacks
      • https://www.hackerrank.com/challenges/balanced-brackets
      • https://www.hackerrank.com/challenges/game-of-two-stacks
        • First attempt: recursion, TLE for half the test cases.
        • Second attempt: key is to build a list of the “smallest” element you can take from the stack each time. Once you build this list, just keep polling until you hit the maximum allowed total. This can be done by tracking two pointers of the respective arrays. Some WA, some TLE
        • Third attempt: no need to build out that list – you can track the total sum so far in the process of updating the two pointers, and return the answer right away when ready.
        • Fourth attempt: the above is actually wrong: the greedy way of picking the lowest number at every step is logically wrong… does need recursive ideas, so let’s do memoization. Memoization done by a HashMap<Index Pair, Capacity> TLE for half the test cases.
        • Fifth attempt: Same as last idea, do bfs on the indices – add index 1 only when permissible, and if this has been calculated before (tracked by a HashSet), don’t do the calculation again. TLE for half of the test cases.
        • Sixth attempt: two pointer passing solution. Passed
  • July 29

Multithreading I

I am reading up on threading and concurrency issues lately. Blogging seems to be an interesting way to write down what I read and to clarify my thoughts a bit.


Prologue: Why concurrency?

We certainly love our devices to process multiple tasks at the same time. If we want to download a file, read a book and play music, we probably don’t want to do them one by one.

For practical purposes though, it is unnecessary for our computer to truly, concurrently download a file, display your book, and play music at the same time.

  • When I display a pdf for you to read, most of the time the computer sits there waiting for your next instructions, such as next page, previous page and so on. Unless you keep flipping the pages of the book and so on, the computer doesn’t have to do anything, after the first rendering of the page.
  • If I spend 50% of each second downloading a file, and the other 50% for other tasks, the file would still be downloaded.
  • To play music, I need to send a number of samples to my speaker every second. For each second, if I can produce and send the number of samples to my speaker needed in 0.01s, then I would have 0.99s for other tasks.

All the figures above are not meant to be accurate, but the idea is that if we can switch between tasks quick enough, practically speaking it would look like the computer is handling several tasks all at once. So practically the real question is then

How can we make process in multiple tasks at the same time?

1. Terminologies

When dealing with concurrency issues, there are several keywords that are used ubiquitously that were a little confusing to me at first. Let us first clarify what they mean.

Multitasking vs multiprocessing

Multitasking means you want to make progress in multiple tasks at the same time. This does not mean that at each instant, we really are executing instructions for separate tasks simultaneously – we can certainly do part of task A, switch to work on part of task B, switch to work on part of task C, come back to task A to finish it up, and so on. Our illustration earlier on downloading a file/displaying a book/playing music is one example of this.

On the other hand, Multiprocessing does mean we are trying to perform several tasks at the same time, by using multiple processors. Most computers these days have multiple-core CPUs, meaning that the CPU itself has multiple processing units/processor. If we execute different processes/tasks on each processor, we are multiprocessing.

Threads vs processes

We were already using the word process, but let us be a bit more precise now.

A process is basically an executable program loaded in the memory. Think of each process as a separate container – it has its own address space, memory, and so on. Nonetheless, processes can still talk to each other, for example by files, sockets, and so on. (Remark: processes can actually share memory, typically when one process is forked by another. As a first iteration of the picture though, this point can probably be ignored.)

Within one process though, we may still want to multi-task. Look at any multiplayer game – the computer needs to process what your character does, as well as talking to the server to see what other characters do. This leads us to threading.

A thread is an execution context ( reads: a sequence of instructions, together with the context of when/with what are these instructions executed ), that can be scheduled. A thread lives in a process, and a process can have multiple threads. All these threads will share the same resources as the process itself. Nonetheless, each threads may still maintain its own call stack to store context, local variables, and so on.

2. Multithreading

Multithreading is a way to achieve multitasking, by coordinating several threads of instructions to execute a task. In a multi-player game situation, we may have three threads in the most naive case:

  • One thread handling user input
  • One thread communicates with server to get the latest version of the whole game
  • One thread renders the latest version of the game.

Even if we have only one CPU, if we can coordinate these three threads well – so that we switch between threads at suitable time – it would look as if we handle these three tasks at the same time.

A basic model for coordinating threads is:

  • Each thread has a runnable task, and a state.
    • New: an initialized thread which is not started yet.
    • Runnable: A thread which is ready to run.
    • Running: A thread which is running/being executed right now.
    • Blocked: A thread which is waiting for completion of another thread to continue.
    • Dead: A thread is terminated, either because it has finished execution, or it gets interrupted.
  • The thread states can be modeled as below:

 

Screen Shot 2017-07-25 at 1.08.41 PM
Picture taken from Maryland CMSC 132 lectures.

Thread scheduling

An important part of this process is scheduling, which is the step of deciding which thread to run when the CPU is available.

Some concerns scheduling have to take into account include:

  • Fairness. If multiple threads are trying to run, it is possible that one thread never actually runs (sometimes called starving), because another thread gets selected each time. Fairness means we try to avoid this situation.
  • Priority. Different threads may have different priorities that we should account for.
  • Deadlines. Must a thread be executed before a certain time?
  • Throughput, i.e. the number of threads that finish running per unit time.
  • Efficiency – e.g. minimizing overhead of scheduler, context switching etc.

The two most basic categories for scheduling algorithms are

  • Non-preemptive scheduling. This means that once a thread starts to execute, it would end unless the thread finishes running and terminate/voluntarily yields the control of CPU.This can be a bad thing – if a time-intensive task is running while a higher-priority task comes up, we will not be able to stop the running thread to execute the higher-priority task first.
  • Pre-emptive scheduling. This means that the current executing thread may be interrupted.

There are many scheduling algorithms available, see here for a general introduction.

3. Some issues with multi-threading

There are some issues/tools we need to be aware of when we use multiple threads.

  • Data Race/Race conditions. Since multiple threads within a process share data, they may try to modify same data at the same time, and that could be a problem.
  • Thread signaling. If we try to split up a task among several threads, a situation like this may happen:
    • thread A does something, and pass the result to thread B.
    • thread B processes whatever it gets from thread A, and passes back to thread A.
    • thread A continues its execution.
      This means that thread B would need to signal thread A that the task is done, so that thread A wakes up and continues the process.

We will look at strategies to deal with these two issues in a future post.

 

Leetcode II

  • 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 &amp;amp;amp;amp;amp;amp;amp;amp;lt; n/2; i++){
        if( arr[i] == arr[n-1-i] ) correctDigit[i] = true;
        else count++;
        }
        
        if( k &amp;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;amp;lt; n/2; i++){
        if( !correctDigit[i] ){
        if( arr[i] &amp;amp;amp;amp;amp;amp;amp;amp;gt; 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 &amp;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;amp;amp; i &amp;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;amp;amp; arr[i] != '9' ){
        arr[i] = '9';
        arr[n-1-i] = '9';
        k--;
        } else if( correctDigit[i] &amp;amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;amp; k &amp;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;amp;amp; arr[i] != '9' ){
        arr[i] = '9';
        arr[n-1-i] = '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;amp;amp; k &amp;amp;amp;amp;amp;amp;amp;amp;gt; 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&amp;amp;amp;amp;amp;amp;amp;amp;lt;Map&amp;amp;amp;amp;amp;amp;amp;amp;lt;Character, Integer&amp;amp;amp;amp;amp;amp;amp;amp;gt;,Integer&amp;amp;amp;amp;amp;amp;amp;amp;gt; substrFreq = new HashMap&amp;amp;amp;amp;amp;amp;amp;amp;lt;&amp;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;amp;lt; n; l++ ){
        substrFreq.clear();
        //initialize map
        Map&amp;amp;amp;amp;amp;amp;amp;amp;lt;Character, Integer&amp;amp;amp;amp;amp;amp;amp;amp;gt; freq = new HashMap&amp;amp;amp;amp;amp;amp;amp;amp;lt;&amp;amp;amp;amp;amp;amp;amp;amp;gt;();
        for(int i = 0; i &amp;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;amp;lt; n-l; i++){ //beginning of substrings that you will throw first char away
        freq = new HashMap&amp;amp;amp;amp;amp;amp;amp;amp;lt;&amp;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 * (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

Leetcode I

 

  • July 10
    • https://www.hackerrank.com/challenges/matrix-rotation-algo
      • Your attempt: straightforward rotation. Why do they like tedious problems..
      • import java.io.*;
        import java.util.*;
        
        public class Solution {
        public static void rotate( int[][] matrix, int r ){
        int m = matrix.length;
        int n = matrix[0].length;
        
        for(int i = 0; i &lt; Math.min(m,n)/2; i++ ){
        // rotate i-th layer
        int perimeter = 2*(m+n-4*i) - 4;
        int shellR = r % perimeter;
        
        int[] array = shellToArray( matrix, i ); // clockwise
        int[] shiftedArray = cyclicShift( array, r );
        updateShellByArray( matrix, i, shiftedArray );
        }
        }
        
        public static int[] shellToArray( int[][] matrix, int layer ){ //copying i-th layer in clockwise direction
        int m = matrix.length;
        int n = matrix[0].length;
        int perimeter = 2*(m+n-4*layer) - 4;
        
        int[] ans = new int[perimeter];
        int count = 0;
        for(int i = layer; i &lt; n - layer-1; i++ ){
        ans[count++] = matrix[layer][i];
        }
        for(int i = layer; i &lt; m - layer-1; i++ ){ ans[count++] = matrix[i][n-layer-1]; } for(int i = n-layer-1; i &gt; layer; i-- ){
        ans[count++] = matrix[m-layer-1][i];
        }
        for(int i = m-layer-1; i &gt; layer; i-- ){
        ans[count++] = matrix[i][layer];
        }
        return ans;
        }
        
        public static int[] cyclicShift( int[] array, int shift ){
        int[] ans = new int[array.length];
        for(int i = 0; i &lt; array.length; i++){
        ans[i] = array[(i + shift) % array.length ];
        }
        return ans;
        }
        
        public static void updateShellByArray( int[][] matrix, int layer, int[] array ){
        int m = matrix.length;
        int n = matrix[0].length;
        
        int count = 0;
        for(int i = layer; i &lt; n - layer-1; i++ ){
        matrix[layer][i] = array[count++];
        }
        for(int i = layer; i &lt; m - layer-1; i++ ){ matrix[i][n-layer-1] = array[count++]; } for(int i = n-layer-1; i &gt; layer; i-- ){
        matrix[m-layer-1][i] = array[count++];
        }
        for(int i = m-layer-1; i &gt; layer; i-- ){
        matrix[i][layer] = array[count++];
        }
        }
        public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner( System.in );
        int m = in.nextInt();
        int n = in.nextInt();
        int r = in.nextInt();
        int[][] matrix = new int[m][n];
        
        for(int i = 0; i &lt; m; i++ ){
        for(int j = 0; j &lt; n; j++ ){
        matrix[i][j] = in.nextInt();
        }
        }
        
        rotate(matrix, r);
        for(int i = 0; i &lt; m; i++ ){
        for(int j = 0; j &lt; n; j++ ){
        System.out.print( matrix[i][j] );
        if( j &lt; n-1 ) System.out.print( " " );
        }
        if( i &lt; m-1 ) System.out.print( "\n" );
        }
        }
        }
        
    • https://www.hackerrank.com/challenges/extra-long-factorials
      • Your attempt: naive multiplication (yeah yeah I know there are quicker ways like Karatsuba’s algorithm, but let’s not bother during interview)
      • import java.io.*;
        import java.util.*;
        
        public class Solution {
        
        public static String factorial( int n ){
         StringBuilder sb = new StringBuilder();
         int[] arr = {1} ;
         int count = 1;
         while( count &lt;= n ){  arr = multiply( count++, arr ); // arr is in reverse order  }  for(int i = arr.length-1; i &gt;= 0; i-- ){
         sb.append( arr[i] );
         }
         return sb.toString();
         }
        
         public static int[] multiply( int n, int[] arr ){
         int[] digits = getDigits( n );
         int[] ans = new int[ arr.length + digits.length ];
         int carry = 0;
        
        for(int i = 0; i &lt; arr.length + digits.length - 1; i++ ){
         int step = carry;
         for(int j = Math.max( 0, i + 1 - digits.length) ; j &lt; Math.min( i+1, arr.length ); j++ ){  step += arr[j] * digits[ i - j ];  }  ans[i] = step % 10;  carry = step / 10;  }  int index = arr.length + digits.length - 1 ;  while( carry &gt; 0 ){
         ans[index++] = carry % 10;
         carry /= 10;
         }
         return Arrays.copyOfRange( ans, 0, index );
         }
        
         public static int[] getDigits( int n ){ // reverse order
         if( n == 0 ) return new int[] {0};
        
         List&lt;Integer&gt; ans = new ArrayList&lt;Integer&gt;();
         while( n &gt; 0 ){
         ans.add( n % 10 );
         n /= 10;
         }
         return listToArray( ans );
         }
        
         public static int[] listToArray( List&lt;Integer&gt; list ){
         int[] ans = new int[ list.size() ];
         for( int i = 0; i &lt; list.size(); i++ ){
         ans[i] = list.get(i);
         }
         return ans;
         }
         public static void main(String[] args) {
         /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
         Scanner in = new Scanner( System.in );
         System.out.println( factorial( in.nextInt() ) );
         }
        }
        
    • https://leetcode.com/problems/median-of-two-sorted-arrays/#/solutions
      • Failed
    • https://leetcode.com/problems/student-attendance-record-ii/#/description
      • Your attempt: Easy recurrence. (85.2%)
      • public int checkRecord(int n) {
         //count is an array counting [ 1 abs, last 2 is L; 1 abs, last one is L; 1 abs, last one not L; 0 abs, last one is L; 0 abs, last 1 is L; 0 abs, last one not L ]
         long[] count = {0,0,1,0,1,1};
         long a,b,c,d,e,f;
         int big = 1000000007;
         for(int i = 1; i &amp;lt; n; i++ ){
         a = count[1];
         b = count[2];
         c = (count[0] + count[1] + count[2] + count[3] + count[4] + count[5]) % big;
         d = count[4];
         e = count[5];
         f = ( count[3] + count[4] + count[5] ) % big;
         count[0] = a;
         count[1] = b;
         count[2] = c;
         count[3] = d;
         count[4] = e;
         count[5] = f;
         }
         return (int) ( ( count[0] + count[1] + count[2] + count[3] + count[4] + count[5] ) % big );
         }
    •  https://leetcode.com/problems/next-permutation/#/description
      • Your attempt: iterate from the end of array, and see if it’s in descending order; when it’s not, arrange the descending order part in ascending order, and swap the new element with the one just larger than it. (86.5% just bubble sort)
      • Tried to clean code up – turned out that using library to sort slows things down a lot here (24% lol)
      • public void nextPermutation(int[] nums) {
         int n = nums.length;
         if( n == 1 ) return;
        
         int max = nums[n-1];
         int i = n-2;
         for(; i &amp;amp;gt;= 0; i-- ){
         if( nums[i] &amp;amp;gt;= max ){
         max = nums[i];
         } else {
         int j = findNextLargerNumberIndex( nums, i+1, nums[i] );
         swap( nums, i, j );
         break;
         }
         }
        
         Arrays.sort( nums, i+1, n);
         }
        
         public int findNextLargerNumberIndex( int[] nums, int startIndex, int search ){
         for(int i = nums.length-1; i &amp;amp;gt;= startIndex; i--){
         if( nums[i] &amp;amp;gt; search ) return i;
         }
         return startIndex;
         }
        
         public void swap( int[] nums, int index1, int index2 ){
         int tmp = nums[index1];
         nums[index1] = nums[index2];
         nums[index2] = tmp;
         }
    • https://leetcode.com/problems/predict-the-winner/#/description
      • Your attempt: DP – find maximum scores of each player in each position. (45%)
      •  public boolean PredictTheWinner(int[] nums) {
         int n = nums.length;
         if(n == 1) return true;
        
         int[][] playerOneScore = new int[n][n]; //player one's max score if we play the game in range from i to j, inclusive.
         int[][] playerTwoScore = new int[n][n];
         for(int i = 0; i &amp;lt; n; i++ ){
         playerOneScore[i][i] = nums[i];
         }
         for(int d = 1; d &amp;lt; n; d++ ){
         for( int i = 0; i &amp;lt; n-d; i++ ){
         playerOneScore[i][i+d] = Math.max( nums[i] + playerTwoScore[i+1][i+d], nums[i+d] + playerTwoScore[i][i+d-1] );
         playerTwoScore[i][i+d] = ( nums[i] + playerTwoScore[i+1][i+d] &amp;lt; nums[i+d] + playerTwoScore[i][i+d-1] ) ? playerOneScore[i][i+d-1] : playerOneScore[i+1][i+d];
         }
         }
         return ( playerOneScore[0][n-1] &amp;gt;= playerTwoScore[0][n-1] );
         }
        
  • July 9
  • July 8
    • Leetcode Contest (Rank 94, 3/4)
  • July 7
    • https://leetcode.com/problems/lfu-cache/#/description (Previously failed)
      • Your attempt: (80.06%, O(log n) get and put – actually not quite, apparently removal in PriorityQueue uses a linear search to look for things you are removing, so eviction is O(n) time )
        • A priority queue to track the next element to evict
        • a map to track the (key, Node) pair.
        • a Node class that tracks key, value, frequency, and last used time.
        • get:
          • If key exists in the map, use map to retrieve the necessary node, and remove from the queue. Add a new node to the map/queue with updated frequency and last used time.
        • put:
          • If key exists in the map, use map to retrieve the necessary node, and remove from the queue. Add a new node to the map/queue with updated value, frequency and last used time.
          • If key doesn’t exist in the map and capacity is not reached, add Node to the map and the priority queue.
          • If key doesn’t exist in the map and capacity is reached, evict the key from the priority queue, and remove corresponding (key, Node) pair from the map. Add a new node to map/queue with the new key, value, freq and current time.
      • Better solution: (O(1) time, 86.25%)
        • Form a Map<Key, Frequency>, and Map<Frequency, LinkedHashSet>, and Map<Key, Value>
          • get:
            • If key exists in map, increment frequency, as well as updating the corresponding key set for the affected frequencies.
          • put:
            • If key exists in map, increment frequency, as well as updating the corresponding key set for the affected frequencies, and the new value.
            • If key doesn’t exist in the map and capacity is not reached, update the three maps accordingly.
            • If key doesn’t exist in the map and capacity is reached, evict the first key for the lowest frequency, update accordingly.
    • https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/#/description (Previously failed)
      • Map to track prefix vs “opposite” prefix
      • Map to track prefix and numbers starting with that prefix, masking initial digits
      • Remove the ones with no opposites, until there’s only one thing left
    • https://leetcode.com/problems/find-the-closest-palindrome/#/description (Previously failed)
    • https://leetcode.com/problems/divide-two-integers/#/description (Previously failed)
  • July 6
    • https://leetcode.com/problems/reverse-linked-list-ii/#/description
      • Your attempt: careful tracing. (4ms, 10.8%)
      • Unclear to me why the other solutions are quicker, since the idea looks the same.
    •  https://leetcode.com/problems/find-k-pairs-with-smallest-sums/#/description
      • Your attempt: use a Priority Queue, initialized with (nums1[i], nums2[0]). Each time, poll an element; and add back a new one with nums2 index incremented. O(klog k) time, 65%
      • Optimization: cache sum – 79%
    • https://leetcode.com/problems/divide-two-integers/#/description
      • Given up
    • https://leetcode.com/problems/find-the-closest-palindrome/#/description
      • Failed
    •  https://leetcode.com/problems/next-greater-element-ii/#/description
      • Your attempt: use a Deque (i.e. stack + queue) O(n) (95%)
        • First pass:
          • Go through nums once. When you get to index i, for existing elements j in Deque, mark nums[j]’s next greatest integer is nums[i] and pop it out whenever nums[j] < nums[i].
          • After going through nums once, you are left with a stack where the bottommost element is the largest element, and the indices in stack would have descending nums values.
          • Mark the max element’s next greatest integer to be -1.
          • Go through nums for the second time, up to the max element’s index, do step 1 again.
          • For the remaining things in the stack, they must have the same value as the max element. Mark all of them to have next greatest integer -1.
    • https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description
      • Your attempt: calculate frequency (for each alphabet) of p. Do the same for each continuous block in s that has same length as p. You can update the frequency of the block as you move one step to the right. (88%)
      • Optimization: The sliding window solution is very clean! You are using the same idea, but his way of writing is much cleaner than yours.
  • July 5
    • https://leetcode.com/problems/number-of-boomerangs/#/description
      • First attempt: cache pairwise midpoint and target slope, check if point is on the line. TLE. (O(n^3))
      • Second attempt: for each point, create a map, and store (distance^2, multiplicity) pair. Then sum up. O(n^2), 35%
      • Third attempt: same as second, except caching the distance^2 for i < j so that I only need to calculate half the distance O(n^2), 19% (Huge memory overhead, and honestly doesn’t seem to save time)
      • Optimization ideas:
        • Use second attempt as skeleton
        • Rather than going through the values and sum freq*(freq-1) afterwards, move this into the first for loop – i.e. whenever the map already contains the key, add 2*map.get(key) (58.72% – fastest try 98%, variance too huge)
    • https://leetcode.com/problems/pascals-triangle/#/description
      • First attempt: recursive buildup by nCr = (n-1)Cr + (n-1)C(r-1) – use list (1ms, 29%)
      • Second attempt: cache last row in an array, hopefully save a little? (Same)
      • Optimization:
        • Trick – Arrays.asList works on int[][], and will convert it to List<List> (possibly 0ms, 99%)
    • https://leetcode.com/problems/lfu-cache/#/description
      • Failed
    • https://leetcode.com/problems/sum-of-left-leaves/#/description
      • Your attempt: recursion (~10ms, 28%)
      • Optimization:
        • make sure it’s tail recursion. (9ms, 48%)
        • Use boolean rather than int, since you need 1 bit of info on whether it’s a left leaf anyway (8ms, 77%)
    • https://leetcode.com/problems/pascals-triangle-ii/#/description
      • First attempt: recursive buildup by nCr = (n-1)Cr + (n-1)C(r-1) (2ms, 59.7%)
      • Second attempt: recursively build up by computing nCr from nC(r-1) – casting is needed (1ms, 88.46%) (if you do this more carefully, you can get it down to 0ms)
  • July 4
  • July 3
    • https://leetcode.com/problems/heaters/#/description
      • First attempt: Trivial linear scan over both houses and heaters. TLE
      • Second attempt: Sort heaters, linear scan over house, and binary search over heaters for each house. (49.7%)
    •  https://leetcode.com/problems/longest-increasing-subsequence/#/description
      • Solution 1 : O(n^2) – DP, by tracking the array of “Longest Increasing Subsequence ending at i”. Then l[i] = 1 + max_{j < i, a[j] < a[i]}  l[i]
      • Solution 2: O(n log n) – DP, by tracking the array of “Smallest possible number of longest Increasing Subsequence of length i-1”. For a new element, we can do a binary search; if it’s larger than all the tails, increasing length of array by 1, and attach the new tail. Otherwise if tail[i] < x <= tail[i+1], update tail[i+1]=x.
    •  https://leetcode.com/problems/russian-doll-envelopes/#/description
      • Your attempt: form a graph – vertex = envelope, edge from a to b if a can be contained in b. Then run bfs to find longest edge in the graph. O(n^2), TLE
      • Second attempt: Optimize by only tracking immediate neighbor – TLE.
      • A possible solution:
        • Sort the sequence in ascending order by width, and descending order by height for same width.
        • The problem is then the Longest-Increasing-Subsequence Problem for height.
    • https://leetcode.com/problems/populating-next-right-pointers-in-each-node/#/description
      • Your attempt: simple BFS using queue(4ms, 9.49%)
      • Second attempt: don’t use queue, use two while loops. (1ms, 30.18%)
      • Optimization:
        • The question actually assumes perfect binary tree FML. So in that case many checks are unnecessary. In particular, recursion is then possible.
    • https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/#/description
      • Your attempt: sort the dictionary in descending order of length then ascending lexicographical order. Then check linearly to see if dictionary dude is subsequence of my word.
      • Possible optimization: don’t need to sort – you need to find the longest only, so just do one pass linear time.
  • July 2
    • https://leetcode.com/problems/convert-bst-to-greater-tree/#/description
      • First attempt: Sort the list of all nodes in descending order. Track accumulating sum and add it to the node value.
      • Second attempt: oh fuck, it’s binary search tree. Use a stack to do postorder traversal. (20.7%)
      • Some possible optimization:
        • Use recursion. When you declare a stack on your own like that, you are just doing what the compiler is doing – more error-prone, and slower.
    •  https://leetcode.com/problems/word-search/#/description
      • First attempt: DFS via recursion. Minor optimization: don’t track the direction you came from. Still very slow (127ms – 3.88%)
      • Second attempt: DFS via stack. Slower – TLE
      • Big optimization:
        • You do NOT have to track visited vertices separately using a set every single time. Observe that when you use dfs, when you have to withdraw from the dfs child, you can mark the parent unvisited again!
        • After this – 7ms – 99% lol
    •  https://leetcode.com/problems/find-right-interval/#/description
      • Your attempt: naive O(nlog n) solution, by tracking one array of starting point, one array of endpoint, sort the start array, and for each endpoint, search for least starting point larger than it.
      • First attempt: TreeMap.
      • Second attempt: Implement it yourself – sort the start array, and write a binary search from scratch.
    • https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/#/description
      • First attempt: use an array to track frequency, a second pass to track down elements with frequency 0. Drawback: O(n) space.
      • Second attempt: In place “cycle” solution, i.e. take an element n out, mark a[n] = -1 for visited, and repeat for the original a[n]. Loop over the whole thing once for that, and track out the unvisited ones. O(1) space.
      • Some other nice ideas:
        • For visited index n, flip the sign of a[n] if a[n] is positive – so that after one pass, only non-visited indices have positive values.
        • For visited index n, add n to a[n]; so that after one pass, only non-visited indices have values <= n.
  • July 1
    • Leetcode Contest 39 (3 out of 4)
  • Jun 30
  • Jun 29
  • Jun 28
  • Jun 27
  • Jun 26
    • https://leetcode.com/problems/random-pick-index/#/description
      • Your attempt: naive map of index list: O(n) memory, O( length of list ) retrieval.
      • One improvement: O(n) memory (with smaller constant – since no manipulation on input is needed), O( length of list ) retrieval. The technique is Reservoir sampling, a technique of doing uniform sampling on an finite stream of numbers of unknown size, given a random number generator.
      • The basic question is: given a finite stream (but unknown size) of numbers, figure out a way to keep/replace the number as the stream passes along so that we are uniformly sampling the whole stream.
    • https://leetcode.com/problems/count-numbers-with-unique-digits/#/description
      • Simple counting.
  • Jun 24
  • Jun 22
  • Jun 21
  • Jun 20