Recently I had some free time and decided to checkout a few questions from LeetCode.

Struggled and relearned a few insights during this experiment so writing them down for my future self.

The idea is to document the unfiltered process, revisit what worked and what did not to improve problem solving skills.

Here’s how it went down along with some relevant commentary.

Picked a medium level problem about rotating a box that may contain stone(s), stationary object(s), obstacle(s) or empty space. The details:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/*
You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the 
box is one of the following:
    A stone '#'
    A stationary obstacle '*'
    Empty '.'
The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each 
stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity 
does not affect the obstacles' positions, and the inertia from the box's rotation does not affect 
the stones' horizontal positions.
It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the 
box.

Return an n x m matrix representing the box after the rotation described above.
Input: box = [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]]
         
         
Input: box = [["#",".","*","."],
              ["#","#","*","."]]
Output: [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]
         
Input: box = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
Output: [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]
         
Constraints:
    m == box.length
    n == box[i].length
    1 <= m, n <= 500
    box[i][j] is either '#', '*', or '.'         
*/

Chapter 1 - I can do it

Dove into LeetCode editor and started coding; assumed that I could figure things out along the way, did not get far. Then I remembered a wise man talking about syncing to paper. Not surprisingly, this is the strategy that Cracking the Code Interview book suggests. Great minds think alike eh?

Chapter 2 - Boxes and Lines

Started drawing the arrays to frame the problem. A few themes appeared. Need a rotated box (transformed array) and a way to transfer the items from the original box to the rotated box. Tried to do both, got quickly overwhelmed by edge cases.

Chapter 3 - Break it down

Decided to break down the problem into smaller pieces.

• Create a rotated box
• Move items from the original box to the rotated box
• Apply gravity to move the stones above empty spaces

Chapter 4 - Progress!

Tackling the first problem using the drawings some patterns emerged.

• Last row in the original box becomes the first column in the rotated box
• Second to last row in the original box becomes the second column in the rotated box
  …

Ignoring the contents of the original box (array) wrote a function to simply rotate the box (array) and tested with different row/column sizes.

1
2
3
4
5
6
7
8
9
10
11
12

const createRotatedBox = (rowLength, columnLength, box) => {
    const rotatedBox = [];
    for(let r = 0; r < rowLength; r++){
        const rowArray = [];
        for(let c = 0; c < columnLength; c++){
            rowArray.push("X") //contents don't matter
        }
        rotatedBox.push(rowArray)
    }

    return rotatedBox
}

Chapter 5 - Moving Day

It’s time to move the items from the original box to the rotated box. I found it difficult to map the coordinates in the original box to the coordinates in the rotated box. My plan was to write a function that would say:

• the item in (0, 2) in the original box will go into (2, 2) in the rotated box

so I created another visual to help tease out the pattern(s)

This made it easier to see the source and target coordinates of each item at a glance. That led to the following simple (in hindsight) function to get the target coordinates from the source coordinates.

1
2

const getRotatedBoxIndex = (rowIndex, columnIndex, rowLength) => 
    ({rowIndex: columnIndex, columnIndex: rowLength - 1 - rowIndex})

Chapter 6 - Gravity

The last small problem to solve was applying gravity and swapping the location of the stones if there is/are space(s) below them.

My strategy was to iterate over the columns, look at the contents and swap items accordingly. Started writing down the conditions when gravity would apply

• if there is a stone in the column and
• if there is a empty space below the stone
• what if there is another empty space below that
• …

I reluctantly had to admit that recursion may be needed in this scenario i.e. for each column start from the top and swap each stone and the empty space below it.

It’s crucial to determine the exit conditions when dealing with recursive functions. A light bulb went off in my head while thinking about when the code should stop applying gravity (swapping items) to the column.
If the code iterated through all the items in the column AND did not swap anything,
then we’re done with that column
else applyGravity again (recurse)

Behold the applyGravity function that is tested separately from the rest of the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const applyGravity= (items) => {
    let swapped = false
    for(let i = 0; i < items.length; i++){
        if(items[i] === "#" && items[i+1] === "."){
            swapped = true
            let temp = items[i]
            items[i] = items[i+1]
            items[i+1] = temp
        }
    }

    if(swapped) return applyGravity(items)
    
    return items
}

Now we have a function that can take an array of items in a column and applyGravity to that column swapping items if necessary. Therefore, the remaining steps are:

• Get the columns (array of items in the column) from the rotated/populated box
• Call applyGravity passing the items in that column (swapping items if necessary)
• After calling applyGravity on each column, put the columns back together (rebuilding the rotated box)

Chapter 7 - AI all the things!

You have been waiting patiently to see when an LLM would come into play. Well, here it is.

Claude prompt:

1
2

javascript function that returns an array of columns for a two dimensional array

response:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function extractColumns(array) {
    // Check if the input is a valid 2D array
    if (!Array.isArray(array) || array.length === 0 || !Array.isArray(array[0])) {
        return [];
    }

    // Get the number of columns based on the first row's length
    const numColumns = array[0].length;
    
    // Initialize an array to store columns
    const columns = Array.from({ length: numColumns }, () => []);
    
    // Iterate through each row
    for (const row of array) {
        // Ensure the current row has the same length as the first row
        if (row.length !== numColumns) {
            throw new Error('All rows must have the same length');
        }
        
        // Add each element to its corresponding column
        for (let colIndex = 0; colIndex < numColumns; colIndex++) {
            columns[colIndex].push(row[colIndex]);
        }
    }
    
    return columns;
}

Claude prompt:

1

now write a function to return a two dimensional array from a columns array

response:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/*I'll create a complementary function that converts an array of columns back into a two-dimensional array.*/

function extractColumns(array) {
    // Check if the input is a valid 2D array
    if (!Array.isArray(array) || array.length === 0 || !Array.isArray(array[0])) {
        return [];
    }

    // Get the number of columns based on the first row's length
    const numColumns = array[0].length;
    
    // Initialize an array to store columns
    const columns = Array.from({ length: numColumns }, () => []);
    
    // Iterate through each row
    for (const row of array) {
        // Ensure the current row has the same length as the first row
        if (row.length !== numColumns) {
            throw new Error('All rows must have the same length');
        }
        
        // Add each element to its corresponding column
        for (let colIndex = 0; colIndex < numColumns; colIndex++) {
            columns[colIndex].push(row[colIndex]);
        }
    }
    
    return columns;
}

I know exactly what these two functions are doing but I’m too lazy to write it myself.

Chapter 8 - Will it work?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

var rotateTheBox = function(box) {
    // In the rotatedBox array
    // box's length will be column length
    // subarray's length will be row length
    const rotatedColumnLength = box.length
    const rotatedRowLength = box[0].length


    const rotatedBox = createdRotatedBox(rotatedRowLength, rotatedColumnLength)

    // populate rotatedBox
    for(let r = 0; r < box.length; r++){
        for(let c = 0; c < box[0].length; c++){
            const rotatedBoxIndices = getRotatedBoxIndex(r, c, box.length)
            const rowIndexInRotatedBox = rotatedBoxIndices.rowIndex
            const colIndexInRotatedBox = rotatedBoxIndices.columnIndex

            rotatedBox[rowIndexInRotatedBox][colIndexInRotatedBox] = box[r][c]
        }
    }

    const colsInRotatedBox = getColumns(rotatedBox)
    const colsAfterGravity = colsInRotatedBox.map(c => applyGravity(c))
    const boxAfterGravity = columnsToArray(colsAfterGravity)

    return boxAfterGravity

};

Not bad for the first iteration.

Afterword

I noticed that simply breaking down the problem enabled working on each one separately reducing the mental load. The functions in the solutions are easy to read (if I may say so myself) and self-contained. Despite mutating state I think the overall solution is comprised of pure functions.

A happy side-effect of this strategy is that in a bigger team we can write unit tests for each of these functions and have multiple developers work on them at the same time going forward.

Has this ever happened to you?

You’re working from home, have a meeting in 20 minutes and haven’t had lunch yet. There is not enough time so you get some fast food. You later discover plenty of lunch options at home. You start running scenarios in your head, I could have:

• had lunch at home
• saved money / gas / environment (less waste)
• (probably) had a healthier meal
• …..

After experiencing this for the umpteenth time, as I was throwing away fast-food trash I realized there had to be another way.
Out of that a new application was born.

Pantry Hopper is a meal tracker decision application for the rest of us. It is designed to help answer questions such as “What’s for lunch?”. Pantry Hopper makes it dead simple to

• Bulk add items from your receipt
• Organize using tags
• Scan receipt, rename and tag items

Check out Pantry Hopper-Beta

I have failed a coding challenge some time ago. It looked like a simple enough problem. However, afer struggling to come up with an answer in the allowed time, I blew it.

As a software professional with about two decades of progressive experience I was disappointed. I decided to do a mini retrospective to see what I can learn from this experience; what went wrong and how I can do better next time. I skimmed through the “Cracking the Coding Interview” book in preparation for the interview. However, I still made the most common interviewing mistake. I jumped into coding too soon without formulating a solution in my head first.

The task looked pretty simple; write a function that converts an integer to roman numeral. I thought I had a pretty good understanding of the problem and that I would be able to come up with an algorithm on the spot. I was unable to find a pattern to code.

I remembered the advice to practice solving coding challenges on paper for practice and decided to give it a try. I have had good luck with what I call “table approach” where you put all the relevant variables in a table and track their values for each iteration.

Started with writing down the rules:

• M: 1000, D: 500, C: 100, L: 50, X: 10, I: 1
• Symbols to the right increment, symbols to the left decrement
• Max 3 consecutive roman numerals are allowed
• Maximum number representable in roman numerals is 3999
• 0 has no equivalent symbol

The last three rules were not immediately obvious before writing them down. It’s easy to see the early exit conditions. If the number is 0 or greater than 3999, there is nothing to do.

Here is a table that shows the roman numerals to represent numbers 1-9 in different places.

Here is the pattern I see:

Let’s code this pattern in javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function convertDigit(c, p, gp, digitNumber){
  // c: current numeral
  // p: parent numeral
  // gp: grandParent numeral
  let digitNumberRomanNumeralTransform = new Map([
    [1, (c) => c],
    [2, (c) => c + c],
    [3, (c) => c + c + c],
    [4, (c, p, _) => c + p],
    [5, (_, p) => p],
    [6, (c, p) => p + c],
    [7, (c, p) => p + c + c],
    [8, (c, p) => p + c + c + c],
    [9, (c, _, gp) => c + gp]
  ])

  const getTransformFunc = digitNumberRomanNumeralTransform.get(digitNumber)
  const result = getTransformFunc(c, p, gp)
  return result
}	

Every digit in an integer can be represented by 3 roman numerals:

• 1s: I, V, X
• 10s: X, L, C
• 100s: C, D, M

Sounds like a simple Map.

1
2
3
4
5
6
7
8
9

function getDigitRomanNumeralsMap(){
  let digitRomanNumeralsMap = new Map([
  [1, { "numeral": "I", "parentNumeral": "V", "grandParentNumeral": "X" }],
  [10, { "numeral": "X", "parentNumeral": "L", "grandParentNumeral": "C" }],
  [100, { "numeral": "C", "parentNumeral": "D", "grandParentNumeral": "M" }],
])

  return digitRomanNumeralsMap
}

Now I can:

• Iterate over each digit
• Pick the 3 roman numerals for the digit place
• Convert each digit to roman numeral
• Concatenate roman numerals

See the code in action here.

Retro time… What have I learned from this experience?

• Read the entire question, ask for clarification and make assumptions explicit
• Read the entire question, ask for clarification and make assumptions explicit (not a typo)
• Do not skip the steps above regardless of how easy the question might seem
• Avoid multitasking, formulate a solution and then write the code
• Draw a table to visualize the available data
• Try to detect a pattern
• Optionally write some pseudocode to mentally test the pattern
• Write code to implement the pattern/algorithm

You’re welcome, future self.

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

Coupling is one of the fundamental concepts that affects the maintainability of software systems as discussed before. Coupling measures how dependent are the components of the system on one another.

• Incoming coupling: who depends on you (aka afferent coupling)
• Outcoming coupling: who you depend on (aka efferent coupling)

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

In this post, we will conclude our request/response analysis. We know that request/response may be unreliable, slow and not scalable.

However, it is not possible to completely avoid using request/response and still build a useful software system. Is there an alternative?

There is good news and bad news. The good news is that we can create reliable, scalable and performant software systems by strictly adhering to the proven principles that have been around for a long time such as loose coupling (more on this later) and encapsulation.

The bad news is that it is challenging to adhere to the principles in the face of marketing from tech vendors and cargo cult programming (Netflix, Uber are building microservices so should we… not so fast).

All you need to know about software:
Tightly coupled designs donot work.
Highly cohesive, encapsulated software loosely coupled from other
highly cohesive, encapsulated software work.
-Udi Dahan (paraphrased)

It is sort of an anticlimactic reveal. You would be hard pressed to find any software developer who have not heard these terms.

In traditional Object Oriented Design nouns become entities, relationships between the entities lead to entity-relationship diagrams (Customer, Order, CustomerOrder etc.) and that usually leads to architectures requiring quite a bit of request/response to do anything useful.

One of the issues with this approach is that we end up putting attributes that do not need to change together in the same place. In a typical Customer among other attributes object, we may see:

• Name
• Date of Birth
• Address

If a customer’s name does not change when they move, name and address donot need to be stored together.

This understanding leads us to one of the most important aspects of the distributed systems design: Finding your service boundaries.

In a nutshell,

• Design and understand user workflows
• Determine the pieces of data needed to enable the workflows
• Organize pieces of data into randomly named piles
• Identify messages/events needed for coordination between the piles
• Name the piles (like CustomerLoyaltyService, ShippingService etc. )

When teams follow this exercise they realize that the traditional singular “Customer” entity does not exist anymore. First name and last name is in this pile(service to be named later), shipping address is in that pile and loyalty status info is in that pile over there. Effectively, we have exploded the customer entity and distributed its attributes to many piles(prospective services). Ideally, these piles have an ID, customer attributes they are responsible for and nothing else so each can totally perform their respective business capability independently. That is what makes them a service.

Service is the technical authority for a given business capability.
-Udi Dahan

Note that I am oversimplifying the process here for the purposes of brevity. The process of identifying how the domain breaks down is reportedly a long, difficult and thankless process. Adam Ralph does a great job explaining the nuances in the webinar linked above. In reality, armed with the principles such as minimal request/response and no data sharing between services (no publishing events like CustomerAddressUpdated) it is a process of trial and error.

These aspects of the service boundary discovery process make it challenging to provide a nice explanation with examples in a blog post. Even the most experienced software architects describe it similar to bumping around in the dark and trying to get a sense of what the shape of the world around you -maybe for days- until discovering some insight.

It’s no surprise then why this approach is not popular among agile teams biased towards action who prefer working software over documentation, work in sprints and timebox their “spikes”.

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

We will focus on performance aspects of request/response interactions. Latency and bandwidth are two important concepts that we need to understand when discussing performance.

Latency: Time to cross the network in one direction.

Remember that latency does not include any processing time (serialization/deserialization of the payload). Furthermore, looking at the scaled latency chart will help us understand relative cost of remote calls.

1
2

var importantService = new ImportantService();
var result = importantService.Process(data);

Assuming that we’re making a remote call across the US, we can conclude that -relatively speaking- if the first line takes 1 second, the second line will take 4 years. Let that sink in for a moment.

Bandwidth: the capacity for data transfer of an electronic communications system

Bandwidth is not usually measured. Most developers are not even aware of the bandwidth that is available for their applications in production. Hence the fallacy: Bandwidth is unlimited. Traditionally, the amount of data processed by the software systems grew much faster than bandwidth capacity. The network will obviously affect the performance of your application.

Example: Gigabit internet= 128mb/sec

Available bandwidth = 128 - 60(TCP cost) - serialization_cost(bigger object graph, xml => higher cost)

Today I learned: Making remote calls can be extremely slow compared to to the rest of the application code. We can safely assume that this is going to hold true for some time.

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

It’s time to analyze the scalability characteristics of synchronous request/response operations as in the case of making REST/gRPC/Web Services to call one or more (micro)services, databases.

Typical scenario where the server is running a language with a Garbage Collector to free up memory (Java, .NET languages)

• Client sends a request to the server
• Server receives the request
• Memory is allocated to get info out the request, stored on the heap
• Server sends a request to another microservice or database
• Server waits for a response for that request
• Garbage Collector (GC) comes (after some miliseconds) and asks: Are you done with that memory?
• Server: Nope, still waiting
• GC: No problem, marks memory as Gen1
• GC comes back (after some miliseconds) and asks: Done yet?
• Server: Nope, still waiting
• GC: No problem, marks memory as Gen2
• Now that memory is pinned. The only way to get it out of Gen2 is to do a global GC.Collect
• Response comes back but GC DOES NOT clear regular memory in Gen2, just the disposables that have gone out of scope.
• GC.Collect will freeze ALL THE THREADS while GC goes and cleans up the memory in Gen2.

I was one of those people who thought that async/await fixes this problem.

No, it doesn’t. That just means the thread gets out of the way so you can take on another request. That actually means you’re gonna fill up faster and use more memory quicker and maybe fail quicker. It is not a solution.
-David Boike

Thanks to ADSD course and to David’s Boike’s presentation, I now understand how under sufficient load, long running queries can exhaust all the memory on a web server.

Today I learned: In addition to being unreliable request/response style interaction does not scale well under load.

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

In the previous post, we demonstrated the unreliability of request/response.

If such a trivial example can show how unreliable request/response could be, why do we continue to write similar type of code?

The problem is request/response code may work in production without any issues for a long time. However, if and when the conditions are right we may receive a bug report about lost data and/or duplicate processing etc.

• Unit tests pass
• Integration tests pass
• End to End test pass
  (If any of these had failed, we would not have deployed to production anyways right?)

At this point, we may attempt to reproduce the issue manually.
Most of the developers have some sort of local setup where we start up each dependent service on our machine and proceed with debugging. The services involved may be logically separate but they are not physically separate (all running on the same machine - more on this on another post). Manual test, click here and there. No dice, close the JIRA ticket with comment.

Cannot reproduce.

Congratulations on joining the Works on my machine club.

This is a part of a series of posts to document my learnings after watching Udi Dahan’s Advanced Distributed Systems Design course.

I reviewed the videos multiple times and took detailed notes to really internalize the principles. These are the kind of technology agnostic principles that have been around for decades and should be relevant for years to come as opposed to the intricacies of the JavaScript framework du jour.

Let’s set the stage by stating our end goal.

Design and build performant, maintainable and resilient software systems where adding the 200th feature is as fast and easy as adding the first.

We will start with reliability. Everyone knows that network is not reliable. However, we continue to write code similar to this.

1

var result = importantService.Process(data);

Udi Dahan used timeout exception to demonstrate the reliability issues with this code snippet.

1. Need to send some data to a remote service for a long running workflow.
2. Invoke a synchronous call and wait for response.
3. Get a timeout exception

Here are some possible scenarios

• Data did not arrive at the server
• Data arrived, service did not complete processing before timeout.

At this point client does not know what to do; this is important data that needs to processed.

• Resend and risk duplicate processing?
• Write service code to handle deduplication? What if we don’t own the service?
• What do we tell the user? I know “An unexpected error occurred” :)

The bottom line is:

If you’re doing this on top of http, you’re always going to be almost there. There’s always going to be the scenario of this time I’ve done it. This time I finally solved all of the edge cases, and then some period of time later in production, some other thing will blow up and you’ll discover oh except that one.
-Udi Dahan

Today I learned: It is very difficult to build reliable systems on top of http with request/response (remote procedure calling-RPC, REST, Web Services etc.)