Got this question at a FAANG company. Interviewer was absolutely not satisfied with linear solution and wanted it solved in log(m + n)

There's a huge meta-game around these questions that you pick up after practicing them enough.

Even without the hint, I intuitively know looking at that question that linear time is too easy for a 1 hour face to face interview at Google.

I also know that as the data is sorted the optimal solution must be logarithmic, as in these contrived problems there's no such thing as an unnecessary detail. Monotonic means binary search.

I haven't built this intuition from my experience as a software developer, but by spending my free time playing the game and grinding these arbitrary puzzles.

The fact you missed this meta, tells me absolutely nothing about your skills as a developer, only that you haven't been grinding leetcode.

That shouldn't be a signal not to hire you, but that's how the game works at FAANG.

If you can make this observation about the arrays, and code a fully functional binary search taking into account whether the total length of both arrays is odd/even, handling the out of bounds case, whilst under pressure on your third interview of the day with just the intuition you've built in your day job, then as far as i'm concerned you are the exception not the rule.

Typical day-to-day programming never requires you to find the median of two-sorted arrays, so a self-taught programmer generally has never thought about how you would tackle a problem like that, especially given the complexity requirement (O(log (m+n))) stated in that problem. If your brain immediately knows what to do when you read that problem, then you probably have a CS degree. If you have to spend 5 min thinking about the complexity notation before you even start the problem, then you probably don't have a CS degree.

And if you see that and go "do they actually say the words 'big oh' when they speak that outloud..." you're interviewing as successfully as I do!

I really appreciate your greater point. I've been given all sorts of CS problems in interviews that I don't have any background in understanding the context enough to know what to do. I changed careers from experimental physics, so my software work is essentially self taught. That doesn't mean I'm totally useless in my job or not an asset to my team or can't deliver products that generate massive revenue. But, those things are how interviewers make me feel.

But wouldn't it be exactly the hallmark of a self-taught programmer to be able to figure things out on their own? In general I don't think a programmer can expect the kind of job where they only do standard things all the time?

Merging and comparing arrays as in that task also seems like something that might actually come up in a job.

However, I take the point of the other comment that the real issue here is doing it with certain speed requirements. That does make it harder, indeed, but still doable.

Self taught programmer here. I get stuff done for the project or program I'm working on. I learn how to do what I need to do securely and automate a lot. I can figure out documentation of frameworks, libraries and random code written 10yrs ago. I can glue things together or write new code in python, golang, C, C++, shell, nim, lua, and others. I'm self taught where it matters to get my job done.

Self learning 'big O' is a waste of time and effort. Never have I needed to know it to accomplish a task beyond interviews. Don't nest six for loops, reading lines from a file into memory each loop. Got it, learnt it, can do. Next problem.

This gatekeeping attitude is bullshit.

I never used the O notation in a job, but I have seen people waste cycles. For example in the early days of ORM, I saw people load the whole table and then sort and filter in Java, rather than writing appropriate SQL queries.

Understanding Big O notation is not that difficult and everybody knows it is a common question in interviews. Analyzing specific algorithms can of course be difficult.

Absolutely - a self-taught programmer should be able to figure out how to solve that problem. All I'm saying is that it's going to take longer for the self-taught to solve it because it's not something they have thought much about before.

Having a CS degree gives you a large advantage when solving problems like this, but that advantage is markedly lower when you are trying solve typical real-world problems in the private sector.

> But wouldn't it be exactly the hallmark of a self-taught programmer to be able to figure things out on their own?

Self-taught or not, no one is able to derive an optimal solution to algorithm problems on the fly. You must have previously learnt the technique, and probably practiced applying it a lot.

I think the tricky part with that specific problem is that it asks you to do it in O(log(m+n)) complexity, so you can't even iterate through the two arrays to see all of the values -- you need to do some binary-search-like thing across both of the arrays. In O(m+n) complexity, yeah you could combine the arrays and then find the median of the combined array, which is much simpler. This is actually a great example of why those questions are so hard!

OK I missed that - that does make it harder indeed.

Also I must admit I used to enjoy such tasks more in former years, now it seems more like a needless chore. On the other hand, somehow I feel compelled to solve games like "Human Resource Machine" or "Infinifactory", which can be equally tedious.

I'll try to solve that leetcode task.

For more points, try solving it in 25 minutes without running the code (i.e. as if it were on a whiteboard), and produce an answer that you're confident doesn't have any major errors, and be able to explain why it's logarithmic time. When you're done with all that, then run it and see if it passes. If not, you fail!

Demanding code that runs is silly, I agree. I think it can be valid to see how people cope.

I was once asked to produce the proof of the theorem of Pythagoras, which I hadn't thought about for many years. I failed to do it in the interview situation and later did it at home. However, I enjoyed the interview and I was also offered the job.

Many of those simple problems are only simple once you understand the underlying techniques, and often have subtle tricks that make or break the underlying solution (for the allowed runtime / memory). I am continually amazed reading Segewick when he points out "this only takes one line here to make it all work! Seems simple, but actually took researchers years to work that out". But if you read (or use similar code) invovling that one line, you might think it easy.

A good exercise, I think, would be to ask people to implement binary search (assuming they never have before). We can all intuitively explain the algorithm, but actually getting all the code just right is a little tricky. See if it trips people up. Then ask them to do it in 20 minutes or they are fired (e.g. comparable to interview scenario).

The point of that exercise seems to me to make people implement binary search without having a solution they have learned by heart.

Well, yes but my supposition is that it will trip some people up in unexpected ways. And given a tight timeline, the results will not translate into how good of a programmer they are. IMHO it will be semi-random whether good programmers can complete the problem. And of those that can, a sub-set will have (whether they recall it or not) completed VERY similar problems in the past.

I've found a great number of "easy" problems too challenging to complete in 45 minutes. And yet once I learned the underlying techinques / DS / Algo's, many "medium" ones I can complete in 10 minutes or less, even when I have not seen that particular problem. Conversely, I was able to complete some of the harder problems in 5-10 minutes without EVER having seen the underlying algorithms before, because I actually had in real life problmes but had never drawn the connection. The more leet code I do, the more I realize when encountering a new problem, it is a complete roll of the dice if it will take me five minutes or five hours, despite being of the same level of difficulty and even same class of problem. But this is not so surprising -- this is how the history of those algorithms unfolded. Many were one line of code away from a far better runtime, and sat for years before someone cracked it.

My main take away is, algorithmic style questions can be useful to test whether candidates adequately prepared and practiced from a given set of information, and is perhaps most predictive of their level of comittment / professionalism / base-aptitude. IMHO unless you are building a novel product or charting unknown territory (rare), its far better to be experienced, prepared, and well read, than it is to be smart. Perhaps. I don't take issue with Google requiring a wide variety of expertise in such problems to get in. I do have a problem with a random set of "easy" problems and then making judgements of people afterwards. But that's just IME.