Claude vs ChatGPT: A Coder's Perspective on LLM Performance

-
In the rapidly evolving world of Large Language Models (LLMs), recent releases from OpenAI's ChatGPT have garnered significant attention. However, when it comes to coding tasks, Anthropic's Claude.ai continues to impress me with its speed and quality of output.

Benchmarking with LeetCode

While LeetCode problems aren't the definitive measure of an AI's coding capabilities (they're pre-designed puzzles, after all), they offer an interesting playground for comparison. Let's dive into a recent example:

The Problem

3319. K-th Largest Perfect Subtree Size in Binary Tree
Medium

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

 

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2000].
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

My Solution
I tackled this problem using a combination of Post-Order Depth-First Search (PO-DFS) and a Priority Queue. Here are the performance stats:

Runtime: 197 ms
Memory Usage: 103.6 MB

```
Marcelo's Solution:

public class Solution {
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        PriorityQueue pQueue = new PriorityQueue(false, 2500);
        int height = 0;
        int numberNodes = 0;
        IsPerfectSubtreePostOrder(root, ref height, ref numberNodes, pQueue);

        int retVal = -1;
        while (pQueue.Count > 0 && k > 0)
        {
            double priority = 0;
            retVal = (int)pQueue.Dequeue(out priority);
            k--;
        }

        return k > 0 ? -1 : retVal;
    }

    private bool IsPerfectSubtreePostOrder(TreeNode node,
                                           ref int height,
                                           ref int numberNodes,
                                           PriorityQueue pQueue)
    {
        if (node == null)
        {
            height = 0;
            numberNodes = 0;
            return true;
        }

        int rightHeight = 0;
        int rightNumberNodes = 0;
        bool rightSubtree = IsPerfectSubtreePostOrder(node.right, ref rightHeight, ref rightNumberNodes, pQueue);

        int leftHeight = 0;
        int leftNumberNodes = 0;
        bool leftSubtree = IsPerfectSubtreePostOrder(node.left, ref leftHeight, ref leftNumberNodes, pQueue);

        height = Math.Max(rightHeight, leftHeight) + 1;
        numberNodes = rightNumberNodes + leftNumberNodes + 1;

        bool isPerfectSubtree = false;
        if (rightSubtree && leftSubtree && rightHeight == leftHeight)
        {
            pQueue.Enqueue(numberNodes, numberNodes);
            isPerfectSubtree = true;
        }

        return isPerfectSubtree;
    }
}

public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private double priority;
        public HeapEntry(object item, double priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public double Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private bool ascend;
    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue(bool ascend, int cap = -1)
    {
        capacity = 10000000;
        if (cap > 0) capacity = cap;
        heap = new HeapEntry[capacity];
        this.ascend = ascend;
    }

    public object Dequeue(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }
    public object Peak(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public object Peak(/*out double priority*/)
    {
        //priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public void Enqueue(object item, double priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        if (this.ascend)
        {
            while ((index > 0) && (heap[parent].Priority > he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        else
        {
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (this.ascend)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority > heap[child + 1].Priority))
                {
                    child++;
                }
            }
            else
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}
```

ChatGPT's Approach
ChatGPT 4 with Code Interpreter took a slightly different route:
  • Highly optimized PO-DFS
  • Used a List instead of a Priority Queue
  • Performance:
Runtime: 170 ms
Memory Usage: 72.2 MB

```
ChatGPT Solution:
public class Solution
{
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        List<int> perfectSubtreeSizes = new List<int>();
        CalculatePerfectSubtreeSizes(root, perfectSubtreeSizes);

        if (perfectSubtreeSizes.Count < k)
        {
            return -1;
        }

        perfectSubtreeSizes.Sort((a, b) => b.CompareTo(a));
        return perfectSubtreeSizes[k - 1];
    }

    private int CalculatePerfectSubtreeSizes(TreeNode node, List<int> sizes)
    {
        if (node == null)
        {
            return 0;
        }

        int leftSize = CalculatePerfectSubtreeSizes(node.left, sizes);
        int rightSize = CalculatePerfectSubtreeSizes(node.right, sizes);

        if (leftSize == rightSize && (leftSize == 0 || IsPowerOfTwoMinusOne(leftSize + rightSize + 1)))
        {
            int currentSize = leftSize + rightSize + 1;
            sizes.Add(currentSize);
            return currentSize;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

Claude's Solution
Claude.ai consistently outperforms ChatGPT in this and other examples I've tested. Its approach:
  • Pruned version of PO-DFS
  • K-min Priority Queue
  • Performance: 
Runtime: 164 ms
Memory Usage: 71.1 MB

```
Claude.ai Solution:

public class Solution
{
    private PriorityQueue<int, int> topK;
    private int k;

    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        this.k = k;
        this.topK = new PriorityQueue<int, int>(k, Comparer<int>.Create((a, b) => a - b));
        
        DFS(root);

        return topK.Count == k ? topK.Peek() : -1;
    }

    private int DFS(TreeNode node)
    {
        if (node == null)
            return 0;

        int left = DFS(node.left);
        int right = DFS(node.right);

        if (left == right && IsPowerOfTwoMinusOne(left + right + 1))
        {
            int size = left + right + 1;
            if (topK.Count < k)
            {
                topK.Enqueue(size, size);
            }
            else if (size > topK.Peek())
            {
                topK.Dequeue();
                topK.Enqueue(size, size);
            }
            return size;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

The Future of AI and Coding

It's astounding to think that we're only in the first decade of LLMs since the groundbreaking "Attention is All You Need" paper. The rapid progress we've seen raises exciting questions:

  1. How will these models evolve in the coming decades?
  2. What impact will they have on software development practices?
  3. How can we best leverage AI assistants in our coding workflows?

As we continue to explore these questions, one thing is clear: the synergy between human creativity and AI capabilities is reshaping the landscape of software development.

Cheers,
ACC

Comments

Post a Comment

Popular posts from this blog

Quasi FSM (Finite State Machine) problem + Vibe

-
Image
Not really an FSM problem since the state isn't changing, it is just defined by the current input. Simply following the instructions should do it. Using VSCode IDE you can also engage the help of Cline or Copilot for a combo of coding and vibe coding, see below screenshot. Cheers, ACC. Process String with Special Operations I - LeetCode You are given a string  s  consisting of lowercase English letters and the special characters:  * ,  # , and  % . Build a new string  result  by processing  s  according to the following rules from left to right: If the letter is a  lowercase  English letter append it to  result . A  '*'   removes  the last character from  result , if it exists. A  '#'   duplicates  the current  result  and  appends  it to itself. A  '%'   reverses  the current  result . Return the final string  result  after processing all char...
Read more

Classic Dynamic Programming IX

-
Image
A bit of vibe code together with OpenAI O3. I asked O3 to just generate the sieve due to laziness. Sieve is used to calculate the first M primes (when I was using Miller-Rabin, was giving me TLE). The DP follows from that in a straightforward way: calculate the numbers from i..n-1, then n follows by calculating the min over all M primes. Notice that I made use of Goldbach's Conjecture as a way to optimize the code too. Goldbach's Conjecture estates that any even number greater than 2 is the sum of 2 primes. The conjecture is applied in the highlighted line. Cheers, ACC. PS: the prompt for the sieve was the following, again using Open AI O3 Advanced Reasoning: " give me a sieve to find the first M prime numbers in C#. The code should produce a List<int> with the first M primes " Minimum Number of Primes to Sum to Target - LeetCode You are given two integers  n  and  m . You have to select a multiset of  prime numbers  from the  first   m  pri...
Read more

HashSet I

-
Image
HashSet is faster and more memory efficient than HashTable. If you don't need the actual hash value, only the hash set, prefer to use HashSet over HashTable. The solution to the problem below exemplifies this situation. I didn't test with HashTable, but I'm sure it would be slower. Cheers, ACC. Partition String - LeetCode Given a string  s , partition it into  unique segments  according to the following procedure: Start building a segment beginning at index 0. Continue extending the current segment character by character until the current segment has not been seen before. Once the segment is unique, add it to your list of segments, mark it as seen, and begin a new segment from the next index. Repeat until you reach the end of  s . Return an array of strings  segments , where  segments[i]  is the  i th  segment created.   Example 1: Input:   s = "abbccccd" Output:   ["a","b","bc","c","cc","d"] Explanation:...
Read more