ChatGPT vs. My Google Coding Interview

Previously, I wrote about my go-to coding interview question, which is a slight twist on a standard binary search. Just for fun, I was curious to see how ChatGPT, the newest AI powered conversation bot, would perform in a mock interview.

If you haven’t read the interview article before, here it is.

My Google Coding Interview Question

Preface

I started working on this article the week after ChatGPT launched in late November 2022. At that time, ChatGPT was able to write a perfect binary search, but was unable to get the “next smallest number” part. It would seem to be confused about the test cases. When one test case was fixed, another would be broken. I wasn’t sure how to weave that into a compelling story.

In December, ChatGPT caught the tech world’s attention. Each time I tried to log back on to continue my research, ChatGPT was out of capacity. Now after the New Year, I was finally able to log back in.

This time, I was able to get completely different results. A surprise even for me.

The Interview

Me:

Good morning. Let’s do a coding interview question. Can you write the solution in JavaScript?

FYI, my commentary will be written like this. ChatGPT defaults to Python but you can ask for other languages.

ChatGPT:

Sure! What’s the question?

Me:

Given a positive sorted array a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];

Define a function f(a, x) that returns x, the previous smallest number, or -1 for errors.

After repeatedly getting the same errors as last November, I got the idea to change “next smallest number” to “previous smallest number”.

Let’s start with test cases first. Given these two test cases, what are others you can think of?

f(a, 12) = 12
f(a, 13) = 12

If I don’t ask to start with test cases, ChatGPT would jump straight into coding the implementation. What a mirror for human software engineers!

ChatGPT:

Here are some additional test cases:

f(a, 3) = 3
f(a, 4) = 4
f(a, 6) = 6
f(a, 9) = 9
f(a, 10) = 10
f(a, 14) = 14
f(a, 15) = 15
f(a, 17) = 17
f(a, 19) = 19
f(a, 21) = 21
f(a, 2) = -1 (x is smaller than the smallest number in the array)
f(a, 22) = 21 (x is larger than the largest number in the array)
f(a, 0) = -1 (x is negative)
f(a, 0.5) = -1 (x is not an integer)
f([], 0) = -1 (the input array is empty)

Nice. ChatGPT found all the edge cases, including the empty array, and explained why! It didn’t do this when I asked for “next smallest”.

Minor nit: I don’t like brute forcing all the numbers in the given array, but no big deal.

Me:

Let’s add f(a, 12) = 12 and f(a, 13) = 12 to the list. Do you understand why f(a, 13) should return 12?

ChatGPT:

Yes, I understand. The function should return the previous smallest number in the array if the input number is not found in the array.

In this case, the input number is 13, which is not present in the array.

Therefore, the function should return the previous smallest number, which is 12.

Even though I specifically asked to add the test cases for f(a, 12)and f(a, 13), I suspected ChatGPT already understood the question, given it had suggested the test case of f(a, 22) = 21.

ChatGPT probably thinks I’m an idiot.

Me:

Before we jump into coding, What algorithm would you choose?

This is literally part of my script when I give this interview question. For human developers, asking them about the algorithm or pseudo code first actually improves the speed and accuracy of the coding part later.

I suspect ChatGPT doesn’t need the help with coding accuracy, but I want to nudge it toward a binary search solution.

ChatGPT:

There are a few different algorithms that we could use to solve this problem. One option would be to use a linear search algorithm, where we iterate through the array and return the last element that is smaller than the input number. This would have a time complexity of O(n), which is not particularly efficient but would work for small inputs.

Another option would be to use a binary search algorithm, which would have a time complexity of O(log n). This would be more efficient for larger inputs. To use a binary search, we would first check the middle element of the array. If the middle element is smaller than the input number, we would search the right half of the array. If the middle element is larger than the input number, we would search the left half of the array. We would repeat this process until we find the previous smallest number or determine that it is not present in the array.

I would recommend using a binary search algorithm, as it is more efficient and should work well for both small and large inputs.

This is good. ChatGPT is explaining both algorithms like a real engineer with the correct Big-O complexity, and made the correct algorithm recommendation.

Me:

Sounds great. Let’s go ahead and write the code.

Will ChatGPT write a correct binary search on the first go? That would be superhuman! LOL

ChatGPT:

Sure thing! Here’s a implementation of the f function using a binary search algorithm:

function f(a, x) {
  // edge cases
  if (a.length === 0) return -1; // array is empty
  // x is smaller than the smallest number in the array
  if (x < a[0]) return -1; 
  // x is larger than the largest number in the array
  if (x > a[a.length - 1]) return a[a.length - 1]; 
  if (x % 1 !== 0) return -1; // x is not an integer

  let start = 0;
  let end = a.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (a[mid] === x) {
      return x;
    } else if (a[mid] > x) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return a[end];
}

This function has a time complexity of O(log n), which is efficient for both small and large inputs. It also handles the edge cases that we identified earlier.

To test the function, we can use the following code:

const a = [3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21];

console.log(f(a, 12)); // 12
console.log(f(a, 13)); // 12
console.log(f(a, 3)); // 3
console.log(f(a, 4)); // 4
console.log(f(a, 6)); // 6
console.log(f(a, 9)); // 9
console.log(f(a, 10)); // 10
console.log(f(a, 14)); // 14
console.log(f(a, 15)); // 15
console.log(f(a, 17)); // 17
console.log(f(a, 19)); // 19
console.log(f(a, 21)); // 21
console.log(f(a, 2)); // -1
console.log(f(a, 22)); // 21
console.log(f(a, 0)); // -1
console.log(f(a, 0.5)); // -1
console.log(f([], 0)); // -1

Cool. 12 and 13 are there. Good job ChatGPT!

At first, I thought there was a bug for f(a, 13). Then after double checking the code, I saw that it returned a[end] at the end of the function. When the number x isn’t found, start and end would criss-cross each other to exit the while loop, hence end is pointing at the previous smallest number. Clever!

In a normal interview I would ask the candidate to walk me through and explain this.

I was actually quite surprised that ChatGPT was able to figure this out on its own. Much better than previous attempts. Note that this particular solution works because of the existence of precondition checks, so that there is no way that end could point at -1 for test case f(a,2). That is actually a common pitfall for this interview question.

Kudos to ChatGPT for coming up with the pre condition checks AND a correct implementation right away!

Me:

There’s a hidden bug in the code if the array is very very very large. Can you spot it and fix the bug?

Let’s see if ChatGPT can figure out the midpoint calculation error.

ChatGPT:

The implementation of the f function that I provided should work correctly for arrays of any size. However, if the array is extremely large, it may take a long time to find the previous smallest number due to the binary search algorithm's time complexity of O(log n).

If you need to find the previous smallest number in a very large array, you might want to consider using a different algorithm or data structure that can handle large inputs more efficiently. For example, you could use a data structure like a binary tree, which has a time complexity of O(log n) for search operations.

That being said, if you just want to fix the current implementation to handle very large arrays more efficiently, you could try using a more efficient search algorithm, such as a ternary search or a jump search. These algorithms have a time complexity of O(log3 n) and O(√n), respectively, which may be faster for very large arrays.

Me:

What would happen to the midpoint calculation for very large arrays?

Trying to give a clue without giving it away…

ChatGPT:

The midpoint calculation in the f function is as follows:

const mid = Math.floor((start + end) / 2);

This calculation will work correctly for arrays of any size, including very large arrays. The Math.floor function rounds the result down to the nearest integer, so the midpoint will always be a valid index in the array.

For example, if start is 0 and end is 10^9 (one billion), the midpoint will be 5*10^8 (five hundred million). This will not cause any problems, as the midpoint will still be a valid index in the array.

Me:

What if the array size was Number.MAX_VALUE?

Okay, I give up.

ChatGPT:

The Number.MAX_VALUE property represents the maximum representable number in JavaScript. It is a very large number, approximately 1.79 x 10^308.

If the size of the array is Number.MAX_VALUE, the midpoint calculation in the f function will still work correctly. However, the binary search algorithm as a whole may not be the most efficient way to search such a large array.

It’s also worth noting that an array with a size of Number.MAX_VALUE is likely to exceed the maximum allowable memory for a JavaScript program, so it may not be possible to create such an array in the first place.

Actually, Number.MAX_VALUE would cause the midpoint calculation to fail.

const end = Number.MAX_VALUE;
> 1.7976931348623157e+308
const mid = end / 2;
> 8.988465674311579e+307
const start = mid + 1;
> 8.988465674311579e+307
console.log((start + end) / 2);
> Infinity
console.log(start + (end - start) / 2);
> 1.3482698511467367e+308

Me:

Theoretically though, is there a way to rewrite the mid calculation to circumvent this issue?

C’mon ChatGPT, you are so close! Let’s DOOOOOOOO THIS!

ChatGPT:

In theory, it is possible to rewrite the midpoint calculation to handle very large arrays without causing any issues. Here is an example of how you could do this:

const mid = start + Math.floor((end - start) / 2);

This calculation works by first subtracting start from end to get the number of elements in the array, and then dividing that number by 2 to find the midpoint. The Math.floor function is used to round the result down to the nearest integer, ensuring that the midpoint is a valid index in the array.

This calculation will work correctly for arrays of any size, including very large arrays. It will not cause any issues with memory or performance, as it does not rely on large numbers being represented as floating point values.

I hope this helps! Let me know if you have any other questions.

Bravo, you did it! ChatGPT figured out the overflow error and proposed the fix that escaped computer scientist for years!

While the memes may seem silly, but often in live interviews, I’m pulling for the interviewee. I want them to succeed!

Interview Assessment

For this interview, I would give a Strong Hire recommendation for Level 3 Software Engineer and Leaning Hire for L4.

ChatGPT was able to come up with the right set of test cases. Gave correct explanation for Big-O complexity. Chose the correct algorithm and implemented a perfect solution with pre-conditions. Needed more hinting but was able to fix the midpoint overflow issue.

ChatGPT could theoretically, given perfect input, make a pretty solid individual contributor. However, as an AI, I still have doubts on its ability to independently drive through ambiguous requirements and influence a team of human engineers, hence I’m withholding a Strong Hire for L4 or even L5 Senior Software Engineer recommendation. For a human, I could justify a L4.

I hope I’m being fair. ChatGPT is technically sound but cannot be trusted (yet) as a fully independent software engineer. ChatGPT still requires a good human as its Tech Lead, a strong indicator for L3.

Improving the Human

To be honest, ChatGPT did very well on this coding interview question, but only after I realized my own mistake.

Previously when I asked for the next smallest number, ChatGPT was really confused and simply could not come up with the correct test cases and implementation, because in computer speech, next means after! While a human can interpret next as previous in this case, this is not true for a computer.

When I changed the question to the previous smallest number, and ChatGPT worked flawlessly.

But isn’t this the beauty of Artificial Intelligence? AI can make the human better. Through the AI, I learned that there was a tiny bug in my decade old interview question. Once I fixed it, ChatGPT worked like a champ.

I started this article thinking that it would be about finding faults with the AI. But instead, ChatGPT helped me find a single word change that made my interview question better.

I didn’t see that one coming, not for a million years!¹ Did you?

[1]: Judi Dench. Philomena https://www.quotes.net/mquote/1051764