TODO (SQL):
- https://leetcode.com/problems/human-traffic-of-stadium/
- https://leetcode.com/problems/trips-and-users/
- https://leetcode.com/problems/department-top-three-salaries/
- https://leetcode.com/problems/nth-highest-salary/
TODO:
- [10 minute problem, for starting out] https://leetcode.com/problems/number-of-1-bits/
- https://leetcode.com/problems/edit-distance/
- https://leetcode.com/problems/recover-binary-search-tree/
- https://leetcode.com/problems/sum-of-distances-in-tree/
- https://leetcode.com/problems/substring-with-concatenation-of-all-words/
- https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
- https://leetcode.com/problems/numbers-with-repeated-digits/
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 implementingiterateBeginEndOverSkyLine
. 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 emulatingcall stack
and usinggoto
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 theN
, and then walk forward
maintaining two pointers: one for current, one forcurrent+N
, whenN 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/