The SQL questions can also be a symptom of the type of job - Facebook's first data science round focuses a lot on SQL but that's because it's a very product/analytics/decision-making focused role without that much coding or ML. With data science you have to be more careful about these things when searching for a job; you can't just use the job title as a descriptor.
I think that's changed a bit over time and the term has expanded to mean more things. In addition to Facebook, another great example is this article from Lyft in 2018 where they say that they're renaming all their data analysts to data scientists and all their data scientists to research scientists - https://medium.com/@chamandy/whats-in-a-name-ce42f419d16c
Like the hilarious thing about Facebook and Data Science is that the term was invented there, and they needed to retitle all of their analysts (like Product Data Science) as they couldn't hire any analytical people with an analyst title in SV (or so I have been told).
Like, data science was defined back in the days as a social science PhD who could run experiments and write MapReduce jobs. I'm pretty sure that most people would disagree with this definition these days.
It's a different story when a) your mind is set on statistics/linear algebra b) you've never had to actually implement binary search by hand since college and c) even if you do implement the algorithm and demonstrate that you have a general understanding, it must work perfectly and pass test cases otherwise it doesn't count.
FWIW I was rarely asked about algorithmic complexity which is more relevant in DS/ML, albeit it's usually in the context of whiteboarding another algorithm and the interviewer mocking me for doing it in O(n) instead of O(logn).
I like this formulation for finding the first index in a half-open range where p is true, assuming p stays true thereafter:
bsearch p i j :=
i if i == j else
bsearch p i m if p m else
bsearch p (m + 1) j
where m := i + (j - i)//2
def bsearch(p, i, j):
m = i + (j - i) // 2
return (i if i == j
else bsearch(p, i, m) if p(m)
else bsearch(p, m+1, j))
(Correction: I said a[m] <= k. This formulation is less tricky than the usual ones, but it's still tricky!)
That's the problem. There are many other ways to do that without risking false negatives and annoying potential candidates (e.g. I would not reapply to places that have rejected me due to skepticism about my programming abilities and using tests blatantly irrelevant to day-to-day work because it's a bad indication of the engineering culture).
Even FizzBuzz is better at accomplishing that task.
If you want a correct program without a compiler/computer I don't think anything is too easy. Maybe like, "make a function returning the sum of two float parameters".
To a certain extent you can dispense with mental logic by using a compiler. But the feedback loop is much slower. Thinking your logic through before feeding it to a compiler is like looking at a map when you're driving a car; you can cut off whole branches of exploration.
Binary search is a particularly tricky logic problem in part because it's so deceptively simple. In a continuous domain it's easy to get right, but the discrete domain introduces three or four boundary cases you can easily get wrong.
But the great-great-grandparent is surely correct that many programming jobs don't require that level of thinking about program logic. Many that do, it's because the codebase is shitty, not because they're working in an inherently mentally challenging domain.
Concerning binary search I acctually implemented that in an ECU for message sorting. It took like a whole day, including getting the outer boundries one off too big in the first test run. Funnely enough the vehicle ran fine anyway.
I would never pull that algorithm off correctly in an interview without training to, I think.
In my case, I typically got the "implement binary search" questions in a technical interview after I passed a take-home exam, which just makes me extra annoyed.
If you're gaming the take-home exam by looking up the answer on Stack Overflow, you could game the same exam in person by reading books of interview questions ahead of time, and the interviewer can avoid that by making up new questions. (OTOH if you're gaming the take-home exam by paying someone else to solve the problem for you, that might be harder to tell.)
In most cases the right way to do a binary search is not to copy and paste a binary search implementation from Stack Overflow (https://stackoverflow.com/a/41956372 is similar to the formulation I gave above), but to call a binary-search library function. If calling a library function isn't the solution the interviewer is looking for, probably they wouldn't be satisfied with you searching for it on Stack Overflow either.