LeetLog

TODO (SQL):

TODO:

This is a Leet log. A log of Leetcode problems and their solutions done by me,
in reverse chronological order.

Useful commands

go test
go test -run TestMinCameraCover
go test -bench BenchmarkMinCameraCover

  • [2019-04-14]
    TODO: solve some SQL problems

  • [2019-04-14] Best time to buy and sell stock III
    I like Python a lot. I can work out a problem a lot faster
    When I have to spend a lot of time writing any solution in Go,
    I spend way less time creating the same solution in Python.
    Optimizing and reading solution is also a lot easier with this language
    And I am feeling more fun when working with it
    I guess, I should try to get a job in Python because it seems there are a lot
    of companies who use this language
    Overall, I am getting a handle on it. It took me ~3 hours to solve this hard problem
    I am still not in the top solutions, but I've managed to pass it all, so here is that
    Submission details: https://leetcode.com/submissions/detail/222333012/

  • [2019-04-14] No leetcode
    A job interview problem. I would classify it as an easy->trivial problem. But it had several nuances
    that I overlooked when started working on it. That is why it took me so long to solve it.
    Overeall, it took me 75/120 minutes to solve all edge cases.
    Let's hope that they accept my solution and I will continue
    to the next interview round

  • [2019-04-13] No leetcode
    Separate problem, that has label hard. The task is to calculate the shortest sequence
    that produces fizzbuzz output.
    The task is not hard, it can be easily solved through bruteforce, given the tiny input
    Overall, the only problem is getting used to solving these problems faster.
    It took me several hours, but It should have taken no more than 50 minutes.

  • [2019-04-12] Decode ways
    Well, I am still have a long way to go for the larger company interview. Such problems are expected to
    be solved in less than 45 minutes. It took me ~5 hours to make it work.
    In the end, I've had a very silly but very hard to notice bug. I've calculated lenghth of the
    dictionary, instead of calculating the sum of all its values.
    Anyway, the problem is solved and I still have some room to optimise
    on memory. The runtime looks nice, I am, almost, in top 10% by runtime distribution.
    On the side note, I should work more with Python. There is no room for cheating, as
    the language is slow, so no bruteforce will get accepted. And the language is very
    fun and easy to use. There is less bolerplate, and it is almost painless to convert
    pseudocode into a working algorithm
    Submission details: https://leetcode.com/submissions/detail/221953044/

  • [2019-03-30] Tallest billboard
    ~10 hours and more, three days, and five approaches later, finally, solved it only to be in the bottom 5% of efficiency!
    And this is for topic that I somewhat already familiar with.
    One year won't be enough for me to prepare for an interview.
    But, nonetheless, the solution was accepted, so I move on:
    Submission details: https://leetcode.com/submissions/detail/218703638/

  • [2019-03-27] Minimum window substring
    Well, this one was hard AF (well, as almost all problems submitted by leetcode).
    The most difficult thing was to figure out how to check for pattern incrementally and fast
    For the pattern with the unique letters the counting problem is trivial. But, for pattern with repeating letters it is hard
    The most annoying and difficult thing is to figure out and debug this stuff.
    On the plus side, it is the first my solution where I am faster than 78% of submitted solutions.
    And this freaking thing got 268 test cases!
    In the end, I've given up debugging 60 lines of a total mess and wrote a nice object oriented, decomplected iterator and tested each part of
    functionality seprately
    So, it may be worth a look.
    Anyway, here are submission details:
    Submission details: https://leetcode.com/submissions/detail/218058420/

  • [2019-03-25] Maximal rectangle
    It is the first problem, which I solved by iteration, not by recursion.
    I am still in the bottom 25% by time efficiency. So, here is that
    But, at least, I am learning now how to make it work. Overall, solving this problem
    took me ~3 hours of deep thinking
    I am not reading top
    Submission details: https://leetcode.com/submissions/detail/217529915/

  • [2019-03-18] Binary Tree Cameras
    Was sick this week, so, didn't add solutions. Now I am continuing working on these things.
    It took me ~3 hours to think up and code a solution for this problem.
    Still, I am in the bottom of submissions (64 ms against 6 ms). But, at least, I have this thing solved.
    Later, when I solve all of the hard ones, I will work on optimizations. Submission details: https://leetcode.com/submissions/detail/215779712/

  • [2019-03-12] Odd even jump
    I am able to implement naive DP solutions. (Meaning I get the intuition behind the solution and
    I can break down problem into subproblems to create a recursive definition) But I still cannot implement performant solutions
    In particular, this problem requires using the monotonic stack technique, that I haven't found
    in CPHB
    So, after I solve first 100 of hard problems, I should work on the optimization of my solutions.
    Submission details: https://leetcode.com/submissions/detail/214320084/

  • [2019-03-11] The Skyline Problem
    Overall, the idea is to not to spend time on tangential problems. For example, I've spent a lot of
    time implementing iterateBeginEndOverSkyLine. Which I shouldn't have done.
    I should have assumed that the average hard problem requires no more than an hour for
    thinking and implementing. If I am thinking about implementing something longer,
    then this solution is most probably not the optimal one
    Submission details: https://leetcode.com/submissions/detail/213984432/

  • [2019-03-09] Largest Component Size by Common Factor Solved this problem by using union find structure. Good thing about this problem is that it had me to study:

    • what is a component of a graph
    • what is a factorization of a number (for example, I didn't know that 1 wasn't prime, and didn't know any factorization algorithms)
    • what is a union find structure. I haven't heard about it before Overall, although, I spent more time on it. (I should solve one/day, not one/2days), this problem was beneficial to me.
      Submission details: https://leetcode.com/submissions/detail/213483591/
  • [2019-03-07] Largest rectangle in histogram
    That wasn't easy at all. First, I tried dynamic programming approach. It passed tests except tle on large input.
    Then, I tried stack based solution. (That I yesterday decided to make). It didn't work either. Today, I tried another
    way to handle this using dynamic programming reducing input through removing one of the params to the DP solve function.
    Then, translated that algorithm into stack based.
    And what is in the end? My solution in the bottom 10% of efficiency. I guess, if I've just calculated all possible solutions
    and choose the best it would work faster.
    Anyways, at least, the solution was accepted, so I move on.
    Later, when I will solve first 100 or so of these problems. I will return back and try to optimize it
    [TODO]: (implement solution using segment trees, study Binary indexed tree)
    Submission details: https://leetcode.com/submissions/detail/213024073/

  • [2019-03-05] Basic calculator
    Implemented tokenizer and calculator for this problem
    For possible optimization, should make streaming tokenizer, not consume entire input into memory
    Submission details: https://leetcode.com/submissions/detail/212534416/

  • [2019-03-05] PostOrderTraversal
    Iterative solution is now working. I've made it by emulating call stack and using goto statements to
    make jumps to recursive points.
    Submission details: https://leetcode.com/submissions/detail/212493978/

  • [2019-03-04] PostOrderTraversal
    Iterative solution: Ok, that wasn't simple. Tomorrow, implement conditional jumps in iterative algorithm. Emulate call stack. Figure out how to make return addresses/jumps within the subroutine. (I am too tired today already)

  • [2019-03-04] PostOrderTraversal
    Recursive solution: https://leetcode.com/submissions/detail/212317430/

  • [2019-03-04] 19. Remove Nth Node From End of List
    Took me 40-50 minutes to solve it. The trick to do it in one pass, is to iterate first to the N, and then walk forward
    maintaining two pointers: one for current, one for current+N, when N is nil, current.next = current.next.next
    Submission details: https://leetcode.com/submissions/detail/212314347/

  • [2019-03-04] 472. Concatenated Words
    Took me long time. Because was implementing trie from scratch
    In the end, replaced trie with a simple hashmap. Ideas to use:

    • first, maximally formalize the problem
    • Second, write the code and tests
    • Third, do not overoptimize. Use whatever structures you already have in stdlib. Trie took me ~4 hours to work and pass all tests and still I am not sure whether it is an optimal trie, or there are more tricks to it. Submission details: https://leetcode.com/submissions/detail/212304244/
  • [2019-03-02] Count the repetitions
    Done for ~3 hours to pass Leetcode test
    Submission details: https://leetcode.com/submissions/detail/211732286/

  • [2019-03-01] Cut off trees for golf.
    Done for 2.5 hours to pass Leetcode test.
    Submission details: https://leetcode.com/submissions/detail/211533228/

  • [2019-02-28] Word break II.
    Done for 4 hours to pass Leetcode test.
    Submission details: https://leetcode.com/submissions/detail/211328790/