• 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 < 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 < n - layer-1; i++ ){
        ans[count++] = matrix[layer][i];
        }
        for(int i = layer; i < m - layer-1; i++ ){ ans[count++] = matrix[i][n-layer-1]; } for(int i = n-layer-1; i > layer; i-- ){
        ans[count++] = matrix[m-layer-1][i];
        }
        for(int i = m-layer-1; i > 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 < 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 < n - layer-1; i++ ){
        matrix[layer][i] = array[count++];
        }
        for(int i = layer; i < m - layer-1; i++ ){ matrix[i][n-layer-1] = array[count++]; } for(int i = n-layer-1; i > layer; i-- ){
        matrix[m-layer-1][i] = array[count++];
        }
        for(int i = m-layer-1; i > 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 < m; i++ ){
        for(int j = 0; j < n; j++ ){
        matrix[i][j] = in.nextInt();
        }
        }
        
        rotate(matrix, r);
        for(int i = 0; i < m; i++ ){
        for(int j = 0; j < n; j++ ){
        System.out.print( matrix[i][j] );
        if( j < n-1 ) System.out.print( " " );
        }
        if( i < 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 <= n ){  arr = multiply( count++, arr ); // arr is in reverse order  }  for(int i = arr.length-1; i >= 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 < arr.length + digits.length - 1; i++ ){
         int step = carry;
         for(int j = Math.max( 0, i + 1 - digits.length) ; j < 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 > 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<Integer> ans = new ArrayList<Integer>();
         while( n > 0 ){
         ans.add( n % 10 );
         n /= 10;
         }
         return listToArray( ans );
         }
        
         public static int[] listToArray( List<Integer> list ){
         int[] ans = new int[ list.size() ];
         for( int i = 0; i < 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 < 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 >= 0; i-- ){
         if( nums[i] >= 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 >= startIndex; i--){
         if( nums[i] > 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 < n; i++ ){
         playerOneScore[i][i] = nums[i];
         }
         for(int d = 1; d < n; d++ ){
         for( int i = 0; i < 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] < nums[i+d] + playerTwoScore[i][i+d-1] ) ? playerOneScore[i][i+d-1] : playerOneScore[i+1][i+d];
         }
         }
         return ( playerOneScore[0][n-1] >= 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

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