Leetcode practice 2024

2024/05/18

Think about BFS/DGS again

• Examples
  • uh these aren’t really bfs/dfs but whatever
    • https://leetcode.com/problems/invert-binary-tree/
    • https://leetcode.com/problems/count-good-nodes-in-binary-tree
    • https://leetcode.com/problems/minesweeper/
  • https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph

2024/05/16

Think about unionfind again

• Abstraction
  • Able to take union of sets
  • Able to find which set an element is in (sort of equivalently, checking if two elements are in the same set)
• Approaches
  • Naive:
    • a map that tracks elem -> set label
    • Union of two sets A and B now takes O(min(|A|, |B|)) time (assuming you know set size for each of them, update each of the label of the smaller set). In other words, worst case O(n).
    • Find which set an element is in O(1)
  • Improved:
    • For each set, use an element of the set as its representative.
      • Property: representatives of sets are then fixed point of the elem -> set label map.
    • Union of two sets A and B: only update label of the representatives. This is O(1). (only one update is needed)
    • Find which set an element is in:
      • would need to keep traverse the elem -> set label map until you find a fixed point, which is then the true representative.
      • Don’t have a good sense what the complexity is. Not sure how many steps merging happen.
  • Trick 1
    • When doing find set, you find the true representative v not just from your starting point a; you find the true representative for all nodes along the path [av].
    • Doing this improves find_set to be O(log n) amortized (Not sure why; same problem why I was stuck about complexity)
  • Trick 2
    • When doing union set, define a metric around size of a node (e.g. size of tree with root node, depth of tree with root node), and attach node with smaller metric to node with larger metric.
    • Point: resulting tree can’t be too imbalanced.
  • Doing trick 1 + trick 2 – time complexity = O(inverse ackermann(n)) apparently; effectively O(1) (not sure why, but okay)

• Examples
  • https://leetcode.com/problems/number-of-islands/
    • Union find speed/memory is p25
    • BFS is faster; speed/memory p90
  • https://leetcode.com/problems/redundant-connection/
  • https://leetcode.com/problems/validate-binary-tree-nodes
  • https://leetcode.com/problems/surrounded-regions/
    • Again, BFS probably faster
  • https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/

2024/05/08

Think about heap/priority queue again:

• data structure of sortable elements where
  • Insert is O(log n)
  • Delete is O(log n)
  • Peek (smallest) is O(1)
  • Pop (smallest) is O(log n)
  • Heapify the entire list is O(n)

• Sample usage
  • Finding k-th smallest element in a list – O(n + k log n)
    • Compared to sorting: O(n log n)
    • Compared to keeping a sorted list of k smallest elements: O(n log k)

• How does a heap look like
  • Max heap: binary tree, where parents >= child nodes
  • Heapify: greedy approach – either sift up, or sift down
    • Sift down is more efficient, and sifting whole array down is O(n). (https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity)
• Exercises
  • https://leetcode.com/problems/kth-largest-element-in-an-array/
  • https://leetcode.com/problems/ugly-number-ii/
    • Not exactly priority queue, but whatever
  • https://leetcode.com/problems/top-k-frequent-elements/
    • Simple sorting is quick enough, but whatever
  • https://leetcode.com/problems/k-th-smallest-prime-fraction
  • https://leetcode.com/problems/maximum-number-of-eaten-apples/
  • https://leetcode.com/problems/most-frequent-ids
    • An example where I needed to manually implement heap, since python heapq doesn’t support update.
    • Apparently the Python solutions there all used a hack to get around the update issue. While the logic makes sense, it’s hard to read/maintain – ignore that approach.

Leetcode

• 10/1
  • https://leetcode.com/problems/network-delay-time
    • Idea:
      • Find the fastest path to each node, given starting node k; then take max time.
      • Start with source vertex S. Suppose we can traverse to B in time t_B. Now we look at vertex A, and A -> B in time t_{AB}. Then we can update t_B -> min(t_B, t_A + t_{AB}).
      • The tricky thing here is if we should update t_B by the path through A, we should also update any vertex downstream to B. There are two ways around this
        • Either: each time t_A + t_{AB} < t_B, we add all downstream vertices of B to do update again; or
        • we traverse vertices in ascending order of time, so that if we traverse to A before B, then t_A + t_{AB} >= t_B.
  • https://leetcode.com/problems/delete-and-earn
  • https://leetcode.com/problems/cells-in-a-range-on-an-excel-sheet/
  • https://leetcode.com/problems/minimum-operations-to-halve-array-sum
• 10/3
  • https://leetcode.com/problems/merge-nodes-in-between-zeros/
  • (still unsolved) https://leetcode.com/problems/maximum-running-time-of-n-computers/
    • Idea: Greedy method – sort battery times, and each round you use the n batteries with best life by one time unit. Repeat.
    • Simplication 1:
      • sort batteries
      • drop 0’s if they exist
      • if number of batteries < computer (n), terminate.
      • if not
        • look at top n for battery life
        • increment run time (a[n] – a[n+1] + 1) (i.e. subtract each of the top n guy by a[n] – a[n+1] + 1
      • Should be correct, but TLE
    • Simplication 2:
      • No need to sort from scratch each time; top n and remaining entries are guaranteed to be sorted, can use bubble sort.
      • Should be correct, still TLE; similar run time
• 10/4
  • https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
    • Clearly common ancestor problem; optimization wasn’t needed to pass
  • https://leetcode.com/problems/count-vowel-substrings-of-a-string/
    • Standard two pointer
  • (unsolved) https://leetcode.com/problems/recover-the-original-array/description/
• 10/5
  • (unsolved) https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/description/
• 10/6
  • https://leetcode.com/problems/maximum-number-of-words-found-in-sentences
  • (unsolved) https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/
  • https://leetcode.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/
• 10/7
  • (unsolved) https://leetcode.com/problems/maximum-path-quality-of-a-graph/
  • (unsolved) https://leetcode.com/problems/fancy-sequence/
• 10/8
  • https://leetcode.com/contest/weekly-contest-366/
    • Solved 1, 2, 3. Couldn’t solve 4.
  • https://leetcode.com/problems/maximum-score-of-a-good-subarray/
    • Naive DP to calculate min of contiguous array containing k of any length: O(n^2), 38/72 test cases passed; TLE.
    • Two pointer extending from k (left and right) and document each time min of contiguous array would drop O(n)
      • This is good enough.
• 10/9
  • https://leetcode.com/problems/course-schedule-iv/
    • DFS; https://www.geeksforgeeks.org/find-ancestors-of-each-node-in-the-given-graph/ is sufficient
• 10/18
  • https://leetcode.com/problems/print-in-order/
    • Read solution, not familiar with threading
• 10/29
  • Leetcode contest 369: 2/4
  • Q3: clear DP.
    • Somehow you keep getting the dp relationship wrong. Wasn’t quite able to think clearly, and you resort to patching failed test case instead of forcing yourself to go back to square one and think clearly; solve quickly after lunch.
    • Lesson: go back to square one if patching doesn’t work for a few times. Don’t be lazy.
  • Q4: didn’t try, due to spending too much time on Q3.
    • Did not have good idea when playing with the problem. Smells like DP, but not clear to me the subtree problems overlap due to different coins config.
      • I see; somehow I keep thinking about commutativity of -k and halving. This is wrong, because the choice of either options does not cause -k in children.
    • Key observation is that the subtree problems overlap, and is indexed by “how many times were the entire subtree halved”. Since there are at most 1000 coins, number of halving <= 14. In which case time complexity is O(15 * E) = O(15n)
    • Naive solution TLE
      • Oh never mind; it’s already good enough. I just forgot to do caching.
• 10/31
  • https://leetcode.com/problems/print-foobar-alternately
    • Solved using a mutex (shared variable across thread). But don’t think the way I write it is “right”. (Use a while True loop; only if shared variable is right, that I break and proceed.)
    • New concepts learnt (for python)
      • Barrier: barrier.wait()
      • Condition: wait_for, notify
      • Event: wait, set, clear
      • Lock (mutex): acquire, release
• 11/5
  • https://leetcode.com/contest/weekly-contest-370/
  • 3/4
    • Q4: naive DP (O(n^2)) TLE (340/345 passed), don’t have better idea right now.
    • Nvm, actually have an idea now (inner loop doesn’t need to be O(n); probably reduce it to O(log n)?), but can’t implement it in time
    • Yeah, the idea is good enough (e.g. https://leetcode.com/problems/maximum-balanced-subsequence-sum/solutions/4250358/nums-i-i-nums-j-j/)
    • Implementation 1: Hmm, when actually implementing this, got to (344/345 passed); implementation is also messy/not clean.
      • By comparing with some working solution, issue maybe that list insert at specific index is slow (I thought it should be O(1), but maybe not? see also https://stackoverflow.com/questions/1110332/performance-of-list-insert)
      • More confidence that may be the reason: all published python solutions used sorted list/tree set in some way. No reason you need to do that if ordinary list works..
    • Implementation 2: OK let’s try sorted containers then. Yeah it works this time; insertion was very likely the problem.
      • After all, even one by one deletion in sorted list was fine :shrug:

from sortedcontainers import SortedList
class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n = len(nums)
        modified_nums = [num - idx for idx, num in enumerate(nums)]
        
        # threshold -> largest possible dp, under given threshold, so far
        # ascending threshold
        dp = SortedList()
        
        for i in range(n):
            threshold = modified_nums[i]
                        
            if not dp:
                dp.add((threshold, nums[i]))
                #print(dp)
                continue
            
            insert_idx = dp.bisect_right((threshold, inf))
            ret = nums[i] + (max(0, dp[insert_idx - 1][1]) if insert_idx > 0 else 0)

            remove_idx = dp.bisect_left((threshold, -inf))
            while remove_idx < len(dp) and (
                ret > dp[remove_idx][1] or threshold == dp[remove_idx][0]
            ):
                dp.remove(dp[remove_idx])
            dp.add((threshold, ret))
            #print(dp)
        return dp[-1][1]

• 11/12
  • https://leetcode.com/contest/biweekly-contest-117/
  • 3/4
    • Last question has clear algorithm, but off the shelf priority queue seems to have bug. Don’t have time to debug.
    • In any case, feel confident I can solve most mediums. Should change strategy to reduce time spent on medium and focus on knowledge gap/hard.
• 11/19
  • https://leetcode.com/contest/weekly-contest-372/
  • 1/2
    • Did Q3.
    • Q4 can be framed as a range minimum query problem that has O((log n)^2) solution per query, but I couldn’t test if it’s quick enough (don’t know how to implement segment tree)
• 11/26
  • https://leetcode.com/contest/weekly-contest-373
  • 2/3
    • Did Q2.
    • Did Q3.
      • Not familiar with disjoint union structure. But solved it conditioned on knowing how to implement that.
    • Q4.
      • There is a clear segment tree solution that may be good enough, but I still don’t know how to implement segment tree.
  • Gap to fill this week: segment tree.
• 11/27
  • https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
  • solved https://leetcode.com/contest/weekly-contest-372/problems/find-building-where-alice-and-bob-can-meet/
• 12/26
  • https://leetcode.com/contest/weekly-contest-377/
    • Q1,Q2 straightforward
    • Q3 is clear Dijkstra, but I don’t know how Dijkstra is done.
      • One approach is: for a fixed source, compute all minimal distance from that source. By iterating on the vertex with lowest unfinalized distance to source.
• 12/31
  • https://leetcode.com/contest/weekly-contest-378/
    • 4/4.
• 1/7
  • https://leetcode.com/contest/weekly-contest-379/problems
    • Did first three, haven’t looked at the 4th.
• 1/15
  • https://leetcode.com/contest/weekly-contest-380/
    • Solved Q4 conditioned on KMP algorithm (didn’t know what this is, :shrug:)
    • Pattern searching
      • Naive: O(nm)
      • Probablistic improvement: rolling hash (Rabin-Karp) – worst case O(nm), but if a substring doesn’t match, you can check that in O(1) time rather than O(m) time. This saves time if most substrings don’t match.
      • KMP: O(n + m) time.
        • Preprocess: for pattern of length m, figure out for each $0 \leq i < m$, the length of longest proper prefer that’s also a suffix (lps[i]).
        • When you roll over the text to check pattern, and say first [0…l] matches with pattern but (l+1)-th position doesn’t, check for lps[i] to know the next possible starting position. In other words, you can start matching (l+1)-th position etc with the lps[i]-th position of pattern.
        • This is pretty ingenious. Tried to implement it at https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description
  • 1/20
    • https://leetcode.com/contest/biweekly-contest-122/
    • 3/4.
      • Can’t give a honest attempt of last question because I don’t know how to implement that can do arbitrary element removal. Can’t find good code for that online. (This is honestly crazy, how is heapq so bad but is never updated? Wanting removal and update to work should be a very basic ask…)
  • 1/27
    • https://leetcode.com/contest/weekly-contest-381/
    • 3/4
      • Last question seems mathematical – WLOG assume x < y, and start < end. Trying to use brute force to remove all absolute values involved.

Vim plugins

General websites

A plugin repository: https://vimawesome.com
Some plugins: https://statico.github.io/vim3.html

Package manager

Vundle: https://github.com/VundleVim/Vundle.vim

Some plugins

• Figutive.vim: git + vim
• Nerd tree: tree explorer in Vim
• Ctrl-p: fuzzy file search
• Vim-color-solarized: color scheme
• youcompleteme: code completion

Vim cheatsheat

Have been familiarizing myself with Vim lately – this post gets updated every now and then as I learn something new.

Recording

• Very helpful for repetitive action/basic macro
• http://www.thegeekstuff.com/2009/01/vi-and-vim-macro-tutorial-how-to-record-and-play
• http://vimgolf.com/challenges/59a2167bd6550c0006000005

Completion

• Ctrl-N
  • Find next keyword (text completion)
• Ctrl-X
  • Enters a submode that does insert completion.
  • e.g. CTRL-X + CTRL-L searches backwards for a line that starts with the same characters as those in the current line (ignoring indent)
  • http://vimdoc.sourceforge.net/htmldoc/insert.html#ins-completion

Copy/paste

• :t = copy line. For example, :t6 = copy current line, paste after line 6.
• In insert mode, <C-R>a pastes from register a.

Register

• Register = clipboard essentially, i.e. temporary storage that you can put stuff in or paste stuff from.
• There are 26 registers (labeled a – z)
• There is also an unnamed register (labeled “) that stores last deleted/inserted text etc
• There are also some read-only registers. For example,
  • “. for last inserted text
  • “% has current file path
  • “/ for last search command
  • “+ for system clipboard
  • “: last command
  • …and so on

Editing

• i, a = insert before/insert after cursor.
• I, A = insert in beginning of line/end of the line.

Moving

• ( and ) are previous/next sentence.
• { and } are previous/next paragraph.
• <C-O> and <C-I> are previous/next visited location.
• 0 and $ are beginning of line/end of the line.
• ; repeats the last f, t, F, T command.

Marks

• m{a-z} set a mark on the current cursor position. (Use A-Z would mark position + the file, i.e. this mark would be cross file.) Can also do m`, kind of like an unnamed mark.
• `{a-z} to the mark, while `{A-Z} to the mark + right file. Can also do “, to jump to the previous context mark.
• :marks show all the marks.

Search

• * search forward for word under cursor, # search backward.
• f{char} searches for next character, forward, and move the cursor to that character. F searches backward.
• t{char} searches for next character, forward, and move the cursor to just before that character. T searches backward.

Text object selection

• This is something you can do after an operator, for example d (delete), c (change), s (substitute). Analogous to motion selection in this context.
• i(stuff) would do selection.
  • iw selects the next word(letter/digit/underscores).
  • iW selects the next WORD(sequence of non-blank characters)
  • i” selects the next word between quotes “. Same for (, <, {, …
  • http://vimdoc.sourceforge.net/htmldoc/motion.html#object-select
• For example, ciw changes the next word.

Visual mode

• V enters visual mode.
• In visual mode:
  • > shifts selected to the right. < shifts selected to the left.

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
  • https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
  • https://leetcode.com/problems/longest-common-prefix/description/
  • https://leetcode.com/problems/fraction-addition-and-subtraction/description/
    • Regex is great! Didn’t know (?=) before
  • https://leetcode.com/problems/pacific-atlantic-water-flow/description/
    • Misinterpreted the problem many times..
  • https://leetcode.com/problems/largest-divisible-subset/description/
    • Bad solution:
      • Sort.
      • use a map with key = last element in a candidate list and value = list itself.
      • Traverse the array. Check the element against each element in the map. If the array element is a multiple of the element – and that it’s the longest list satisfying this – put (array element, list appended with array element) to the map. The only other possibility is that the array element is not a multiple of any key, in which case, put (array element, singleton list of the array element)
      • O(n^2) speed, O(n) space.
    • Some improvements:
      • Looks like others’ basic ideas are all the same. One improvement is rather than tracking the whole list, use an array to track the previous index instead.
  • Trie practices
    • https://www.hackerrank.com/challenges/contacts
      • I usually use maps to do Tries, but it will be too slow for one test case here.
    • https://www.hackerrank.com/challenges/no-prefix-set
• 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
    • https://www.hackerrank.com/challenges/self-balancing-tree/problem
      • AVL tree insertion – did take me a long time to figure out the whole thing
      • Redo tomorrow: it’s possible to not track ancestors and handle all the changes you need during recursion.
    • https://www.hackerrank.com/challenges/median
      • Fairly likely that keeping a balanced tree together with number of elements in left/right subtree would be sufficient – O(log n) add/remove/get median.
      • Redo tomorrow: don’t want to look at AVL deletion right now.
  • 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
  • Basic tree traversal problems
    • https://www.hackerrank.com/challenges/is-binary-search-tree
      • The editorial’s idea of restricting range is very nice.
    • https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor
      • The case for binary search tree is trivial – should look at efficient ways for general trees.
    • https://www.hackerrank.com/challenges/square-ten-tree
      • Have mathematical ideas on how I can do this, but even for small numbers this feels excessively troublesome.
      • Find it hard to write down precisely what I have in mind – but roughly something like
        • keep dividing 10^{2^k} until the two numbers are the same.
        • Add number of intervals of that range that can lie in [L,R]
        • split the remaining interval into left and right piece, and do recursion.
      • Obstruction:
        • to figure out number of intervals in that range, need to subtract L by 1 then divide by 10^{2^k} – seems troublesome to do so.
        • to write down the splitted intervals’ range, would need to initialize a fairly big array.
      • After reading editorial:
        • Certainly a mistake to not trying to solve [1,R] case first – was surprised at how simple that case is.
    • https://www.hackerrank.com/challenges/jenny-subtrees

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:

 

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
  • Basic Tree Traversal problems
    • https://www.hackerrank.com/challenges/swap-nodes-algo
    • https://www.hackerrank.com/challenges/kittys-calculations-on-a-tree
      • Finding lowest common ancestor quickly?
• July 27
  • https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle
    • Standard Floyd cycle detection.
  • Basic Tree Traversal problems
    • https://www.hackerrank.com/challenges/tree-preorder-traversal
    • https://www.hackerrank.com/challenges/tree-postorder-traversal
    • https://www.hackerrank.com/challenges/tree-inorder-traversal
    • https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree
    • https://www.hackerrank.com/challenges/tree-top-view
    • https://www.hackerrank.com/challenges/tree-level-order-traversal
    • https://www.hackerrank.com/challenges/binary-search-tree-insertion
    • https://www.hackerrank.com/challenges/tree-huffman-decoding
  • LC Hard: https://leetcode.com/problems/edit-distance/tabs/description
    • Failed
• 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
  • Jenkov’s concurrency tutorial (section 11-15)
  • Concurrency exercises: http://www.cs.carleton.edu/faculty/dmusican/cs348/java_multi/ (Homepage: http://www.cs.carleton.edu/faculty/dmusican/cs348w16/)
  • https://www.hackerrank.com/challenges/the-power-sum
  • https://www.hackerrank.com/challenges/crossword-puzzle
    • Redo this again – although you solved it, this is certainly your weakest link.
  • https://www.hackerrank.com/challenges/recursive-digit-sum
• 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
  • https://leetcode.com/problems/the-skyline-problem/#/description
    • Use a sorted Map<Interval, Height>, where intervals would be disjoint (except on the border)
    • When you add an interval, search for intervals such that your start <= interval end <= your end.
    • For each interval, do intersection if necessary, and update height.
    • For printing, go through each interval while tracking last height:
      • If current height > last one, add (start, height) to the list; else keep going
      • track the end of the last guy, and append (end, 0) at the end
    • The idea should be correct, but your code is buggy.
  • https://www.hackerrank.com/challenges/torque-and-development
    • Equivalent to finding number of connected components. Gave a dfs solution.
  • https://www.hackerrank.com/challenges/gridland-metro
    • naive countdown latch solution.
  • https://www.hackerrank.com/challenges/journey-to-the-moon
    • size of each connected components. Still doable by dfs.
    • Initially brute force compute sum of pairwise product of connected component size. That results in TLE in one test case, so change it to half of square of sum – sum of squares.
• July 17
  • Java Concurrency Exercises:
    • https://www.cl.cam.ac.uk/teaching/1516/ConcDisSys/con-systems-prac.txt
    • Exercises 1-3
  • Go back to https://leetcode.com/problems/jump-game-ii/#/description
    • Implemented Range Minimum Query using Segment tree – actually not that messy for implementation.
    • Reference: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
    • There’s a much nicer O(n) greedy solution.
  • https://www.hackerrank.com/contests/w34/challenges/once-in-a-tram
    • Should read how others write this later – this is precisely my weakness; I can write working but extremely messy code for this kind of thing.
  • https://www.hackerrank.com/challenges/fraudulent-activity-notifications
    • I still don’t understand what went wrong with previous solution – since it gave me WA rather than TLE. Nonetheless, implemented bucket sort solution anyway.
  • https://www.hackerrank.com/challenges/hackerland-radio-transmitters
    • Your attempt: sort. Start from the lowest element, set the center to be the farthest possible element that can still cover your current low. Increment counter and update.
• July 16
  • https://www.hackerrank.com/challenges/quicksort3
  • https://www.hackerrank.com/challenges/quicksort4
  • https://www.hackerrank.com/challenges/countingsort4
  • https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem
    • Couldn’t pass test, not sure what’s happening.
    • Failed
  • https://www.hackerrank.com/challenges/lilys-homework/problem
    • Couldn’t pass test for a long time – later realize that it doesn’t have to be sorted ascendingly – the other way can also happen.
  • https://leetcode.com/problems/maximum-average-subarray-ii/#/description
    • Brute force does work actually, lmao.
    • Official solution uses binary search – very nice!
• July 15
  • https://www.hackerrank.com/challenges/richie-rich
    • Initial attempt:

      static String richieRich(String s, int n, int k){
      if( n == 0 ) return "-1";
      
      char[] arr = s.toCharArray();
      int count = 0; //number of wrong digits
      boolean[] correctDigit = new boolean[n/2];
      for(int i = 0; i < n/2; i++){
      if( arr[i] == arr[n-1-i] ) correctDigit[i] = true;
      else count++;
      }
      
      if( k < count ) return "-1";
      else{
      //initial update
      k -= count;
      for(int i = 0; i < n/2; i++){
      if( !correctDigit[i] ){
      if( arr[i] > arr[n-1-i] ) arr[n-1-i] = arr[i];
      else arr[i] = arr[n-1-i];
      }
      }
      //update from beginning, by replacing pairs by 9 whenever possible.
      int i = 0;
      while( k > 0 && i < n/2 ){
      if( !correctDigit[i] && arr[i] != '9' ){
      arr[i] = '9';
      arr[n-1-i] = '9';
      k--;
      } else if( correctDigit[i] && k > 1 && arr[i] != '9' ){
      arr[i] = '9';
      arr[n-1-i] = '9';
      k -= 2;
      }
      i++;
      }
      //handle the middle guy
      if( n%2 == 1 && k > 0 ) arr[n/2] = '9';
      return String.valueOf( arr );
      }
      }

  • https://www.hackerrank.com/challenges/sherlock-and-anagrams
    • Initial attempt:

       static int sherlockAndAnagrams(String s){
      Map<Map<Character, Integer>,Integer> substrFreq = new HashMap<>();
      
      char[] arr = s.toCharArray();
      int n = arr.length;
      int ans = 0;
      for(int l = 1; l < n; l++ ){
      substrFreq.clear();
      //initialize map
      Map<Character, Integer> freq = new HashMap<>();
      for(int i = 0; i < l; i++){
      freq.put( arr[i], freq.getOrDefault( arr[i], 0 )+1 );
      }
      substrFreq.put( freq, 1 );
      
      //walk through the substrings of length l
      for(int i = 0; i < n-l; i++){ //beginning of substrings that you will throw first char away
      freq = new HashMap<>( freq );
      if( freq.get( arr[i] ) == 1 ) freq.remove( arr[i] );
      else freq.put( arr[i], freq.get(arr[i]) - 1 );
      
      freq.put( arr[i+l], freq.getOrDefault(arr[i+l], 0 )+1 );
      substrFreq.put( freq, substrFreq.getOrDefault( freq, 0)+1 );
      }
      
      //increment answer
      for(int num : substrFreq.values() ){
      ans += num * (num-1) /2;
      }
      }
      return ans;
      }

  • https://www.hackerrank.com/challenges/bear-and-steady-gene
    • Your attempt:
      • Store the accumulative frequency of A,C,G,T up to i.
      • In particular, the last such array counts the frequency of A,C,G,T in whole array. If all of them equals n/4, return 0.
      • If not, this gives us the discrepancy vector between each alphabet and n/4. For each index i, we seek the smallest index > i such that the number of alphabets in this range, is bigger than the discrepancy vector in every component.
      • Since accumulative frequency is increasing in each component, we can do the last step by binary search.
      • The overall algorithm is O(n log n)
• July 14
  • Four hackerrank problems (ixl)
  •  https://leetcode.com/problems/jump-game-ii/#/description
    • Your attempt: Clearly a range minimum query problem, trying to understand how segment tree can be used to solve it.
    • Not done
  • https://leetcode.com/problems/reverse-pairs/#/description
    • Your attempt: Keep [0,i] sorted so that we can binary search for the index/update answer. When we get to i+1, bubble down the latest element to make it sorted. O(n^2) (TLE)
    • Failed
    • Your idea is okay, as in you know that you should do something in [0,i] progressively to facilitate searching. Bad thing is bubble things down is too slow for this purpose – having some data structure would help.
      • Binary search tree would work, with average time O(log n) insertion and searching. This brings the average run time down to O(n log n). (Tried to implement naive unbalanced search tree – TLE)
      • Of course you may worry about unbalanced trees, so you can use any balanced binary search trees to make it actually O(n log n).
      • I don’t understand how Fenwick tree can be applied here.
• July 12
  • https://www.hackerrank.com/challenges/sherlock-and-valid-string
  • https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/#/description
    • Your attempt: DP, track two double arrays: (Memory limit exceeded)
      • max profit, at most k transactions, holding at the end of n-th day ( bought but not sold yet is not counted as a transaction)
      • max profit, at most k transactions, not holding at the end of n-th day
    • Second attempt: to calculate the arrays at (k,n), only need data for (k, <n) and (k-1, <n) – so just two rows is fine, rather than int[k][n]; (Time limit exceeded)
    • Third attempt: clearly k <= n/2. also note that notHolding array doesn’t need to cache the last k at all. O(kn), all test cases passed but still TLE
    • Fourth attempt: note also that the precomputation you need for (k,n) depends on (k, n-1) or (k-1, n-1) – in particular the window n-k never increases. This means as you iterate j up to k, you only need to look up to (j, j + n-k) rather than up to n. TLE
    • Failed, nonetheless

    •  public int maxProfit(int k, int[] prices) {
       int n = prices.length;
       if( n == 0 ) return 0;
      
       k = Math.min( n/2, k );
       int[] holding = new int[n]; // max profit, for at most j transactions and holding at the end of n-th day, j up to k
       int[] notHolding = new int[n]; // max profit, for at most j transactions and not holding at the end of n-th day, j up to k
      
       //initialize
       int min = Integer.MAX_VALUE;
       for(int i = 0; i < n; i++){
       min = ( prices[i] < min ) ? prices[i] : min;
       holding[i] = -min;
       }
      
       int window = n-k;
       //recurrence
       for(int j = 1; j <= 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 < 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 < 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 < 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 < 2) return 0;
      
       boolean[] composite = new boolean[n];
       int ans = 0;
       for(int i = 2; i < n; i++ ){
       if( !composite[i] ){
       ans++;
       int count = 2*i;
       while( count < 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<Integer> largestValues(TreeNode root) {
       if( root == null ) return new ArrayList<Integer>();
       Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
       queue.add( root );
      
       List<Integer> ans = new ArrayList<Integer>();
       while(!queue.isEmpty()){
       int size = queue.size();
       int max = Integer.MIN_VALUE;
       for(int i = 0; i < size; i++ ){
       TreeNode node = queue.poll();
      
       if( node.val > 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 < splitWords.length; i++ ){
      char[] arr = splitWords[i].toCharArray();
      for(int j = arr.length-1; j >= 0; j--){
      sb.append( arr[j] );
      }
      
      if( i < 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 < 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
  • https://leetcode.com/problems/increasing-triplet-subsequence/#/description
    • Your attempt: DP by tracking tail – similar to longest increasing subsequence (7ms, 35%)
  • https://leetcode.com/problems/roman-to-integer/#/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/brick-wall/#/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/different-ways-to-add-parentheses/#/description
    • Failed
• 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
  • https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/#/description
    • Failed
  • https://leetcode.com/problems/merge-k-sorted-lists/#/description
    • Your attempt: merge sort via priority queue.
    • Possible improvement: use recursion – generally if you want speed, avoid data structure.
  • https://leetcode.com/problems/bitwise-and-of-numbers-range/#/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/best-time-to-buy-and-sell-stock-iii/#/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/simplify-path/#/description
    • Your attempt: use an array and index to track what depth and filename I am at currently.
• 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
  • https://leetcode.com/problems/unique-paths/#/description
    • Your attempt: basic combinatorics – direct DP.
    • Improvement: the math solution (i.e. do (m+n-1)C(n-1) or something is faster)
  • https://leetcode.com/problems/valid-palindrome/
    • Your attempt: one pass on both ends to check the next alphanumeric characters.
  • https://leetcode.com/problems/island-perimeter/#/description
    • Your attempt: Track the 1’s – if one direction (out of 4) has no neighbor, increment perimeter.
  • https://leetcode.com/problems/magical-string/#/description
    • Your attempt: Use a queue to track generation of new numbers.
    • Improvement: Use array + pointer is faster than queue.
• Jun 29
  • https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/#/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/basic-calculator-ii/#/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/expression-add-operators/#/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/sort-characters-by-frequency/#/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/lowest-common-ancestor-of-a-binary-tree/#/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?
• Jun 28
  • Did four problems – accidentally deleted it 😦
  • https://leetcode.com/problems/binary-tree-level-order-traversal/#/description
  • https://leetcode.com/problems/house-robber-iii/#/description
  • https://leetcode.com/problems/concatenated-words/#/description (Failed)
  • https://leetcode.com/problems/move-zeroes/
  • https://leetcode.com/problems/group-anagrams/#/description
• Jun 27
  • https://leetcode.com/problems/design-excel-sum-formula/#/description
    • Failed
  • https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/#/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/sum-of-two-integers/#/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/add-strings/#/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/01-matrix/#/description
    • Your attempt: BFS with two queues
    • BFS is fine, although one actually doesn’t need BFS (!) Note that for a 1-cell and a 0-cell, you can either use left/top or right/down to reach the 0-cell from the 1-cell.
    • 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?
• 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
  • https://leetcode.com/problems/game-of-life/#/description
• Jun 22
  • https://leetcode.com/problems/lru-cache/#/description
  • https://leetcode.com/problems/out-of-boundary-paths/#/description
• Jun 21
  • https://leetcode.com/problems/friend-circles/#/description
  • https://leetcode.com/problems/reshape-the-matrix/#/description
• Jun 20
  • https://leetcode.com/problems/increasing-subsequences/#/description
  • https://leetcode.com/problems/search-a-2d-matrix/#/description

First blog post

This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog.