ChatGPT & Me — Part 1: Solving programming problems & Interview Questions

Motivation: Unless you’ve been living under a rock for the last couple of months, you must’ve heard about ChatGPT either from the news, random youtube videos, or from your social circle. You probably heard people describing it as “scary”, “disruptive” or even straight “BS”. In this publication I’ll be documenting my experiments using ChatGPT, trying to push its boundaries, unpacking its capabilities, and looking beyond the hype.

TL;DR: I tried using ChatGPT to solve programming problems and typical interview questions with various levels of difficulty, from websites such as HackerRank. The results are mind blowing to say the least especially for easy and medium problems. It also was an eye opener on how much of an impact detailed prompts have on the quality of the output, especially that the description of such problems is formally very well written on websites such as HackerRank and the like.

ChatGPT solving software developer interview problems:

Problem 1 :Finding the missing element in an array (Difficulty Level — Easy):

Input Prompt:

“Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

Example 1:

Input:
N = 5
A[] = {1,2,3,5}
Output: 4

Example 2:

Input:
N = 10
A[] = {6,1,2,8,3,4,7,10,5}
Output: 9

Your Task :
You don't need to read input or print anything. Complete the function MissingNumber() that takes array and N as input parameters and returns the value of the missing number.”

Output:

To solve this problem, we can use the fact that the sum of integers from 1 to N is N*(N+1)/2. If we add up all the elements in the array, we can subtract this sum from the expected sum to find the missing number.

Algorithm:

Initialize a variable “expected_sum” to N*(N+1)/2

Iterate over the elements in the array and add them up to a variable “actual_sum”

Return the difference between “expected_sum” and “actual_sum”, which is the missing number.

Here’s the implementation of the algorithm in Python:

def MissingNumber(array, N):

expected_sum = N*(N+1)//2

actual_sum = sum(array) return expected_sum — actual_sum

Rating: 4.5/5

The solution generated is great on so many levels. The steps of the algorithm were perfectly explained. It solved it in (according to my knowledge) the most efficient way, it also returned the proper output for the test cases given, and even generated extra test cases (disclaimer: I did not copy this part to avoid making the post extremely long). I gave it only a 4.5, as it outputted the python code, without indenting the lines in the proper way, which is surprising as it usually does it perfectly. Extra: If you ask it to transform the code in another programming language, it does so perfectly.

How my fellow developers must be feeling!

Problem 2: Lexicographical Order (Difficulty Level — Medium):

Disclaimer: This is a problem from the website HackerRank. I’ve copied the problem description as an input prompt to hacker rank, as follows:

Input Prompt:

“Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list. Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria: It must be greater than the original word It must be the smallest word that meets the first condition Example w=abcd, The next largest word is abdc. Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer.

Function Description

Complete the biggerIsGreater function in the editor below. biggerIsGreater has the following parameter(s):

string w: a word

Returns — string: the smallest lexicographically higher string possible or no answer

Input Format The first line of input contains , the number of test cases. Each of the next lines contains .

Constraints will contain only letters in the range ascii[a..z].

Sample Input 0 5 ab bb hefg dhck dkhc

Sample Output 0 ba no answer hegf dhkc hcdk

Explanation

Test case 1: ba is the only string which can be made by rearranging ab. It is greater.

Test case 2: It is not possible to rearrange bb and get a greater string.

Test case 3: hegf is the next string greater than hefg.

Test case 4: dhkc is the next string greater than dhck.

Test case 5: hcdk is the next string greater than dkhc.

Sample Input 1 6 lmno dcba dcbb abdc abcd fedcbabcd

Sample Output 1 lmon no answer no answer acbd abdc fedcbabdc”

Output:

Solution:

To create a lexicographically larger string from the given string, we need to find the rightmost character which is smaller than its next character. We call the index of this character “pivot.” Then we need to find the smallest character to the right of the pivot, which is greater than the pivot. We call the index of this character “swap.” Then we swap the characters at pivot and swap indices and sort the substring to the right of the pivot index in ascending order. If no such pivot exists, we return “no answer.”

For example, let’s say we have the string “abcd” and we want to find the next lexicographically larger string. The pivot index is 2 (the character ‘c’) because ‘c’ is smaller than ‘d’ and there is no smaller character to its right. The swap index is 3 (the character ‘d’) because ‘d’ is the smallest character to the right of the pivot that is greater than the pivot. We swap the characters at indices 2 and 3, giving us the string “abdc.” Finally, we sort the substring to the right of the pivot index in ascending order, which gives us the final string “abdc.”

Implementation:

def biggerIsGreater(w):
    # Convert the string to a list of characters for easy manipulation
    s = list(w)   # Find the pivot index
    pivot = -1
    for i in range(len(s) - 1):
        if s[i] < s[i + 1]:
            pivot = i    # If no pivot exists, the string cannot be rearranged
    if pivot == -1:
        return "no answer"
# Find the swap index
    swap = -1
    for j in range(len(s) - 1, pivot, -1):
        if s[j] > s[pivot]:
            swap = j
            break
    # Swap the characters at pivot and swap indices
    s[pivot], s[swap] = s[swap], s[pivot]
    # Reverse the substring to the right of the pivot index
    s[pivot + 1:] = reversed(s[pivot + 1:])
    # Convert the list back to a string and return it
    return "".join(s)
# Testing the function with the given sample inputs
print(biggerIsGreater("ab"))  # Expected output: ba
print(biggerIsGreater("bb"))  # Expected output: no answer
print(biggerIsGreater("hefg"))  # Expected output: hegf
print(biggerIsGreater("dhck"))  # Expected output: dhkc
print(biggerIsGreater("dkhc"))  # Expected output: hcdk

Rating: 5/5

It solved the problem PERFECTLY, giving a great explanation of the algorithm, and outputting a python function that does exactly the job, and passes every test on HackerRank with flying colours:

Output after submitting the solution on HackerRank blindly

PoV — You’re a developer and it took you sometime to understand the problem.

Last but not least, I wanted to try out how it would handle a hard problem from HackerRank, which a non-seasoned junior developer would have a really hard time solving — Spoiler Alert: The results are not what you’d expect.

Problem 3: String Similarity (Difficulty Level: Hard)

Disclaimer: This is another problem from the website HackerRank, I’ve copied the problem description as an input prompt to hacker rank, as follows:

Input Prompt:

“For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

Calculate the sum of similarities of a string S with each of it’s suffixes.

Input Format

The first line contains the number of test cases t.
Each of the next t lines contains a string to process, .

Constraints

is composed of characters in the range ascii[a-z]

Output Format

Output t lines, each containing the answer for the corresponding test case.

Sample Input

2
ababaa
aa

Sample Output

11
3

Explanation

For the first case, the suffixes of the string are “ababaa”, “babaa”, “abaa”, “baa”, “aa” and “a”. The similarities of these strings with the string “ababaa” are 6,0,3,0,1, & 1 respectively. Thus, the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is 2 + 1 = 3.”

I also copied the sample code and just asked it to complete the respective function.

Output:

def stringSimilarity(s):
    n = len(s)
    sum_similarity = 0
    for i in range(n):
        suffix = s[i:]
        similarity = 0
        for j in range(min(len(suffix), len(s))):
            if suffix[j] == s[j]:
                similarity += 1
            else:
                break
        sum_similarity += similarity
    return sum_similarity

Evaluation: 3/5

It passes the initial sample cases however when I submit the solution, it passes only 5/12 Use Cases, where for the other there is a runtime error.

PoV: Experienced Developers

In an unexpected turn of events, a few days after releasing this story, GPT-4 was released, the newer model from OpenAI, so I had to try this problem again, and update the story. Let’s see if anything would change.

Given the exact same prompt, using ChatGPT with GPT-4, available only using ChatGPT Plus subscription, at the time of writing this story. We get the following output:

def stringSimilarity(s):
    total_similarity = len(s)
    
    for i in range(1, len(s)):
        suffix = s[i:]
        j = 0
        while j < len(suffix) and s[j] == suffix[j]:
            j += 1
        total_similarity += j
    
    return total_similarity

When I copy and paste this code to HackerRank, it passes 6/12 Use Cases. It fails the other 6 due to a “TimeOut Error”, probably due to a lack of efficiency of the code.

I then ask ChatGPT, if it could make the code more efficient, and it most certainly does:

Input:

can you make it more efficient? in terms of complexity?

Output:

Yes, we can make it more efficient by using Z-algorithm to compute the Z-array, which can be used to find the sum of the similarities more quickly. The Z-algorithm has a linear time complexity of O(n), making it more efficient compared to the previous implementation.

Here’s the updated code with the Z-algorithm:

import math
import os
import random
import re
import sys
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i > r:
            l, r = i, i
            while r < n and s[r - l] == s[r]:
                r += 1
            z[i] = r - l
            r -= 1
        else:
            k = i - l
            if z[k] < r - i + 1:
                z[i] = z[k]
            else:
                l = i
                while r < n and s[r - l] == s[r]:
                    r += 1
                z[i] = r - l
                r -= 1
    return z
def stringSimilarity(s):
    z_values = z_algorithm(s)
    return sum(z_values)

At this point curiosity killed me, before looking into the code, I copied it and pasted the solution again in HackerRank, and this happened:

GPT-4 resolves the hard problem after a few prompts!

Devs be like:

If you’re as lazy as me, and couldn’t be bothered to go through the details of the Z-algorithm, I asked ChatGPT to explain it to us:

Certainly! The Z-algorithm is a linear time string matching algorithm that efficiently constructs an array of equal length to the input string. This array, called the Z-array, stores the length of the longest common prefix between the input string and each of its suffixes. The primary use case for the Z-algorithm is pattern matching within a larger text.

Here’s a breakdown of the Z-algorithm:

Initialize an array z of length n (the length of the input string s), with all elements set to 0. Set z[0] = n because the entire string is always equal to itself.

Define two pointers, l (left) and r (right), both initialized to 0. These pointers define the current "Z-box" that we are working with: a substring that starts at position l and ends at position r.

Iterate through the string s from the second character (index 1) to the last character (index n-1). For each index i:

a. If i > r, it means the current index is outside the Z-box. In this case, set both l and r to i. Then, compare characters starting from the current index i with the corresponding characters from the beginning of the string, and increment r until a mismatch is found. Update z[i] to the length of the matched substring (r - l) and decrement r by 1.

b. If i <= r, it means the current index is inside the Z-box. Calculate k = i - l. Now, there are two possibilities:

i. If z[k] < r - i + 1, it means the Z-value at index i is the same as the Z-value at index k. Update z[i] to z[k].

ii. If z[k] >= r - i + 1, it means we need to perform further comparisons to determine the correct Z-value at index i. Set l to i, and compare characters starting from index r with the corresponding characters from the beginning of the string. Increment r until a mismatch is found, update z[i] to the length of the matched substring (r - l), and decrement r by 1.

After the loop finishes, the Z-array is complete and can be used for further processing.

The Z-algorithm’s time complexity is O(n), making it an efficient approach for solving string-related problems, such as pattern matching or calculating string similarities.

Reflection

ChatGPT has performed significantly well on HackerRank type of problems (With an exception of the few test cases it hasn’t passed in the hard problems). This highlights how much of a role the detail level of the prompts correlate with the quality of the output, especially that the HackerRank problem descriptions are written in a great level of detail, in a highly structured manner and a lot of test case examples. In ChatGPT’s favour, all of the test cases described in the problem were passed in the String Similarity problem above. Most likely with more experience in prompt engineering, and writing better test cases, we could get it to correct the StringSimilarity code to pass all of the test cases.

To sum up:

Great results come from great prompts!

The Verdict:

I don’t think anyone could deny how powerful ChatGPT is in generating code with this quality, given that something like this was quite unthinkable a few months ago (at least for someone not working on cutting edge AI research). I am also sure that common “easier” everyday tasks, such as generating test cases, finding the bug in a code, or optimizing a function should be a walk in the park for GPT models in general. I am also aware that there is currently an extension in VSCode called CodeGPT, which could help achieve such tasks.

And now to address the elephant in the room: would this technology make developers’ jobs obsolete?

In my personal opinion, no, quite unlikely, at least not in the short-term for most highly skilled developers. However, if a big chunk of your work has to do with writing simple automation scripts, macros or even slightly more complex functions…..

On the more optimistic side, I think this will serve as a great motive for developers to up-skill themselves, and will open up new opportunities for “prompt engineering” jobs.

Make sure you follow this publication and stay tuned for more exciting use cases & experiments using ChatGPT in this publication!