TIL - Generating Permutations and API Level Testing
Tags: todayilearned, algorithms, testing, learning
Published: 2020-09-08 15:29:37

Today I learned...

A method for generating permutations and patterns for API level testing!

## Generating Permutations 

While trying to solve a new programming problem, I recognized that it involved generating all permutations of an array. While I wasn't able to solve it completely as I missed permutations in the generation sequence, I dove deep in the solutions and internalized the patterns.

This method involves Divide and Conquer, Swapping, and Backtracking.

Namely this method is for generating all permutations of an array by swapping elements that you haven't seen so far with ones that you have.

The divide and conquer part comes from dividing the length of the array into two parts, a prefix from 0 -> i and a postfix from i -> end. The postfix essentially becomes a smaller subproblem of the original as we consider the prefix part done, hence making it divide and conquer.

The swapping is used to swap elements in the prefix and postfix to generate different permutations as an array of `[1, 2, 3]` has a valid permutation `[2, 1, 3]` which is out of order. The swapping creates that out of order.

The backtracking is to go back to a previous state after a swap since you can swap the first index with the second, but want to reverse that process so you can also swap the first with the third.

The base case is when the current index is the same as the length of the array as it means your prefix has become the entire array, indicating that you have finished that path of generating permutations.

![Generating Permutations](https://dev-to-uploads.s3.amazonaws.com/i/bcflsjkxdsat09helgrz.png)
*Quick example of generating permutations from Leetcode image*

The pseudo-code looks something like this:

```
def outerFunction():
    initialize vars needed

    helperFunction()

def helperFunction(array, start_index):
    if (start_index == len(array)):
        Do base case work here
        return;
    
    for (i = start_index; i < len(array); i++):
        swap(start_index, i)
        helperFunction(array, start_index + 1)
        swap(start_index, i)

    return;
```

## API level testing patterns

I also looked into API level testing patterns for my productivity tracker. I learned a lot of information such as the cases you need to test for API's (status code, response body, response headers, etc) as well as what to mock in API level testing.

In my case, I am trying to automate the API level testing from end-to-end so I learned in general you should only mock anything external to what you are trying to test including external libraries / APIs.

Furthermore, different test cases should be handled for security groups, authentication, headers, cookies depending on the API implementation.

I also found out that a common pattern people use to develop APIs is having a combination of a real-api backend and mocked apis. The real-api backends are kept/utilized once the APIs are implemented while the mocked ones are for new features and made quickly so that it doesn't block any frontend workers.

This paradigm reduces the amount of time spent doing nothing as much as possible.