DEV Community: Max Kumundzhiev

Talk with You Series #3

Max Kumundzhiev — Sat, 27 Jul 2024 07:33:21 +0000

Intro

Today we gonna cover the theoretical and practical foundations of Binary Tree as well as the ways to traverse it.

Tree, in general, is the subset of graphs family, which follow certain rules within their construction and management.

Binary Trees

Binary Tree is a concrete data structure in which each node has at most two children. Commonly every node has 3 attributes: data, leftChild and rightChild.

It is used to classify Binary Tree with different types by their "criteria".

Let's see which types (classes) exists out there:

Types of Binary Tree based on the number of children (criteria: node number of children)
Types of Binary Tree on the basis of the completion of levels (criteria: tree completion of levels)
Types of Binary Tree on the basis of the node values (criteria: node values)

Let's have a look at each type separately.

Types of Binary Tree based on the `number of children`

Full Binary Tree
Degenerate (or pathological) tree
Skewed Binary Tree

Types of Binary Tree on the basis of the `completion of levels`

Complete Binary Tree
Perfect Binary Tree
Balanced Binary Tree

Types of Binary Tree on the basis of the `node values`

Binary Search Tree
AVL Tree
Red Black Tree
B Tree
B+ Tree
Segment Tree

If you d like to dig deeper about each of them, here's complete overview.

Good, now we have an understanding what is Binary Tree conceptually as well as what might be the types.

Now, let's code it up. To recall, Binary Tree consists of nodes, where each node has data, leftChild and rightChild properties.

from typing import Any

class TreeNode:
    def __init__(self, data: Any):
        self.data = data
        self.left = None
        self.right = None

# define all the nodes we need
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')

# connect all the nodes between each other
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD

# what we've got
    R
   / \
  A   B
 / \ 
C   D

The next thing which is crucial - how to traverse Binary Tree.

Traverse Binary Tree

Commonly, there are 2 main ways (types) to traverse Binary Tree, Breadth First Search (BFS) and Depth First Search (DFS).

BFS stands for when the nodes on the same level are visited before going to the next level in the tree. This means that the tree is explored in a more sideways direction.
DFS stands for when the traversal moves down the tree all the way to the leaf nodes, exploring the tree branch by branch in a downwards direction.

Additionally, there are three types of DFS traversals:

pre-order
post-order
in-order

DFS and it's types of traversal

"""
preOrder - is done by visiting the root node first, then recursively do a pre-order traversal of the left subtree, followed by a recursive pre-order traversal of the right subtree.

This traversal is "pre" order because the node is visited "before" the recursive pre-order traversal of the left and right subtrees.
"""

def pre_order(node):
    if node:
        print(node.value)
        pre_order(node.left)
        pre_order(node.right)

"""
postOrder - works by recursively doing a Post-order Traversal of the left subtree and the right subtree, followed by a visit to the root node.

What makes this traversal "post" is that visiting a node is done "after" the left and right child nodes are called recursively.
"""

def post_order(node):
    if node:
        post_order(node.left)
        post_order(node.right)
        print(node.value)

"""
inOrder - does a recursive In-order Traversal of the left subtree, visits the root node, and finally, does a recursive In-order Traversal of the right subtree.

What makes this traversal "in" order, is that the node is visited in between the recursive function calls. The node is visited after the In-order Traversal of the left subtree, and before the In-order Traversal of the right subtree.
"""

def in_order(node):
    if node:
        in_order(node.left)
        print(node.value)
        in_order(node.right)

That's it for today. Wrapping, we've revamped what is Binary Tree, it's types split by criteria and what are the ways to traverse it.

Talk with You Series #2

Max Kumundzhiev — Sun, 21 Jul 2024 08:07:51 +0000

Intro

Today we gonna kick off our overview about concepts which are used to tackle various algorithmic problems. An understanding of a certain concept might give you an intuition from which angle to start thinking about the potential solution.

There are different but not too much concepts out there. Today I will invest your attention into sliding window concept.

Sliding Window

The concept of the sliding window is a bit more involved, than at first sight. I will demonstrate that within practical examples. For now, keep in mind, conceptual idea is that we will have some window which we have to move. Let's start from the example right away.

Assume you have an array of integers and predefined size of the subarrays. You are asked to find such a subarray (aka window) which sum of values would be maximum among others.

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

Well, looks quite straightforward:
(1) sliding window of size 2
(2) 2 subarrays
(3) count the sum of each
(4) find the max between them

Let's implement it.

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum

Well, seems we've just efficiently used the concept of sliding window. Actually, not exactly. We might get "proof" of that by understanding the time complexity of the solution.

The complexity will be O(l)*O(w), where l is amount of windows in array and w is amount of elements in window. In other words, we need to traverse l windows and for each l-th window we need to calculate the sum of w elements.

What is questionable in here? Let's conceptually depict the iterations to answer the question.

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|

The answer is that even though we're sliding the array, on each iteration we need to "recalculate" k-1 elements which were already calculated on the previous iteration.

Basically, this insight should suggest us to ask a question:

"is there a way to take advantage of calculations from previous step?"

The answer is yes. We can get the sum of elements of the window by adding and subtracting the first and the next after the window elements. Let me put this idea into the code.

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

Here we might see, at the point when we constructed the subarray of length of size, we started subtracting the very first element from the window sum, what allows us to reuse calculations from the previous step.

Now, we might say we efficiently utilised the concept of sliding window whereas we got a proof checking the time complexity, which reduced from O(l*w) to O(l), where l is the amount of windows we will slide.

The major idea which I'd like to highlight, sliding window concept is not just about slicing the iterable with the window of specific size.

Let me give you some problems, where we will learn how to detect the problem might involve a sliding window concept as well as what exactly you might do with the window itself.

Problems Overview

Since I'm talking here just about concepts, I'd skip "how to count something inside of the window".

Problem one

Given an array, find the average of all contiguous subarrays of size K in it.

Sliding window ? - contiguous subarrays the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
Do we know the size of sliding window ? - yeap, K, we got the size of window, which should be the length of K.
What exactly are we supposed to manage/check within sliding window ? - find the average of ...

Good, now we might define the approach the way: iterate over the input array with the window of size K. On each iteration count the average of window ...

Problem two

Given an array of positive numbers and a positive number K, find the maximum sum of any contiguous subarray of size K.

Sliding window ? - contiguous subarrays again, the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
Do we know the size of sliding window ? - yeap, K, we got the size of window, which should be the length of K.
What exactly are we supposed to manage/check within sliding window ? - .. the sum ...

Now: traverse the input array with the window of size K. On each iteration count the sum of window ...

Problem three

Given an array of positive numbers and a positive number S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.

Sliding window ? - contiguous subarrays again, the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
Do we know the size of sliding window ? - actually no, we need to figure it out.
What exactly are we supposed to manage/check within sliding window ? - ... sum is >= to S ...

Now, we might define the approach the way: "firstly, iterate over input array and construct such a first window, which would satisfy the conditions (sum is >= to S). Once done, move window, managing window start and end ..."

Problem four

Given a string, find the length of the longest substring in it with no more than K distinct characters.

Sliding window ? - longest substring, the first keyword, meaning we should take care of windows, which would represent a substrings.
Do we know the size of sliding window ? - no, we need to figure it out.
What exactly are we supposed to manage/check within sliding window ? - ... amount of distinct characters ...

The approach in here is a bit more involved, thus I'll skip it here.

Problem five

Given an array of integers where each integer represents a fruit tree, you are given two baskets, and your goal is to put the maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.
You can start with any tree, but you cant skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.
Write a function to return the maximum number of fruits in both baskets.

Seems not that obvious, let's simplify the conditions first.

There is an input array. Array might contain only 2 distinct digits (buckets). You are asked to find such contiguous subarray whose length would be the maximum.

Now it's times easier to see we might work with sliding window concept.

Sliding window ? - contiguous subarray
Do we know the size of sliding window ? - no, we need to figure it out.
What exactly are we supposed to manage/check within sliding window ? - ... whether digits are distinct and the length of the window ...

Problem six

Given a string and a pattern, find out if the string contains any permutation of the pattern.

Firstly, we do have 2 strings, original and pattern. We know we have somehow compare original and pattern, what lead to the idea, we need construct the window of size of the pattern and further perform permutations check. This means, we might use sliding window concept.

Outro

When you deal with sliding window keep in mind following questions:

do you understand the size of the window
do you understand how to construct the window
do you understand how to move/shrink the window
do you understand what is valid/invalid window
do you understand how to make invalid window valid one

Talk with You Series #1

Max Kumundzhiev — Tue, 09 Jul 2024 18:10:20 +0000

**cover image mirror mood at the moment of posting

Wanna start with the thoughts, that for a while, I do have a habit to write down challenges and their potential solutions I used to face on a daily basis, whether it was part of my job or free time activities.

Starting from this post, I've decided to introduce "Talk with You" series, where I'd post them in here (at least for now, at most once in few days) to spot them out to the public.

On one hand now I'll glimpse in here from time to time instead of my well structured notes to revamp some information and DevCommunity gonna handle storage, navigation in ascending order and all the other stuff, on another one I believe the things I write here might find the audience not on my behalf only. Fasten, let's kick off.

Count Occurrences

Quite often working with DS u need to count an amount of occurrences of values and afterwords to query those in an efficient manner, preferably Time O(1).

Obviously, you might think of creating HashTable and then traverse DS, populating the HashTable. That's true and might look as:

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

Today I faced an alternative approach which would perfectly work on lists of digits avoiding usage of HashTable (sometimes it might be a necessity).

The idea behind is firstly to get the maximum value from list and create a new list of length of the maximum value, which will be used as indices mapping.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

Now, lets' traverse original list and map occurrence of each value in indices list.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

What just happened. Well, basically, we took value from original list and used it as index in our indices list (and incremented value at index).

Now if we would like to represent our results using mapping list, we might say, there are 0 zero-s because at index 0 we have value 0, at index 1 we do have value of 2, meaning there are 2 one-s, at index 2 we have value of 1, meaning there are 1 two-s, etc.

Mirror Elements in Matrix

Even though holding 2 degrees BSc and MSc, when I find out a new math trick, I'm still getting the feelings of fascinating, aka "gosh, that's so simple and works".

Okay, back to the topic, assume you have a matrix of N*N and you need to reverse rows and columns in way to get the maximum sum of all the elements (row by row).

From the first glimpse, perhaps you even do not know where to start from. But here is the trick with mirrored elements.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

The key point in here is, A in the matrix might be swapped only by another A-s. Lets image we are in the top left corner A (which is 1) and we'd like to know if there are another A (only mirrored A) which is grater. And indeed, we do have such in right upper corner (9).

Following the logic and recalling the original problem (max sum reversing rows and columns) we might conclude that in reality we do not need to perform any reverse operations, instead just look up the max value among mirrored ones. And that's it.

Stack. Trade-off between Time and Space complexity.

Assume you've got a task to implement a stack wrapper with only 3 functionalities: (1) pop (2) push (3) get_min. You might use interface of stack for (1) pop and (2) push, however still need to implement (3) get_min. Annnd get_min() should work for O(1) Time.

Well, when I's firstly tackling the problem, I completely forgot about a trade-off, which says: "When you optimise Time performance, you probably get worse with Space and wise versa". Why it's important, cause I started thinking of optimised DS which lead me to HashTables, but I truly missed naive lists, which could work for O(1) (amortised) as well.

So I reached the point when I was creating a HashTable where I might store each state of a wrapper class ... will stop here cause "simpler is a better option" (sometimes). Let's see the implementation with additional list to store min value for every state of stack.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

As simple as it is.

Concluding

keep coding and developing
remember about trade-offs and do not overcomplicate (when u are not asked)

Talk with You Series #1

Max Kumundzhiev — Tue, 09 Jul 2024 18:10:20 +0000

**cover image mirrors mood at the moment of posting

Starting from this post, I've decided to introduce "Talk with You" series, where I'd post them in here (at least for now, at most once in few days) to spot them out to the public.

Count Occurrences

Quite often working with DS u need to count an amount of occurrences of values and afterwords to query those in an efficient manner, preferably Time O(1).

Obviously, you might think of creating HashTable and then traverse DS, populating the HashTable. That's true and might look as:

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

Today I faced an alternative approach which would perfectly work on lists of digits avoiding usage of HashTable (sometimes it might be a necessity).

The idea behind is firstly to get the maximum value from list and create a new list of length of the maximum value, which will be used as indices mapping.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

Now, lets' traverse original list and map occurrence of each value in indices list.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

What just happened. Well, basically, we took value from original list and used it as index in our indices list (and incremented value at index).

Mirror Elements in Matrix

Even though holding 2 degrees BSc and MSc, when I find out a new math trick, I'm still getting the feelings of fascinating, aka "gosh, that's so simple and works".

Okay, back to the topic, assume you have a matrix of N*N and you need to reverse rows and columns in way to get the maximum sum of all the elements (row by row).

From the first glimpse, perhaps you even do not know where to start from. But here is the trick with mirrored elements.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

Stack. Trade-off between Time and Space complexity.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

As simple as it is.

Concluding

keep coding and developing
remember about trade-offs and do not overcomplicate (when u are not asked)

DEV Community: Max Kumundzhiev

Talk with You Series #3

Intro

Binary Trees

Types of Binary Tree based on the number of children

Types of Binary Tree on the basis of the completion of levels

Types of Binary Tree on the basis of the node values

Traverse Binary Tree

DFS and it's types of traversal

Talk with You Series #2

Intro

Sliding Window

Problems Overview

Outro

Talk with You Series #1

Count Occurrences

Mirror Elements in Matrix

Stack. Trade-off between Time and Space complexity.

Talk with You Series #1

Count Occurrences

Mirror Elements in Matrix

Stack. Trade-off between Time and Space complexity.

Types of Binary Tree based on the `number of children`

Types of Binary Tree on the basis of the `completion of levels`

Types of Binary Tree on the basis of the `node values`