I remember fondly those university years back when I was studying Computer Science, all the lectures, materials, knowledge I was discovering and the friends I met during this time, many of which I still keep in touch with.

There is a distinction in Computer Science to talk about disciplines, summarising them into two categories: DSA (Data Structures and Algorithms) and System Design.

Personally, I have always found System Design more appealing than DSA. The thought of breaking down requirements, carefully analyzing them, designing an architecture that suits these use cases and validate it always sounded more attractive to me than optimizing loops and iterations.

That was, until I came across a real example during my professional life.

Consulting work is a job that tends to be dynamic. Working as a consultant, it is possible to get in touch with lots of people, lots of projects, and lots of technologies. Thanks to this, I was able to see projects from both the engineer’s and the stakeholder’s point of view, and since I always worked as “Forward Deployed Engineer”, being close to both of these POVs helped me do a better job.

Good software is not good because it was written following the Bible of Architecture. What makes good software good is that it fixes a problem while being still possible to maintain and extend.

I recall working in this project where I was doing consulting on improving certain processes of the software development cycle. At their latest stage, which was Integration testing this company was relying on people performing manual tests with mobile devices. This was inefficient and slow, and required people to perform repetitive tasks on mobile applications without any way to take shortcuts or skip steps.

These mobile apps were huge and had lots of complicated logic, screens would be activated or deactivated based on the data provided by the backend, and the team tried to build a 500LoC if-else clause navigation function to navigate from one screen to the other.

Technical debt was growing, so I gladly took on the task to come up with a better idea.

Analyzing the app

After playing around with the app, noticed that the app was built like a tree, which simplified things. I already had the idea in mind to use a graph, but a tree made even easier to work with.

The home screen had around 16 tiles, each of these would have other screens beneath it. During tests, it was common that users would need to navigate from one deep screen to another deep screen that stemmed from a different father.

This tree illustrates the concept behind this. During a test, a user might need to perform an action in (F) that affects (D) and (E).

        (A)
       /   \
     (B)   (C)
     / \     \
   (D) (E)   (F)

Let’s say we want to go from (F) to (E). In the way in which the navigation function was implemented before the refactor I introduced, a big IF-ELIF would check what screen was currently displayed screen, and then, would do two things:

  1. if the target screen is directly accessible from the current screen, follow a descending hard-coded path.
  2. if the target screen is not below the current screen in the tree, go back to the root (home) and follow a descending hard-coded path.

This was an easy way to solve the problem, but it required writing code for each new screen that would appear in the flow as development advanced further. So, it was time to apply some DSA and graph algorithms.

LCA - Lowest Common Ancestor

My solution was designed around two concepts. First, the concept of “finding the path”, and second, the concept of “following the path”. Before diving any deeper, the concept behind the graph modelling has to be explained.

Graph algorithms stem from Graph theory, which the reader probably knows about. Else, the reader can check it out. Since the app navigation resembles a tree, it can be modelled as a graph, to which graph algorithms can be applied. The “find a path” problem is one of the most common problems in DSA interviews.

What the new feature will do is, firstly, compute the path the user needs to follow to go from one node to another, and then, perform the navigation. So that gives us a couple more details that we have to watch out: - we need to identify the current page, or we won’t have inputs for the algorithm. - is the back navigation consistent? Can we always press the same button or the Android navigation button to go back?

After sorting those two problems, the focus can be set on the algorithm. The algorithm in use here is LCA, Lowest Common Ancestor. The Lowest Common Ancestor (LCA) algorithm takes two nodes of a tree as inputs and returns the deepest (lowest) node of a tree that is an ancestor to both of the nodes that are passed as arguments. Lowest, that is, the first node we can find coming from both nodes that has both as descendants.

Example: in the tree showed before, if we called the algorithm with D, E, we would get B. If we called it with E, C, we would get A. If we correctly map the application, we easily calculate the optimal path, return it as a list, and let a crawling algorithm follow it.

Afterwards, a crawler takes the path and performs as many clicks back and clicks on elements to go forward as required. An extra update to this was the ability to define the tree/graph in a .CSV file instead of hardcoding it in source code, making it easier to maintain.


def get_lca(curr_node, dest_node):
    curr_node_ancestors = get_ancestors_node(curr_node)
    dest_node_ancestors = get_ancestors_node(dest_node)
    
    # walk through the dest_node_ancestors until 
    # a node is both in dest_node_ancestors 
    # and curr_node_ancestors
    for node in dest_node_ancestors:
        if node in curr_node_ancestors:
            lca = node
            computed_steps_back = curr_node_ancestors[lca]
            
            [...]
            
            return computed_steps_back, forward_path
    raise ValueError("oops!")

This (very simplified) version of the code describes the core idea of applying LCA to a tree with two nodes as inputs. The impact of this function was immediately noticeable, since it eased the maintenance effort of the navigation function and allowed to unify all these navigation know-how in one single place, successfully allowing code reutilization.