Sheng Li (gmachine1729) wrote,
Sheng Li

Tech industry, an interview question, and tail recursion

Originally published at 狗和留美者不得入内. You can comment here or there.

I have written on here before that I sort of disliked the tech industry. Why? Because I felt many of the people there are kind of boring and not that smart, and much of the work is quite mundane, though of course there are some extremely good ones who do the bulk of the technical heavy lifting (I’m not, though maybe I could become one), who are grossly under compensated relative to their actual contribution. Of course, my standards must be way too high, or I must be way too weird or non-conformist, or too spoiled. At the very least, the tech industry pays quite well, especially the big companies which offer bonus and equity. Of course, plenty of 150+ IQ people will go into grad school in math or physics or computer science, doing some much more academically involved work, often with contempt for the intellectual lightweights in the tech industry. I plead guilty to having had that sort of attitude as well, and maybe I still do. Related to that is how I found the whole artificial marketing and inflation of achievement in tech kind of disingenuous. However, I’ve figured out by now that one only has much to lose from not playing along in that game. I’ve been paying more attention to LinkedIn recently. It’s literally a credentialist cesspool of professional posturing, full of mediocrities who put on there literally every detail of their professional and extracurricular life. My having become more accepting of that indicates somewhat that I’ve improved attitude-wise. I feel like I talk to some non-techs too now, in a normal way, without expressing any sign of contempt, because what’s the point? My next step would probably be to shut down this socially unacceptably nerdy and elitist and non-PC blog, but unfortunately, I don’t feel comfortable dulling myself out like that. Of course, it might just be that the whole career game more or less compels me to do so sooner or later. When I say this, I have in mind the following from Michael O Church’s essay Does Genius Exist:

Most gifted children seem like they might achieve creative excellence in adulthood; very few actually do. I’ve observed the careers of extremely intelligent (i.e., IQ 160+) people and the results are, at best, disappointing. About half go to graduate school; the other half go to Wall Street or Silicon Valley straight out of college. Either way, they expect to defeat the morons in business handily, retire within ten years, and dedicate the remainders of their lives to intellectual pursuits. It almost never works out that way. It’s not uncommon for highly intelligent people to be mobbed and bullied in their corporate jobs by resentful mediocrities, although even more common is for them to disappear into the bland, beige fog, and to lose every element of originality they once had. Most often, they disappear somewhere in the folds of middle management, and do what they can to hide what they once were.

I already feel more comfortable doing what, according to this, is most often done by the gifted later in life, not that I am +4 sigma above the mean, which is evident from my credentials, though +3 sigma sounds about right. Surely, success in the corporate world relies much on being liked by those in power which requires being conformist, loyal (or at least appearing so), dependable, and not threatening to the interests above. You get promoted by becoming the manager’s favorite, which is done by being the one who supports the career of the manager the most in an indispensable way.

I don’t like much the whole interview process in tech. It’s like the problems are so trivial (they are artificial and not all that related to real engineering) and some of the interviewers are nowhere near as smart as me, IQ-wise. Well, it doesn’t matter, because one has to adapt to one’s world instead of the other way round. And like it or not, for those on the tail end, the distribution of IQ/ability in the world is what it is today.

Speaking of tech interviews, I was asked this question in a recent interview.

Flatten a list. The list, of course, can have list elements. So something like
flatten([1,2,3,[10,30]]) => [1,2,3,10,30]

I had done this problem before. There is the brute force recursion solution. In Python, which is a dynamically typed language (which is more or less necessary for this problem (because otherwise, one would have to impose some type constraints and on top of that find a way to make nested lists work within a static type system, which as far as I can tell, would require defining some generic sum type of primitive types and the list type of that generic sum type itself), this would be, in functional style

def flatten(l):
  return [l] if type(l) != list else sum(map(flatten, l), [])

Of course, in the actual interview, I wrote it imperative style, to increase my chance of passing it. 😉

This is of course actually inefficient, in that there will be a copy made at each level of the recursion. To avoid that, we employ a helper function.

def traverse(acc, l):
  if type(l) != list:
    for e in l:
      traverse(acc, e)

The flatten function itself would be

def flatten(l):
  acc = []
  traverse(acc, l)
  return acc

By essentially preallocating the space for the output flattened list and appending to it via traversal, we use constant memory aside from the linear for the returned flattened list itself.

What did this problem remind me of? Tail recursion. Functional languages support it to avoid adding a new stack frame on each recursive call, which would be very handy for this problem. In fact, the traverse function, in its pattern of implementation can be translated to a tail recursive one in a functional language. We’ll leave that for later.

To start, we’ll present a canonical example of tail recursion, the factorial function. In Haskell, the immediate implementation it would be

factorial :: Int -> Int
factorial n = if n <= 0 then 1 else n * factorial (n-1)

In assembly, we would have something like

        # create new stack frame
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $16, %rsp
        # copy parameter to stack
        movl    %edi, -4(%rbp)
        # compare parameter with 0
        cmpl    $0, -4(%rbp)
        # the recursive case
        jg      .L2
        # the base case, set 1 as return value and return
        movl    $1, %eax
        jmp     .L3
        # set argument in recursive call to current argument minus one
        movl    -4(%rbp), %eax
        subl    $1, %eax
        movl    %eax, %edi
        call    _Z9factoriali
        # set return value to n * factorial(n-1)
        imull   -4(%rbp), %eax

One can see explicitly in the assembly the adding of a new stack frame for the recursive call. To avoid that, we employ tail recursion as follows.

factorialTail :: Int -> Int -> Int
factorialTail acc n = if n <= 0 then acc
                      else factorialTail (acc*n) (n-1)
factorial = factorialTail 1

In assembly, this would be

        # move acc to %edi
        movl    %edi, %eax
        # bitwise AND of %esi with %esi itself is %esi, set SF, ZF, PF flags accordingly
        testl   %esi, %esi
        # return if sign flag (SF) or zero flag (ZF) are on
        jle     .L5
        # acc *= n
        imull   %esi, %eax
        # n -= 1, subl also sets zero flag 
        subl    $1, %esi
        # loop back if zero flag is not set, return once n == 0
        jne     .L2

Notice how this is essentially a for loop, with no recursive calls. With the -O2 flag set on x86-64 gcc 8.1, which I used to generate the above assembly code, with my own comments later added, the tail recursion compiler optimization was implemented, as evidenced by the assembly produced. I ran this not on my own machine, but on the cloud via the handy compiler explorer I found, the code of which happens to be on GitHub. And I can only say that the guy who created this tool looks like another one of those uber prolific programmers blessed with tremendous instinct and power for building software systems. You might think that my writing a blog post with Haskell and x86 leans me towards this category as well. Oppositely, I actually think that I’m quite pathetically weak at computer stuff (and started off very unnatural at it), though I also believe that with some dedicated practice I can become good. I would say that I was natural with mathematics and algorithms but not with engineering or systems, though surely, with quite a lot of exposure, I developed, slowly, a sense for the latter as well, gradually steering what had been a horrendously off intuition towards the right direction, and concurrently, reducing, stage by stage, the sense of awe and intimidation I had felt with respect to the actual natural hackers. I can at least console myself by thinking that much of my awe’s having transformed into some sense of normalized (mentally) understanding is an indicator of rapid progress. Yes, there are still plenty of people way better than I am, but I no longer feel like what they are doing, their thought progress, cannot even be understood by my weakling brain, that once perceived it as some form of otherworldly wizardry beyond my comprehension, and of course, its actor some form of higher being.

On quite another domain, I felt somewhat similarly with regard to those at the top of the socioeconomic and political hierarchy. The default for corporate executives and those officially at the top is one of reverence. People assume that because they are on the top, they must be inherently superior in some way or another in their ability. Programmers, as status-insensitive, socially clueless aspies, are supposed to be largely oblivious to the political machinations orchestrated by those on top, to what is the reality of their (subordinate) position within the whole hierarchy. In any case, those people felt to me to be in a whole other world, similar to the impression I had of these elite programmers; I was much oblivious to that world and also could care less about it. Until I more or less developed, as far as I tell, a more accurate intuition for how that world works as well, much aided, of course, by experience, mostly indirect, but enough for me to, with my intelligence and independent judgment, construct what I believe is a reasonable picture or model for what actually goes on, one which I expect to be enhanced over time with more data collected. I’ve increasingly grown to realize, over time, that people are very much naturally psychologically chained to the reality of their official position, their formal credentials, which are correlated very imperfectly with actual ability, or in some cases loaded on (largely born) social position and artificial perception, even nil or negatively correlated; it takes an independent mind, a revolutionary mind to break free from that by disentangling the real and the artificial. And becoming mentally free is the first step towards becoming actually free.

Tags: algorithms, functional programming, haskell, 互联网行业, 编程, 面试

  • Disqus comment search service released!

    Originally published at 狗和留美者不得入内. You can comment here or there. THIS HAS BEEN UPDATED. SEE…

  • Ron Maimon on Disqus

    Originally published at 狗和留美者不得入内. You can comment here or there. I used my Disqus comment search to get all of Ron Maimon’s comments on…

  • Found my Disqus search on Google

    Originally published at 狗和留美者不得入内. You can comment here or there. On the third or second or seventh page. I think I was a bit harsh on them lol.…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened