counting sheep

gistfile1.txt

# Counting Sheep

**Target Role(s)**:

1. Software Engineer, Platform
2. Software Engineer, Frontend
3. Software Engineer, Mobile
4. Software Engineer, Intern
5. Sr. Software Engineer

## Problem Statement

You are an engineer at Sheeple, a large and prestigious livestock company, and you have been tasked with developing an efficient algorithm for counting sheep within various animal enclosures on company land.

Sheeple’s current layout involves constructing enclosures in a 2D grid, with different numbers of sheep in each one:

|    	|    	|    	|    	|    	|    	|
|----	|----	|----	|----	|----	|----	|
| 17 	| 28 	| 64 	| 56 	| 16 	| 6  	|
| 39 	| 12 	| 2  	| 9  	| 20 	| 35 	|
| 15 	| 7  	| 23 	| 18 	| 21 	| 8  	|
| 88 	| 14 	| 4  	| 16 	| 10 	| 23 	|
|    	|    	|    	|    	|    	|    	|

Your system needs the ability to determine the number of sheep within any contiguous range of enclosures, and receives queries of the form `count_sheep(i1, j1, i2, j2)` to count the sheep in the subrectangle defined with top left corner `(i1, j1)` and bottom right corner `(i2, j2)`, inclusive.

Additionally, by natural processes the number of sheep in each enclosure may change at any given time. Your system receives word of such count changes as queries of the form `update(i, j, new_val)`.

Given that you are able to run any preprocessing job before your system runs in production, implement the following 3 functions to yield the best possible performance:

```python
enclosure_grid = [… [ … ] …] # 2D array

def preprocess():
	# your code here

def count_sheep(i1, j1, i2, j2):
	# your code here

def update(i, j, new_val):
	# your code here
```

What is the runtime complexity of your solution?

## Solution

If `update` calls are much more common than `count_sheep`, then the naive solution of storing the sheep array directly and just updating entries directly on updates is optimal. This is `O(mn)` for `count_sheep` but `O(1)` for `update`, where `m` and `n` are the grid dimensions.

If `count_sheep` calls are much more common than `update`, the easiest and most efficient algorithm to implement is to preprocess the array by storing subarray sums (preprocess the grid by replacing the element at `(i, j)` with the sum of all values in the sub-rectangle from `(0, 0)` to `(i, j)`). This should take `O(mn)` time to preprocess, and leads to being able to compute `count_sheep(i1, j1, i2, j2)` in `O(1)` time by computing

```python
enclosure_grid[i2][j2] - enclosure_grid[i1][j2] - enclosure_grid[i2][j1] + enclosure_grid[i1][i2]
```

Doing this requires `O(mn)` time for the implementation of `update()`, where you will update all values for which the updated value is part of the sum for. Other solutions involving memoization may be valid as well.

## Common Mistakes and Positive Signals

* Good candidates will note that their selected implementation will depend on patterns - does the system tend to receive calls to `count_sheep` more frequently, or `update`?