Coding Challenge #13 - diff

Coding Challenge #13 - diff

This challenge is to build your own diff command line tool.

The diff tool has been part of every software developers tool box since it was initially released in June 1974. How’s that for legacy code that’s still providing value today!

Coding Challenges Live - Cohort Training Course

Would you like to tackle one of these coding challenges with a cohort of other software engineers - and me?

I’m building a three-week cohort-based course around a coding challenges On the course you’ll learn:

  1. How the application is built - the data structures, algorithms, and architecture behind it.
  2. How to tackle the project in stages - breaking it down into a series of steps and testing as you go.
  3. How to collaborate with other software engineers - reviewing their code and offering feedback on their solutions.

If that sounds interesting, you can register your interest and provide feedback on which challenge you’d like to cover here: https://maven.com/forms/cfd972

I’ll be offering a 50% discount to everyone who fills out the survey.

Ok let’s get into the challenge of building diff….

The Challenge - Building diff

Fundamentally like all the Unix command line tools diff does a very simple job. If we check the man output for diff (man diff), we get:

The **diff** utility compares the contents of file1 and file2 and writes 
to the standard output the list of changes necessary to convert one 
file into the other.? No output is produced if the files are identical.        

The core algorithm that is commonly used is described in "An O(ND) Difference Algorithm and its Variations" by. Eugene W. Myers. There is also the Hunt-Szymanski Algorithm for LCS which was originally used.

The Meyers algorithm is the default used in git. You probably didn’t know - I didn’t before writing this - that git also supports three other algorithms. If your curious to learn more check out the paper: How different are different diff algorithms in Git?

Step Zero

Like all great software development, Coding Challenges is zero indexed! In this step you’re going to set your environment up ready to begin developing and testing your solution.

I’ll leave you to setup your IDE / editor and programming language of choice. After that please ensure you have your favourite unit testing library ready to go - for this challenge we’re going to write unit tests first.

Once that’s done you can download some test files for the later steps from my Dropbox.

Step 1

In this step your goal is to implement an algorithm to solve the longest common subsequence problem with a single string. The Wikipedia article on the longest common subsequence provides some pseudo code that might help or you can dig into the papers linked earlier in the challenge.

You should implement some unit tests for your algorithm, here are a few test cases:

String 1: "ABCDEF"
String 2: "ABCDEF"
Expected LCS: "ABCDEF"
String 1: "ABC"
String 2: "XYZ"
Expected LCS: ""
String 1: "AABCXY"
String 2: "XYZ"
Expected LCS: "XY"
String 1: ""
String 2: ""
Expected LCS: ""
String 1: "ABCD"
String 2: "AC"
Expected LCS: "AC"        

Please think carefully about any others you might need. Hint think carefully about the time and space complexity of the algorithm and consider some tests with that in mind.

Once you’re happy you can find the LCS in a pair of strings move on to step 2.

Continued....

You can find Step 2 and beyond on the?Coding Challenges?website as?Write You Own diff

Or if you'd rather get the whole challenge delivered to you inbox every week, you can subscribe on the?Coding Challenges Substack.

Mohit Jain

Software Tech Lead @Zemetric | ex Co-Founder @Evy Energy (Acquired)

1 年

John Crickett, here's my solution in Typescript: https://github.com/jainmohit2001/coding-challenges/tree/master/src/13 It's great to see those basic concepts of Dynamic Programming come together in harmony to create these real-life tools.

Sarah Gruneisen ??

Engineering Manager | Leadership Trainer | Author | Complexity Buster & Motivator | Keynote Speaker | Certified Leadership Coach | 20+ in Software Engineering | 15+ in Leadership | ? Addict

1 年

Your weekly coding challenges are an excellent strategy for developers to improve their skills. So nice to see ??

Omar Halabieh

Tech Director @ Amazon Payment Services | I help professionals lead with impact and fast-track their careers through the power of mentorship | #1 LinkedIn Arab World Creator in Management & Leadership

1 年

I love your approach to leveling up coding skills through practical application building John Crickett

Mohamed Alsoudani

Head of Engineering @ Tap

1 年

This is great! Diffing is a super useful algorithm.

Rūtenis Raila

Freelance web developer

1 年

That's a great way to learn, for sure. One thing I would add to the list: build your own framework (don' try to replicate the efficiency and robustness of a framework, focus on more on understanding how the web works in general). I recently found Dan Abramov's (React Core team) guide on rebuilding React Server Components from scratch. The guide is available on GitHub and takes you on an interesting journey through web development from the early 2000s to the present day.

要查看或添加评论,请登录

John Crickett的更多文章

  • From The Challenges - Memcached Server

    From The Challenges - Memcached Server

    ?? ?? Happy Birthday Coding Challenges - Two Years Old! ?? ?? Coding Challenges is turning two this week! To celebrate…

    13 条评论
  • Coding Challenge #85 - Time Zone Converter

    Coding Challenge #85 - Time Zone Converter

    Coding Challenge #85 - Time Zone Converter This challenge is to build your own Time Zone Converter. That is a tool to…

    12 条评论
  • From The Challenges - IRC Client

    From The Challenges - IRC Client

    Welcome To Coding Challenges - From The Challenges! In this Coding Challenges “from the challenges” newsletter I’m…

    5 条评论
  • Coding Challenge #84 - Mandelbrot Set Explorer

    Coding Challenge #84 - Mandelbrot Set Explorer

    This challenge is to build your own Mandelbrot set explorer. The Mandelbrot set is a set of fractals that exhibit great…

    4 条评论
  • From The Challenges - Cat

    From The Challenges - Cat

    Welcome To Coding Challenges - From The Challenges! In this Coding Challenges “from the challenges” newsletter I’m…

    7 条评论
  • Coding Challenge #83 - Markdown Presentation Tool

    Coding Challenge #83 - Markdown Presentation Tool

    Coding Challenge #83 - Markdown Presentation Tool This challenge is to build your own version of Go’s Present or…

    3 条评论
  • From The Challenges - Shell

    From The Challenges - Shell

    Welcome To Coding Challenges - From The Challenges! In this Coding Challenges “from the challenges” newsletter I’m…

    3 条评论
  • Coding Challenge #82 - Markdown To PDF Editor

    Coding Challenge #82 - Markdown To PDF Editor

    Coding Challenge #82 - Markdown To PDF Editor This challenge is to build your own tool to convert markdown to PDF. It…

    14 条评论
  • From The Challenges - Diff

    From The Challenges - Diff

    Welcome To Coding Challenges - From The Challenges! In this Coding Challenges “from the challenges” newsletter I’m…

    7 条评论
  • Coding Challenge #81 - Brainf*ck Interpreter

    Coding Challenge #81 - Brainf*ck Interpreter

    This challenge is to build your own Brainf*ck Interpreter. Just in case you’re wondering, yes the * should be a u, but…

    34 条评论

社区洞察

其他会员也浏览了