Recursive decomposition
Recursive decomposition
Six recursion-friendly data structures. Plus an introduction to key-value storages.
Hi Friends,
Welcome to the 22th issue of the Polymathic Engineer newsletter.
Today we will talk about:
Recursive friendly data structures
Key-value data storages
Coding challenge
Interesting tweets
Recursive decomposition
Recursion is not inefficient, but it is often misused. For example, recursion is great when a problem or data structure is inherently recursive.
The following 6 objects have a common trait. They are inherently recursive and decomposable into smaller instances of the same type. Such recursive decomposition stops at the simplest object of that type and is a smell for using recursive algorithms.
Strings: Deleting the 1st character from a string, you get a shorter string. The base case is an empty string. Strings are recursive objects.
Trees: Deleting the root of a tree, you get a set of smaller trees. Deleting any leaf of a tree, you get a slightly smaller tree. The base case is a single tree node. Trees are recursive objects.
Graphs: Deleting any vertex from a graph, you get a smaller graph. Dividing the vertices of a graph into 2 groups and cutting all edges between the 2 groups, you get 2 smaller graphs. The base case is a single vertex. Graphs are recursive objects.
Subsets. Consider all subsets of the elements {0,...,n}. Deleting the element n from each of those subsets, you get all subsets made of the elements {0,..., n−1}. The base case is an empty set. Subsets are recursive objects.
Points: Taking a cloud of points and draw a line separating them into 2 groups, you get 2 smaller clouds of points. The base case is a single point. Sets of points are recursive objects.
Polygons: Inserting a diagonal between 2 nonadjacent vertices of a polygon, you get 2 smaller polygons. The base case is a triangle. Polygons are recursive objects.
Key-value storages
Key-value storages are widely used in distributed systems design.
They behave much like hash tables data structures. They store collections of key-value pairs, mapping from keys to arbitrary values. Both keys and values can be anything, ranging from simple objects like strings to complex compound objects.
The main advantages of key-value storage are:
• Flexibility: they don't impose any structure on the values
• Speed: accessing values using keys gives lower latency and higher throughput
• Scalability: they are highly horizontally scalable compared to relational databases
Of course, they also have weaknesses like:
• values can't be easily filtered or sorted using queries
• the whole value is returned/updated after a request
• without a unified query language, requests may not transportable to different storages
Some key-value storages like DynamoDB, support somewhat complex filtering and sorting operations for single-table. But it’s hard, and it's necessary to have a good design for the table up front.
The primary use cases of key-value storage are:
• cache frequently accessed data and access them using a hash
• store unique configuration parameters used across the system
• access real time random data like user session attributes in web applications
For example, a web application can use a key-value database to store responses to network requests and retrieve them using a hash of the IP address or username. Or it can record data about user sessions and retrieve them using their identifiers.
Some popular key-value storage implementations are:
• Dynamo DB: fully managed and serverless storage part of the AWS portfolio
• Zookeeper: a strongly consistent, highly available storage often used for dynamic configuration
• Redis: in-memory storage typically used as a fast, best-effort caching solution
• Etcd: a strongly consistent, highly available storage often used for implementing leader election
Coding challenge
The coding challenge for this week is Boats to save people.
The problem takes as input a list of people's weights and some boats with a maximum capacity. The goal is to find the minimum number of boats required to save all the people, given the following constraints:
that each boat can only carry maximum two people
the weight of the people in a boat shall not exceed its capacity.
This classic optimization problem can be solved using a greedy algorithm. Greedy algorithms work by making the best possible choice at each step, hoping that these choices will lead to an optimal solution.
For this particular problem, the key is to sort the list of people's weights in descending order. Once the list is sorted, we can make the optimal choice by picking the heaviest and lightest people each time. Only the heaviest is picked if their weight exceeds the boat's capacity.
Here is a possible implementation of the solution:
The time complexity is O(NlogN) to sort the input array, while the space complexity is O(1).
Interesting Tweets
Asking for a promotion is not a one-time interaction. It requires a series of ongoing dialogues with your manager. It is critical to articulate why you desire a promotion and to keep the talks focused on what it would take to get to the next level. It's more of a project, less of a single ask.
It’s easy to get blinded by perks and glitters and value the company more than it deserves. But this could be a mistake.
Finishing the last year of my PhD while working as a software engineer has been one of the toughest things I have ever done.
