5 ms·

Is it good at algos? From interviews: Implement queue that supports three methods: * push * pop * peek(i) peek returns element by its index. All three met

Is it good at algos? From interviews: Implement queue that supports three methods: * push * pop * peek(i) peek returns element by its index. All three methods should have O(1) complexity [write code in Ruby]. ChatGPT wasn't able to solve that last time I tried https://twitter.com/romanpushkin/status/1617037136364199938 https://twitter.com/romanpushkin/status/1617037136364199938

voxl 3y ago
in what world is a hashtable lookup worst case O(1)? Your own solution doesn't match your requirements. If you want amortized complexity then a simple vector suffices.
- RomanPushkin 3y ago
  1. I like toxic comments like that saying something is simple without actually solving the problem, you're the best. 2. The average complexity to search, insert, and delete data in a hash table is O(1), for interviews it works 99% of the time. 3. There is alternative O(1) solution you're looking for, I'll leave this exercise to you, bro. As well as the other exercise of being less toxic and a bit more respectful to people you don't know online lol.
  - Mystery-Machine 3y ago
    Average and big-O notation don't go together... Yes, it works 99% of the time, but parent explained to you why you won't get that 1% of the offers. That, plus taking offence by his comment, which makes you not pass behavioral part of the interview.
    - RomanPushkin 3y ago
      > which makes you not pass behavioral part of the interview I'm okay not getting 1% of the offers. I'm not $100 bill so everyone likes me. I appreciate an attempt to educate me though, I wanted to make clear that any discussion like that is useless without solution to a problem. Post your solution, we'll discuss downsides. You can see it from my side, and I have another one. The parent commenter ain't got no solution, but keeps insisting he can implement that easily with this and that... Good luck passing interviews with that attitude...
  - voxl 3y ago
    Pointing out a mistake is toxicity? Your ego is off the charts. Also, I gave you a solution that would probably be _better_ than yours in 99% of scenarios, a simple vector from any standard library, std::vector in C++, and Vec in Rust. This solution gives you O(1) worst case for peek, and amortized worst case O(1) for the other operations. To be actually toxic for a moment, you do know that amortized and average are different right? There is an easy solution to get O(1) for all operations too by allowing them to throw an exception: a simple array. There is no other O(1) solution for all operations that I am aware. In fact it is probably not too difficult to prove that such a solution does not exist.
    - RomanPushkin 3y ago
      If your interviewer is asking for solution and you keep insisting that "I have you a solution"... without actual code... Also saying my ego is off the charts. Good luck passing interviews with that attitude.
anotherpaulg 3y ago
I tried using aider to work with GPT-4 on this problem. Initially it went for a solution based on `shift`. But when challenged, it realized that shift was O(n) and was able to come up with a dual stack solution. It considers this solution O(1) when amortized over many operations. I don't know ruby well, so I can't verify that. https://aider.chat/share/?mdurl=https://gist.github.com/paul-gauthier/e3f32d84b9bbc592731bcb9db50f035d https://aider.chat/share/?mdurl=https://gist.github.com/paul...
redox99 3y ago
GPT4 made a mistake on its first try, but after asking what the complexity of pop is, it figured out its mistake and fixed it. https://chat.openai.com/share/d527f65f-8a6d-4602-acab-4d80ed915379 https://chat.openai.com/share/d527f65f-8a6d-4602-acab-4d80ed...

voxl 3y ago

in what world is a hashtable lookup worst case O(1)? Your own solution doesn't match your requirements. If you want amortized complexity then a simple vector suffices.

RomanPushkin 3y ago
1. I like toxic comments like that saying something is simple without actually solving the problem, you're the best. 2. The average complexity to search, insert, and delete data in a hash table is O(1), for interviews it works 99% of the time. 3. There is alternative O(1) solution you're looking for, I'll leave this exercise to you, bro. As well as the other exercise of being less toxic and a bit more respectful to people you don't know online lol.
- Mystery-Machine 3y ago
  Average and big-O notation don't go together... Yes, it works 99% of the time, but parent explained to you why you won't get that 1% of the offers. That, plus taking offence by his comment, which makes you not pass behavioral part of the interview.
  - RomanPushkin 3y ago
    > which makes you not pass behavioral part of the interview I'm okay not getting 1% of the offers. I'm not $100 bill so everyone likes me. I appreciate an attempt to educate me though, I wanted to make clear that any discussion like that is useless without solution to a problem. Post your solution, we'll discuss downsides. You can see it from my side, and I have another one. The parent commenter ain't got no solution, but keeps insisting he can implement that easily with this and that... Good luck passing interviews with that attitude...
- voxl 3y ago
  Pointing out a mistake is toxicity? Your ego is off the charts. Also, I gave you a solution that would probably be _better_ than yours in 99% of scenarios, a simple vector from any standard library, std::vector in C++, and Vec in Rust. This solution gives you O(1) worst case for peek, and amortized worst case O(1) for the other operations. To be actually toxic for a moment, you do know that amortized and average are different right? There is an easy solution to get O(1) for all operations too by allowing them to throw an exception: a simple array. There is no other O(1) solution for all operations that I am aware. In fact it is probably not too difficult to prove that such a solution does not exist.
  - RomanPushkin 3y ago
    If your interviewer is asking for solution and you keep insisting that "I have you a solution"... without actual code... Also saying my ego is off the charts. Good luck passing interviews with that attitude.

anotherpaulg 3y ago

I tried using aider to work with GPT-4 on this problem. Initially it went for a solution based on `shift`. But when challenged, it realized that shift was O(n) and was able to come up with a dual stack solution. It considers this solution O(1) when amortized over many operations. I don't know ruby well, so I can't verify that. https://aider.chat/share/?mdurl=https://gist.github.com/paul-gauthier/e3f32d84b9bbc592731bcb9db50f035d https://aider.chat/share/?mdurl=https://gist.github.com/paul...

redox99 3y ago

GPT4 made a mistake on its first try, but after asking what the complexity of pop is, it figured out its mistake and fixed it. https://chat.openai.com/share/d527f65f-8a6d-4602-acab-4d80ed915379 https://chat.openai.com/share/d527f65f-8a6d-4602-acab-4d80ed...