For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the Daily Coding Problem (DCP) and decided to give it a shot.
The code is in C#.
How it works?
The folks at DCP send you a problem that was asked at a top company everyday for you to solve. The premium membership also offers the opportunity to verify your solution.
Problem #2
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node: def init(self, val, left=None, right=None): self.val = val self.left = left self.right = right The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right')) assert deserialize(serialize(node)).left.left.val == 'left.left'
My solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Task03
{
public class Program
{
private const string Empty_Marker = "1";
public static void Main(string[] args)
{
var node = new Node("root", new Node("left", new Node("left.left")), new Node("right"));
var serialized = Serialize(node);
Console.WriteLine(serialized);
node = Deserialize(serialized);
Console.WriteLine(node.Left.Left.Value);
}
public static string Serialize(Node node)
{
if (node == null)
{
return Empty_Marker + '-';
}
var builder = new StringBuilder();
builder.Append($"{node.Value}-");
builder.Append(Serialize(node.Left));
builder.Append(Serialize(node.Right));
return builder.ToString();
}
public static Node Deserialize(string serializedNode)
{
var nodes = serializedNode
.Split('-', StringSplitOptions.RemoveEmptyEntries)
.ToArray();
var queue = new Queue<string>(nodes);
var node = DeserializeNode(queue);
return node;
}
private static Node DeserializeNode(Queue<string> nodes)
{
if (nodes.Peek() != null)
{
var nextNode = nodes.Dequeue();
if (nextNode == Empty_Marker)
{
return null;
}
var node = new Node(nextNode);
node.Left = DeserializeNode(nodes);
node.Right = DeserializeNode(nodes);
return node;
}
return null;
}
}
Explanation
For the serialization, we traverse the tree depth first and add the current node's value to the serialized string. When we reach a node which is null (basically it's parent doesn't have a child), we put an Empty_Marker
to signal that there is no node here. This works assuming the symbols for Empty_Marker
and '-' are not going to be used in any node's value.
For the deserialize, we split the given string and put the results in a queue. Then build the tree depth first, getting through the queue's first element and stopping when we reach an Empty_Marker
I will try to do the daily problem everyday, but sometimes life gets in the way :)
Solutions are posted in my github account
.
Feel free to leave a like and let me know in the comments if I should continue to post my solutions.
If you also have any better solution in mind, by all means share it, so we can learn from each other.
Top comments (10)
In Javascript, JSON serialization/unserialization is already supported, so this felt like cheating:
Exactly man, I looked at it, and thought, what?? They're asking one thing that already exists?
The tricky part is to make it work for arbitrary values, i.e. drop the assumption the symbols for Empty_Marker and '-' are not going to be used in any node's value.
Here's such a solution in Perl, tests included:
Python solution defining
__repr__
, which is meant for exactly this purpose:Edit: Included test from problem statement in the code, so that it should now be ready for copy and paste into file and
python3 -i <file>
. While we are at it, implemented__eq__
and__hash__
, so that we can assert even stronger tests.Quite impressive, thank you!
I think this is a minimal and fast solution :
Go solution. Its a bit verbose as it does not have optional/default params.
Here's my C# solution
Python solution using recursion.
My first time to see someone using Lua, thanks for the code, cool!