## 一个算法题

input: vector > kSortedArrays
pair valueAndIndex;
vector res;

heap > minHeap;

int currentIndex[k];
memset(currentIndex, 0, sizeof(currentIndex);

for (int i = 0; i < k; i++)

while (minHeap.empty()) {
int index = heap.pop().second
res.push_back(heap.pop().first);
if (++currentIndex[index] < kSortedArrays[index])
}

return res;

## Harvard girl

My QQ Browser home page content recommendation engine gave me some news about this “Harvard girl,” who created some sensation around 1999 in China for her admission to Harvard. Her mom ended up writing and publishing some book on that that sold well.

That news article mentioned that that girl, despite her saying that she would return to 报效祖国 (contribute to the mother country), she ended staying in America and getting US citizenship. Maybe perhaps likely she also married a white guy. There was a photo of her with a white guy in it.

As for the comments, there were maybe over a thousand. The ones with the most upvotes were mostly negative from what I remember. Of course, it’s statistically speaking quite hard for Chinese to immigrate to America. For most Chinese, it’s basically a dream. I was very fortunate in that my family actually got the green card relatively quickly and smoothly, without engaging in anything that could be truly regarded as the spineless behavior that you see in many Chinese in America, though of course, in that regard, you can always do better, but that of course, depends much on your ability. Basically, there’s no guarantee that you’ll be able to stay and if you aren’t and have to return to China, you will feel like a failure, and likely your prospects back in China won’t be all that great either. To the majority of native Chinese, the attitude towards the emigrants and the emigrants-in-trial (those without the green card) is one of a combination of envy and contempt, or actually, maybe more like apathy since those people are so far removed from the majority of the Chinese population. Some native Chinese guy when I mentioned the term “banana-man” was even like, “what is that?” I guess back in the late 90s, it was much more of envy, but now it’s much more of contempt. To be fair, my attitude towards those smart but not that smart Chinese-American kids who are foreign to the Chinese language and culture is mostly one of contempt. I don’t really care much about alienating them because they don’t have any power and pretty much never will. If they really were actually really genuinely smart, they wouldn’t be that way. Even if that person has elite academic credentials, that person’s IQ can still be somewhat questioned, or more so, that person’s (and parents’) taste and judgment.

I asked this mother under age 40 in China if she knew of that Harvard girl, and she said yes. She mostly thought that that girl wasn’t terribly exceptional in talent or ability, and that at the time, information on how to get into Harvard in China was very limited, and rumor has it that some recommendation letter from this American helped. She was certainly quite lucky, but at the same time, her level of career success in America, so it seems, pretty much matches her talents. There was not all that much she could bring to China anyway.

In contrast, that mother mentioned this girl from a small place who really was exceptional at English, winning first place again and again in some competition in English public speaking in Britain. She got into Fudan with gaokao waived but because she didn’t like the major she got into that much, she entered the English department at Nanjing University. Now she’s 40 and a prominent TV news anchor in English. I asked her to send me a video and indeed her English really was exceptional. (Mine is too, but that’s another matter, and I also grew up in America so it’s not a fair comparison. It’s also not fair to compare my Chinese to those who grew up in China.) In contrast, that social climbing slut Zhang Zetian who married JD’s founder/CEO Richard Liu, her English was really meh, despite there being “Zhang Zetian English” as a search recommendation on Baidu. I believe her father who was quite rich (not ridiculously so though) had people manufacturing her image behind the scenes. I was told that her father wanted her to marry a “third generation red,” the ones who are the true elite in China as opposed to billionaires from the grassroots like Richard Liu. Rumor has it that she dated one and got dumped.

What that mother told me that really cracked me up was

Translated to English, it is

During that time, there was news of her everywhere. Her mother was really extreme. In her book, she wrote that to train her persistence, she had her grab ice blocks with her bare hands, and as a result, many braindead parents followed suit.

Like this is just absolutely fucking ridiculous. No more comment.

By the way, I also back in 2015-6 helped this Harvard girl (ethnic Chinese but not culturally Chinese at all) who won science prizes in high school prepare for coding/algorithm interviews. (I didn’t do it for free earned a little side money from that as well. I was mostly interested in meeting her at that time.) I was surprised at the gross inconsistency between her high school achievements and how little she knew about computer science as well as how slow she was to learn. Like, she kept on asking me what the difference was between a linked list and a cache. There is this interview question of simulating an LRU cache in software. I had told her that there are hardware caches as well with orders of magnitude lower latency than reading than from memory, and that really, disk -> memory -> L2 cache -> L1 cache -> register is basically a cache hierarchy. Really, caching is quite intuitively obvious. It’s like how in the home you have a small bucket for trash that you only empty to the bigger one outside when it gets full. She also couldn’t understand why quick-select was average case $O(n)$ and worst case $O(n^2)$. I explained to her that pivot operation (in quick-sort it’s the same) but she just couldn’t get it. I then told her that nobody in the fucking software or machine learning world would give a fuck about quick-select, but her reaction was one of

NOOOOOOO!!!!!! QUICKSELECT!!!!!!

What really brought me into disbelief was when she asked me for some homework problem how to compute $\int_0^{2\pi} \cos^2 x dx$ and I was like “you must be trolling.” The method I instantly thought of was using the nothing esoteric trig identity $2\cos^2 x - 1 = \cos (2x)$. It’s an obvious $1/2 \cdot 2\pi$ since the $\cos (2x)$ component is vanished by the integral by symmetry.

There is of course also noticing that by symmetry $\int_0^{2\pi} \cos^2 x dx = \int_0^{2\pi} \sin^2 x dx$. Sum the two to get $2\pi \cdot 1$ and divide by two.

I think I also told her that one can substitute $\cos x$ with $\frac{e^{ix}+e^{-ix}}{2}$, square that and integrate. Anyone who’s studied Fourier series should instantly tell that we only care about the constant coefficient, which is an obvious $2 \cdot \frac{1}{4}$.

I spoke of this case to a former Harvard PhD student from China and he was like,

Maybe she’ll eventually become director of research at Google. And write a book like Lean In.

Only then, did I learn that Lean In was some book written by Jewish Facebook exec Sheryl Sandberg who also went to Harvard. Her husband was also an exec, and my reaction to that case was basically one of

How the fuck do you die running on a treadmill. That guy must have been unusually clumsy or had some serious health problems to begin with.

## Bubble sort using IORef

I started learning Haskell around summer of 2015, and to be honest, I found it very difficult. It, as a representative of functional programming, requires a very different mode of reasoning, one that I had not really exposed myself to before. I used very light features of Haskell at a real job for testing purposes. With “very light,” IORef is obviously disqualified. I haven’t touched it for over a year, and I am quite rusty on it. Though I expect, since I had diligently worked through example code of various Haskell constructs and patterns, to the point where I could follow what was going on without much difficulty, I can retrain up to the level I had previously been at without too much difficulty.

## Tech industry, an interview question, and tail recursion

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: