This challenge allows you to practice the concepts and techniques learned over the past week and apply them in a concrete project. This Sprint, we learned how hash tables combine two data structures to get the best of both worlds and were introduced into the fascinating world of blockchains. In your challenge this week, you will demonstrate proficiency by solving algorithms in Python using hash tables and add another key feature to your blockchain.

Read these instructions carefully. Understand exactly what is expected before starting this Sprint Challenge.

This is an individual assessment. All work must be your own. Your challenge score is a measure of your ability to work independently using the material covered through this sprint. You need to demonstrate proficiency in the concepts and objectives introduced and practiced in preceding days.

You are not allowed to collaborate during the Sprint Challenge. However, you are encouraged to follow the twenty-minute rule and seek support from your PM and Instructor in your cohort help channel on Slack. Your work reflects your proficiency in Python and your command of the concepts and techniques in related to hash tables and blockchains.

You have three hours to complete this challenge. Plan your time accordingly.

Commit your code regularly and meaningfully. This helps both you (in case you ever need to return to old code for any number of reasons and your project manager.

This sprint challenge is divided up into three parts: Hash tables coding, blockchain coding, and a short interview covering parts of hash tables and blockchain.

Explain in detail the workings of a dynamic array:

• What is the runtime complexity to access an array, add or remove from the front, and add or remove from the back?

The runtime complexity to access an element in the array is O(n) because you don't know where in the array that item is located so potentially you would be iterating through every single element The runtime complexity to add/remove from the front of an array is O(n) because you need to shift everything in memory to go after that element, one at a time, since arrays are contiguous blocks of memory The runtime complexity to add/remove from the back of an array is O(1) because in an array that is the only place where some free slots exist. An item can be added there instantly

• What is the worse case scenario if you try to extend the storage size of a dynamic array?

The runtime complexity to resize a dynamic array is O(n) because each element needs to be added to the new array one-by-one

Explain how a blockchain is structured. What are the blocks, what is the chain? How is the data organized?

A blockchain starts with a genesis block of data which contains a dictionary of information like timestamp, previous_hash, and a proof. Each successive block follows the same pattern including having the hash value of the previous block making it sort of like a reverse Linked List. The chain is the sequence of these blocks starting at the genesis and going up to the present one. The data is organized as text in a dictionary that is hashed to create a fixed length hash which secures the data

Explain how proof of work functions. How does it operate. How does this protect the chain from attack. What kind of attack is possible?

The proof of work is how the blockchain can succeed. Each of the miners will work on this proof in order to try to be the first one to solve it so they can be the one to mine the next block. This is also how the block mining can be slowed down by providing the miners with appropriately difficult problems to solve. Attackers may want to try to modify their transactions in order to give themselves lots of money. However this makes it hard in practice because of the hash protection. Plus they will have to modify each of the previous hashes all the way to the beginning. But by the time that has happened the chain will have already moved on

For the hash tables portion of the sprint challenge, you'll be working through two algorithm problems that are amenable to being solved efficiently using a hash table. You know the drill at this point. Navigate into each exercise's directory, read the instructions for the exercise laid out in the README, implement your solution in the .py skeleton file, then make sure your code passes the tests by running the test script with make tests.

A hash table implementation has been included for you already. Your task is to get the tests passing (using a hash table to do it). You can remind yourself of what hash table functions are available by looking at the hashtable.py file that is included in each exercise directory (note that the hash table implementations for both exercises differ slightly).

You may not use any advanced, built-in Python functions to solve these problems.

For the blockchain portion of the challenge, you will be writing code for a new miner that will solve a different Proof of Work algorithm than the one we have been working with.

Your goal is to mine at least one coin. Keep in mind that with many people competing over the same coins, this may take a long time. By our math, we expect that an average solution should be the first to find a solution at least once in an hour or two of mining.