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

Standard Priority Queue IX: Vowels Frequency

-
Tally the frequency of the vowels. Push that into a pQueue, the caveat is when the frequencies are the same, you need to keep track of the first occurrence of each vowel and do some math to insert into the priority queue with the right order. After that, it is just dequeuing and inserting into the proper places. Use StringBuilder to avoid unnecessary string allocations. Code is down below, cheers, ACC. Sort Vowels by Frequency - LeetCode You are given a string  s  consisting of lowercase English characters. Rearrange only the  vowels  in the string so that they appear in  non-increasing  order of their frequency. If multiple vowels have the same  frequency , order them by the position of their  first occurrence  in  s . Return the modified string. Vowels are  'a' ,  'e' ,  'i' ,  'o' , and  'u' . The  frequency  of a letter is the number of times it occurs in the string.   Example 1: Input:   ...
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed...
Read more

Binary Search to Find Next Greater Element V

-
You can use the .BinarySearch method of List<T>. It works well, there is a bit of a trick that you need to do when the return index is negative (just assign it to its complement, ~index). No need to perform the Binary Search "by hand" anymore. Achieves a good NLogN, fast solution. LC suggests a Tree to be used but this approach (two lists, one for even, one for odd) works well. Code is down below, cheers, ACC. Count Smaller Elements With Opposite Parity - LeetCode You are given an integer array  nums  of length  n . The  score  of an index  i  is defined as the number of indices  j  such that: i < j < n nums[j] < nums[i] nums[i]  and  nums[j]  have different parity (one is even and the other is odd). Return an integer array  answer  of length  n , where  answer[i]  is the score of index  i .   Example 1: Input:   nums = [5,2,4,1,3] Output:   [2,1,2,0,0] Explanation: Fo...
Read more