Since I've been playing around with ChatGPT because it's interesting and fun, and I wanted to sharpen my programming skills when there is a time limit of 30 min or less, I decided to let ChatGPT give me some programming prompts and try to solve them.

I asked:

Can you provide me a java programming prompt that I might encounter in an interview

Here is the first response:

The first response was super easy, something I could have done in middle school (literally). O(n) time and O(constant) memory, fun busy activity for 5-10 minutes max.

I regenerated the same prompt to see what else it would give. The next question was

Also very easy, maybe a tiny bit longer because it actually involves tokenizing. But still like a 5-10 minute activity. It's nice that it came with a solution, but I can easily ignore that.

Once again I try the same prompt, third time's the charm right?

It generates:

Another 5-10 minute problem. And most of the time is just typing out the code, the answer was already obvious as soon as I read this.

I decided to refine my prompt to ChatGPT.

Since Google is well known for interesting and challenging interview problems, I asked:

Can you provide me a java programming prompt that I might encounter in an interview for Google.

This time the answer was much more aligned with what I had expected.

This question was much more interesting than the previous ones, not very hard, but more complex compared to the first three. Can you notice an error in the programming prompt? I didn't notice it until I coded it and ran it. Did you already spot it on your own? Good, it is not obvious, and only shows up if you try to execute mentally or on a machine.

The negative 5 should be in the subarray, since it is negative, it actually makes room for more integers to be added. Though the rest of the integers are just two big, even with negative 5 it would not sum to less than or equal to 7.

So I was curious how ChatGPT would react when I corrected it:

you are wrong, the largest subset for that example is [1, -2, 3, 4, -5] which has a sum of 1.

It acknowledge the mistake, and corrected the prompt:

What an agreeable fellow, I wouldn't mind interacting with such a polite system.

So I thought I had a solution, it provided what I expected based on what I understood of the initial problems and constraints. But then I realized there is a slight indication that the array should maintain order. It wasn't explicitly said, so I decided to ask.

Does the subarray have to be consecutive elements?

And ChatGPT responded with:

With that additional constraint, I had to rewrite the entire algorithm.

The original one was optimizing for time, so using a priority queue to hold items too that pushed the subset's sum greater than 7. I was able to come up with this O(n log n) solution quickly. I saw some solutions out there for subset sum that had an O(sum * n) which uses Dynamic programming. A few points that make the DP solution not the best match for this programming prompt.

The solution does require some dedicated time to understand and maintain. Unless the company is filled with rockstar DP programmers, it will take them some time/effort to understand and maintain the code. This is one of the prompt's requirements.

The difference between O(n log n) and O(sum * n) is the sum and log n. Unless you're going to keep the sum in the low hundreds, log n is usually smaller. Assuming a binary tree was used to support the priority queue, 2^100 = 1.26x10^30. So N needs to be ridiculously large to have a sum of 100 or less favor O(sum*n) over O(n log n).

The DP Solution took me more time to comprehend the code compared to how I was able to come up with my first idea in minutes and implement it in less than 50 lines with comments. If there is interest in the solutions I came up with, I can write another blog on that later.

With the additional constraint of order mattered, I was only able to quickly come up with an O(n^2) time complexity solution. Which takes O(n) memory. This one involved having two hash maps, one to track the start/stop of the subset, and one to track the sum for each starting position. With negative numbers, it is entirely possible the sum larger than the max suddenly drops below the max, which means we update the start/stop hash map. Turns out to only take up 23 lines, with a few comments.

I was able to have quite a lot of fun with this last prompt, despite the initial error in the example given, which had two flavors of code.

These programming prompts are mostly self-consistent unless it's taking the problem completely from some problem found on the internet. I did not find any evidence of this, I did encounter similar prompts, but nothing exactly the same. In this use case, ChatGPT provided me with something I could have found on the internet. So what is the differentiation between ChatGPT and an internet search? After an internet search, I would need to spend time reviewing the search result to see which one satisfied my need, and I would have to pick from a list of them. So ChatGPT saved me the trouble of those two steps. It seems to be very suitable as an intelligent assistant. Able to summarize and provide their version of knowledge based on all the knowledge it was trained on. If I can get a ChatGPT app that can integrate on my phone and Siri, that would be great. The current Siri answering questions by bringing up internet search results is great, but I still have to parse through the information sometimes myself. This is where the current ChatGPT can excel at.

In the context of AI, ChatGPT was able to formulate this prompt based on similar prompts on the internet. It was able to make it make sense mostly, to provide and calculate its own examples. Though it did make a mistake on one of the expected outputs. Does ChatGPT "understand" what it is outputting? Is it just really good at generating relevant text? From the outside, it looks like a very good way to generate these prompts. It has not yet generated anything I haven't seen on other coding prep websites before.

Perhaps in the future, we would have interviews conducted by AI. Save all the engineers a bunch of time doing multiple interviews with multiple candidates each time the team needs more people and gives back consistent scores for a candidate in each skill.

Reference: