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?
Assuming the question is about a dynamic array: accessing is O(1), like a regular array; adding/deleting at from the front is O(n), as the whole of the rest of the array needs be shifted up/down; and adding/removing to the end is O(1) on average, or O(n) when the array needs to be resized to accommodate the new element., as this involves copying the entire array.
-
What is the worse case scenario if you try to extend the storage size of a dynamic array?
I suppose the worst case scenario is there's no memory left to grow into! E.g. if the dynamic array is running on some kind of small, embedded chip.
But to interpret the question a little differently: The worst case scenario is O(n), as every existing element of the array needs to be copied over into a new, larger array.
Explain how a blockchain is structured. What are the blocks, what is the chain? How is the data organized?
A blockchain is just that, a 'chain' of 'blocks' where a block is just an object comprising certain data and methods 'chained' to other blocks with hash codes. Specifically, one block is 'chained' to the next when the hash of its hash (an identifying code) together with its 'proof' (a number, usually; also sometimes called a 'nonce') and perhaps an encoding of all of its transactions (objects keeping track of amounts, senders, and recipients) meets some predefined criterion — usually, that it contains some number of leading zeroes.
In the case of Bitcoin, this criterion is massaged to ensure that a new coin is added to the blockchain (or 'mined') about every 10 minutes. This is done by increasing or decreasing the number of leading zeroes required.
So, a block contains transactions, a 'proof', and the hash of the previous block as well as an index and a timestamp. At least.
Explain how proof of work functions. How does it operate. How does this protect the chain from attack. What kind of attack is possible?
A proof of work is just an arbitrarily difficult (i.e. resource-intensive) computational task. It ensures that mining blocks is rare, and that — because a block's hash depends on the hash of the previous block, and its on the block before it, and so on — blocks inside the chain cannot be tampered with without the need to re-meet the proof-of-work of all of the blocks which come after them: an almost impossible computational task, ever more impossible the farther back in the chain tampering is attempted.
One possible attack is to pool together vast computational resources — perhaps with malware that infects people's computers — and try to re-write block history. But it's probably more efficient, if one has accesss to vast computational resources, to simply mine new blocks.
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.
| OBJECTIVE | TASK | 1 - DOES NOT MEET EXPECTATIONS | 2 - MEETS EXPECTATIONS | *3 - EXCEEDS EXPECTATIONS |
|---|---|---|---|---|
| implement and describe how high-level array functions work down to the memory level | Interview Question | The student fully explains two or fewer of the bulleted items in the solution repo. | The student fully explains at least 3 of the items in the bulleted list. | The student fully explains 4 or more items from the bulleted list. |
| implement and utilize basic hash table + handle collisions and resizing in a hash table | Hash Problem 1 & 2 | Tests do not pass on one or both problems, or solutions do not use hash tables. | Tests pass on both problems. Solution utilizes a hash table. | Tests pass on on both problems with solutions utilizing hash tables, linear runtime complexity, no flake8 complaints. |
| diagram and code a simple blockchain, utilizing a cryptographic hash | Interview Question | The student fully explains two or fewer of the bulleted items in the solution repo. | The student fully explains at least 3 of the items in the bulleted list. | The student fully explains 4 or more items from the bulleted list. |
| utilize a Proof of Work process to protect a blockchain from attack | Blockchain Problem | The student is unable to mine a coin before the end of lunch. | The student was able to mine a coin before the end of lunch. | The student presented a unique solution that was able to mine more than 100 coins before the end of lunch. |
| build a protocol to allow nodes in a blockchain network to communicate to share blocks and determine consensus. | Interview Question | The student fully explains two or fewer of the bulleted items in the solution repo. | The student fully explains at least 3 of the items in the bulleted list. | The student fully explains 4 or more items from the bulleted list. |