43 ms·

Tell HN: OpenAI can solve Leetcode problems

55 points by autotune 4y ago

I gave OpenAI the following LC prompt: https://leetcode.com/problems/determine-if-two-strings-are-close https://gist.github.com/autotune/e6345fab54f6acab0ba95c45ec15f22a#file-openai_test_prompt-txt It returned the following result that matched 3/3 test cases: https://gist.github.com/autotune/e6345fab54f6acab0ba95c45ec15f22a#file-openai_test_result-txt I didn't even have to do any manual formatting, it just generated the solution right where it needed to. Now that LC has been automated can we move onto trying something else in the standard software dev interview process?

aaek9 4y ago
Can you write a cover letter to become chief marketing manger at car wash
DonsDiscountGas 4y ago
I've tried a few easy-levels and it passed them all. I tried one medium and it completely failed. I especially liked its solution for two sum; first it gave the O(N^2) solution and then it gave the O(N) solution. With good explanations for both.
wizofaus 4y ago
I gave it a similar example that happened to be a function I needed to write recently (case-insensitive substring replacement, which is missing from the version of .NET framework I was stuck with), and the solution it gave looked superficially correct too (and very similar to what I wrote), except it actually lower-cased everything, which I wouldn't consider correct. I just had to re-prompt "now without using ToLower", and it gave the correct solution though. I haven't tried co-pilot yet, but it would be curious to see how similar they are. I then asked it to give me a class to convert a Stream to a seekable Stream (something else I needed to do recently), and again, pretty impressed with the result (though I needed to avoid using MemoryStream so it could work with potentially huge streams, I tried to explain that but the solution didn't look right at all - basically the only way you can do it is by storing the data on disk).
DenisM 4y ago
There’s no limit to what you can do when testing your model on the training dataset.
b20000 4y ago
thanks, since AI is not capable of generating novel/unique output itself yet without training, but can only learn to remix and transform what is already there, it makes sense that it would do well on leetcode. this implies that hiring people via leetcode interviews will result in staff who can only copy paste and remix standard solutions they have been trained on and are incapable of being creative and generating completely new or unorthodox solutions. the latter is what most companies need, but don’t know yet they need. leetcode was the wet dream of executives. a standard factory like process to produce more code drones in a cheap and efficient way. the next wet dream is replacing them with AI. they forget that software development is a creative process.
- nicholasjarnold 4y ago
  > they forget that software development is a creative process Exactly. Very few executives have read Hackers & Painters [0], from what I've been able to anecdotally personally gather. Nobody (almost) should be fearful that low-code solutions and/or AI will replace their livelihood yet. [0] - http://www.paulgraham.com/hackpaint.html http://www.paulgraham.com/hackpaint.html
- GaggiX 4y ago
  >thanks, since AI is not capable of generating novel/unique output itself yet without training, but can only learn to remix and transform what is already there, it makes sense that it would do well on leetcode. I guess you're implying that this doesn't happen with humans as well, although if you give a pen to an infant or a man who has always lived in a cave he's not going to draw anything meaningful like an untrained AI, I have the opinion that everything is derivative.
samvher 4y ago
It could be that it was trained on leetcode content? I.e. that it has seen this problem more or less verbatim. Any information on whether that would be the case? I'm not so familiar with what OpenAI do and don't use for training.
tmaly 4y ago
GPT-4 might be able to handle it. All we need now is a pocket AI device out of one of William Gibson's novels paired to a neurallink and one can solve the hardest interview questions.
heurist 4y ago
It solves easy problems and gets nowhere close on hard problems. But I'm sure that's coming.
- sayogo1227 4y ago
  Here is what I tried for (https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ https://leetcode.com/problems/longest-increasing-path-in-a-m...) INPUT: Given an m x n integers matrix, return the length of the longest increasing path in matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed). Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9]. class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: ChatGPT: if not matrix or not matrix[0]: return 0 # initialize the 2D array with all zeros dp = [[0] * len(matrix[0]) for _ in range(len(matrix))] # initialize the result with 0 result = 0 # iterate through each cell in the matrix for i in range(len(matrix)): for j in range(len(matrix[0])): # perform DFS starting from the current cell result = max(result, self.dfs(matrix, dp, i, j)) # return the result return result # helper function to perform DFS def dfs(self, matrix, dp, i, j): # if the path length is already calculated, return it if dp[i][j] > 0: return dp[i][j] # initialize the path length with 1 path_len = 1 # check the adjacent cells for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: # get the coordinates of the adjacent cell x, y = i + dx, j + dy # check if the adjacent cell is valid if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]): # check if the adjacent cell has a smaller value if matrix[x][y] > matrix[i][j]: # perform DFS on the adjacent cell and update the path length path_len = max(path_len, 1 + self.dfs(matrix, dp, x, y)) # store the path length in the 2D array dp[i][j] = path_len # return the path length return path_len
  - DenisM 4y ago
    Have you tried submitting it?
going_ham 4y ago
Dear executives, You have AI that is capable of solving your interview questions. These questions were designed to select the best candidates. Now you have AI that is cheaper and faster. Please, fire your engineers and embrace the next generation of programming. Why would you need engineer when a bot will do it for you? After all, your candidates suck at leetcode interview.
- paulcole 4y ago
  > These questions were designed to select the best candidates I’d reconsider this assumption. My assumption is also wrong but in a different way. I think these questions were designed to (in no particular order): • Identify hirable candidates • Be very scalable and allow for the interviewing, rejection, and acceptance of hundreds/thousands of candidates • Determine who would put the work in to pass this sort of screening
- jstx1 4y ago
  Dear candidate, What's even cheaper and faster than the AI solution is for us to look up the answer in our own database. It turns out that we already know the answers to all the questions we ask in interviews. We're afraid that you've completely misunderstood that goals of our interviewing process.
  - spoils19 4y ago
    What are the goals then?
- hcks 4y ago
  Im sorry you still can’t code a medium leetcode after all these years
- riku_iki 4y ago
  > These questions were designed to select the best candidates. more like do initial screening and filter out garbage candidates?
teraflop 4y ago
This code superficially resembles a correct solution, but it is not correct, and if it passes, it's only because the test cases for this problem are woefully sparse. (EDIT: I tried actually submitting it, and it doesn't pass Leetcode's tests, so I'm not sure what OP was talking about.) For example, the correct answer for closeStrings("aabbcc", "abbbcc") is false, but this solution incorrectly returns true. In addition, it has O(n^3) time complexity and may take a very long time to run. Try closeStrings("a"*1000+"b", "a"*1000+"c"), and then consider that the problem statement allows each string to be up to 100,000 characters in length.
- b20000 4y ago
  that doesn’t really matter. leetcode interviews are about producing the solution the interviewer expects.
  - dogbox 4y ago
    What kind of interviewer expects a solution that's not only incorrect, but also woefully inefficient?
    - actually_a_dog 4y ago
      Nobody expects that, obviously, but such solutions do occasionally get accepted (by humans). Beyond a certain basic level of competency, a lot of interviews, including LC-based ones, are about how good the candidate is at story telling and/or explaining their thought process.
  - teraflop 4y ago
    So you're saying the interviewer expects a wrong solution, and the wrong solution they expect is the same wrong one the AI generates (which happens to be twice as long as the correct version), and the interviewer doesn't bother to run the tests?
    - whimsicalism 4y ago
tarr11 4y ago
The kind of work solved by leetcode will be solved by AI. Testing for it interviews in a few years will make no more sense than testing for people to generate optimized machine code. (Unless you are a super specialized systems developer who actually writes such things) This will enable engineers to focus on higher order problems, similar to how compilers and programming languages allowed engineers to be more productive than having to write assembly. The way that this play out for software development is we may include gpt prompts to our code repositories and treating them as library functions or macros which could be compiled as regular code, or interpreted at runtime.
jstx1 4y ago
It's cool if it can really do it (as opposed to spitting out wrong solutions that look plausible at a glance) but I don't think it's a good argument against LC interviews. The point is that they're testing your understanding of general CS concepts and how you communicate about code, a language model being able to solve these problems doesn't really change any of this. It's not like the company cares about your actual solution, they already know what the solution is.
- autotune 4y ago
  >It's not like the company cares about your actual solution Every time I have ever been tested in any kind of interview, they 100 percent care more about the solution than how to get there. Some of the honest ones have admitted it, some of the others have pretended they don't to try and make you feel better about not reaching it in time. I have never passed an interview with a live coding round, especially one involving leetcode, where they were fine with me not having reached a solution in the 10, 35, or 45 minute time window given.
  - jstx1 4y ago
    I think I phrased it in a confusing way. They care about your solution in the sense that they want to know if/how you'll solve the problem. They don't care in the sense that they aren't trying to learn the answer by interviewing you. It's not like they have a critical red-black tree problem and they called you in to fix things for them. They know the solution so the existence of an additional out-of-interview way to get to the solution like a language model doesn't change anything about the usefulness of the interview.
yakkityyak 4y ago
We've basically just automated copying and pasting stack overflow answers.
- Workaccount2 4y ago
  As opposed to manually doing it now.
  - DonsDiscountGas 4y ago
    ChatGPT has a wayyyyy nicer interface than SO.
bugfix-66 4y ago
It was trained on numerous Leetcode solutions (question/answer), which you can find on GitHub. People are proud of their Leetcode efforts: they post their solutions, as if it is an achievement. Now tell me, how many of the BUGFIX-66 problems can it solve? https://BUGFIX-66.com https://BUGFIX-66.com Copilot can solve a few of the simple ones at the beginning (simple matrix multiplication, simple radix sort, etc., that appear often in the training data, and some of the harder ones whose solution appears on GitHub, e.g., the uncorrected prediction/correction compressor/decompressor whose solutions were front-page on Hacker News). But as you go down the list, into material outside the training set, the language model won't be able to solve it. Try it. Paste the tile, the introductory text, and the unfixed code, and see whether the omnipotent AI can solve these (quite straightforward) problems. For how many does it need the hint?
- kapsi 4y ago
  Let me check in a year
frontman1988 4y ago
It's basically ingested the question and the answer. Won't be able to solve a new question, or just changing the language of the question fools the AI. Example it's not trained on codeforces programming competetion website and fails to solve most of the problems like these: https://codeforces.com/contest/1672/problem/D https://codeforces.com/contest/1672/problem/D Leetcode is a hazing ritual and it doesn't matter if AI excels in it, what matters is if human programmers are able to 'perform' in front of an interviewer. So leetcode is here to stay, otherwise you will have these competetive programming problems replacing them and turn interviewing into an even bigger nightmare.
DenisM 4y ago
As time goes more content on the internet will be produced by these models, and eventually these models will be learning from each other rather than from humans. That kind of snake eating its own tail will likely accumulate errors over time, and eventually the internet will be just chaos.
- jstx1 4y ago
  Wouldn't it be more converging to a bad average of everything instead of being chaos?
  - DenisM 4y ago
    It’s not obvious to me. It might degenerate into an alphabet soup, or it might stabilize around something higher level. I guess it’s on the same spectrum.

55 points by autotune 4y ago

aaek9 4y ago

Can you write a cover letter to become chief marketing manger at car wash

DonsDiscountGas 4y ago

I've tried a few easy-levels and it passed them all. I tried one medium and it completely failed. I especially liked its solution for two sum; first it gave the O(N^2) solution and then it gave the O(N) solution. With good explanations for both.

wizofaus 4y ago

I gave it a similar example that happened to be a function I needed to write recently (case-insensitive substring replacement, which is missing from the version of .NET framework I was stuck with), and the solution it gave looked superficially correct too (and very similar to what I wrote), except it actually lower-cased everything, which I wouldn't consider correct. I just had to re-prompt "now without using ToLower", and it gave the correct solution though. I haven't tried co-pilot yet, but it would be curious to see how similar they are. I then asked it to give me a class to convert a Stream to a seekable Stream (something else I needed to do recently), and again, pretty impressed with the result (though I needed to avoid using MemoryStream so it could work with potentially huge streams, I tried to explain that but the solution didn't look right at all - basically the only way you can do it is by storing the data on disk).

DenisM 4y ago

There’s no limit to what you can do when testing your model on the training dataset.

b20000 4y ago

thanks, since AI is not capable of generating novel/unique output itself yet without training, but can only learn to remix and transform what is already there, it makes sense that it would do well on leetcode. this implies that hiring people via leetcode interviews will result in staff who can only copy paste and remix standard solutions they have been trained on and are incapable of being creative and generating completely new or unorthodox solutions. the latter is what most companies need, but don’t know yet they need. leetcode was the wet dream of executives. a standard factory like process to produce more code drones in a cheap and efficient way. the next wet dream is replacing them with AI. they forget that software development is a creative process.

nicholasjarnold 4y ago
> they forget that software development is a creative process Exactly. Very few executives have read Hackers & Painters [0], from what I've been able to anecdotally personally gather. Nobody (almost) should be fearful that low-code solutions and/or AI will replace their livelihood yet. [0] - http://www.paulgraham.com/hackpaint.html http://www.paulgraham.com/hackpaint.html
GaggiX 4y ago
>thanks, since AI is not capable of generating novel/unique output itself yet without training, but can only learn to remix and transform what is already there, it makes sense that it would do well on leetcode. I guess you're implying that this doesn't happen with humans as well, although if you give a pen to an infant or a man who has always lived in a cave he's not going to draw anything meaningful like an untrained AI, I have the opinion that everything is derivative.

samvher 4y ago

It could be that it was trained on leetcode content? I.e. that it has seen this problem more or less verbatim. Any information on whether that would be the case? I'm not so familiar with what OpenAI do and don't use for training.

tmaly 4y ago

GPT-4 might be able to handle it. All we need now is a pocket AI device out of one of William Gibson's novels paired to a neurallink and one can solve the hardest interview questions.

heurist 4y ago

It solves easy problems and gets nowhere close on hard problems. But I'm sure that's coming.

sayogo1227 4y ago
Here is what I tried for (https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ https://leetcode.com/problems/longest-increasing-path-in-a-m...) INPUT: Given an m x n integers matrix, return the length of the longest increasing path in matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed). Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9]. class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: ChatGPT: if not matrix or not matrix[0]: return 0 # initialize the 2D array with all zeros dp = [[0] * len(matrix[0]) for _ in range(len(matrix))] # initialize the result with 0 result = 0 # iterate through each cell in the matrix for i in range(len(matrix)): for j in range(len(matrix[0])): # perform DFS starting from the current cell result = max(result, self.dfs(matrix, dp, i, j)) # return the result return result # helper function to perform DFS def dfs(self, matrix, dp, i, j): # if the path length is already calculated, return it if dp[i][j] > 0: return dp[i][j] # initialize the path length with 1 path_len = 1 # check the adjacent cells for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: # get the coordinates of the adjacent cell x, y = i + dx, j + dy # check if the adjacent cell is valid if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]): # check if the adjacent cell has a smaller value if matrix[x][y] > matrix[i][j]: # perform DFS on the adjacent cell and update the path length path_len = max(path_len, 1 + self.dfs(matrix, dp, x, y)) # store the path length in the 2D array dp[i][j] = path_len # return the path length return path_len
- DenisM 4y ago
  Have you tried submitting it?

going_ham 4y ago

Dear executives, You have AI that is capable of solving your interview questions. These questions were designed to select the best candidates. Now you have AI that is cheaper and faster. Please, fire your engineers and embrace the next generation of programming. Why would you need engineer when a bot will do it for you? After all, your candidates suck at leetcode interview.

paulcole 4y ago
> These questions were designed to select the best candidates I’d reconsider this assumption. My assumption is also wrong but in a different way. I think these questions were designed to (in no particular order): • Identify hirable candidates • Be very scalable and allow for the interviewing, rejection, and acceptance of hundreds/thousands of candidates • Determine who would put the work in to pass this sort of screening
jstx1 4y ago
Dear candidate, What's even cheaper and faster than the AI solution is for us to look up the answer in our own database. It turns out that we already know the answers to all the questions we ask in interviews. We're afraid that you've completely misunderstood that goals of our interviewing process.
- spoils19 4y ago
  What are the goals then?
hcks 4y ago
Im sorry you still can’t code a medium leetcode after all these years
riku_iki 4y ago
> These questions were designed to select the best candidates. more like do initial screening and filter out garbage candidates?

teraflop 4y ago

This code superficially resembles a correct solution, but it is not correct, and if it passes, it's only because the test cases for this problem are woefully sparse. (EDIT: I tried actually submitting it, and it doesn't pass Leetcode's tests, so I'm not sure what OP was talking about.) For example, the correct answer for closeStrings("aabbcc", "abbbcc") is false, but this solution incorrectly returns true. In addition, it has O(n^3) time complexity and may take a very long time to run. Try closeStrings("a"*1000+"b", "a"*1000+"c"), and then consider that the problem statement allows each string to be up to 100,000 characters in length.

b20000 4y ago
that doesn’t really matter. leetcode interviews are about producing the solution the interviewer expects.
- dogbox 4y ago
  What kind of interviewer expects a solution that's not only incorrect, but also woefully inefficient?
  - actually_a_dog 4y ago
    Nobody expects that, obviously, but such solutions do occasionally get accepted (by humans). Beyond a certain basic level of competency, a lot of interviews, including LC-based ones, are about how good the candidate is at story telling and/or explaining their thought process.
- teraflop 4y ago
  So you're saying the interviewer expects a wrong solution, and the wrong solution they expect is the same wrong one the AI generates (which happens to be twice as long as the correct version), and the interviewer doesn't bother to run the tests?
  - whimsicalism 4y ago

tarr11 4y ago

The kind of work solved by leetcode will be solved by AI. Testing for it interviews in a few years will make no more sense than testing for people to generate optimized machine code. (Unless you are a super specialized systems developer who actually writes such things) This will enable engineers to focus on higher order problems, similar to how compilers and programming languages allowed engineers to be more productive than having to write assembly. The way that this play out for software development is we may include gpt prompts to our code repositories and treating them as library functions or macros which could be compiled as regular code, or interpreted at runtime.

jstx1 4y ago

It's cool if it can really do it (as opposed to spitting out wrong solutions that look plausible at a glance) but I don't think it's a good argument against LC interviews. The point is that they're testing your understanding of general CS concepts and how you communicate about code, a language model being able to solve these problems doesn't really change any of this. It's not like the company cares about your actual solution, they already know what the solution is.

autotune 4y ago
>It's not like the company cares about your actual solution Every time I have ever been tested in any kind of interview, they 100 percent care more about the solution than how to get there. Some of the honest ones have admitted it, some of the others have pretended they don't to try and make you feel better about not reaching it in time. I have never passed an interview with a live coding round, especially one involving leetcode, where they were fine with me not having reached a solution in the 10, 35, or 45 minute time window given.
- jstx1 4y ago
  I think I phrased it in a confusing way. They care about your solution in the sense that they want to know if/how you'll solve the problem. They don't care in the sense that they aren't trying to learn the answer by interviewing you. It's not like they have a critical red-black tree problem and they called you in to fix things for them. They know the solution so the existence of an additional out-of-interview way to get to the solution like a language model doesn't change anything about the usefulness of the interview.

yakkityyak 4y ago

We've basically just automated copying and pasting stack overflow answers.

Workaccount2 4y ago
As opposed to manually doing it now.
- DonsDiscountGas 4y ago
  ChatGPT has a wayyyyy nicer interface than SO.

bugfix-66 4y ago

It was trained on numerous Leetcode solutions (question/answer), which you can find on GitHub. People are proud of their Leetcode efforts: they post their solutions, as if it is an achievement. Now tell me, how many of the BUGFIX-66 problems can it solve? https://BUGFIX-66.com https://BUGFIX-66.com Copilot can solve a few of the simple ones at the beginning (simple matrix multiplication, simple radix sort, etc., that appear often in the training data, and some of the harder ones whose solution appears on GitHub, e.g., the uncorrected prediction/correction compressor/decompressor whose solutions were front-page on Hacker News). But as you go down the list, into material outside the training set, the language model won't be able to solve it. Try it. Paste the tile, the introductory text, and the unfixed code, and see whether the omnipotent AI can solve these (quite straightforward) problems. For how many does it need the hint?

kapsi 4y ago
Let me check in a year

frontman1988 4y ago

It's basically ingested the question and the answer. Won't be able to solve a new question, or just changing the language of the question fools the AI. Example it's not trained on codeforces programming competetion website and fails to solve most of the problems like these: https://codeforces.com/contest/1672/problem/D https://codeforces.com/contest/1672/problem/D Leetcode is a hazing ritual and it doesn't matter if AI excels in it, what matters is if human programmers are able to 'perform' in front of an interviewer. So leetcode is here to stay, otherwise you will have these competetive programming problems replacing them and turn interviewing into an even bigger nightmare.

DenisM 4y ago

As time goes more content on the internet will be produced by these models, and eventually these models will be learning from each other rather than from humans. That kind of snake eating its own tail will likely accumulate errors over time, and eventually the internet will be just chaos.

jstx1 4y ago
Wouldn't it be more converging to a bad average of everything instead of being chaos?
- DenisM 4y ago
  It’s not obvious to me. It might degenerate into an alphabet soup, or it might stabilize around something higher level. I guess it’s on the same spectrum.