Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

networking
server
network

What is time to live (TTL)?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Time to live (TTL) is a mechanism of associating a time-span with data packets in a network or computer system. It inhibits the indefinite circulation of those messages in the network by limiting their lifetime or lifespan.

Implementation

In this implementation, the network structure is represented by n-ary trees. The server can be at any node in the tree. We want to determine which nodes will successfully receive a message from the server, given a specific TTL value.

Let’s try to understand this better with an illustration:

Let’s see how we might implement this functionality:

  1. Initialize the adjacency list.

  2. Perform DFS on the root node and add every node’s parents and children to the adjacency list.

  3. Mark the server node as the result and iterate TTL times over the adjacency list, starting from the server node.

  4. During iteration, we will get all the parents and children nodes of the current node and mark them as the result.

  5. When the loop ends, you’ll have the nodes that are TTL distance from the server as the result.

using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public List<TreeNode> children;
public TreeNode(int x) {
val = x;
children = new List<TreeNode>();
}
};
class Solution {
public static List<int> getDevices(TreeNode root, TreeNode server, int ttl) {
Dictionary<int, List<int>> neighbors = new Dictionary<int, List<int>>(); // Adjacency list
dfs(null, root, neighbors);
// BFS to find nodes
List<int> bfs = new List<int>();
bfs.Add(server.val);
HashSet<int> lookup = new HashSet<int>(bfs);
for (int i = 0; i < ttl; i++) {
List<int> temp = new List<int>();
foreach(int node in bfs)
foreach(int nei in neighbors[node])
if (lookup.Contains(nei) == false)
temp.Add(nei);
bfs = temp;
lookup.UnionWith(bfs);
}
return bfs;
}
private static void dfs(TreeNode parent, TreeNode child, Dictionary<int, List<int>> neighbors) {
// DFS to build adjacency list
if (child == null){
return;
}
if (parent != null) {
if (!neighbors.ContainsKey(parent.val))
neighbors[parent.val] = new List<int>();
if (!neighbors.ContainsKey(child.val))
neighbors[child.val] = new List<int>();
neighbors[parent.val].Add(child.val);
neighbors[child.val].Add(parent.val);
}
for (int i = 0; i < (child.children).Count; i++)
dfs(child, child.children[i], neighbors);
}
public static void Main() {
// Driver Code
TreeNode root = new TreeNode(1);
root.children.Add(new TreeNode(2));
root.children.Add(new TreeNode(3));
root.children.Add(new TreeNode(4));
root.children[0].children.Add(new TreeNode(5));
root.children[0].children[0].children.Add(new TreeNode(10));
root.children[0].children.Add(new TreeNode(6));
root.children[0].children[1].children.Add(new TreeNode(11));
root.children[0].children[1].children.Add(new TreeNode(12));
root.children[0].children[1].children.Add(new TreeNode(13));
root.children[2].children.Add(new TreeNode(7));
root.children[2].children.Add(new TreeNode(8));
root.children[2].children.Add(new TreeNode(9));
TreeNode server = root.children[0].children[1];
int ttl = 2;
Console.WriteLine("The TTL value will expire on node IDs: [{0}]", string.Join(", ", getDevices(root, server, ttl).ToArray()));
}
}
TTL Implementation

RELATED TAGS

networking
server
network
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring