Created
December 17, 2018 17:35
-
-
Save priyankvex/685ee934338bee9fa470da7acfcb4598 to your computer and use it in GitHub Desktop.
Scamming the coding interview: Problem 005: File Syncing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Scamming the coding interview | |
""" | |
from hashlib import md5 | |
class MerkerFile(object): | |
def __init__(self): | |
self.content = "" | |
self.hash = "" | |
self.children = [] | |
self.is_dir = None | |
self.parent = None | |
def set_content(self, new_content): | |
if self.is_dir: | |
raise Exception("Can't set the contents of a directory") | |
self.content = new_content | |
self.recalculate_directory_hash() | |
def recalculate_directory_hash(self): | |
parent = self.parent | |
if not self.is_dir: | |
self.hash = md5(self.content.encode()).hexdigest() | |
while parent: | |
children = parent.children | |
collated_hash = "" | |
for child in children: | |
collated_hash += child.hash | |
parent.hash = md5(collated_hash.encode()).hexdigest() | |
parent = parent.parent | |
def add_file_to_directory(self, directory): | |
directory.children.append(self) | |
self.parent = directory | |
self.recalculate_directory_hash() | |
def get_files_that_are_different(root_1, root_2, file_changes_for_system_1, file_changes_for_system_2): | |
if not root_1 and not root_2: | |
return file_changes_for_system_1, file_changes_for_system_2 | |
if not root_1 or not root_2: | |
file_changes_for_system_1.append(root_2) | |
file_changes_for_system_2.append(root_1) | |
return file_changes_for_system_1, file_changes_for_system_2 | |
if root_1.hash != root_2.hash: | |
file_changes_for_system_1.append(root_2) | |
file_changes_for_system_2.append(root_1) | |
root_1_children = root_1.children | |
root_2_children = root_2.children | |
len_diff = abs(len(root_1_children) - len(root_2_children)) | |
if len(root_1_children) > len(root_2_children): | |
root_2_children = root_2_children + [None for i in range(0, len_diff)] | |
elif len(root_2_children) > len(root_1_children): | |
root_1_children = root_2_children + [None for i in range(0, len_diff)] | |
for child_1, child_2 in zip(root_1_children, root_2_children): | |
get_files_that_are_different(child_1, child_2, file_changes_for_system_1, file_changes_for_system_2) | |
return file_changes_for_system_1, file_changes_for_system_2 | |
if __name__ == '__main__': | |
# create a directory structure on the first computer | |
root_directory = MerkerFile() | |
root_directory.is_dir = True | |
file1 = MerkerFile() | |
file1.is_dir = False | |
file1.add_file_to_directory(root_directory) | |
file1.set_content("owl city rocks!") | |
file2 = MerkerFile() | |
file2.is_dir = False | |
file2.add_file_to_directory(root_directory) | |
file2.set_content("owl city rocks again!") | |
directory_2 = MerkerFile() | |
directory_2.is_dir = True | |
directory_2.add_file_to_directory(root_directory) | |
file3 = MerkerFile() | |
file3.is_dir = False | |
file3.add_file_to_directory(directory_2) | |
file3.set_content("owl city rocks!") | |
# create a directory structure on the second computer | |
root_directory_2 = MerkerFile() | |
root_directory_2.is_dir = True | |
file1_2 = MerkerFile() | |
file1_2.is_dir = False | |
file1_2.add_file_to_directory(root_directory_2) | |
file1_2.set_content("owl city rocks!") | |
file2_2 = MerkerFile() | |
file2_2.is_dir = False | |
file2_2.add_file_to_directory(root_directory_2) | |
file2_2.set_content("owl city rocks again!") | |
directory_2_2 = MerkerFile() | |
directory_2_2.is_dir = True | |
directory_2_2.add_file_to_directory(root_directory_2) | |
file3_2 = MerkerFile() | |
file3_2.is_dir = False | |
file3_2.add_file_to_directory(directory_2_2) | |
# This is the only file that is different | |
file3_2.set_content("owl city rocks! pop") | |
# Now to know the files that have changed, we can just compare the two trees | |
# and effectively know which files have changed and need syncing. | |
file_changes_for_system_1, file_changes_for_system_2 = get_files_that_are_different( | |
root_directory, root_directory_2, [], [] | |
) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment