
Iteration is taking each item from a collection of items. That collection does not need to be indexed. For example, sets in python are not indexable, but we can iterate over sets. Just imagine you have a bucket of items and you are just randomly picking an item out of the bucket.

```py
     my_set={'a','b','c','d'}
     for item in my_set:
        print(item)

    {'b','d','a','c'} # Note items are not printed in order
```

To iterate over collections, we need to implement a method like `getme_next_item()` to get the next item. After creating this method, we will encounter three issues to solve:

1- How to tell python to stop the iteration. Otherwise we will be getting inifite amount of items

2- How are we going to call **for** to iterate.

3- Are we going to be able to restart the iteration?

Let's start our journey with defining a method to get the next item.

```py
class Square:
    def __init__(self):
        self.i = 0
    # since next is a python keyword, I name it next_
    def next_(self):
        result = self.i ** 2
        self.i += 1
        return result

sq=Square()
# we can call next_() infinitely and it will always print the square of next item. We will have an infite collection
sq.next_()
```

Let's start to solve the first issue: We specify the size of the collection when we create the instance, then we keep track of how many times we called `next_`. If we call `next_` too many times we raise `StopIteration`.

```py
    class Square:
        def __init__(self, length):
            self.i = 0
            self.length = length
        def next_(self):
            if self.i >= self.length:
                raise StopIteration
            else:
                result = self.i ** 2
                # We track how many times we called next_
                self.i += 1
                return result
```

Now when we create a new instance of Square, we will pass "length" argument, so if we call `next_` more than "length" times, we raise StopIteration.

![stop iteration in python iterable](stop-iteration.png)

We tackled the first issue, but we still cannot iterate using for loops and once the iteration start we cannot restart it because it will raise StopIteration after we call more than length times.

Before we proceed, let's write our class in a pythonic way. In current implementation calling `sq.next_()` is annoying. Python has built in `__next__` function and when you call this on an object, it is going to call the special method, `__next__` inside the object. Similar to `next`, python also has `len`, which will invokes the `__len__` method of the object.

```py
class Square:
    def __init__(self, length):
        self.length = length
        self.i = 0
    # next(instance) will invoke this
    def __next__(self):
        if self.i >= self.length:
            raise StopIteration
        else:
            result = self.i ** 2
            self.i += 1
            return result
    # len(instance) will invoke this
    def __len__(self):
        return self.length
```

```py
    sq=Square(5)     # pass the length argument
    next(sq)  # this will return the next item.
```

let's tackle the second issue. How are we going to iterate using **for**.

### Iterator Protocol

The iterator protocol has two methods. \***\*iter**:** This should just return the instance itself
\*\***next**:** Getting the next item. We already implemented this.

If we implement those 2 methods, python is aware that we are implementing the iterator protocol. Therefore, an **iterator** is an object that implements those two methods. If an object is an iterator, we can now use it with **for** loops. Our Square class already has **next** method, we just need to add \***\*iter\*\***.

```py
class Square:
    def __init__(self, length):
        self.length = length
        self.i = 0
    # for loop calls this method first, gets the iterator obj, then works on this object
    def __iter__(self):
        print('calling __iter__')
        return self
    def __next__(self):
        print('calling __next__')
        if self.i >= self.length:
            raise StopIteration
        else:
            result = self.i ** 2
            self.i += 1
            return result
```

```py
sq=Square(3)
for item in sq:
    print(item)
# calls the __iter__ first
calling __iter__
calling __next__
0
calling __next__
1
calling __next__
4
calling __next__
```

If we call **for** on **sq** again, we get nothing because we finished iterating. We can never restart our iteration. Once we looped through all the items the iterator has been **exhausted**, we can no longer use it. To loop second time, we have to create a new instance.

      Iterators are just throw away objects, once we loop through it, we can no longer use it again.

If we closely look at the Square class, it does two things. It mainstains the collection and then iterating over the collection. So when we are done with iterating, data is also thrown away which is wasteful. To tackle the last issue, we need to separate those two things. Maintaining the data of the collection should be one object and iterating over the data should be a separate object. Therefore we need to learn a new concept: **iterable** and thet will be in the next post.

### Consuming Iterators Manually

We do not have to use for or comprehensions to iterate over iterators. As I showed above, for loop calls the **iter** first and then calls the **next**, we can call those manually

```py
i="I am an iterator"
#  iter() calls the __iter__() of i
iter_i=iter(i)
# iter(i) returns iterator and stores it as iter_i
next(iter_i)
# next calls the __next__() of the iterator iter_i
    'I'
next(iter_i)
    ' '
next(iter_i)
    'a'
```

```



```

Next ----> [iterables on python](https://bingolyilmaz.com/blogs/iterables-on-python)


Iterators on Python


![block and blockchain](block-hash.png)

On the [previous part](https://bingolyilmaz.com/blogs/coding-bitcoin-in-javascript-part-1) of this series, I wrote code for Block class, explained nonce and difficulty. In this part I will be writing about Blockchain class which is responsible for connecting the blocks. To better understand how blockchain works, here is a [great video](https://www.youtube.com/watch?v=_160oMzblY8) to visually show what blockchain is and how nonce works.

Constructor is where we define what properties each instance of Blockchain class will have.

```js
class Blockchain {
  constructor() {
    // first block is genesisBlock
    this.chain = [Block.getGenesisBlock()];
    this.getLastBlock = function () {
      return this.chain[this.chain.length - 1];
    };
}

```

Then we add a method to mine block and add it to the chain. We will be using this method at the end of the post.

```js
class Blockchain {
  constructor() {
    // first block is genesisBlock
    this.chain = [Block.getGenesisBlock()];
    this.getLastBlock = function () {
      return this.chain[this.chain.length - 1];
    };
  }

  // Each instance of Blockchain class has a secret property called "prototype'. Methods that defined outside constructor are stored in prototype.
  addBlock({ data }) {
    // check mineBlock() in the first part of the post
    const newBlock = Block.mineBlock({
      lastBlock: this.chain[this.chain.length - 1],
      data,
    });
    this.chain.push(newBlock);
  }
}
```

## What exactly is Mining?

Bitcoin's money supply is created by mining. Mining is an incentive system. Since it needs a lot of work to be done, miner gets two types of reward: New coins that created with each new block and transaction fees from all the transactions included in the block. All transactions have the different transaction fees, so the miners can look for the transaction that has the highest fee, and validate those.

To earn these rewards, miners compete to solve a difficult mathematical problem based on a cryptographic hash algorithm. The solution to the problem, called the **Proof-of-Work**, is included in the new block and acts as proof that the miner expended significant computing effort. That proof is actualy finding the **nonce** value. Bitcoin was first mined in 2009 and mining reward was 50 bitcoin which values about 3 million dollars as of writing this blog post. In November 2012, the new bitcoin issuance rate was decreased to 25 bitcoin per block. Every 4 years, which is precisely after 210000 blocks get created, that rewards cuts in half, in 2016 it was 12.5 and since 2020, it was 6.25. That means every 4 year, there will be less and less bitcoin to be sold by miners, that one reason why bitcoin price will keep go up as new supply lowers and demand gets higher.

       The first transaction in any block is a special transaction, called a **coinbase transaction**. This is the transaction that miner receives the mining reward.

Mining secures the decentralized bitcoin network. By mining, transactions are validated and cleared. Before creation of a new block, there is a pool for new transactions. After a new block gets created, new transactions will be stored in the transaction pool. Miner's job is to validate those transactions. When Blockchain calls **addBlock** method, addBlock will receive those transactions as data argument. Validation of the transaction will be done by the Transaction class which we will discuss in the next post.

In bitcoin, a new block gets created in every 10 minutes, by those valid transactions. Once a transaction becomes a part of the block it is called **confirmed**, then receiver can spend it. The block that contains the transaction is counted as one confirmation of that transaction. Each block that gets added to this block will strenghtening the trust in that transaciton. By convevntion, any transaction with more than 6 confirmations is considered irrevocable.

Any system, such as a server, desktop application, or wallet, that participates in the bitcoin network by “speaking” the bitcoin protocol is called a bitcoin node. Any bitcoin node that receives a valid transaction it has not seen before will immedi‐
ately forward it to all other nodes to which it is connected.Thus, the transaction rapidly broadcasted across the peer-to-
peer network, reaching a large percentage of the nodes within a few seconds. Some of the nodes on the bitcoin network are specialized nodes called miners which do not keep the all the transactions in the blockchain, they just listen to those new incoming transactions.

## The Supply of Bitcoin Is Limited to 21 Million

There are only 21 million bitcoins that can be mined in total. As of writing this post, 18.65 million bitcoin has been mined. That does not mean that 18.65 million bitcoin is in circulation. Because people who lost access to their bitcoin account, or have died without transferring their bitcoin, actual amount of bitcoin in circulation is less than 18.65. Also, in the first months of bitcoin, new bitcoins were mined only by its creator, Satoshi Nakamoto. His account has about 1.1 million untouched bitcoins which is worth of $66 billion. If bitcoin was created by a single person and s/he was still alive, he would definitely touch this money.

How do we know that Satoshi has 1.1 million bitcoin in his account? Blockchain technology offers decentralized and private system. No name is written on the transactions or on the wallet address in the block. If Alice sends money to Bob, we do not see their name we just see their wallet id.

    from : "543f9f9118a5ad.2836dd734d2804fe65fa35779"
    to   :  "186f9f998a5e2836dd734d2804fe65fa3577119"

Since Satoshi is the first miner, and mining rewards go to the same address, we say it belongs to Satoshi.

     In blockchain, we can see all the previous transactions
     We cannot see who sent it and we cannot alter the transaction history.

In fact we could apply this in voting system. Every registered voter would have their unique id, they will be voting in the blockchain system, everyone else could see the results without altering it.

Since every 4 years mining reward cuts in half, the last bitcoin will be mined by the year 2140. There will not be more than 21 million bitcoins. Bitcoin can not be inflated by creating new bitcoin the way how central banks prints more and more money. Price of anything depends on the intersection of demand and supply. Since supply can not be altered, we just need to predict the demand. If demand increases, price will rise, if demand decreases price will drop

         Bitcoin has been deflationary so far  meaning that purchasing power has been increasing.

### Transaction Pool

Let's get back to coding. Transaction pool is not stored in the blockchain, therefore we will write another class to handle this pool.

```js
// we use this to validate the transactions
const Transaction = require("../transaction/Transaction");

class TransactionPool {
  constructor() {
    // this is where transactions gets stored. it dynamically gets populated by incoming transactions
    this.transactionMap = {};
  }
  // after trnasactions are added to a new block, it gets cleared
  clear() {
    this.transactionMap = {};
  }
  // every transaction has id. this is how transactions are stored
  //     this.transactionMap = { idOfTranaction : transactionObject };
  setTransaction(transaction) {
    this.transactionMap[transaction.id] = transaction;
  }
  // this will be used later on for synchronization. If a  node was shutdown, when it runs again, it has to get the latest data
  setMap(transactionMap) {
    this.transactionMap = transactionMap;
  }
  // This checks if incoming transaction was received before
  existingTransaction({ inputAddress }) {
    const transactions = Object.values(this.transactionMap);
    return transactions.find(
      (transaction) => transaction.input.address === inputAddress
    );
  }
  // Validates all transactions
  validTransactions() {
    return Object.values(this.transactionMap).filter((transaction) =>
      Transaction.validTransaction(transaction)
    );
  }
  // when we replace a new chain, I will talk about it later, we go throught all the transactions inside new blockchain,
  // if any transaction inside transactionPool exists in new blockchain, we delete that transaction from the transaction pool.
  clearBlockchainTransactions({ chain }) {
    for (let i = 1; i < chain.length; i++) {
      const block = chain[i];

      for (let transaction of block.data) {
        if (this.transactionMap[transaction.id]) {
          delete this.transactionMap[transaction.id];
        }
      }
    }
  }
}
```

To summarize, for mining we need 4 things:

1- TransactionPool which stores the transactions that need to be mined and then clears the list.

2- Miner's wallet to send the reward

3- Blockchain to add the new block to the chain

4 Lastly a broadcasting mechanism to broadcast the new chain.

```js
class TransactionMiner {
  constructor({ blockchain, transactionPool, wallet, pubsub }) {
    this.blockchain = blockchain;
    this.transactionPool = transactionPool;
    this.wallet = wallet;
    this.pubsub = pubsub;
  }

  mineTransactions() {
    //  gets the all valid transactions
    const validTransactions = this.transactionPool.validTransactions();
    // sending the reward to the miner is also a transaction, therefore Transaction class sends the reward
    // Transactions will be the topic of next part
    validTransactions.push(
      Transaction.rewardTransaction({ minerWallet: this.wallet })
    );
    // Blockchain class adds the new block by mining the validTransactions
    this.blockchain.addBlock({ data: validTransactions });
    // This broadcasts the new chain to each note to be replaced as new chain which I will be writing about it later
    this.pubsub.broadcastChain();
    // after transactions are mined, transactionPool clears itself.
    this.transactionPool.clear();
  }
}
```

I mentioned transaction a alot but I have not told you anything about it. In the next part I will dive deep into the transaction, write the TransactionPool class and introduce you Wallet class which uses cryptography. This post started with Blockchain class but it is not completed yet. As we learn more new concepts, I will write other responsibilites of Blockchain class.


Coding Bitcoin with Javascript Part-2


    You are given an array of positive integers where each integer represents the height of a vertical line on a chart. Find two lines which together with the x-axis forms a container that would hold the greatest amount of water. Return the area of water it would hold.

imagine you are given this array.`[1,8,6,2,9,4]`. Each element maps to its correspondig line in order. Our goal is picking two lines that would form a container with the bottom x-axis that hold certain area of water. In this case, greates are would be between 8 and 9. What we have to imagine is that if water were to be poured into this, it would fill up a certain amount of water, which is equal to the shaded area. The area goes up to the 8 because the water will spill over after above 8. We need to return the area that this container holds. area would be 24. When we calculate the width, we consider each element is 1 unit away from previous one.

![container with most water](container.png)

Let's consider the edge cases:

1- Does the thickness of the lines affect the area?

No, assume that lines take up no space.

2- Do the left and right sides of the graph count as walls?

No. sides cannot be used to form a container. We have to use a value inside of the array in order to form the wall.

3- Does a higher line inside our container affect our area?

![container with most water](container-2.png)

On the above example, greates area is between 7 and 6, assume that none of the lines between 6 and 7 affect the area calculation.

The question seems very intimidating but the coding the solution will take only a few lines of code. Let's start with the naive approach, using nested for-loops.

This question is maximal value question that means we will run through all combinations and return the value, unlike [sum of two integer question](https://bingolyilmaz.com/blogs/sum-of-two-integers-in-array). In that question when we find the target value we stop searching and returned the indices. The maximal value can be determined if we have calculated the area of every single container first.

Before diving into coding, let's think through the logical solution. We will be comparing 2 values, from those values, we drive lenght and width. As you saw fromt the first image, greatest amount of water was between 8 and 9. Since water will spill over above 8, we picked the 8 as lenght. So given two elements, "a" and "b":

      Length = minimum(a,b)

Width will be the difference between their indices. 4^th^

      Width = b<sub>i</sub> - a_i  // i is for index

      Area = Length * Width = min(a,b) * (b_i-a_i)

When we calculate the area of first pair of values, we will be storing it as our maxValue. Then we calculate the area of next pair, we compare the new area with the maxValue, if new area is greater than maxValue, we store this as our new maxValue. We will do the same operations till we calculate the area for all pair of elements and we return the maxValue.

```js
const getMaxWater = (heights: int[]) => {
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    for (let j = i + 1; j < heights.length; j++) {
      const height = Math.min(heights[i], heights[j]);
      const width = j - i;
      const area = height * width;
      maxArea = Math.max(maxArea, area);
    }
  }
  return maxArea;
};
```

Space complexity of this solution is O(1) because no matter how many iteration we do, we will be storing only maxArea in the memory and it does not scale, it is primitive value. However since we have two nested for loops, its time complexity T: O(N^2). Our lovely interviewer will definitely ask if we could optimize the code. To optimize the code, we use two pointers technique.
We initialize two pointers at the opposite sides of the array.

We have to decide under which conditions we are going to move the pointers. There are two things we have to pay attention as we compare the values.

        const heights= [1,8,6,2,9,4]

First pointer is the index 0 which pointes to 1, and second pointer will be the last index element, which is 4. For the first pointers, area=1\*4=4

Now which pointer is going to shift first. If I shift the first pointer forward, I reach 8, **8 X 4=32** but if I shift the second pointer, I reach 9, **9X1=9**. For this we have to examine the formula more closely.

     Area = Length * Width = min(a,b) * (bi-ai)

No matter which pointer we shift **bi-ai** will always get smaller. So we will be focusing if **min(a,b)** gets larger or smaller. If moving the first pointer increases min(a,b), I will move the first pointer otherwise I will move the second pointer.

For the first values, min(1,4)=4. If I shift the second pointer to 9, min(1,9)=1. Shifting second pointer, gave us a larger value but it had no impact on min(1,4). It is still 1. If I shift the first pointer, from 1 to 8, min(8,4)=4, so for the first step I will shift the first pointer. my first pointer points -->8, and second pointer still points -->4 and min(8,4)=4

If I shift the first pointer from 8 to 6, our new min value, min(6,4)=4 but this time, if I shift the second pointer from 4 to 9, our new min value will be min(8,9)=8. This time it increased.

So the rule is, if the value at first pointer is smaller than value at second pointer, I will be shifting the first pointer, otherwise I will be shifting the second pointer.

```js
const optimal = (heights) => {
  // Instead of types, you could write custom validation rules
  if (!Array.isArray(heights)) {
    throw new Error("input must be an array");
  }
  //   p1 and p2 are indices. [p1,  ,  ,  ,  ,p2]
  let p1 = 0,
    p2 = heights.length - 1,
    maxArea = 0;
  // We will be testing till the pointers meet
  while (p1 < p2) {
    const height = Math.min(heights[p1], heights[p2]);
    const width = p2 - p1;
    const area = height * width;
    maxArea = Math.max(maxArea, area);
    if (heights[p1] <= heights[p2]) {
      // if condion met, shift the first pointer
      p1++;
    } else {
      // otherwise shift the second pointer
      p2--;
    }
  }
  return maxArea;
};
```

## Python Solution

Here is the optimal solution with python.

```py
from typing import List
def max_water(A:List[int])->int:
    left=0
    right=len(A)-1
    maxArea=0
    while left<right:
        height=min(A[left],A[right])
        width=right-left
        maxArea=max(maxArea,height*width)
        if A[left]<A[right]:
            left+=1
        else:
            right-=1
    print(maxArea)
```


Container With Most Water


![google interview question, find two sum in array](google-two-sum.png)

The question is given an array of integers, return the indices of the two numbers that add up to a given target. For example

```js
const myArray = [2, 5, 6, 8, 12];
```

Let's say our target is 20, we will be looking for two integers that adds up 20 and return the indices of those two values.

Before diving into the solution, we have to figure out the edge cases to clearly solve the problem. I come up with 5 edge cases.

    1- Are all numbers in the array positive?
    Yes, consider no negative numbers exist.

    2- Are there any duplicate numbers in the array.
    No

    3- Will there be always a solution?
    No

    4- If there is not any solution, what should I return?
    In this case, return -1.

    5- Can there be multiple pairs that add up to the target?
    No

If you see a similar question, looking for a pair in a given data, we use **two pointer technique**. We initialize one pointer that points at some value, usually the first item in the array. Let's say first item in the array is pointed by "p1". First, I want to test every possible combination that involves **p1**. Then we need second pointer, **p2**. p2 points to the other number that we are looking for in the array so that `p1+p2` is equal to given array. Note that p1 and p2 are indices not the values.

Naive solution for this would be brute force solution which is using two nested for loops.

```js
       const bruteForce= function(nums,target){
           for(let p1=0; p1<nums.length; p1++){
                const numberToFind=target-nums[p1]
                for(p2=p1+1;p2<nums.length,p2++){
                    if(numberToFind===nums[p2]){
                        return [p1,p2]
                    }
                }
            }
            return null
        }
```

We start from first item, `nums[p1]=2`. In the second loop, we go through the rest of the array items which are [5,6,8,12]. Our target is 20. So, second value should be `20-2=18`. Technically we are looking for value 18 in the second iteration for the first value 2. If we cannot find 18 in the second iteration, we move the next item in the array for p1 which is 5, then we loop over [6,8,12] to find `20-5=15`. We go through this steps till we find the soluitoon, if not we return null.

As you know, solving an algorithm question is not enough. We have to analyze the performance with space complexity and time complexity. In this problem, the `nums` array is the only argument that gets scale. We have to consider, how much time and space will our code will take if "nums" array gets really really big.

For space complexity, the only thing that we are doing is, we are setting variable p1 which is a static variable which means it does not scale. So our space complexity is S:O(1).

With time complexity, we have to ask ourself, how many more iterations our code has to run if the "nums" array really gets big. We have two nested for-loop. In first loop, we run through all the elements in the array and in the second loop we run through the rest of elements in the array. For the first element in the array, we will be making `n-1` iterations in the second loop, if there is no solution, we jump to second element and we make `n-2` iterations in the second loop. In the worst case scenorio, If we have no solution we will end up making these many iterations:

      `(n-1) + (n-2) + (n-3) + ...............+ 3 + 2 + 1 = ((n^2)-n) / 2`

Its formula looks scary but it is actually very easy to derive it. We have "n-1" summations. if you sum up first and last item in the sequence, you get `(n-1)+1=n`. If you sum up the second item from the beginnning and from the end, `(n-2)+2=n`. You will end up (n-1)/2 times n. This is how many total iteration we make in second loop. We also make n iterations to iterate over the first array. In both iterations we would be making

        (((n-1)/2)*n)+n=((n^2)+n)/2

Our time complexity would be `T:O(((N^2)+N) / 2)= O(N^2)`. Because if "nums" array gets larger, `N^2` will grow faster than N, so we can neglect N and division, because if N^2 is very large, N^2 divided by 2 will be very large too.

We solved our problem which is a valid solution, but since we have time complexity `O(N^2)`, interviewer will definitely ask us if we could optimize the solution.

## Optimizing the Solution

Optimizing the algorithm question means finding a faster and less wasteful way, so our app will be faster and client will have better user experience. In any algorithm question, we should be avoiding nested for loops. Be aware that reducing the time complexity will increase the space complexity, there is always trade-off between both.

Our logic will change. We will not use 2 pointers technique. Instead, we will have only 1 for-loop, we loop over our array, for each element in the array, we will be calculating `target-elementValue` and store it in a hashmap. The reason why we use hashmap is, time complexity for look up operation is O(1). Our target is still 20. We will be storing `index` as value and `target-elementValue` as key:

`{target-elementValue : value}`

       const myArray=[2,5,6,8,12]

- For the first element, element 2, `20-2=18`, index=0, store={ {18,0} }

- For element 5, we look up if `store[5]` exists, if it does, it will give us the index, and we return that index with current index=1. if it does not exist, we add ,`20-5=15` {15,1} to the store
  `store={ {18,0},{15,1} }`

- For element 6, we look up if `store[6]` exists, it does not so we add {14,2} `store={ {18,0},{15,1},{14,2} }`

- For element 8, we look up if `store[8]` exists, it does not, we add {12,3}
  `store={ {18,0},{15,1},{14,2},{12,3} }`

- For element 12, we look up for `store[12]`, it does exist and its value is 3, so we return [3,4]. 4 is the index of the current item 12.

Here is its code. It is very clear code. One important thing is, anytime you write a function, you have to validate the inputs. I will be using typescript or you could write custom validations with if statement and return errors.

```ts
const findTwoSum = function (nums: number[], target: number): int[] | null {
  // hash map look up is O(1)
  const store = {};
  for (p = 0; p < nums.length; p++) {
    // we are looking for goal
    const goal = target - nums[p];
    if (store[goal]) {
      return [store[goal], p];
    } else {
      store[nums[p]] = p;
    }
  }
  return null;
};
```

## Python Solution

```py
    from typing import List
    def twoSum(nums:List[int],target:int)->List[int] or None:
        m={}
        n=len(nums)
        for i in range(0,n):
            goal=target-nums[i]
            if(goal in m):
                return [m[goal],i]
            m[nums[i]]=i
    return None
```


Front End

Back End

YILMAZ BINGOL

FEATURED POSTS

Iterators on Python

Coding Bitcoin with Javascript Part-2

Container With Most Water

Sum of 2 integers in an array

FRONT END

HTML / CSS / SCSS

JavaScript

React

Angular

BACKEND

Node.js

Python

GraphQL

SQL / NOSQL

Copyrigth Yilmaz Bingol. All rights reserved