Domain names
Domain names
How the DNS protocol works. Plus the Bachmann–Landau notations for algorithms.
Hi Friends,
Welcome to the 17th issue of the Polymathic Engineer newsletter.
Today we will talk about:
How the DNS protocol works
Benchmarking algorithms with the Bachmann–Landau notations
Coding challenge
Three interesting tweets
Domain Name System
DNS is the protocol converting human-readable website names into IP addresses. Looking at it as a black box, it could be considered as a phone book, but for the internet.
To understand how it works, consider what happen when a user that types the address of the www. xyz .com website in a browser. In this scenario, the browser represents a DNS client that needs the website's address.
The DNS protocol allows getting the website's address in 5 steps:
The browser checks its local cache to see if it already has the corresponding IP address. If the IP address isn't cached, it sends a DNS request to the DNS resolver.
An Internet Service Provider (ISP) usually hosts this dedicated server.
The DNS resolver checks its local cache. If the corresponding IP address isn't cached, it tries to solve the request iteratively. Iteratively means it tries to contact different servers until it doesn't get the IP address.
First, the DNS resolver sends a request to a root name server. This is a server mapping the top-level domain ".com" to the address of the name server responsible for that domain. The address of the ".com" name server is sent back to the DNS resolver.
The DNS resolver sends a resolution request for "mywebsite .com" to the ".com" name server. The ".com" name server maps "mywebsite .com" to the address of the authoritative name server responsible for it. This address is sent back to the DNS resolver.
The DNS resolver sends a resolution request for "www. mywebsite .com" to the authoritative name server. The authoritative name server then returns the destination IP address. If the request also includes a subdomain, a further step is required. The authoritative name server returns the server's IP address responsible for the subdomain. And an additional request by the DNS resolver is then performed.
The whole resolution process requires many round trips, and it is time-consuming. For this reason, all the components make extensive use of caching. It's essential to set the expiration time of all those cache entries correctly. This expiration time is known as time-to-live (TTL) and has a trade-off. If the TTL is too high, the clients won't be able to see a change for a long time. If the TTL is too low, the load on name servers and the average response time increase.
Bachmann–Landau Notations
Bachmann–Landau is a family of mathematical notations that includes:
• Big O (Oh)
• Big Ω (Omega)
• Big ϴ (Theta)
They are commonly used to measure the space and time complexity of algorithms. To understand how they differs, Consider the Insertion Sort algorithm applied to an array of length n.
The algorithm partitions an input array into 2 subarrays: one sorted and one unsorted. At each step the 1st element of the unsorted subarray is inserted into its proper place in the sorted one. Here is what happen at each step: - the blue cell represents the sorted subarray. - the red item is moved from the unsorted to the sorted subarray - the blue items are shifted to the right to make space for the red one - the black items are unmoved
The algorithm makes n-1 steps. In the worst case, the algorithm moves all the items in the sorted subarray at each step to make space for the current unsorted one. Let's analyze the Insertion Sort worst-case execution with the Bachmann–Landau notations.
O-notation provides an approximate definition of less-than or equal-to (<=). We can say that Insertion Sort's worst-case complexity is O(n²), because it takes a quadratic number of steps at most. But we could also say O(n³) because big O establishes only an upper bound.
Ω-notation provides an approximate definition of greater-than or equal-to (>=). We can say that Insertion Sort's worst-case complexity is Ω(n²) because it takes at least a quadratic number of steps. But we could also say Ω(n) because Ω establishes only a lower bound.
ϴ-notation provides an approximate definition of equality (=). We can say that Insertion Sort's worst-case complexity is ϴ(n²) because it takes precisely a quadratic number of steps. ϴ is a more robust notion than O and Ω, defining a tight bound (both upper and lower).
The coding challenge for this week was Asteroid Collision. The problem gives as input an array of integers representing asteroids in a row and asks to find out the state of the asteroids after all collisions.
The sign of the integer represents the asteroid's direction (positive = right, negative = left), and two asteroids collide if one goes to the right and the other to the left.
After a collision, the bigger asteroid (in absolute value) survives, and the smaller one explodes. Both asteroids explode, of their absolute value is equal.
From the problem description, the proper way to calculate the final state is to iterate over all the asteroids and simulate the possible collisions. Furthermore, since all the collisions occur from right to left, it looks clear how a stack data structure can help.
The algorithm requires iterating over all the asteroids, and it is straightforward:
If the stack is empty or there is no collision between the current asteroid and the last inserted one, push the current asteroid into the stack
If there is no collision between the current asteroid and the last inserted one, apply the collision logic
Each time a collision occurs, the collision logic needs to be applied until there is no more collision between the top of the stack and the current asteroid or the current asteroid explodes. Once all the asteroids have been processed, the final state corresponds to the content of the stack from bottom to top.
Here is the code for this solution:
The time complexity of the solution is O(N), where N is the number of asteroids. Indeed each asteroid is processed, pushed, and popped from the stack at most once.
The space complexity is O(N) because potentially all the asteroids could be pushed into the stack.
The coding challenge for the next week is Removing Stars From a String.
Interesting Tweets
The worst thing would be accepting a management position only for the salary without having a true interest or aspiration.
In that case you not only can make yourself unhappy, but also other people.
Continuous learning is crucial in software engineering, but you can't learn everything.
Some things will have an bigger impact, others less. So both learning and knowing what to learn are crucial.
