 July 10
 https://www.hackerrank.com/challenges/matrixrotationalgo
 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 ith layer int perimeter = 2*(m+n4*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 ith layer in clockwise direction int m = matrix.length; int n = matrix[0].length; int perimeter = 2*(m+n4*layer)  4; int[] ans = new int[perimeter]; int count = 0; for(int i = layer; i < n  layer1; i++ ){ ans[count++] = matrix[layer][i]; } for(int i = layer; i < m  layer1; i++ ){ ans[count++] = matrix[i][nlayer1]; } for(int i = nlayer1; i > layer; i ){ ans[count++] = matrix[mlayer1][i]; } for(int i = mlayer1; 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  layer1; i++ ){ matrix[layer][i] = array[count++]; } for(int i = layer; i < m  layer1; i++ ){ matrix[i][nlayer1] = array[count++]; } for(int i = nlayer1; i > layer; i ){ matrix[mlayer1][i] = array[count++]; } for(int i = mlayer1; 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 < n1 ) System.out.print( " " ); } if( i < m1 ) System.out.print( "\n" ); } } }
 https://www.hackerrank.com/challenges/extralongfactorials
 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.length1; 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/medianoftwosortedarrays/#/solutions
 Failed
 https://leetcode.com/problems/studentattendancerecordii/#/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 &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/nextpermutation/#/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[n1]; int i = n2; for(; i &amp;gt;= 0; i ){ if( nums[i] &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.length1; i &amp;gt;= startIndex; i){ if( nums[i] &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/predictthewinner/#/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 &lt; n; i++ ){ playerOneScore[i][i] = nums[i]; } for(int d = 1; d &lt; n; d++ ){ for( int i = 0; i &lt; nd; i++ ){ playerOneScore[i][i+d] = Math.max( nums[i] + playerTwoScore[i+1][i+d], nums[i+d] + playerTwoScore[i][i+d1] ); playerTwoScore[i][i+d] = ( nums[i] + playerTwoScore[i+1][i+d] &lt; nums[i+d] + playerTwoScore[i][i+d1] ) ? playerOneScore[i][i+d1] : playerOneScore[i+1][i+d]; } } return ( playerOneScore[0][n1] &gt;= playerTwoScore[0][n1] ); }
 https://www.hackerrank.com/challenges/matrixrotationalgo
 July 9
 https://leetcode.com/problems/increasingtripletsubsequence/#/description
 Your attempt: DP by tracking tail – similar to longest increasing subsequence (7ms, 35%)
 https://leetcode.com/problems/romantointeger/#/description
 Your attempt: scan from left to right, if the next numeral is bigger than current one in value, update current value and next index accordingly. (74.86%)
 Optimization:
 Actually take O(n) time to convert each digit into numeral (rather than calling hash map every time) is actually much quicker.
 https://leetcode.com/problems/brickwall/#/description
 Your attempt: track frequency of the “breakpoints”, and the answer is number of rows – maximum frequency. (43%)
 Optimization:
 Using a classical for loop for each row rather than for(Integer : row) rises it to 86%, wtf? The biggest reason is probably removing an element is taking time.
 https://leetcode.com/problems/differentwaystoaddparentheses/#/description
 Failed
 https://leetcode.com/problems/increasingtripletsubsequence/#/description
 July 8
 Leetcode Contest (Rank 94, 3/4)
 July 7
 https://leetcode.com/problems/lfucache/#/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.
 get:
 Form a Map<Key, Frequency>, and Map<Frequency, LinkedHashSet>, and Map<Key, Value>
 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 )
 https://leetcode.com/problems/maximumxoroftwonumbersinanarray/#/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/findtheclosestpalindrome/#/description (Previously failed)
 https://leetcode.com/problems/dividetwointegers/#/description (Previously failed)
 https://leetcode.com/problems/lfucache/#/description (Previously failed)
 July 6
 https://leetcode.com/problems/reverselinkedlistii/#/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/findkpairswithsmallestsums/#/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/dividetwointegers/#/description
 Given up
 https://leetcode.com/problems/findtheclosestpalindrome/#/description
 Failed
 https://leetcode.com/problems/nextgreaterelementii/#/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.
 First pass:
 Your attempt: use a Deque (i.e. stack + queue) O(n) (95%)
 https://leetcode.com/problems/findallanagramsinastring/#/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.
 https://leetcode.com/problems/reverselinkedlistii/#/description
 July 5
 https://leetcode.com/problems/numberofboomerangs/#/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*(freq1) 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/pascalstriangle/#/description
 First attempt: recursive buildup by nCr = (n1)Cr + (n1)C(r1) – 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/lfucache/#/description
 Failed
 https://leetcode.com/problems/sumofleftleaves/#/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/pascalstriangleii/#/description
 First attempt: recursive buildup by nCr = (n1)Cr + (n1)C(r1) (2ms, 59.7%)
 Second attempt: recursively build up by computing nCr from nC(r1) – casting is needed (1ms, 88.46%) (if you do this more carefully, you can get it down to 0ms)
 https://leetcode.com/problems/numberofboomerangs/#/description
 July 4
 https://leetcode.com/problems/maximumxoroftwonumbersinanarray/#/description
 Failed
 https://leetcode.com/problems/mergeksortedlists/#/description
 Your attempt: merge sort via priority queue.
 Possible improvement: use recursion – generally if you want speed, avoid data structure.
 https://leetcode.com/problems/bitwiseandofnumbersrange/#/description
 Your attempt: check for the first binary digit that’s different – from there on all the remaining digits is 0.
 https://leetcode.com/problems/besttimetobuyandsellstockiii/#/description
 Your attempt: Use DP to track: maximum profit if you sell at time i, and maximum profit if you buy at >=i time.
 https://leetcode.com/problems/simplifypath/#/description
 Your attempt: use an array and index to track what depth and filename I am at currently.
 https://leetcode.com/problems/maximumxoroftwonumbersinanarray/#/description
 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/longestincreasingsubsequence/#/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 i1”. 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/russiandollenvelopes/#/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 LongestIncreasingSubsequence Problem for height.
 https://leetcode.com/problems/populatingnextrightpointersineachnode/#/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/longestwordindictionarythroughdeleting/#/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.
 https://leetcode.com/problems/heaters/#/description
 July 2
 https://leetcode.com/problems/convertbsttogreatertree/#/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 errorprone, and slower.
 https://leetcode.com/problems/wordsearch/#/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/findrightinterval/#/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/findallnumbersdisappearedinanarray/#/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 nonvisited indices have positive values.
 For visited index n, add n to a[n]; so that after one pass, only nonvisited indices have values <= n.
 https://leetcode.com/problems/convertbsttogreatertree/#/description
 July 1
 Leetcode Contest 39 (3 out of 4)
 Jun 30
 https://leetcode.com/problems/uniquepaths/#/description
 Your attempt: basic combinatorics – direct DP.
 Improvement: the math solution (i.e. do (m+n1)C(n1) or something is faster)
 https://leetcode.com/problems/validpalindrome/
 Your attempt: one pass on both ends to check the next alphanumeric characters.
 https://leetcode.com/problems/islandperimeter/#/description
 Your attempt: Track the 1’s – if one direction (out of 4) has no neighbor, increment perimeter.
 https://leetcode.com/problems/magicalstring/#/description
 Your attempt: Use a queue to track generation of new numbers.
 Improvement: Use array + pointer is faster than queue.
 https://leetcode.com/problems/uniquepaths/#/description
 Jun 29
 https://leetcode.com/problems/constructbinarytreefrompreorderandinordertraversal/#/description
 Your attempt: Spent a long time figuring out why preorder and inorder characterizes the binary tree, and used recursion.
 Second attempt: same idea; don’t copy array, just track index.
 Exercise: do not use recursion, use stack instead.
 Optimization:
 Avoid O(n) search to find separator, by caching index via hash map
 https://leetcode.com/problems/basiccalculatorii/#/description
 Your attempt: Extremely unclean brute force code, essentially by dealing with the previous block expression right away whenever you see + or – and update the answer.
 98.29% lol
 https://leetcode.com/problems/expressionaddoperators/#/description
 Failed
 Learnt how to write recursion for these – not too bad actually, but somehow you keep confusing yourself.
 Possible Optimization:
 Use StringBuilder rather than String addition.
 Rather than using String.substring, quicker to convert string into char array first and track index.
 https://leetcode.com/problems/sortcharactersbyfrequency/#/description
 Your attempt: one pass track frequency of characters, sort characters in descending order by frequency, then write the String.
 Possible Optimization:
 Do not use HashMap – in standard encoding Java characters is 2 bytes long (unsafe! Should not make this assumption in general) – so can do bucket sort using an array of length 256.
 Do not sort – Just build buckets. (O(n) vs O(nlog n))
 https://leetcode.com/problems/lowestcommonancestorofabinarytree/#/description
 Your attempt: compute the map from node to parent, then backtrack. Note: this one is actually binary tree, rather than binary search tree.
 Unsure how to speed up though – recursion (22%) is faster than my solution (9%).
 G4G: What is binary search tree – advantage over usual binary tree? Applications? Implementations?
 https://leetcode.com/problems/constructbinarytreefrompreorderandinordertraversal/#/description
 Jun 28
 Did four problems – accidentally deleted it 😦
 https://leetcode.com/problems/binarytreelevelordertraversal/#/description
 https://leetcode.com/problems/houserobberiii/#/description
 https://leetcode.com/problems/concatenatedwords/#/description (Failed)
 https://leetcode.com/problems/movezeroes/
 https://leetcode.com/problems/groupanagrams/#/description
 Jun 27
 https://leetcode.com/problems/designexcelsumformula/#/description
 Failed
 https://leetcode.com/problems/lowestcommonancestorofabinarysearchtree/#/description
 Your attempt: backtrack ancestor, then traverse the ancestor to find first intersection.
 Your attempt would work for any binary tree – this one is a binary SEARCH tree – which means you can take advantage of the fact that lowest common ancestor is the first node whose value is between the two target nodes.
 64.25% final
 https://leetcode.com/problems/sumoftwointegers/#/description
 Failed
 Your initial idea was great: a^b is sum without carry, and (a&b) << 1 is precisely the carry. But you didn’t note that this gives you a recursive solution!
 https://leetcode.com/problems/addstrings/#/description
 Your attempt: naive addition
 Seems fine; Optimization possible:
 StringBuilder seems to be much faster than String addition.
 For loop faster than while loop
 https://leetcode.com/problems/01matrix/#/description
 Your attempt: BFS with two queues
 BFS is fine, although one actually doesn’t need BFS (!) Note that for a 1cell and a 0cell, you can either use left/top or right/down to reach the 0cell from the 1cell.
 In particular, that means you can start from the top left corner, sweep to the bottom right by right/down, and update answer using only top or left neighbor. Then you can sweep back from bottom right to top left by left/top, and updates the answer by considering the bottom or right neighbor too.
 This saves on the number of updates you need to do.
 G4G: What is a heap?
 https://leetcode.com/problems/designexcelsumformula/#/description
 Jun 26
 https://leetcode.com/problems/randompickindex/#/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/countnumberswithuniquedigits/#/description
 Simple counting.
 https://leetcode.com/problems/randompickindex/#/description
 Jun 24
 Jun 22
 Jun 21
 Jun 20
Advertisements