I occasionally solve algorithm questions on Leetcode as a fun exercise. I recently wrote about a dynamic programming question I solved, and I thought it would be fun to share another one. This time it’s a simple linked list question.

Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

I started off just creating a skeleton of the solution that allows me to run the examples and see the output.

class ListNode
  attr_accessor :val, :next
  def initialize(val = 0, _next = nil)
    @val = val
    @next = _next
  end
end

# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
  head
end

def print_list(head)
  result = []
  while head
    result << head.val
    head = head.next
  end
  pp result
end

print_list(remove_nth_from_end(ListNode.new(1, ListNode.new(2, ListNode.new(3, ListNode.new(4, ListNode.new(5))))), 2))
print_list(remove_nth_from_end(ListNode.new(1), 1))
print_list(remove_nth_from_end(ListNode.new(1, ListNode.new(2)), 1))

Now onto the actual solution. Since this is a linked list we can’t simply walk all the way to the end of the list and then backtrack. Instead I found it useful to think of the desired end state of the algorithm - we want to end up with a pointer pointing to the node before the nth node from the end of the list. So in the example of [1, 2, 3, 4, 5] we want a pointer at the 3 node, which is the third node from the end, in order to be able to do p.next = p.next.next.

The trickiest part of this algorithm is the edge cases - I got a bit stuck on how to solve for [1, 2] with n = 1 (the result being [1]) and n = 2 (the result being [2]). Then I realized that when the size of the list is the same as n, that is a special case where you return head.next. In all the other cases I can modify the list and return head.

# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
  p = head
  list_size = 0
  until p.nil?
    list_size += 1
    p = p.next
  end

  if n == list_size
    head.next
  else
    p = head
    (list_size - n - 1).times { p = p.next }
    p.next = p.next.next
    head
  end
end

I didn’t really enjoy doing this algorithm as much as the dynamic programming one. I’m doing the algorithms because it’s something I enjoyed doing when I was a student, and it helps to bring back some of the joy of programming for it’s own sake. Maybe I’ll stick to the ‘hard’ questions, or at least questions where a brute force answer is easy but an optimal one takes some creativity.

Discussion

We often need to run shell commands from within Ruby code, and Ruby provides a number of ways to do that. It’s sligtly confusing at first - specifically because there are different ways of accomplishing the same thing. I found this useful flowchart on StackOverflow that helps you choose the appropriate option. If you’re looking for a detailed writeup of the different options I recommend reading 6 Ways to Run Shell Commands in Ruby by Nate Murray.

One common mistake I’ve seen - and made myself - is to use string interpolation when passing arguments to a shell command. For example, in my recent post on Tweeting new Jekyll Posts I was using Ruby to interact with the git command. I could have written:

# Git add and commit (unsafe example)
commit_message = "Blogged: #{document.title} #{URI.join(site_config.fetch('url'), document.url)}"
`git add #{post_path}`
`git commit -m "#{commit_message}"`

This is a bad idea because

1. Can break if it includes double quotes, ampersands, semicolons, etc.
2. Can lead to command injection if the title includes malicious input.

We could get around (1) by using Shellwords.escape and you could argue I don’t have to worry about (2) because I control the input. However, best practice dictates that you should never interpolate any arguments into shell commands. Instead you should use system and pass the arguments as parameters.

# Git add and commit
commit_message = "Blogged: #{document.title} #{URI.join(site_config.fetch('url'), document.url)}"
system('git', 'add', post_path)
system('git', 'commit', '-m', commit_message)

This principle doesn’t just apply to Ruby - I had the exact same issue with Java code I wrote recently. Instead of building the entire command:

String command = String.format(
    "pg_dump --dbname=%s --host=%s --port=%s --username=%s",
    connectionProperties.dbName(),
    connectionProperties.host(),
    connectionProperties.port(),
    connectionProperties.username()
);

ProcessBuilder processBuilder = new ProcessBuilder("bash", "-c", command);
processBuilder.redirectErrorStream(true);
Process process = processBuilder.start();

Pass the arguments as parameters:

List<String> pgDumpCommand =
    List.of(
        "pg_dump",
        "--dbname",
        connectionProperties.dbName(),
        "--host",
        connectionProperties.host(),
        "--port",
        connectionProperties.port().toString(),
        "--username",
        connectionProperties.username()
    );

ProcessBuilder processBuilder = new ProcessBuilder(
    Stream.of(pgDumpCommand, options).flatMap(Collection::stream).toList()
);
processBuilder.redirectErrorStream(true);
Process process = processBuilder.start();

In this example I also needed to allow the consumers of this code (which I control) to pass additional options. In that case I would also suggest that you use an explicit whitelist/allowlist for accepted options.

Discussion

As I’ve been updating the stylesheets on my blog, I ran into an issue with browser caching — changes to my CSS weren’t showing up right away. Since I’m serving assets through AWS CloudFront with a 7-day cache for non-HTML files, this behavior makes sense. While I could disable caching altogether, that feels like a blunt and amateur solution. Instead, I’m implementing asset fingerprinting to keep the performance benefits of caching while ensuring everyone always get the latest version of my styles.

I’m using the built-in jekyll-sass-converter plugin for Jekyll to compile my SASS files into CSS. Unfortunately it doesn’t offer any support for fingerprinting assets. I searched around and found the jekyll-minibundle which supports both minification and fingerprinting, but it doesn’t work with jekyll-sass-converter. I did stumble upon this gist by Yaroslav Markin which looked appealing - just a few lines of code and you have a hand-rolled digesting solution.

# frozen_string_literal: true

require 'digest'

module Jekyll
  # Jekyll assets cachebuster filter
  #
  # Place this file into `_plugins`.
  module CachebusterFilter
    # Usage example:
    #
    # {{ "/style.css" | cachebuster }}
    # {{ "/style.css" | cachebuster | absolute_url }}
    def cachebuster(filename)
      sha256 = Digest::SHA256.file(
        File.join(@context.registers[:site].dest, filename)
      )

      "#{filename}?#{sha256.hexdigest[0, 6]}"
    rescue StandardError
      # Return filename unmodified if file was not found
      filename
    end
  end
end

Liquid::Template.register_filter(Jekyll::CachebusterFilter)

I ran my site locally and it worked - my css file had a fingerprint appended.

<link rel="stylesheet" href="/css/main.css?b0763bce">

I pushed it to my staging site and it didn’t work - no fingerprint. Which must mean the filename wasn’t found. I then went through a few rounds of debugging with ChatGPT - adding Jekyll logging, etc - and finally concluded that ChatGPT’s initial direction (which I ignored) was correct - when the filter runs the compiled CSS file doesn’t exist yet. It works locally because the previous build had already generated the file.

A quick hacky fix was to run jekyll build twice in staging, which did work - but is obviously not a great solution. Instead I needed to either get access to the compiled CSS file or generate the digest from the source SASS files. I don’t think it’s possible to access the compiled CSS file - because it doesn’t necessarily exist yet - so instead I started to look at the jekyll-sass-converter code in more detail.

At a high level the filter is invoked on the output of the SASS converter - in my case, /css/main.css. It then needs to

1. Find the source manifest file - in my case, /css/main.scss
2. Find all referenced SASS files

Instead of trying to parse out the SASS files I opted to simply look at all the files in my /_sass directory. The plugin allows you to alter the source directory for the SASS files (and add others) so ideally I need to interact with the plugin directly and get the config that way - I didn’t want to duplicate the code to parse the plugin’s config. Luckily this is something supported by Jekyll.

# frozen_string_literal: true

require 'digest'

module Jekyll
  # Jekyll assets sass_digest filter
  module SassDigestFilter
    # Usage example:
    #
    # {{ "/style.css" | sass_digest }}
    # {{ "/style.css" | sass_digest | absolute_url }}
    def sass_digest(filename)
      site = @context.registers[:site]
      return site.data['sass_digest'][filename] if site.data.dig('sass_digest', filename)

      scss_file = site.in_source_dir("#{File.dirname(filename)}/#{File.basename(filename, '.css')}.scss")
      unless File.exist?(scss_file)
        Jekyll.logger.warn 'SassDigest:', "#{scss_file} does not exist"
        return filename
      end

      scss_converter = site.find_converter_instance(Jekyll::Converters::Scss)
      if scss_converter.nil?
        Jekyll.logger.warn 'SassDigest:', "#{Jekyll::Converters::Scss} converter not found"
        return filename
      end

      files = [site.in_source_dir(filename.sub(/\.css$/, '.scss'))]
      scss_converter.sass_load_paths.each do |path|
        Dir.glob("#{site.in_source_dir(path)}/**/*.scss") do |sass_file|
          files << sass_file
        end
      end

      site.data['sass_digest'] ||= {}
      site.data['sass_digest'][filename] = "#{filename}?#{digest(files)}"
    end

    private

    def digest(files)
      combined = files.sort.map { |f| File.read(f) }.join
      Digest::SHA256.hexdigest(combined)[0, 8]
    end
  end
end

Liquid::Template.register_filter(Jekyll::SassDigestFilter)

The last piece that I had to figure out was how to cache the computed digest within a single build - it turns out the site object has a data hash that makes this straightforward.

I’m using this for now, but I’m not confident that this is the correct approach. I want to see if it’s possible to add this to the jekyll-sass-converter plugin directly.

Discussion

I previously wrote about my experience attempting to use Github Actions to post a tweet every time I publish a new post on my self-hosted Jekyll/S3/Cloudfront blog. I managed to get to a working solution that was too complicated, so I’m trying another approach. I was following this post by Dave Brock where he described using the commit message as the entire tweet - so every commit message and git push is a tweet. I dismissed it as too simple, but now that I’ve seen how complicated the alternative is I’m going to try something similar.

Here is the new, simplified, workflow I envisioned:

1. When I am ready to add a new post to git I run a Ruby script that generates the commit message
2. When I deploy to product a step in the production deploy Github Action workflow tweets out the commit message

The first step is to write a Ruby script that generates the commit message. Identifying the post title and full url seems straightforward, but Jekyll allows you lots of flexibility around generating URLs, so I didn’t want to optimize for one specific use case. It turns out that I can instantiate the jekyll objects and tell it to parse the post itself.

#!/usr/bin/env ruby
# frozen_string_literal: true

require 'uri'
require 'jekyll'

# Get uncommitted post files
status_lines = `git status --porcelain _posts`.lines
new_posts = status_lines.select { |line| line.start_with?('??') }.map { |line| line.split.last }

if new_posts.empty?
  puts 'No new, uncommitted post found.'
  exit 0
end

# Initialize a site object from _config.yml
site_config = Jekyll.configuration({ quiet: true })
site = Jekyll::Site.new(site_config)

# Path to the new post
post_path = File.expand_path(new_posts.first)
document = Jekyll::Document.new(post_path, { site: site, collection: site.posts })
document.read

# Git add and commit
commit_message = "Blogged: #{document.title} #{URI.join(site_config.fetch('url'), document.url)}"
system('git', 'add', post_path)
system('git', 'commit', '-m', commit_message)

puts "Committed with message:\n#{commit_message}"

A nice part of this approach is that I can easily test the script locally.

A key piece of nuance is that not every commit is a new post - sometimes I’m editing an old post (fixing a typo, updating a link, etc), or I’m making a change to the site itself (Jekyll config, css, etc). I wanted to update my Github Action workflow to look for a commit message with the Blogged: prefix. Github Actions exposes the latest commit message via a variable - github.event.head_commit.message - but it’s not populated on manual workflows (which is what I’m using for a production deploy). So instead I need to manually fetch the latest git commit.

- name: Get latest commit message
  id: get_commit
  run: |
    msg=$(git log -1 --pretty=%B)
    echo "message=$msg" >> $GITHUB_OUTPUT

- name: Tweet the new post
  if: startsWith(steps.get_commit.outputs.message, 'Blogged:')
  uses: nearform-actions/github-action-notify-twitter@master
  with:
    message: ${{ steps.get_commit.outputs.message }}
    twitter-app-key: ${{ secrets.TWITTER_CONSUMER_API_KEY}}
    twitter-app-secret: ${{ secrets.TWITTER_CONSUMER_API_SECRET}}
    twitter-access-token: ${{ secrets.TWITTER_ACCESS_TOKEN }}
    twitter-access-token-secret: ${{ secrets.TWITTER_ACCESS_TOKEN_SECRET }}

This is a much simpler approach to what I had before, and it’s much easier to debug and predict what is going to happen. The only downside is that I need to be careful with my git commits before pushing to production - for example, if I fix a typo before pushing to production I need to be careful to amend the original commit.

Discussion

This site is built with Jekyll and hosted on Amazon S3, with Cloudfront as the CDN. I recently did some work to make the deployments automated with Github Actions.

I wrote about that experience already, but the current workflow is:

1. Every push to main is deployed to a staging environment (I don’t use pull requests)
2. Deployments to production is handled through a github action workflow that is manually triggered

I previously used Blogger and WordPress to manage my blog and both of those had the option to automatically tweet about new posts, but there is no built-in mechanism to do that with Jekyll (if you’re self-hosting). Of course I could manually tweet about every new post, but what’s the fun in that?

Here is the workflow I envisioned:

1. When I trigger the deployment to production some Github Action is triggered that checks for any new posts
2. For every new post (usually just one), extract the title and URL of the post
3. Tweet about it

How hard could it be? (Spoiler: very)

I read through this post by Dave Brock who had a similar goal, but he simply put his desired tweet as the commit message. I didn’t really like that approach - Jekyll already knows the post title and URL, and it’s all available in git - so I should be able to get that information and tweet it out.

The first idea I had was to start using Github releases to track every new ‘publication’ - meaning when I deploy to production a new release is created, and I can check for any new posts introduced between this latest release and the previous one. I started down that path but then I realized that it’s actually too heavy-handed for what I wanted - I’m really only using the existance of the tag.

I started off creating a new tag on every production deploy, so just extending my existing workflow:

- name: Create Release Tag
  env:
    GH_TOKEN: ${{ secrets.GITHUB_TOKEN }}
  run: |
    TAG_NAME=production-release-$(date +'%Y.%m.%d.%H%M')
    git tag "$TAG_NAME"
    git push origin "$TAG_NAME"

The GITHUB_TOKEN is automatically exposed by Github Actions, so that felt like I was on the right track. Instead of extending the production workflow further I decided to have a dedicated ‘tweet’ workflow that is triggered by the creation of a new tag.

on:
  push:
    tags:
      - 'production-release-*'

In order to test this new workflow I simply had it print out the newly created tag name. However, when I tested it the workflow never triggered. Apparently this is by design:

GitHub does not trigger a new workflow run when a tag is pushed using the default GITHUB_TOKEN (which you’re using via GH_TOKEN). This is a deliberate design choice to prevent infinite loops between workflows.

Not to worry, I did some more reading and discovered I can set the trigger for my tweet workflow to explicitly kick off when the production deployment workflow completes. That’s arguably even cleaner, since I’m not relying on side effect of the deployment - I’m relying on the deployment workflow itself. The only annoying bit is that I need to explicitly check if the workflow run was successful.

on:
  workflow_run:
    workflows: ["Deploy to production on manual trigger"]
    types:
      - completed
jobs:
  tweet:
    if: ${{ github.event.workflow_run.conclusion == 'success' }}
    runs-on: ubuntu-latest
    ...

I tested this and ran into an obscure error:

Error
No event triggers defined in `on`

Again, apparently this is a known issue (according to ChatGPT - I didn’t find this note in the documentation):

workflow_run only triggers on workflows that run in response to events like push, pull_request, schedule, etc. It does not trigger for workflows started manually via workflow_dispatch.

This is a known limitation in GitHub Actions: workflow_run does not support triggering on workflows that were manually triggered (workflow_dispatch).

I had the option of trying to use a repository_dispatch - which is manually calling a Github API to trigger the workflow via an HTTP API - or simply adding the tweet steps to the existing workflow. Since having a separate workflow wasn’t particularly important I opted to try that first.

At this point I needed to parse the current and previous tags, determine if there was a new post in the changeset, extract the title and URL of the post(s), and invoke the proper twitter API. The git part of this was reasonably straightforward after I read through some of the documentation:

- name: Get previous production release tag
  id: calculate_previous_release_tag
  run: |
    TAG=$(git tag --list 'production-release-*' --sort=-creatordate --no-contains | head -n 1)
    echo "previous_release_tag=$TAG" >> $GITHUB_OUTPUT

- name: Identify new published post
  id: identify_new_post
  run: |
    CURRENT_TAG=${{ github.ref_name }}
    PREVIOUS_TAG=${{ steps.calculate_previous_release_tag.outputs.previous_release_tag }}

    echo "The new release tag is: $CURRENT_TAG"
    echo "The previous release tag is: $PREVIOUS_TAG"

    POST_PATH=$(git diff --name-only --diff-filter=A "$PREVIOUS_TAG" "$CURRENT_TAG" -- _posts/ | head -n 1)
    if [ -n "$POST_PATH" ]; then
      echo "Found new post: $POST_PATH"
      echo "post_path=$POST_PATH" >> $GITHUB_OUTPUT
    fi

Extracting the title and URL of the post was not that straightforward. I was hoping there was a jekyll command to get that metadata, but nothing like that exists (although I’m sure you could write a plugin to do that nicely). I started to do this with a bunch of bash scripts but it felt super shaky, so I wrote a simple ruby script instead.

content = File.read(options[:post_path])
post_metadata = YAML.safe_load(content.split(/^---\s*$/, 3)[1])

if options[:extract] == 'title'
  raise "#{options[:post_path]} does not contain a title" unless post_metadata.key?('title')

  puts post_metadata['title']
else
  raise "#{options[:post_path]} does not contain a permalink" unless post_metadata.key?('permalink')

  site_metadata = YAML.safe_load(File.read('_config.yml'))
  puts URI.join(site_metadata['url'], post_metadata['permalink'])
end

This script also feels a bit shaky, but less so than having to write bash to remove comments out of a YAML file. At this point I finally had the title and URL of the newly added post, all extracted from the git history. All that was left was to use the Github Action to send Twitter notifications.

- name: Tweet the new post
  if: steps.identify_new_post.outputs.post_path != ''
  uses: nearform-actions/github-action-notify-twitter@master
  with:
    message: "🚀 Blogged: ${{ steps.extract_post_info.outputs.post_title }}\n\n${{ steps.extract_post_info.outputs.post_url }}"
    twitter-app-key: ${{ secrets.TWITTER_CONSUMER_API_KEY}}
    twitter-app-secret: ${{ secrets.TWITTER_CONSUMER_API_SECRET}}
    twitter-access-token: ${{ secrets.TWITTER_ACCESS_TOKEN }}
    twitter-access-token-secret: ${{ secrets.TWITTER_ACCESS_TOKEN_SECRET }}

And at this point I decided I really hate this entire solution: it’s way too complicated. I think the approach used by Dave Brock is actually much better - I can simply write commit messages with a certain format and invoke the Github Action as part of production releases if that format is present. I can easily write a ruby script to write the commit message which will be much easier to test and debug.

Read on to part 2 where I implement this new approach.

Discussion