[Solution]Problem 47:File Syncing Code [Google]]
A bit of a curveball, but a question you should know
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
I hope y’all had fun with this question yesterday,
It’s not your typical Leetcode-style question, but it can be very helpful to mix things up. This type of question will really work on your algorithm development skills. I like such questions because they test your problem-solving ability over your ability to memorize 300+ Leetcode questions (seems like there are a lot of LinkedIn gurus teaching that recently).
Problem
This problem was asked by Google.
Implement a file syncing algorithm for two computers over a low-bandwidth network. What if we know the files in the two computers are mostly the same?
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https:/ount.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-
Step 0: Understanding the Problem Domain
Before we get into designing algorithms, it is always prudent to look at what the problem domain is. When would such an algorithm be useful/needed? Let’s take an example.
Consider video games. Every time a new patch/update drops, you want your game to be updated. If you had to reinstall all the game files for updates, things would be very slow and costly. And you’d spend a lot of time setting up the game to your liking again. No one is happy about this (except for Internet Service providers, who get to charge you more money).
To make things more efficient, what the servers do is that they go through your game files and compare them to the updated files on their servers. They only update the parts that are different. So far so good.
This should give you a clear understanding of where to go next. How can we efficiently compare the differences in the two files? Clearly, just sending the master files over the network will not be smart. What can we do to minimize the data transferred across the network?
Step 1: Computing Differences
Really this is the first major problem that we must solve to create our solution. How can we compute the differences between two text files? To answer this, first let’s define a fundamental problem, what even is a difference?
Let’s look at files in the first place. We can say that two files are separated from each other by a finite number of insertions and deletions. If we can delete some content from file A, and then add some other content to it, then we can get to be identical to file B. Nothing too strange there, but take a second to confirm it for yourself.
We are also helped by the question because it tells us that the files are mostly similar. For simplicities sake, let’s assume we want to update file B to match file A. This means that we want to implement the following program that does the following-
Look through the files and find the parts where our files differ.
Purge the parts that are different in file B.
Send the new parts of file A and add those to file B at the relevant locations.
Keep in mind the differences in content might be at the beginning, middle, or end. Our algorithm for spotting the differences should be able to accommodate them all. This is where we start doing the next part. You will see such an approach used in a lot of areas so make sure you pay special attention.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.