daily #1

Sep 17, 2018

I’ve taken Kakao blind test last week. It was an online coding test that took about 5hrs long. I was shocked that I’ve missed 2 problems out of 7!

The first of the two was about reconstructing a tree given points with the $(x,y)$ coordinate, from specific rules like (a) parent has bigger $y$ coordinate than its children, and (b) the left child has smaller $x$ coordinate than its parent. I implemented it with recursion, then faced RTE(runtime error). I once thought about the stack depth, however, denied that possibility since the maximum depth of a tree was $1000$. It was a sheer misunderstanding.

Only after the test I found that Python has a very limited recursion depth($<998$). It was my first time using python in a test, it was never a problem in C++. This gave me a precious lesson using Python: never think of using recursion. I also once read about function call overhead in Python. I sought after some optimizations for function calls in Python, but hardly could find any.

The second one I missed was about parsing HTML tags. I think the hard part was counting words in the HTML file, which were in the text data, and were split by non-alphabetical characters. I continued to get WA(wrong answer) from it. In hindsight, I think I had a wrong regular expression counting words.

For counting words that were enclosed by non-alphabetical characters, I used the this regular expression.

([^A-Za-z]|\A)WORD([^A-Za-z]|\Z)

However, it was not able to count the case WORD\nWORD or WORD2WORD correctly. It is because the first match actually consumes \n with the pattern [^A-Za-z]|\Z, so that the next word cannot take the match for another [^A-Za-z]|\A.. Sigh. I am thinking about the correct version, but I think it needs some research. (Actually, it’s said that this kind of thing is what RE is NOT good at.)

Nah, I found it. This works.

(?<![A-Za-z])WORD(?![A-Za-z])

It uses lookbehind((?<!sth)) and lookahead((?!sth)) assertions to check if the word was not enclosed by alphabets. You can see the detail here. These lookaround assertions do not consume any character so it rocks.

To be honest, I seriously thought it would be a piece of cake (like qualification rounds in Google Codejam). So I had a plan to use all the 7 languages (C++, Java, Python2, Python3, JavaScript, Swift, and Kotlin) to solve 7 problems. After spending 2 hours trying to solve problem 2 and 3 in Javascript and Swift each, I discovered I messed it up .