5 ms·

I must admit I don't understand how one can not be able to solve them and be able to solve other programming problems at the same time. I believe you and other

I must admit I don't understand how one can not be able to solve them and be able to solve other programming problems at the same time. I believe you and others when they claim they are good developers. I just want to point out that for many people, it can be impossible to understand how your minds work. Maybe it is a bit like dyscalculia, where some people can not comprehend "amounts". They can not calculate well, but they can actually be good in other fields of mathematics. Edit: I never did a lot of leetcode, but for reference, here is a problem they categorize as "hard": https://leetcode.com/problems/median-of-two-sorted-arrays/ https://leetcode.com/problems/median-of-two-sorted-arrays/ It requires calculating the median of an array. Is that really a kind of thing people who are otherwise good developers can not do? I must admit it really boggles my mind and makes me a bit hopeless and desperate. It seems all attempts to explain stuff to people are futile anyway, at least for some things.

jugg1es 5y ago
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.
- Cd00d 5y ago
  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.
- kkjjkgjjgg 5y ago
  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.
  - jugg1es 5y ago
    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.
  - PenguinCoder 5y ago
    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.
    - kkjjkgjjgg 5y ago
      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.
claudiulodro 5y ago
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!
- kkjjkgjjgg 5y ago
  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.
  - wan23 5y ago
    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!
    - kkjjkgjjgg 5y ago
      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.
cloverich 5y ago
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).
- kkjjkgjjgg 5y ago
  The point of that exercise seems to me to make people implement binary search without having a solution they have learned by heart.
  - cloverich 5y ago
    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.
dmw1 5y ago
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.

jugg1es 5y ago

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.

Cd00d 5y ago
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.
kkjjkgjjgg 5y ago
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.
- jugg1es 5y ago
  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.
- PenguinCoder 5y ago
  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.
  - kkjjkgjjgg 5y ago
    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.

claudiulodro 5y ago

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!

kkjjkgjjgg 5y ago
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.
- wan23 5y ago
  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!
  - kkjjkgjjgg 5y ago
    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.

cloverich 5y ago

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).

kkjjkgjjgg 5y ago
The point of that exercise seems to me to make people implement binary search without having a solution they have learned by heart.
- cloverich 5y ago
  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.

dmw1 5y ago

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.