LeetCode - completed easy level problems

LeetCode is one of the popular coding practice online sites. One can find coding interview questions from big IT / financial companies, and submit their code for each questions to compare code performance against statistics from thousands of other coders. As of this writing there are 957 problems available; easy / medium / hard difficulty being roughly one third respectively. In order for the submitted code to be accepted, it has to pass all (as many as hundreds) test cases of varying length and complexity, within reasonable amount time. One will see 'time limit exceeded (TLE)' error if not. So solving a problem means [1] implementing [2] efficient algorithm.

Earlier this year I started Python coding practice with LeetCode. Back then with rudimentary coding skills I managed to solve a few easiest problems after fixing the code many times due to TLE. It was so annoying to have my code denied by invincible extreme test cases. So I gave up within a few weeks. I switched to a far more interesting challenge site - Project Euler. LeetCode has primarily computer science style problems, whereas PE heavily involves mathematics which I like. I learned a lot about basics of Python by comparing my PE code with others. After about 4 months of serious dedication into Project Euler with Python (I will write about this later) I retried LeetCode. The problems now seemed far easier. A lot of codes I wrote for easier problems passed all test cases pretty quick. What a surprising improvement.

Then I switched back to LeetCode. Time permitting, I could solve 10 problems within 3~4 hours in one shot, even including the time spent on examining code by other people for subsequent study, and on recording the code and notes (I have most of the codes saved on my Gmail account)! Furthermore, easy level problems felt too easy thus not worth wasting my time and effort. But I decided to be a bit patient. I wanted to cover all major topics and to learn basic code snippets particularly because I am not a computer science major. 

I solved the easy problems one by one with increasing difficulty. Toward the end the problems were getting hard, so recently I could solve only a few per day. And today, on X-mas 2018 (not what I intended), at last I completed all ~240 easy problems available free (about 10% of problems are open to paid premium users, which I plan to solve later all together).

Through the journey I could self-study crucial topics such as array / string / hashing / dynamic programming / binary tree / etc. Out of the key areas, depth first traversing binary trees using recursive algorithm was the hardest to get used to since it requires a highly distinct mode of reasoning. Now that I successfully went through tens of simple examples by myself, I am afraid no more of writing recursive code blocks, while I definitely was in the past. Truly a big step forward.

In LeetCode, you can see other's code in the discussion board for each problem without having your code accepted. But I would like to emphasize that there were less than ~5 cases out of ~240 problems where I did that. Those were mostly when the problem description was unclear, for which a lot of users had strong complaints. Except for those, I am proud of myself finishing easy problems all by myself.

Now I am walking into medium level problems. Hope I don't give up until I finish all of them, and post the news in the near future.

Unique features of Houston and the downtown

Recently I visited Houston, TX for the first time (been in Texas though). I observed a few interesting points in downtown, which I haven't seen or I'm not used to in anywhere else in the US.

[1] One-way streets

So many (or most of the) streets were 4~5 lanes wide but one-way. It was so wide to allow double lanes of street parking on BOTH sides, still leaving spaces for two-way traffic in the middle if it were Manhattan. I stayed in downtown only during the weekend, so have no idea on the traffic conditions during weekday. One-way streets should suffer from much less issues associated with intersections / traffic lights / left turn, so one-way-dominant could be a better scheme for busy downtown. Anyway I haven't seen any city streets that wide mostly running one-way. Isn't one-way street typically for narrow roads in old cities?

[2] Parking space

Houston downtown had many blocks only for parking. There were many parking only buildings around, up to 10~15 stories high. Even more interesting thing was open parking lot (no building or whatever) occupying a whole block. Where else in other big US cities can you imagine so many of a whole building or even open parking lot right in the middle of high-rise buildings. Later I learned that Houston is the only city in the US without 'zoning' regulation, meaning no governing set of rules on allowed facilities zone by zone. Or parking building is such a lucrative business contrary to my expectation, probably because of negligible maintenance cost and stable cash in-flow, only prohibited by zone control?

[3] Traffic against passenger pickup

I noticed this immediately upon leaving the Houston airport (IAH) terminal C to get a taxi. The traffic was moving to my left! It means that passengers need to cross the street to get on board. Not only inconvenient, but also accident-prone. The pick-up / drop-off area was larger on the other hand, so it was not as messy as it could have been in other US airports, but I could not figure out the reason that the airport traffic was designed in an opposite sense of rotation (when looked down from the sky). For valet maid to stay away from the building, not to be in the lobby area for their 'master'? More surprisingly, some downtown hotels had similar traffic pattern in the entrance area. Apparently Houston-specific way of thinking. I am truly wondering why.

[4] Toothpick

Many of the restaurants I visited had a bucket of toothpick ready for pickup in the reception / counter area. Much higher frequency than any other cities. Why..?

Mathematical vs. Computational approach II - linear algebra

I was solving LeetCode #874 - Walking Robot Simulation. (Yes, I am almost done with solving Easy level problems!) Here you need to be able to turn the direction of robot motion, out of four possible orientations: North / South / East / West, or simply ±X and ±Y. What came to me first was purely mathematical, or linear algebra: rotation matrix. For clockwise rotation, you can use R(-90°) where R is the 2x2 unitary matrix corresponding to CCW rotation, and R(90°) for opposite rotation.

But there are only four direction vectors: (±1, 0) and (0, ±1). Rotation means circulating the four either with increasing or decreasing indices. R(90°) is equivalent to cyclic (1,0) → (0,1) → (-1,0) → (0,-1) → (1,0).

The mathematical logic using rotation matrix can generalize the vector rotation into any angle. In that sense it is a fundamental principle. But the special case of direction vectors only along x or y axis doesn't even need any math, except that you denote the direction vectors with proper tuple (set) of coordinates. The latter is obviously much simpler and quicker to calculate, thus optimal for this particular problem.

To me the distinction between mathematical and computational approach in the present case goes far beyond a question of which is faster or better. I feel that I am seeing a deep philosopical dichotomy between pure and applied knowledge (or science). The former type of people, or principle-based thinkers may not understand or like those with the latter, and vice versa. The gap between the two regime might be far wider and deeper than we assume.

Certified Solidworks Associate & Professional

I have 10 years of professional experience using Solidworks. In constructing large-scale custom-designed cryogenic UHV (ultra-high-vacuum) experimental probe stations. Which involves thousands of components of varying length scale from fraction of inches to a few feet, as well as actual assembly / testing / trouble-shooting of each components into intermediate modules, and finally to a final station.

Dassault Systèmes, manufacturer of 

Solidworks, offers certificate exam for user proficiency in three levels: certified associate / professional / expert, of course in increasing difficulty. According to Solidworks, as of today, there are 226007 associate, 98971 professional, and 3642 experts worldwide.

I was long aware of the the certificates. I also already reached levels to pass professional exams with little additional preparation, but only recently attempted.

In my experience, associate exam was quite easy. Parts were relatively straightforward to design. I finished the exam in a little over half of the given time. But professional exam demanded much higher level of proficiency. You have to pass three sections: parts / configurations / assemblies. The later two sections were not that hard, although you need to be familiar with minor functions. But parts section was quite difficult. In fact I failed the first attempt particularly because I had not much experience with equation-driven designs. I had to do a bit of practice, and passed the second attempt.

I am just one of the ~100K professionals. But I suspect only a few of them has a Physics Ph. D. degree from Ivy League university. Furthermore, I feel almost obligation toward challenges when I see an immediate next goal: a certified Solidworks Expert. There are a few prerequisites and I need some self-training for it. But I hope that I post expert certificate soon.

Unbearable nuisance of a tiny sub-icon to Google Chrome icon in the Windows task bar

There are tiny things that I can't bear with, even in cases I can just ignore. Simply I can't. I must figure out why or what's happening and resolve. Here is an example.

Sometimes I found a small sub-icon is attached at the right bottom corner of Google Chrome browser icon (under Windows, but I believe it should be platform-independent) like this -

I remember to have seen this a few times in the past. My past web search into the reason always failed probably because in the first place I failed to figure out the right search keyword. The fact that I couldn't figure it out was far more annoying than the appearance of the sub-icon itself.

Today I finally figured out by accident. Not by web search. It seems to happen when more than one user account is logged into the Google Chrome browser.

So click 'Manage people' and remove unnecessary users. Then the sub-icon disappears. So great to see that it is gone.

Mathematical vs. Computational approach - combinatorial

Here's the question. You are given rods of lengths 2 and 3. You are to line them up so that the total length is 20. How many different ways are there to make length of 20? You have sufficient quantity of both types of rods. Not meant to be a non-sense / tricky question. There are at least two major distinct types of approaches.

[1] Algebraic / Mathematical

Let x and y represent the number of rods of lengths 2 and 3, respectively. Then the governing equation is 2x + 3y = 20 with x and y being non-negative integers. For each (x, y) combination, there are f(x,y) = (x+y)!/(x!y!) different ways of arranging them. So for each combination,

(x, y) = (10, 0) gives f(10, 0) = 1

(x, y) = (7, 2) gives f(7, 2) = 36

(x, y) = (4, 4) gives f(4, 4) = 70

(x, y) = (1, 6) gives f(7, 6) = 7

and the answer is 1 + 36 + 70 + 7 = 114.

[2] Computational

We can incrementally increase the length of the rod, using rod of lengths shorter by 2 or 3. For L = 7 for example, you can add L=2 rod to the right end of each configuration for L=7-2=5, or add L=3 to right end of configuration for L=7-3=4. So the governing equation here is g(7) = g(4) + g(5), or in general g(L) = g(L-3) + g(L-2), with g(0) = 0, g(1) = 0, g(2) = 1, g(3) = 1. We can 'climb the ladder' one by one, or increase L by one until L=20. To list a few intermediate cases,

g(4) = 1

g(5) = 1

g(6) = 2

g(7) = 3

g(10) = 7

g(12) = 12

g(15) = 28

g(20) = 114

[1] requires systematic understanding of underlying principle. You can write a general solution, but you would need to compute each cases from scratch. If you need to figure out an answer for only one final length, this might be a better option.

[2], on the other hand, does not require (or require far less) understanding of logical structure. You only need to find recurrence relation from simpler / smaller cases. And you reuse answers for shorter lengths, so [2] could be your choice if you need to repeat this computations a lot of times.

I have been a type [1] person for a long time. I would have been upset at [2] since it does not conform to 'solving' a problem. It could only be called finding the answer.

But there are classes of problem you can solve only with [2]. Or type [1] approach is far less efficient. What if you have more than two types of rod, like 5 types of rods? Thus I have been making a gradual transition to (or adoption of) type [2] thinking.

Which of the two came up to you first?

PS - approach [2] is called Dynamic Programming in computer science, in that one can think of the original problem being made up of smaller problems of the same logic. In mathematics it belongs to sequence (described by recurrence relation), so you may call both approaches mathematical. Taxonomy is not the main point of this article.