When demonstrating an algorithm it often helps to have some simple examples to follow. What are some simple strings that we might use for demonstration? How about English words that when reversed are a different word. I am not talking about a palindrome, rather I am referring to words that when reversed make entirely different words.

Word | Reverse |
---|---|

draw | ward |

emit | time |

knits | stink |

dam | mad |

stun | nuts |

spots | stops |

There are many different ways to reverse a string. Some languages support reversing a string easily while others do not. Before we get into the specifics of any language we should first define one algorithm for performing the reversal.

```
set len = current_string length
initialize empty string reverse_string of length len
set current_index to last index of current_string.
set next_index to index 0 of reverse_string
while current_index is greater than first index of current_string
copy character at current_index to next_index
move current_index to the left by one position in current_string
move next_index to the right by one position in reverse_string
end while
```

If you follow the algorithm above you will have a new string that is the reverse of the first and will require 4 iterations of the while loop to reverse the string and use two string variables.

The first string has the value of the string to be reversed. The second string starts as an empty string that is the same size as the first string.

0123 0123

TIME

After the first operation the last letter will be in the first position of the new string.

0123 0123

TIME E

The next assignment will result in one more letter being assigned to the new string..

0123 0123

TIME EM

One more assignment

0123 0123

TIME EMI

Finally, the last letter will be assigned.

0123 0123

TIME EMIT

The result is the string reversed.

graph TD
T0(T) --> E
I0(I) --> M
M0(M) --> I
E0(E) --> T

This algorithm has a time complexity of O(n) and a space complexity of O(n). We are ignoring the space used by the original string since that memory is already allocated outside of the algorithm.

The algorithm must iterate the while loop four times, or the length of the string, to complete. This is where the O(n) time complexity is determined.

In order to reverse the string another variable the same size as the original string must be created. This means that the algoritm will use the space of the original string length (n) as well as the space for the new reversed string. This results in the space complexity of O(n).

Another algorithm that will result in less time and space complexity will keep track of the beginning and end of the string and use only a single byte of extra memory.

In this algorithm the current characters being moved is stored in a temporary variable. The two letters are then swapped and the indexes for the first and last character to swap are moved.

```
set index i to index 0 of current_string (The first character)
set index j to last index of current_string (length of current_string - 1)
while index j is greater than index i
assign character at index i to tmp
assign character at index j to index i
assign character in tmp to index j
increment index i to right by one position
decrement index j to left by one position
end while
```

This results in two iterations instead of 4.

graph LR
E0(E) --> T
M0(M) --> I
E0 --> T
M0 --> I

Here is how it looks for each step.

flowchart TD
subgraph Swap1[Swap 1]
subgraph Step3[Assign index tmp to index j]
direction LR
subgraph tmp3[tmp]
t3[T]
end
subgraph TIME3[ ]
direction LR
T3[E] -.-
I3[I] -.-
M3[M] -.-
E3[T]
end
subgraph indexes3[indexes]
direction LR
i3[i] --> iT3[E]
j3[j] --> iE3[T]
end
end
subgraph Step2[Assign index j to index i]
direction LR
subgraph tmp2[tmp]
t2[T]
end
subgraph TIME2[ ]
direction LR
T2[E] -.-
I2[I] -.-
M2[M] -.-
E2[E]
end
subgraph indexes2[indexes]
direction LR
i2[i] --> iT2[E]
j2[j] --> iE2[E]
end
end
subgraph Step1[Assign tmp]
direction LR
subgraph tmp1[tmp]
t1[T]
end
subgraph TIME1[ ]
direction LR
T1[T] -.-
I1[I] -.-
M1[M] -.-
E1[E]
end
subgraph indexes1[indexes]
direction LR
i1[i] --> iT1[T]
j1[j] --> iE1[E]
end
end
subgraph Step0[Start]
direction LR
subgraph tmp0[tmp]
t0[ ]
end
subgraph TIME0[ ]
direction LR
T0[T] -.-
I0[I] -.-
M0[M] -.-
E0[E]
end
subgraph indexes0[indexes]
direction LR
i0[i] --> iT0[T]
j0[j] --> iE0[E]
end
end
end
Step0 --> Step1 --> Step2 -->Step3

flowchart TD
subgraph Swap1[Swap 1]
subgraph Step3[Assign index tmp to index j]
direction LR
subgraph tmp3[tmp]
t3[I]
end
subgraph TIME3[ ]
direction LR
T3[E] -.-
I3[M] -.-
M3[I] -.-
E3[T]
end
subgraph indexes3[indexes]
direction LR
i3[i] --> iT3[M]
j3[j] --> iE3[I]
end
end
subgraph Step2[Assign index j to index i]
direction LR
subgraph tmp2[tmp]
t2[I]
end
subgraph TIME2[ ]
direction LR
T2[E] -.-
I2[M] -.-
M2[M] -.-
E2[T]
end
subgraph indexes2[indexes]
direction LR
i2[i] --> iT2[M]
j2[j] --> iE2[M]
end
end
subgraph Step1[Assign tmp]
direction LR
subgraph tmp1[tmp]
t1[I]
end
subgraph TIME1[ ]
direction LR
T1[E] -.-
I1[I] -.-
M1[M] -.-
E1[T]
end
subgraph indexes1[indexes]
direction LR
i1[i] --> iT1[I]
j1[j] --> iE1[M]
end
end
subgraph Step0[Start]
direction LR
subgraph tmp0[tmp]
t0[T]
end
subgraph TIME0[ ]
direction LR
T0[E] -.-
I0[I] -.-
M0[M] -.-
E0[T]
end
subgraph indexes0[indexes]
direction LR
i0[i] --> iT0[I]
j0[j] --> iE0[M]
end
end
end
Step0 --> Step1 --> Step2 --> Step3

The time and space complexity is improved for this algorithm. The time complexity is now O(n/2) and the space complexity is O(1). Again, we ignore the space allocated by the original string since it is being allocated outside the algorithm.

The number of iterations to reverse the string is now looping half as many times. Instead of looping once for each character and assigning that character to a new string each time we only need to loop until we have swapped half of the characters. In this algorithm we still make as similar number of operations, so we are not saving much on the actual operations front.

The real savings is on the space complexity. In the previous algorithm we had to allocate enough space to store the reversed string. This meant that the amount of space used would grow as the size of the input string grew. In this algorithm we only need enough memory to store a single character. This means that the memory requirements of the algorightm to not depend on the size of the input string.

Great question. Other than to show off your skills in a coding interview, what have you used a reverse string algorithm for?

]]>What is a string? It is nothing more than a series of zero or more characters. For computers, characters are just symbolic representations of numbers. What is the difference between the letter `A` and the number `65`? To a computer nothing. The difference is how the value is interpreted by the higher level language. If a program labels the as an integer then it is the number `65`. If a program labels the value as a character then the value is interpreted as the letter `A`.

If we want to create a string then we need to represent it as a series of characters. So the string `Hello, World!` is a series of 13 characters that are put together to form a string.

Once of the first standards for encoding characters was the ASCII character set. The ASCII table contains a set of values that can be represented in 8 bits. This is a standard used to ensure a standard way to exchange information. This ensures that when a computers stores the 8 bit representation of an `A` that all other computers would understand what that the value represents and not interpret is as different value.

As computers spread throughout the world the need to be able to represent characters outside of the standard English alphabet became more important. New ways of encoding characters were created to enable this. One of these is the UTF-16 character encoding. This encodes characters in a 16-bit instead of 8-bits. This requires more memory per character but allows for a much richer set of characters to be encoded.

To better understand what a string is we need to understand how it is stored in a computer. First we will look at the architecture of a 32-bit computer. This means that every spot in memory has an address that can be represented by 32 bits. One way to think about this is a piece of graph paper.

Imagine a piece of graph paper that has a grid on it. The grid is 32 squares wide. The rows represent a single row in the memory. So if you have 256 bits of memory on a 32 bit architecture you would have 8 rows total.

There are a lot of different architectures out there for computers. The most common are 32-bit and 64-bit. However, there are plenty out there that have a different architecture. Additionally, how memory is addressed on each of the architectures depends on the implementation. For more information word sizes see this article

If we use an 8-bit representation to store and encode characters like in ASCII then we could represent a `Word`

as four characters. Each of the characters are stored in a 1-byte space of memory.

If we start at the memory address of 0 (0x0) then we would have the character `W`

at memory address 0 (0x0) followed by the character `o`

at address 8 (0x8), the character `r`

at address 16 (0x10) and finally the character `d`

at address 24 (0x18).

Since computers store information in the form of 1's and 0's the characters are represented as binary numbers. Using the ASCII representation results in the letters represented as the following numbers.

Character | Decimal | Hex | Binary |
---|---|---|---|

W | 87 | 56 | 0101 0111 |

o | 111 | 6F | 0110 1111 |

r | 114 | 72 | 0111 0010 |

d | 100 | 64 | 0110 0100 |

If we put the characters into our memory space as a series of contiguous 8-bit (1-byte) numbers we get something that looks like this.

A string is just a series of contiguous characters stored in memory. To store a string we need to know two things. The starting address of the first character and the size of the string or length of string. The length is just the number of characters in the string.

Now that we have a `Word`

stored in memory we can see that the first character starts at address 0x0. This is where the starting address of a string would be indicated. The length of `Word`

is 4. When we want to get the value of the string we return the address of the first character and each character that follows until we have reached the length of the string.

That is a relatively basic explanation. The specifics on how a string is stored and read will depend on the architecture of the hardware that is being used. When writing in a programming language the manner in which you define the string will also be dependent upon the language. Some define a string as an array of characters. Others have a type that represents a string just like a type represents an integer.

]]>The problem presented is that you have a one dimensional array of numbers. From that array you need to find the maximum sum sub-array. The sub-array must be contiguous.

The solution to this can be in several forms. You could just want the actual maximum sum of the numbers. In this case you would find the sub-array and then sum all of the numbers and return the value of the maximum sum. Another solution could be that you want the elements of the sub-array. Finally, perhaps you just need to provide the indices where the sub-array starts and ends.

There are several ways you can implement this solution.

- Brute-force. Just look at every possible combination and choose the best one.
- Divide and Conquer. This approach will divide the problem into a smaller problem and solve the smaller problems.
- Kadane's algorithm.

Here we explore Kadane's algorithm.

Presented with an array of numbers, find the maximum sum sub-array.

Kadane's algorithm is an optimized method of scanning the array to find the largest sum sub-array. Like the brute-force method it iterates over the array to find the maximum sum. However it does it using a single loop which improves the performance.

```
maxSum = 0
currentSum = 0
// Iterate over the array
for (i = 0; i < array.length; i++)
{
// add current index to sum
currentSum = currentSum + array[i]
// Is the current sum less than zero?
if(currentSum < 0)
{
// Reset the sum and subarray indexes.
currentSum=0
}
if(currentSum > maxSum)
{
maxSum = currentSum;
}
}
return maxSum
}
```

In addition to only having a single loop this algorithm has another change from the brute-force method. It resets the `currentSum`

to zero if it ever drops below zero. This is the key to this algorithm. If the `currentSum`

is ever less than zero then you can safely discard the entire sub-array that you have built up to this point. Any values to the left of the current position will only result in a smaller sum no matter how large the positive values are remaining in the array.

Finally, the `currentSum`

is compared to the `maxSum`

and a new `maxSum`

is assigned if the `currentSum`

is larger.

If we use our example array towalk through the algorithm this is what we see. First the iterator starts with position 0. This results in a sub-array of length 1 with a currentSum of -1

The `currentSum`

is found to be less than zero and so the `currentSum`

is reset to 0. Since the `currentSum`

is not greater than the `maxSum`

the loop continues and increments to the next item.

During the second time through the loop the array[i] value of 3 is examined. The `currentSum`

is incremented by 3 resulting in a value of 3 since we reset the `currentSum`

to zero during the previous loop. The currentSum is not less than zero so we do not need to reset it. The currentSum is greater than the current maxSum and so the maxSum is now set to the curentSum and the loop is incremented to the next element.

The array[2] is now being inspected. The value of this is added to the currentSum and results in a value of 1 since the value of currentSum is 3 and the value of array[i] is -2.

The loop continues to inspect the next element in the array and add it to the currentSum. Each time the currentSum is larger than the maxSum it is assigned to maxSum.

After reaching array[6] the maxSum is currently set to 6.

The array index is incremented to the next two elements array[7] and array[8]. Each time the currentSum is insepcted it is found that it is less than the maxSum. After inspecting all of the elements it has been determined that the maxSum is 6.

The solution must iterate over the entire array before it can determine the maximum sum. However it only needs to do this one. This means that the time for this algorithm to complete it will take `N`

iterations. This results in a complexity of O(n).

The algorithm as it is presented will not work if all numbers in the array are negative or if the highest value item is a zero. A minor change to the algorithm can remedy this though. Set the initial `maxSum`

to `MIN_INT`

to represent the minimum value for an integer. Secondly, move the check for a currentSum less than zero to after the maxSum is set.

```
maxSum = MIN_INT
currentSum = 0
// Iterate over the array
for (i = 0; i < array.length; i++)
{
// add current index to sum
currentSum = currentSum + array[i]
if(currentSum > maxSum)
{
maxSum = currentSum;
}
// Is the current sum less than zero?
if(currentSum < 0)
{
// Reset the sum and subarray indexes.
currentSum=0
}
}
return maxSum
}
```

Now imagine an array where ALL of the values are `MIN_INT`

. With the maxSum now set to the minimum value for an integer any value in the array is guaranteed to be greater than or equal to the maxSum. If the first value in the array is the `MIN_INT`

then the maxSum will remain `MIN_INT`

. The currentSum will be reset to 0. At each iteration, the value of currentSum will be found to be less than or equal to the maxSum and therefore the maxSum will not change.

After all of the array values have been inspected the maxSum of `MIN_INT`

will be returned.

If there is an array where at least one of the values is greater than `MIN_INT`

then the currentSum will be greater than maxSum and it will be set accordingly.

You now can compute the maximum sum sub-array in O(n) time and process an array with all negative values or a mix of negative and positive.

]]>The problem presented is that you have a one dimensional array of numbers. From that array you need to find the maximum sum sub-array. The sub-array must be contiguous.

The solution to this can be in several forms. You could just want the actual maximum sum of the numbers. In this case you would find the sub-array and then sum all of the numbers and return the value of the maximum sum. Another solution could be that you want the elements of the sub-array. Finally, perhaps you just need to provide the indices where the sub-array starts and ends.

There are several ways you can implement this solution.

- Brute-force. Just look at every possible combination and choose the best one.
- Divide and Conquer. This approach will divide the problem into a smaller problem and solve the smaller problems.
- Kadane's algorithm

Here we explore the Brute-Force method.

Whenever I am trying create a solution, the brute-force method is one of the first things I do. It certainly is not the best, but it can be an effective way to better understand the problem and ensure you are getting a correct solution.

The concept behind the brute-force method is that you will just try all of the possible solutions until you are satisfied that you have the best.

Brute force algorithms are rarely the best. Sometimes they are the only method available for a problem. This is not the case for this problem though.

Using the array [-1, 3, -2, 3, -2, -1, 5, -4, -1] the maximum sum sub-array of [3, -2, 3, -2, -1, 5] starting at index 1 and ending at index 6 with a sum of 6.

A brute force approach to finding this value would be to iterate over the array and keeping track of each sub-array and the sum. If a sum is found that is higher you keep track of that.

```
maxSum=0
currentSum=0
for(i=0; i < array.length; i++)
{
currentSum=0
for(j=i; j < array.length; j++)
{
currentSum = currentSum + array[j];
if(currentSum > maxSum)
{
maxSum = currentSum;
}
}
}
return maxSum;
```

In the pseudo-code we start at the first position in the array and reset the current sum. The first check inside the second loop looks at the value of the sub-array starting at index 0 and of a size of 1.

The first time through the loop with `i=0`

and `j=0`

the sum is -1. Since -1 is less than the current `maxSum`

it will not be assigned to `maxSum`

The end index `j`

will be incremented to 1 and point to the next element in the array. This increases the size of the current sub-array to 2.

The value of the `array[j]`

is now added to the `currentSum`

and `currentSum`

becomes 2. The `currentSum`

is compared against the `maxSum`

. Since the current `currentSum`

is greater than the `maxSum`

the `maxSum`

is updated to be the value of `currentSum`

.

The inner loop continues to increment the index value of `j`

and add the value of `array[j]`

to the `currentSum`

. Each time the `currentSum`

is incremented it is compared against the value of `maxSum`

. If the value of `currentSum`

is greater than `maxSum`

it will become the new `maxSum`

.

This results in the `maxSum`

changing during the initial loop of `j`

to 3 and then 5 before reaching the end of the array.

Now that the inner loop has completed to the end of the array the outer loop iterator `i`

is incremented to 1 and the `currentSum`

is reset to 0. At this time the `maxSum`

is 5. Now the process of examining a sub-array and the sum resumes. However, this time the sub-array will start at position 1.

The process of incrementing the inner loop iterator and incrementing the `currentSum`

will continue until the inner loop reaches the end of the array. When we reach the ending index inside the inner loop with a value of 6 we find the next `maxSum`

of 6.

The inner loop continues to be incremented until it again reaches the end of the array. The final scan of a sub-array starting at index 1 results in a sub-array of size 8 with a `maxSum`

of 6.

After the scanning the array with position 0 as the starting index and then scanning the array again with the starting position as 1 we have a new `maxSum`

of 6.

The process of incrementing the staring index and then scanning the array until the end continues. Anytime a greater `maxSum`

is found it is saved. Eventually the starting index will be incremented to the very last index in the array and the final sub-array to be tested will be a sub-array of size 1 starting at index 8.

At this point every possible sub-array has been tested and the maximum sum has been determined.

The time complexity of the solution depends on the loops. The inner loop must iterate over the array `N`

times. This means that the number of iterations depends on the number of elements in the array.

The outer most loop must also iterate over the array `N`

times. Since the second loop is nested inside the outer loop this makes the complexity `N*N`

. This is expressed as `O(n^2)`

.

The next thing to consider is the amount of space, or memory, that is required to complete the solution. In this solution we have to initialize a few variables, but the size of those variables is constant. The size of the incoming array is also constant. The amount of memory used in this solution remains constant during the entire process. This makes the space complexity `O(1)`

.

After running some sample data through this algorithm you might notice that there are some edge cases that do not work. The first one is when you have an array that contains all negative numbers. The current algorithm doesn't seem to handle it very well. It reports that the `maxSum`

is zero depsite there being no way to have that value if all of the numbers are negative.

This can be easily fixed.

Instead of initializing the `maxSum=0`

, initialize it to the minimum integer value possible.

```
maxSum=MIN_INT
```

This simple change will now allow the algorithm to properly report on an array that has all negative numbers.

Another aspect of the current algorithm is that you cannot actually report on what the sub-array is that provides the maximum sum. You only know what that sum is. By iterating through the example we can see that the maximum sub-array is actual the array starting at index 1 and ending at index 6.

To be able to provide this information as a result of the algorithm we need to make some minor changes. We need to track what the beginning and ending indexes are. We can do this by adding a few extra variables.

```
maxStartIndex = 0
maxEndIndex = 0
```

Initially we assign the values to zero. Each time we find a `currentSum`

that is larger than the `maxSum`

we assign the index values. This results in the outer loop iterator `i`

being assigned to the `maxStartIndex`

and the inner loop iterator `j`

being assigned to `maxEndIndex`

.

We now know at the end of all of the scans that the start and end index is for the sub-array that results in a maximum sum.

Using this information a new sub-array can be returned or just the indexes of the sub-array can be returned.

]]>It has been some time in my career since I had to really analyze an algorithm and come up with an efficient way to solve a problem. When I do, it can really tax my brain.

Perhaps you have the same issue. It would bring me comfort to know that I am not the only one with this problem.

Perhaps you were never presented with a particular type of problem. Perhaps you never learned how to create an algorithm and determine how efficient it is. Perhaps it has just been a really long time since you had a real world problem that required a really smart and efficient solution and "good enough" has been, well, good enough. Let's face it, there are plenty of us that do not work in a life-or-death environment or where the pressure to optimize everything is paramount.

After being stumped on how to compute the largest sub-array with a maximum sum I decided to do a little research on how this could be solved.

There are several ways you can implement this solution. We will consider a few of them.

- Brute-Force. Just look at every possible combination and choose the best one.
- Divide and Conquer. This approach will divide the problem into a smaller problem and solve the smaller problems.
- Kadane's algorithm

Sometimes you need to use a filename in your code. While hard-coding a filename can be easy it can make the long term maintenance of the code a little more challenging.

One use case, but certainly not the only, is when you want to write something to a log file for debugging purposes. In this case you may want to easily associate the name of the log file with the name of the originating file.

There are a few ways you can get the name of the file.

`__FILE__`

is a special token that returns the name of the file where it is. This works a lot like the similar in the C preprocessor. It substitutes the name of the current file.

As an example lets presume that a Perl script is written named `file.pl`

. Inside of this script we call a subroutine called `logit`

within a module called `file.pm`

.

In the `file.pm`

the `logit`

module performs a simple print.

```
$ perl file.pl
file.pl # <- __FILE__ when called from file.pl
file.pm # <- __FILE__ when called from file.pm
$
```

**Pros**

- The token will automatically update if you change the name of the file.
- It returns the name of the file where it occurs.

**Cons**

- If you place within a subroutine of a Perl Module then you will get the name of the PM, not the file where you call the subroutine. (I suppose this could equally be a pro)

`$0`

is a special variable in Perl. It contains the name of the program being executed. If we use the same example as above but slightly modify the file.pl we can see how this differs.

```
$ perl file.pl
file.pl # <- $0 when called from file.pl
file.pl # <- $0 when called from file.pm
$
```

The output from the Perl script and the package are now both the same.

**Pros**

- The value will automatically update to the value of the command being executed.
- Returns the command being executed regardless of the actual file it is located in.

**Cons**

- If you place the within a subroutine of a Perl Module then you will get the name original command executed, not the file where you call the subroutine. (I suppose this could equally be a pro).

This can be done using a CancellationToken passed to the `HttpClient.SendAsync()`

method.

```
public class HttpRequestHandler : IHttpRequestHandler
{
public CancellationToken CancellationToken => _cancel;
public HttpRequestHandler(IHttpContextAccessor httpContext)
{
_cancel = httpContext?.HttpContext?.RequestAborted ?? CancellationToken.None;
}
/// <summary>
/// Execute request and return response.
/// </summary>
public virtual async Task<IResponse<T>> ExecuteAsync<T>(IRequest request) where T : class, new()
{
// ...
var response = await this.GetClient(request).SendAsync(request1, completionOption, CancellationToken).ConfigureAwait(false);
// ...
}
}
```

]]>As part of the connection to an ASP.NET Core Controller there is the HttpContext. This provdes access the a CancellationToken.

To test if the process should cancelled you check the status of the `RequestAborted`

.`IsCancellationRequested`

property within the HttpContext.

```
[HttpGet]
public async Task<IActionResult> Get(IHttpContextAccessor httpContext)
{
if(httpContext?.HttpContext?.RequestAborted.IsCancellationRequested)
{
// Stop processing
}
}
```

The `RequestAborted`

is an instance of a CancellationToken.

Another way to access the CancellationToken is to pass it as part of the Dependency Injection (DI) into the Controller.

```
[HttpGet]
public async Task<IActionResult> Get(CancellationToken cancellationToken)
{
// ...
if(cancellationToken.IsCancellationRequested)
{
// Stop processing
}
// ...
}
```

Once the cancellation request has been detected the process should gracefully stop the processing and return.

]]>