Refactoring messy Test Suite in Python

Recently, I did some code reviews on my peer's code. We've created 100+ pySpark jobs and each job has its own test cases. When I looked at the file, it was super long. Let's take a look at main function. It is pretty general test suite main function. ``` if __name__ == "__main__": loader = unittest.TestLoader() suite = create_unit_suite() runner = unittest.TextTestRunner(verbosity=2) runner.run(suite) ``` However, when diving into create_unit_suite function, I was utterly dumbfounded. ``` def create_unit_suite(): suite = unittest.TestSuite() suite.addTests(loader.loadTestsFromModule(tests.test_job_1)) suite.addTests(loader.loadTestsFromModule(tests.test_job_2)) suite.addTests(loader.loadTestsFromModule(tests.test_job_3)) # ... suite.addTests(loader.loadTestsFromModule(tests.test_job_100)) suite.addTests(loader.loadTestsFromModule(tests.test_job_101)) suite.addTests(loader.loadTestsFromModule(tests.test_job_102)) # ... ``` And the import statements look like ``` import tests.test_job_1 import tests.test_job_2 import tests.test_job_3 # ... import tests.test_job_100 import tests.test_job_101 import tests.test_job_102 # ... ``` Every time a new job is created, the developers need to import it and and add a new addTests line. The folder structure is way more complicated and there is no guarantee that all developers remember to add the tests. You can't tell which jobs are missing test cases simply by looking at this file. Thanks to unittest, there is a function called ``discovery`` introduced in v3.2. It can be used like TestLoader.discover() or from the command line. From the documentation, it states that Unittest supports simple test discovery. In order to be compatible with test discovery, all of the test files must be modules or packages (including namespace packages) importable from the top-level directory of the project (this means that their filenames must be valid identifiers). In order to expose the test files, we need to make them modules. We can do that simply by adding __init__.py. Here's what's left. Specify the path and pattern for unittest to discover. No long import statements and addTests code. ``` import unittest from tests import * if __name__ == "__main__": testsuite = unittest.TestLoader().discover("tests", pattern="test_*.py") runner = unittest.TextTestRunner(verbosity=2).run(testsuite) ``` Simply run the below command to get the result. ``` python -m unittest ``` However, running all the test cases may take a great of time. In order to have more flexibility, it should be able to run in a specific module. We can use ``argparse`` to take ``--module`` flag to determine which module we are going to run test cases on. ``` import argparse ``` Put the logic in main() ``` def main(): parser = argparse.ArgumentParser() parser.add_argument("--module", action="store", default="all", help="the module of a collection of test cases to be executed") args = parser.parse_args() target_module = args.module target_path = "tests" if target_module == "all" else "tests/{}".format(target_module) testsuite = unittest.TestLoader().discover(target_path, pattern="test_*.py") runner = unittest.TextTestRunner(verbosity=2).run(testsuite) if __name__ == "__main__": main() ```

Unbounded Knapsack

Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created. To create the sum, use any element of your array zero or more times. For example, if arr=[2,3,4] and your target sum is 10, you might select [2,2,2,2,2], [2,2,2,3] or [3,3,3,1] . In this case, you can arrive at exactly the target. Sample Input ``` 2 3 12 1 6 9 5 9 3 4 4 4 8 ``` Sample Output ``` 12 9 ``` Explanation In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}. This is a unbounded knapsack so we cannot use the classic way to solve this problem. To solve it, we can break the problem into smaller problems first. If we put the first item into the knapsack, then the remaining capacity would be ``W-w1``. So we can break it down to find out the maximum value ``max1`` if we pack the same item ``N`` times in a knapsack of capacity ``W-w1``. For the second item, we do the same thing to get ``max2`` so that it has a remaining capacity of ``W-w2``, and so on. Each item has a own value now but we have to add the original value to it. ``` itemMax1 = max1 + v1 ``` The maximum value is ``` W = max(itemMax1,itemMax2,...,itemMaxN) ``` where ``W`` is the maximum value packed in the knapsack of capacity. Psuedo code ```cpp f(v[], w[], c) { // v: array of values // w: array of weights // c: capacity // n: length of the array // base case // if it is full, the total value of a 0 capacity knapsack is 0 if(c==0) return 0; int[] m; // break it down to smaller problem // ---------------------------------------- for(int i=0;i<n;i++){ // if we can put item 1 if(w[i]<c) m[i]=f(v,w,c-w[i]); // not enough space else m[i]=0; } // add back the original value // ---------------------------------------- for(int i=0;i<n;i++){ // if we can put item 1 if(w[i]<c) mm[i]=m[i] + v[i]; // not enough space else mm[i]=0; } // find the maximum value // ---------------------------------------- int ans=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>ans) ans=mm[i]; } return ans; } ``` However, we can use bottom-up dynamic programming solution for this problem to improve the above solution. As we may see that we only have one parameter ``c`` for the recursive method where ``c`` ranges from ``W`` to ``0`` and ``v[]`` and ``w[]`` remain unchanged. Therefore, we can store the results computed by the recursive function in a 1d array. ```cpp int dp[W+1]; ``` We can set our base case to 0. ```cpp dp[0] = 0; ``` We can turn ```cpp f(v,w,c-w[i]); ``` to ```cpp dp[c-w[i]] ``` and also from ```cpp int ans=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>ans) ans=mm[i]; } return ans; ``` to ```cpp dp[c]=mm[0]; for(int i=1;i<n;i++){ if(mm[i]>dp[c]) dp[c]=mm[i]; } ``` and the result would be ```cpp return dp[c]; ``` So we have the following structure ```cpp dp[0] = 0 for C=0 ... W: for i=0 .. N: if w[i]<=C: dp[i] = max ( dp[i], ( dp[C-w[i]] + v[i] ) ) else dp[i] = 0 ```

The Longest Increasing Subsequence Problem

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. For example, the length of the LIS for [15,27,14,38,26,55,46,65,85] is 6 since the longest increasing subsequence is [15,27,38,55,65,85] Sample Input ``` 5 2 7 4 3 8 ``` Sample Output ``` 3 ``` Explanation In the array [2,7,4,3,8], the longest increasing subsequence is [2,7,8]. It has a length of 3. Given that an array with a length of `n`, we can create two vectors with the same size - one called ``l`` for holding the length, another one ``s`` for holding the sub-sequence index. ``` arr [2,7,4,3,8] n [1,1,1,1,1] s [0,0,0,0,0] ``` If we list out the index, we should see ``` idx 0,1,2,3,4 arr [2,7,4,3,8] ``` let's say we have ``i`` and ``j`` where ``i`` starts from ``1..n-1`` and j starts from ``0..i``. ``` j,i idx 0,1,2,3,4 arr [2,7,4,3,8] ``` we check if ``arr[j]`` is lesser than ``arr[i]``. If so, check if ``l[j]+1`` is greater than ``l[i]`` In this case, ``arr[j]`` is 2 which is lesser than ``arr[i]`` which is 7. So we add ``l[j]`` by 1 to see if it is greater than ``l[i]``. It is. So we set ``l[j]+1`` to ``l[i]`` and set the index ``j`` to ``s[i]``. Repeat the above steps till ``i`` reaches ``n-1``. Find out the maximum value of ``l``. That is the length of the LIS. ```cpp int lis(vi a, int n){ vi l(n); vi s(n); int max=0; l[0]=1; FOR(i, 1, n){ l[i] = 1; REP(j,i){ if(a[j] < a[i]){ if(l[j]+1>l[i]){ l[i]=l[j]+1; s[i]=j; if(l[i]>max) max=l[i]; } } } } return max; } int main() { // SKIPPED } ``` However, this approach is ``O(N^2)`` which gives you Terminated due to timeout (TLE) Error. We need a faster approach to resolve this problem. Supposing there is a vector called ``vi``. The strategy is - If ``vi`` is empty, set the input ``a`` to ``vi[0]``. - If ``vi`` is not empty and the input ``a`` is the largest value of ``vi``, append ``a`` at the end - If ``vi`` is not empty and the input ``a`` is in between, find the correct index and replace the existing value. We can implement a binary search function to look for the correct index or we can just use STL. The answer is the size of ``vi``. Final Solution ```cpp int main() { FAST_INP; int n,a; cin >> n; vi v; REP(i,n){ vi::iterator it; cin >> a; if(i==0) v.push_back(a); else { it=lower_bound(v.begin(),v.end(),a); int k=it-v.begin(); if(k==v.size()) v.push_back(a); else v[k]=a; } } cout << v.size(); return 0; } ```

Breadth First Search (BFS)

Breadth First Search (BFS) can be used to explore nodes in different layers, compute shortest paths and connected components of undirected graph. The run time complexity is in linear time O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges in the graph. Initally all nodes are not visited, starting from vertex 1 in a graph G, mark 1 as visited. Let ``q`` be a FIFO queue, initialized with 1. While ``q`` is not empty, remove the first node of ``q`` called ``v``. For each edge ``u``, if ``u`` is not visited, mark it visited and add it to ``q.`` ```cpp memset(vis, 0, sizeof(vis)); queue<int> q; q.push(1); vis[1] = 1; while(!q.empty()) { int v = q.front(); q.pop(); for(auto u : g[v]) { if(!vis[u]) { vis[u] = 1; q.push(u); } } } ``` If vis[x] is 1, we can say that G has a path from 1 to x. Applications: - Shortest Paths ``` dist[v] = 0 if v = s, else INT_MAX for edge (v, u) if v is not visited set dist[u] = dist[v] + 1 ``` The shortets path result is stored in ``dist[u]``. - Connected Components via BFS ``` for i = 1 to n if not visited bfs(g, i) ```

Handling NULL values in GREATEST() function in Oracle Database

We can use GREATEST function to return the greatest value in a list of expressions. For example, below statement will return the value 3. ``` SELECT GREATEST(1, 2, 3) FROM DUAL; ``` However, if there is a NULL value in it, the return value will be NULL. As NULL is unknown, there is no way to do the comparison. If you call a SQL function with a null argument, then the SQL function automatically returns null. The workaround here is to use ``NVL`` to return an alternative value when an expression is NULL. Let's say we want to find out the max value between DATE 1 - 3. We can change the statement from ``` SELECT GREATEST( DATE1, DATE2, DATE3 ) FROM MY_TABLE; ``` to ``` SELECT GREATEST( NVL(DATE1, TO_DATE('1970-01-01', 'YYYY-MM-DD')), NVL(DATE2, TO_DATE('1970-01-01', 'YYYY-MM-DD')), NVL(DATE3, TO_DATE('1970-01-01', 'YYYY-MM-DD')) ) FROM MY_TABLE; ``` By adding ``NVL``, we can ensure that the expected return value is not NULL.