Forem: Omkar Bhagat

I Made Emoji To PNG Converter

Omkar Bhagat — Wed, 04 Mar 2026 22:21:46 +0000

I used AI to build a tool that solves my own annoyances.

I’ll be honest: I was tired of hunting for high-res, transparent emoji files for my designs and ending up with blurry screenshots or "fake" transparent JPEGs.

Instead of searching for a solution, I sat down with Gemini and we hammered out a tool to handle it once and for all.

The result is emoji-to-png.

It’s a super lightweight utility that renders any Unicode emoji onto an HTML5 <canvas> and spits out a crisp, high-quality PNG. Is it complex? No. Does it save me 10 minutes of frustration every time I need an asset? Absolutely.

The Breakdown:

AI-Assisted: Built this in a fraction of the time by pairing with AI to handle the boilerplate and logic.
Actually Transparent: No more magic-wanding backgrounds. You get a clean, ready-to-use asset.
Crisp Quality: Uses your system's native rendering, so it stays sharp even at larger sizes.

If you’ve ever fought with emoji assets in Figma or Photoshop, this is for you. Check out the code, see how the AI/human collaboration turned out, and grab a copy on GitHub.

👉 See the repo here

HTTP Protocols Explained Simply

Omkar Bhagat — Tue, 03 Mar 2026 23:22:57 +0000

Think of HTTP (Hypertext Transfer Protocol) as the rules for how a waiter (the Server) delivers food (the Data) to your table (the Browser). Over the years, we’ve gotten much better at designing the restaurant.

First let's see the high level picture of each HTTP protocol:

HTTP/1.0: The "One Trip" Rule

In the early days, the waiter was very inefficient. If you wanted a burger, fries, and a shake, the waiter would walk to the kitchen, grab the burger, bring it to you, and then go home. To get the fries, you had to call him back, he’d go to the kitchen, and then come back again.

The Technical Bit: Every single request required opening a new connection.

The Real-World Feel: Loading a page with 10 images felt like watching a slideshow. You’d see one image pop up, then a pause, then the next.

HTTP/1.1: The "Keep-Alive" Upgrade

We realized that firing the waiter after every dish was silly. In HTTP/1.1, the waiter stays at your table until you're done. However, there’s a catch: he only has two hands. He can bring the burger and the fries, but you have to wait for him to come back before he can bring the shake.

Real Example: If a big, heavy high-resolution banner image is at the top of a website, it "clogs" the pipe. The small text files behind it have to wait for that big image to finish loading before they can move. This is called Head-of-Line Blocking.

HTTP/2: The "Magic Serving Tray"

This is where things got high-tech. Instead of a waiter with two hands, imagine a waiter with a massive tray that has dozens of tiny compartments. He can bring the burger, the fries, the shake, and the napkin all at the same exact time.

Key Features:

Multiplexing: Multiple requests happen at once over one connection. No one has to wait in line.

Server Push: If the waiter knows you always want ketchup with your fries, he’ll just bring it before you even ask.

The Real-World Feel: Websites suddenly felt "snappy." Even heavy sites with lots of icons and scripts started loading almost instantly because everything arrived in one big delivery.

HTTP/3: The "No-Traffic" Route

HTTP/2 was great, but it had a weakness: if the waiter tripped on a rug, he’d drop the whole tray, and everything would stop until he cleaned it up. HTTP/3 uses a new system (called QUIC) that handles errors better. If one fry falls off the tray, he keeps walking and delivers the rest of the meal while someone else grabs a replacement fry.

The Real-World Feel: This is huge for mobile phones. If you're walking out of your house and your phone switches from Wi-Fi to 5G, HTTP/3 handles that handoff without dropping your connection or making you refresh the page.

To understand why 1.1 was an upgrade, you have to see how "polite" (and painfully slow) HTTP/1.0 was.

HTTP/1.0: The "Hang Up" Conversation

Imagine you are at a payphone. You have three things to tell your friend, but the phone automatically cuts off after 30 seconds.

Browser: "Can I have index.html?"
Server: "Sure, here is index.html."
[CONNECTION CLOSED]
Browser: (Wait... I need the CSS too! Redialing...) "Can I have style.css?"
Server: "Sure, here is style.css."
[CONNECTION CLOSED]
Browser: (Wait... I forgot the image! Redialing...) "Can I have logo.png?"
Server: "Here is logo.png."
[CONNECTION CLOSED]

Why this was a nightmare? The most "expensive" part of the internet (in terms of time) isn't sending the data—it's opening the connection.

To open a connection, the browser and server have to do a "Three-Way Handshake":

Browser: "Hey, you there?"
Server: "Yeah, I'm here. You there?"
Browser: "Yeah, let's talk."

In HTTP/1.0, you had to do that handshake for every single file on the page. If a website had 20 small icons, you did 20 handshakes. It was like driving to the grocery store, buying one apple, driving home, and then driving back for a banana.

HTTP/1.1: The Serial Conversation

In 1.1, the conversation is strictly back-and-forth. The browser cannot ask for the next thing until the first thing arrives.

Browser: "Can I have index.html?"
Server: "Sure, here is index.html."
Browser: (Receives file) "Okay, now can I have style.css?"
Server: "Sure, here is style.css."
Browser: (Receives file) "Great, finally, can I have logo.png?"
Server: "Here is logo.png."

The Problem: If index.html is a massive file, the CSS and Image are "blocked" and the screen stays blank for a long time.

HTTP/2: The Mixed Conversation

HTTP/2 introduces Binary Framing. It breaks the files into tiny "chunks" (frames) and mixes them together. The browser sends all requests at once, and the server sends bits of everything back simultaneously.

Browser: "I need index.html, style.css, and logo.png. Send them all!"

Server: "Coming right up. Here is a piece of the HTML... here is a piece of the CSS... here is a piece of the Image... here is the rest of the HTML..."

The Benefit: The browser gets enough "pieces" of the CSS and HTML at the same time to start drawing the page on your screen much faster.

HTTP/3: The Smarter Conversation

HTTP/3 looks like HTTP/2 (everything happens at once), but the "language" it speaks is different. It uses QUIC instead of TCP.

In HTTP/2, if one "piece" of the image gets lost in the mail, the server stops everything to find it. In HTTP/3, the server says, "I lost a piece of the image, but I'll keep sending you the CSS and HTML while I go find it."

Browser: "Send me the files over this new fast lane!"

Server: "Sending! (A packet of data gets lost)... Oh, looks like a packet dropped. I'll re-send that specific one in a second, but keep processing the other files I'm sending you right now."

Let's explore how QUIC is different from TCP in a separate post.

Python Sample HTTP CRUD with FastAPI and Flask

Omkar Bhagat — Tue, 03 Mar 2026 23:04:33 +0000

In the world of Python web development, "CRUD" (Create, Read, Update, Delete) is the bread and butter of almost every application. But for beginners, the first hurdle isn't the logic—it's the tooling. Do you go with Flask, the reliable "micro-framework" that has been a industry staple for over a decade? Or do you reach for FastAPI, the high-performance newcomer that’s taking the dev world by storm?

The biggest difference often comes down to how you run them. While FastAPI requires an external server like uvicorn to handle its asynchronous powers, Flask comes with its own "no-nonsense" built-in server for quick local development.

fastapi_server.py

from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
from typing import Dict

app = FastAPI()

# Data Schema
class User(BaseModel):
    name: str
    email: str

# In-memory "Database"
db: Dict[int, User] = {}

@app.post("/users/{user_id}")
def create_user(user_id: int, user: User):
    if user_id in db:
        raise HTTPException(status_code=400, detail="User already exists")
    db[user_id] = user
    return {"status": "Created", "data": user}

@app.get("/users/{user_id}")
def read_user(user_id: int):
    if user_id not in db:
        raise HTTPException(status_code=404, detail="User not found")
    return db[user_id]

@app.put("/users/{user_id}")
def update_user(user_id: int, user: User):
    if user_id not in db:
        raise HTTPException(status_code=404, detail="User not found")
    db[user_id] = user
    return {"status": "Updated", "data": user}

@app.delete("/users/{user_id}")
def delete_user(user_id: int):
    if user_id not in db:
        raise HTTPException(status_code=404, detail="User not found")
    del db[user_id]
    return {"status": "Deleted"}

# To run: uvicorn fastapi_server:app --reload

Test: test_fastapi.py

import requests

BASE = "http://127.0.0.1:8000/users"

# POST
print("POST:", requests.post(f"{BASE}/1", json={"name": "Alice", "email": "alice@web.com"}).json())
# GET
print("GET:", requests.get(f"{BASE}/1").json())
# PUT
print("PUT:", requests.put(f"{BASE}/1", json={"name": "Alice Smith", "email": "alice@web.com"}).json())
# DELETE
print("DELETE:", requests.delete(f"{BASE}/1").json())

Server: flask_server.py

from flask import Flask, request, jsonify

app = Flask(__name__)

# In-memory "Database"
db = {}

@app.route('/users/<int:user_id>', methods=['POST'])
def create_user(user_id):
    if user_id in db:
        return jsonify({"error": "Exists"}), 400
    db[user_id] = request.json
    return jsonify({"status": "Created", "data": db[user_id]}), 201

@app.route('/users/<int:user_id>', methods=['GET'])
def read_user(user_id):
    user = db.get(user_id)
    return jsonify(user) if user else (jsonify({"error": "Not found"}), 404)

@app.route('/users/<int:user_id>', methods=['PUT'])
def update_user(user_id):
    if user_id not in db:
        return jsonify({"error": "Not found"}), 404
    db[user_id] = request.json
    return jsonify({"status": "Updated", "data": db[user_id]})

@app.route('/users/<int:user_id>', methods=['DELETE'])
def delete_user(user_id):
    if user_id in db:
        del db[user_id]
        return jsonify({"status": "Deleted"})
    return jsonify({"error": "Not found"}), 404

if __name__ == '__main__':
    # Built-in server (No uvicorn needed)
    app.run(port=5000, debug=True)

Test: test_flask.py

import requests

BASE = "http://127.0.0.1:5000/users"

# POST
print("POST:", requests.post(f"{BASE}/1", json={"name": "Bob", "email": "bob@web.com"}).json())
# GET
print("GET:", requests.get(f"{BASE}/1").json())
# PUT
print("PUT:", requests.put(f"{BASE}/1", json={"name": "Bob Jones", "email": "bob@web.com"}).json())
# DELETE
print("DELETE:", requests.delete(f"{BASE}/1").json())

Which one should you choose?

Now that you’ve seen both in action, the choice depends on your project goals:

Choose Flask if you want a simple, lightweight setup where you have total control over every line of code and want to run your app with a simple python app.py command.

Choose FastAPI if you’re building something modern that needs to scale, or if you simply love the idea of automatic data validation and instant, interactive documentation.

Guide To Installing Python Packages In Virtual Environment

Omkar Bhagat — Tue, 03 Mar 2026 22:45:17 +0000

Never install packages "globally." If Project A needs Django 3 and Project B needs Django 5, your system will crash. Use a virtual environment (venv) to keep them isolated.

python3 -m venv .venv

Activate it:

source .venv/bin/activate

pip is your package downloader. Once your environment is active, use it to grab libraries from the web.

Install a package: pip install requests
Install a specific version: pip install fastapi==0.110.0
Remove a package: pip uninstall requests

Don't make people guess what they need to run your code. Create a requirements file.

To save your current setup:

pip freeze > requirements.txt

To install everything from someone else’s list:

pip install -r requirements.txt

Sample requirements.txt file:

# Web Framework
fastapi==0.109.0
uvicorn==0.27.0

# Database
sqlalchemy==2.0.25
psycopg2-binary==2.9.9

# Utilities
requests==2.31.0
python-dotenv==1.0.0

To stop using your current virtual environment and return to your system's global Python, simply type:

deactivate

Leetcode Number Of Islands

Omkar Bhagat — Fri, 13 May 2022 20:20:10 +0000

In this post we'll have a look at LeetCode problem #200 called Number Of Islands.

The problem statement is quite straightforward. Given a grid of 1s and 0s, we need to find the total number of islands in a given grid.

They mention:

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

For example:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

And another example:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

How do we solve it?

My approach is to look at each (unvisited) cell in the grid, if it contains 1 then (recursively) expand outward from there as long as its neighbour also has a 1. This is called BFS (breadth first search).

When we visit a cell, we'll mark that cell as visited, such that we'll not visit it again later.

Here's the solution:

class Solution:
    def numIslands(self, grid):

        ROWS, COLS = len(grid), len(grid[0])
        res = 0
        visited = set()

        def dfs(r,c):
            if r<0 or c<0 or r>=ROWS or c>=COLS or (r,c) in visited or grid[r][c] != "1":
                return

            visited.add((r,c))
            dfs(r+1,c)
            dfs(r-1,c)
            dfs(r,c+1)
            dfs(r,c-1)

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1" and (r,c) not in visited:
                    res += 1
                    dfs(r,c)

        return res

The code itself is also very straightforward to understand. I hope you find it helpful.

Note that we can avoid using a visited set by simply marking 1s with some symbol, like a # sign.

--
Cover Photo by Sacha Gregoire on Unsplash

Python: last minute notes for your coding interviews

Omkar Bhagat — Sat, 16 Apr 2022 08:50:46 +0000

If you are someone who opts for the Python language for your coding (data structures and algorithms) interviews, then you may want to bookmark this post for your last minute revision.

1. Convert dictionary key-values to a list of tuples

seen = {'i': 2, 'love': 2, 'leetcode': 1, 'coding': 1}

seen.items()
# [('i', 2), ('love', 2), ('coding', 1), ('leetcode', 1)]

2. Populating a dictioonary with +1/-1

Quickly increment or decrement a value of a key in a dictionary:

seen[c] = 1 + seen.get(c,0)
seen[c] = seen.get(c,0) - 1

3. Sort based on key and reverse

# sorting interval at index i 
# by 1st value as key in that interval
# [ [1,2], [3,4] ]
# and then reversing the result
# [ [3,4], [1,2] ]

items.sort(key=lambda x: x[1], reverse=True)

4. Check if list type

if isinstance(x, list)

# OR

if type(x) is list

5. ASCII values

ord('A') = 65

ord('Z') = 90

ord('a') = 97

ord('z') = 122

chr(65) = 'A'

6. Limit float to 2 decimal places

round(x, 2)

7. Using a double ended queue

from collections import deque

>>> word = 'hit'

>>> q = deque([word])
>>> q
deque(['hit'])

>>> q = deque(word)
>>> q
deque(['h', 'i', 't'])

# functions like these exist:
# q.appendleft
# q.popleft
# q.append
# q.pop

8. Creating adjacency list with defaultdict

from collections import defaultdict

neighbours = defaultdict(list)

# creates a structure like this:
# neighbours = {
#     key1: [item1, item2],
#     key2: [item1, item2, item3],
# }

# can be populated as follows:
for key, val in somelist:
    neighbours[key].append(val)

9. Intersection of two sets

>>> a = { 1, 2, 3 }
>>> b = { 3, 4, 5 }
>>> a.intersection(b)
{3}
>>> list(a.intersection(b))
[3]

10. Combinations vs Permutations

a = "ABC"

>>> list(itertools.permutations(a))
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

>>> list(itertools.combinations(a, 3))
[('A', 'B', 'C')]

>>> list(itertools.combinations(a, 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]

>>> list(itertools.permutations(a, 2))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

11. Reading input line by line

if __name__ == '__main__':
    n = int(input().strip())

    words = []

    for _ in range(n):
        words_item = input()
        words.append(words_item)

    # call some function after reading..
    noPrefix(words)

12. Writing test cases

class Solution:

    def twoSum(self, nums, target):

        seen = {}

        for i, num in enumerate(nums):
            num2 = target-num

            if num2 in seen:
                return [seen[num2], i]
            else:
                seen[num] = i

import unittest
class BasicTests(unittest.TestCase):

    testcases = [
        ([2,7,11,15], 9, [0,1]),
        ([3,2,4], 6, [1,2]),
        ([3,3], 6, [0,1])
    ]

    def test1(self):
        s = Solution()
        for nums, target, expected in self.testcases:
            actual = s.twoSum(nums, target)
            # print(actual, expected)
            assert actual == expected or list(reversed(actual)) == expected

if __name__ == "__main__":
    unittest.main()

I have personally found this quite helpful and I hope you too will get some value from it. Good luck!

QuickSort Explained

Omkar Bhagat — Fri, 21 Jan 2022 06:16:02 +0000

In this post, let's have a quick look at how Quick Sort works.

Let's take the following example:

4 2 6 5 3

Quick sort works by finding the correct position (the partition index) for the pivot element.

Thereby partitioning the array into two parts: a) unsorted parts before the partition index and b) unsorted parts after the partition index.

The item at the partition index would be at the correct position. Therefore we would simply run the algorithm again recursively for the unsorted parts to get the desired result of a complete sorted array.

Let's see this with the help of an example.

Partitioning

Step 1 - Choose A Pivot

To sort it using the Quick Sort, we'll first need to choose a "pivot" item. Let's choose the last item "3" as "pivot".

4 2 6 5 [3]

Step 2 - Choose A Partition Index

Now we choose a partition index called "pIndex". Let that be the first item in the given array (4 in this case).

Then we loop through the array (excluding pivot), comparing current item with pivot, and swapping with pIndex when the condition currentItem <= pivot is True.

4 2 6 5 [3]
p
^

Is 4 <= 3 ? No.

4 2 6 5 [3]
p
  ^

Is 2 <= 3 ? Yes. Swap with pIndex and increment pIndex.

2 4 6 5 [3]
  p
    ^

Is 6 <= 3 ? No.

2 4 6 5 [3]
  p
      ^

Is 5 <= 3 ? No.

Step 3 - Swap pIndex With Pivot

After going through the first loop, we found the correct position (the partition index) for our pivot item.

Swap the item at pIndex with Pivot and return pIndex.

2 [3] 6 5 4
   p

Step 4 - Recursively Sort Unsorted Parts

This means we'll need to run QuickSort again on the unsorted parts as follows:

quickSort(array, start, pIndex-1)
quickSort(array, pIndex+1, end)

Step 5 - Dry run of the recursion

Currently, we have the following array:

2 [3] 6 5 4

The left part only has one item 2 so it is already sorted. Only the right part needs to be sorted.

Let's do that by following the steps 1 to 4.

Choose the last item "4" as the pivot.
Choose the first item "6" as the pIndex.

2a. Go through the array excluding the pivot and swap where we find an item less than the pivot.

This is to make sure:

all the items on the left of pIndex are less than or equal to the pivot.
and all the items on the right are greater than the pivot.

6 5 [4]
p
^

Is 6 <= 4 ? No.

6 5 [4]
p
  ^

Is 5 <= 4? No.

Loop ends.
Swap item at pIndex with Pivot.
Return pIndex.

[4] 5 6
 p

4 is at the right place.
Unsorted numbers are 5 and 6.

Following step 4, recursively sort the unsorted parts.

Recursion would help us discover that 5 and 6 are already at their correct positions.

Therefore the array is already sorted:

2 3 4 5 6

The Code

The code should be fairly easy to read, especially after test case explained above.

def quicksort(arr, start, end):

  if start >= end:
    return

  pIndex = partition(arr, start, end)
  quicksort(arr, start, pIndex-1)
  quicksort(arr, pIndex+1, end)

  return arr

def partition(arr, start, end):

  pivotIndex = end
  pIndex = start

  for i in range(start, pivotIndex): # excluding pivotIndex
    if arr[i] <= arr[pivotIndex]:
      arr[i], arr[pIndex] = arr[pIndex], arr[i]
      pIndex += 1

  arr[pIndex], arr[pivotIndex] = arr[pivotIndex], arr[pIndex]
  return pIndex

If you have a difficult time understanding it, just take the above example and perform a dry run on a piece of paper. It is the fastest way to learn and absorb a new concept!

FAQ

(1) What's the average case complexity?

Time: O(n log n)
Space: O(log n)

(2) What's the worst case complexity?

Time: O(n^2)
Space: O(n)

(3) What would be the worst case?

When the array is already sorted. Why? because each loop in each recursive call would touch every single item.

The n recursive calls would take O(n) space. Also, n recursive calls, each running a for loop that has n iterations would result in O(n^2) time complexity.

(4) What's the difference between Quick Sort and Merge Sort?

Quick Sort algorithm doesn't require any extra storage, Merge sort requires extra storage space to store the auxiliary array.

The Three Basic N^2 Sorting Algorithms

Omkar Bhagat — Thu, 20 Jan 2022 15:01:48 +0000

In this post, we'll have a look at the three basic O(n^2) sorting algorithms:

Bubble Sort
Insertion Sort
Selection Sort

Note: I'll cover QuickSort, MergeSort and HeapSort in separate posts.

Bubble Sort

The idea of bubble sort is to compare every item to every other item, swapping as needed and then repeating these steps n number of times (where n is the total number of items in a given array).

def bubbleSort(array):
  n = len(array)
  for i in range(n):
    for j in range(n-1):
      if array[j] > array[j+1]:
        array[j], array[j+1] = array[j+1], array[j]
  return array

For Example:

Array: [4 2 6 5 3 9]

Outer Loop 1:
4 2 6 5 3 9 -- (4>2? Yes, swap)
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (6>5? Yes, swap)
2 4 5 6 3 9 -- (6>3? Yes, swap)
2 4 5 3 6 9 -- (6>9? No)

Outer Loop 2:
2 4 5 3 6 9 -- (2>4? No)
2 4 5 3 6 9 -- (4>5? No)
2 4 5 3 6 9 -- (5>3? Yes, swap)
2 4 3 5 6 9 -- (5>6? No)
2 4 3 5 6 9 -- (6>9? No)

Outer Loop 3:
2 4 3 5 6 9 -- (2>4? No)
2 4 3 5 6 9 -- (4>3? Yes, swap)
2 3 4 5 6 9 -- (4>5? No)
2 3 4 5 6 9 -- (5>6? No)
2 3 4 5 6 9 -- (6>9? No)

Now the array is sorted but we will still have outer loops 4, 5 and 6 because the length of the array is 6.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

Insertion Sort

The idea here is to imagine you are holding the items as cards in your left and right hand.

Initially you have no cards in your left hand, all the cards are in your right hand.
You insert one card from the right hand to the left hand in one iteration.
Once you move a card to the left, you immediately sort the cards in your left hand.
Then you repeat the process by adding another card to your left hand.

def insertionSort(array):
  n = len(array)
  for i in range(n):
      for j in range(i):
          if array[j] > array[i]:
              array[j], array[i] = array[i], array[j]
  return array

For Example:

Array: [4 2 6 5 3 9]

Step 0

Left hand:
Empty

Right hand:
4 2 6 5 3 9

Step 1

Left hand:
4

Right hand:
2 6 5 3 9

Step 2

Left hand:
4 2 -- (4>2? Yes, swap)
2 4

Right hand:
6 5 3 9

Step 3

Left hand:
2 4 6 -- (2>6? No)
2 4 6 -- (4>6? No)
2 4 6

Right hand:
5 3 9

Step 4

Left hand:
2 4 6 5 -- (2>5? No)
2 4 6 5 -- (4>5? No)
2 4 6 5 -- (6>5? Yes, swap)
2 4 5 6

Right hand:
3 9

Step 5

Left hand:
2 4 5 6 3 -- (2>3? No)
2 4 5 6 3 -- (4>3? Yes, swap)
2 3 5 6 4 -- (5>4? Yes, swap)
2 3 4 6 5 -- (6>5? Yes, swap)
2 3 4 5 6

Right hand:
9

Step 6

Left hand:
2 3 4 5 6 9 -- (2>9? No)
2 3 4 5 6 9 -- (3>9? No)
2 3 4 5 6 9 -- (4>9? No)
2 3 4 5 6 9 -- (5>9? No)
2 3 4 5 6 9 -- (6>9? No)
2 3 4 5 6 9

Right hand:
Empty

The array is sorted at this point.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

Selection Sort

In selection sort, we select the correct item for the current position and then move to the next.

def selectionSort(array):
  n = len(array)
  for i in range(n):
    for j in range(i+1, n):
      if array[i] > array[j]:
        array[i], array[j] = array[j], array[i]
  return array

For Example:

Array: [4 2 6 5 3 9]

Outer Loop 1:
4 2 6 5 3 9 -- (4>2? Yes, swap)
2 4 6 5 3 9 -- (2>6? No)
2 4 6 5 3 9 -- (2>5? No)
2 4 6 5 3 9 -- (2>3? No)
2 4 6 5 3 9 -- (2>9? No)

Outer Loop 2:
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (4>6? No)
2 4 6 5 3 9 -- (4>5? No)
2 4 6 5 3 9 -- (4>3? Yes, swap)
2 3 6 5 4 9 -- (3>9? No)

Outer Loop 3:
2 3 6 5 4 9 -- (6>5? Yes, swap)
2 3 5 6 4 9 -- (5>4? Yes, swap)
2 3 4 6 5 9 -- (4>9? No)

Outer Loop 4:
2 3 4 6 5 9 -- (6>5? Yes, swap)
2 3 4 5 6 9 -- (5>9? No)

Outer Loop 5:
2 3 4 5 6 9 -- (6>9? No)

The sorted array is: 2 3 4 5 6 9.

Complexity:

Time complexity: O(n^2)
Space complexity: O(1)

All these algorithms have a worst case time complexity of O(n^2). We can do better with QuickSort or MergeSort where the average case time complexity would be O(n log n).

Tree Problems Made Easy

Omkar Bhagat — Sun, 16 Jan 2022 12:58:06 +0000

Tree problems can be a little difficult to wrap your head around, especially when you are a beginner. This post will try and make tree problems easy for you with the help of some examples.

1. Sum of all values

The goal is to get sum of all the values in the tree.

def getSum(root):

  if not root:
    return 0

  return root.val + getSum(root.left) + getSum(root.right)

This is quite simple. The sum of all values in the tree is simply the sum of:

a) the current node
b) the sum of all values on its left
c) the sum of all values on its right

What if there's no node? That should return zero. That's also our base case.

2. Get max value in the tree

The goal here is to get max value from a tree where the values are all >=0.

def getMax(root):

  if not root:
    return 0

  return max(root.val, getMax(root.left), getMax(root.right))

To get the max value in the tree, we return the maximum between:

a) the value of current node
b) the max value on its left
c) the max value on its right

And when there is no node, we return the max as 0. That's also our base case.

3. Get max tree height

The goal here is to find the maximum tree height or the maximum depth of the tree.

For example, the maximum depth of this tree would be 3:

def getHeight(root):

  if not root:
    return 0

  return 1 + max(getHeight(root.left), getHeight(root.right))

To get the max height, we count the current node as 1 and add it to the max height we get from its branches.

If there's no node, we return 0, which is our base case.

4. Check if value exists in a tree

def valExists(root, val):
  if not root:
    return False
  return root.val == val or valExists(root.left, val) or valExists(root.right, val)

The idea is to check if value exists in the root node, or the left branch or the right branch. If so, return True.

If we end up reaching a non-existent (NULL) node, we can safely return False (i.e. we can safely say the value doesn't exist in this Tree).

5. Invert a binary tree

Original:

     1
    / \
   3   2
      / \
     5   4

Inverted:

     1
    / \
   2   3
  / \
 4   5

def invert(root):
  if not root:
    return

  root.left, root.right = root.right, root.left

  invert(root.left)
  invert(root.right)

We can invert a binary tree as follows:

For the current node, swap values of its left and right branches.
Repeat this for the node on the left and the node on the right.
Stop when we hit an empty node.

6. Check if same tree

def sameTree(t1, t2):

  if not t1 and not t2:
    return True

  if t1 and t2:
    return t1.val == t2.val and sameTree(t1.left, t2.left) and sameTree(t1.right, t2.right)

  return False

For both trees to be the same:

both nodes need to exist.
their root values need to match.
their left branch and right branch needs to match (we can check this recursively).

If while checking we end up reaching a position where both branches are missing, we know we have hit the leaf nodes without any mismatch in values between two trees. Therefore we must return True when we hit leaf nodes.

In all other cases, we should return False.

7. Check if subtree of another tree

def isSubTree(root, subRoot):

  if not root:
    return False

  return sameTree(root, subRoot) \
    isSubTree(root.left, subRoot) \
    isSubTree(root.right, subRoot)

To check if one tree is a subtree of another tree, simply re-use the sameTree function from above with the following logic:

Is current node and subRoot the same tree? If so, return True.
Otherwise recursively check its left and right branches.
If we hit a leaf node, we should return False because we haven't found a True value for sameTree function so far.

8. Binary Search Tree (BST): Lowest Common Ancestor

In a BST, all the values on the left are strictly less than the current node while all the values on the right are strictly greater than the current node.

We can use this to our advantage in finding the lowest common ancestor as follows:

def LCAofBST(root, p, q):

  if not root:
    return False

  if p.val < root.val and q.val < root.val:
    return LCAofBST(root.left, p, q)

  if p.val > root.val and q.val > root.val:
    return LCAofBST(root.right, p, q)

  return root

The logic is quite simple:

If there's no root, return False.
If both values are less than root, check the left side.
If both values are greater than root, check the right side.
In all other cases, we know p falls on the left and q falls on the right, this makes the current node the least common ancestor between the two, therefore we return root.

9. Lowest Common Ancestor in a Binary Tree

What if our tree is not a BST? Then finding the LCA is a little difficult but not impossible. Here's how to do it:

def lca(root, p, q):

  if not root:
    return None

  if root.val == p or root.val == q:
    return root

  left_result = lca(root.left, p, q)
  right_result = lca(root.right, p, q)

  if left_result and right_result:
    return root

  if left_result:
    return left_result
  else:
    return right_result

The logic here can be made simple with two key points:

If the left branch and the right branch has p and q respectively, return the current node as LCA.
If only one branch as p or q, return p or q respectively.

For example:

(A) Finding 4 and 5

You hit 4, you return 4.
You hit 5, you return 5.
You hit 2, you get 4 and 5, so you return 2.
You hit 3, you return None.
You hit 1, you get 2 and None, you return 2.

(B) Finding 2 and 5

You hit 2, you return 2.
You hit 3, you return None.
You hit 1, you get 2 and None, you return 2.

You hit 2, you return 2.
You hit 3, you return 3.
You hit 1, you get 2 and 3, you return 1.

10. Final tip

My final tip would be to visualize the tree and try to solve it for smaller problems as follows:

Imagine having a Null node, a single node, a node with two branches, a node with left branch, and finally a node with right branch.

How would you solve for these cases? This would help you make some progress on the given problem :)

Finding Unique Substrings In A Given String

Omkar Bhagat — Wed, 27 Oct 2021 19:32:35 +0000

Given a string abc, our goal is to generate the following unique substrings:

['abc', 'bc', 'ab', 'c', 'b', 'a']

With A Queue

We can do it with the help of a queue.

Here's the logic:

Take the given string, add it to our queue q.
While the q is not empty, repeat steps 3-5.
Pop the first item in the q.
Add this to our final result list called res.
Add left substring (e.g. ab) and right substring (e.g. bc) to the queue only if it isn't already in res.
Once queue is empty, print res.

def findSubstrings(s):

    res = set()
    q = [s]

    while q:

        s = q.pop(0)
        res.add(s)

        x = 0
        y = len(s)-1

        right_string = s[x+1:y+1]
        left_string = s[x:y]

        if right_string and right_string not in res:
            q.append(right_string)

        if left_string and left_string not in res:
            q.append(left_string)

    return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']

With Recursion

Here the logic is the same but we do it recursively using one helper function.

def findSubstrings(s):

    res = set()

    def helper(s):

        if len(s) <= 0:
            return

        res.add(s)

        right_string = s[1:len(s)]
        left_string = s[0:len(s)-1]

        if right_string not in res:
            helper(right_string)

        if left_string not in res:
            helper(left_string)

    helper(s)

    return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']

Complexity

I guess the worst case time here could be (2^n)-1 if we don't use a set to check for unique values (where n is length of the given string).

Final Thoughts

Where can you use this? Once you understand the basic logic, you can use it to solve many string related problems. For example: Finding the longest palindromic substring.

There could be various other (simpler) ways to achieve this but I believe this approach helps us visualize the process. Thanks for reading! :)

A High Level View Of Web Engineering

Omkar Bhagat — Thu, 21 Oct 2021 13:12:07 +0000

How does the web work? What happens behind the scenes? Where do you start if you're completely new to all this?

I don't have a definite answer but I have studied this for sufficiently long time to put together a post which can cover everything (the important bits) in one place.

You can essentially use this as a cheat sheet or last minute prep to prepare for web/software engineering interviews.

I know it can't be an exhaustive list of all things but I'm putting the effort to get as close to it as possible to help anyone who's looking for it.

Okay, let's start with "what happens when you type in Google.com or visit any URL in your web browser?"

What happens when you type Google.com in the browser?

When you type in Google.com and hit enter. Your browser wants to translate the domain name Google.com into an IP address. This process is called Domain Name Resolution and is done by DNS (Domain Name System).

Here’s how it starts: Your browser will look for IP address of Google.com in your browser’s DNS cache. If it’s not there, it’ll check your OS (Operating System’s) DNS cache. If it’s not there, it’ll send that request to your Router. If it’s not there, it’ll send that request to your ISP.

Still not there? Your ISP will send that request to one of the 13 root servers (not exactly 13 physical servers but 13 named authorities that maintain hundreds of these physical servers around the world).

The root server will share the address of the respective TLD (Top Level Domain) server with your ISP. In this case, it is “.COM” TLD server.

Your ISP then contacts that respective TLD Server, which returns the address of the Authoritative DNS server.

Finally your ISP contacts the Authoritative DNS sever which will return the IP address (the “A” record of DNS) back to it.

Your ISP then sends it back to your router and your router sends it back to you. At this point, your ISP, Router, OS and Browser will most likely maintain a cached record of this IP in their tables.

Why? The next time you or someone in your network requests for Google.com, one of these entities will know where to send that request without making a full DNS trip.

Now that your browser knows the address of Google.com, it is time to start making HTTP requests to actually get the page/resource.

Reference: https://medium.com/@maneesha.wijesinghe1/what-happens-when-you-type-an-url-in-the-browser-and-press-enter-bb0aa2449c1a

Github repo: https://github.com/alex/what-happens-when

What is HTTP?

HTTP is Hyper Text Transfer Protocol. What is a protocol? Protocol is a set of rules that tells two machines how to talk to each other (similar to the rules in our language).

HTTP is stateless protocol, that means it doesn’t maintain a state after each request. This also results in HTTP being connectionless. That means the client (your browser/machine) and the server is only aware of each other during one/current request.

To fix this, HTTP operates over TCP (Transmission Control Protocol) which opens and keeps the connection alive.

HTTP/1.0

A new TCP connection was required for each request/response pair. That leads to poor performance because it is time and resource expensive to create a TCP connection for each request.

Image source: Mozilla

HTTP/1.1 (persistent connections are default)

We still have to wait for a response before sending a request but we can have multiple request/response pairs in a single connection.

Also, we can open multiple connections but most browsers support up to 6 parallel connections per domain.

To fix this limitation, a technique called domain sharding is used where resources are delivered from multiple subdomains. For example, you may have seen images being served from i1.wp.com, i2.wp.com on WordPress.com.

HTTP/1.1 (with pipelining)

Multiple requests can be sent without waiting for a response but the responses have to be in order they were requested. This is poorly supported by browsers and servers and is almost never used.

HTTP/2 (multiplexing)

Multiple requests can be sent without waiting for a response and the responses can be in any order. This vastly improves performance (see a demo: here and here. It can also break the responses into smaller items and send them as soon as they are ready.

HTTP/2 (with push)

Let’s say we request index.html, the server can check this file needs few more files like style.css and scripts.js and the server automatically “pushes” these to us. Thus the browser didn’t need to make separate requests for them.

Reference:
https://stackoverflow.com/questions/36517829/what-does-multiplexing-mean-in-http-2

Refer this sweet animation which explains all this beautifully: https://freecontent.manning.com/animation-http-1-1-vs-http-2-vs-http-2-with-push/

What about HTTPS?

HTTPS is a way of encrypting HTTP. It basically wraps HTTP messages up in an encrypted format using SSL/TLS.

SSL is secure sockets layer and TLS is transport layer security, both are cryptographic protocols designed to provide communications security over computer network.

SSL is basically deprecated and TLS is what we all use (so if someone says SSL today, they’re most likely referring to TLS).

Note that TLS is not mandatory according to the HTTP/2 spec but most browsers will only allow HTTP/2 over TLS.

Encryption: Asymmetric vs Symmetric

TLS handshake uses asymmetric encryption where the server produces two keys: public and private. Data can be locked/encrypted using the server’s public key but can only be unlocked/decrypted using the server’s private key.

The server sends server’s public key to the client. It can be seen by anyone on the network but it doesn’t matter because it is a public key (which can only be used to lock/encrypt things).

Client now creates a new symmetric key on its side (a key that can be used to both lock and unlock). Client locks this symmetric key in a box using the server’s public key and sends it to the server.

People can again see this box on the network but cannot unlock it without the server’s private key. (Note: The act of secretly listening to a private conversation is called eavesdropping).

Once server receives this box, it unlocks it using server’s private key and finds a symmetric key with a note from the client which says “we shall now communicate using this symmetric key”.

At this point, client and server don’t need to send keys anymore. They can send data by locking it with the symmetric key and unlock it using the same symmetric key.

💥 Boom! That’s how data is securely sent over the network!

Reference: https://www.cloudflare.com/learning/cdn/cdn-ssl-tls-security/

Here's a cool video that I created with my friends, it explains encryption with motion graphics:

HTTP Request Methods

Each HTTP request have their own headers which tell the server what the request is all about. You can see this by opening developer tools in your browser, heading to the network tab, loading a page and then inspecting each request.

HTTP methods are classified into two types:

Safe methods: They don’t change anything on the server side.
Idempotent methods: They produce the same results no matter how many times they are called.

Idempotence catchphrase →

Send and send and send my friend, it makes no difference in the end.

Now let’s look at each of these methods:

GET

Fetch a resource from the server.
Example: GET /users/207
Safe: ✅
Idempotent: ✅

POST

Modify/update a resource on the server.
Example: POST /users
Safe: ❌
Idempotent: ❌

PUT

Create a new resource or overwrite if one is present.
Example: PUT /users/207
Safe: ❌
Idempotent: ✅

DELETE

Remove a resource from the server.
Example: DELETE /users/207
Safe: ❌
Idempotent: ✅

PATCH

Apply partial modifications to a resource.
Example: PATCH /users/207
Safe: ❌
Idempotent: ❌

POST vs PUT vs PATCH

There is an excellent StackOverflow post that covers this in detail. Here’s an excerpt from that post →

POST to a URL creates a child resource at a server defined URL.
PUT to a URL creates/replaces the resource in its entirety at the client defined URL.
PATCH to a URL updates part of the resource at that client defined URL.

If the endpoint on the server is idempotent (i.e safe to do the request over and over again) and the URI is address to the resource being updated then we can safely use PUT, else use POST.

PUT will essentially take an object and replace the entire resource at the URI. For example, if we had to update only the email of a user, we would send the entire resource:

PUT /users/207
{
  name: "Omkar Bhagat",
  email: "omkar@bhagat.com",
  city: "Mumbai"
}

If we only send email (a partial resource) as follows →

PUT /users/207
{
   email: "omkar@google.com"
}

Then the rest of the properties will have NULL values. That’s where PATCH comes to our rescue.

Reference: https://medium.com/@kumaraksi/using-http-methods-for-restful-services-e6671cf70d4d

Reference models

When it comes to online communication, we have some conceptual model or framework that partitions the communication system into abstract layers.

Why is this important? Let’s understand this with a real life example.

You place an order for food via a smartphone app
The order is received at the server and sent to the restaurant
That restaurant prepares the food and packages it when done
A delivery person arrives on a motorcycle, collects the food and delivers it to you!

Now this whole process can be partitioned into different layers (where each layer operates independently). You can fix problems at each layer, make changes and it won’t affect the other layers.

Like let’s say instead of delivering food via motorcycle, you decide to upgrade to a truck. Or your organization switches from iOS app to Android App. It doesn’t affect the other layers. If there’s a problem at any particular layer, you know who to call and what to do. That’s the power of abstraction.

There are two models to remember:

OSI Model

OSI (Open Systems Interconnection) is a 7 layer reference model developed by ISO (International Organization Of Standarization) in 1974. No modern protocols implement this model fully.

Image Source: GeeksForGeeks

TCP/IP Model

TCP/IP networking model is used by the TCP/IP protocol suite which is used by the internet (inter-network of computing devices).

Image Source: Wikipedia

TCP vs UDP

These are two important transport layer protocols. The basic difference is that TCP is connection oriented and UDP is connectionless (meaning it doesn’t establish a connection before sending data).

TCP is reliable because data sent via TCP is guaranteed to be delivered to the receiver. If data is lost in communication, it will recover and resend it. It’ll also check packets for errors to make sure the data received is not corrupted. UDP doesn’t do any of that.

TCP also provides flow control that ensures the sender is not overwhelming the receiver with too many packets at a time. To do this, both sender and receiver maintains “buffers”. Each time a packet is received, a message is sent to the sender with the value of current receive window.

UDP doesn’t provide flow control, instead packets arrive in a continuous “stream”.

TCP ensures the packets sent and received are in the correct order. UDP doesn’t care about order.

Since TCP does a lot of extra work (establish connection, error-check, flow control, ordering) to be “reliable”, it is slower than UDP.

TCP is best suited for applications that require high reliability → HTTP, HTTPS, SSH, FTP, SMTP, etc. For example, email, file transfer, internet banking (where every digit/packet matters).

UDP is best for applications that need speed and efficiency like streaming videos, online games, DNS resolution, VoIP, etc.

Email Protocols

Just because I mentioned SMTP in the previous section, I’ll quickly cover 3 email protocols.

SMTP (Simple Mail Transfer Protocol)
POP3 (Post Office Protocol 3)
IMAP (Internet Mail Access Protocol)

SMTP

SMTP is pretty much the delivery truck that takes your email and delivers it to the right address after you hit the send button. It’s the protocol for transferring email over the internet.

POP3

POP3 is what you can use to receive/download an email. It’s designed to delete the email from the server as soon as you download it.

IMAP

IMAP is again what you can use to receive/download an email (and the folder structure) while retaining the email on server. You can think of it as remote file server. For example, you can download email on your mobile and laptop and it’ll continue to stay in your email inbox (and at all other places).

I'm tempted to end the post here but I'll quickly add a bonus Networking section here which could help to cover a few things at a glance.

Networking

Networking is vast but as the title of this post says, I’ll only cover the high level view.

Hub → It can only broadcast to every other node connected to it.
Switch → It knows the MAC (media access control) address of every node connected to it. It knows where to send the data within the network.
Router → It can do all of the things above and route traffic between networks. It’s intelligent and knows how to find the shortest path to the destination.
MAC address → Media Access Control. Every network component has its own MAC address (physical address) that’s embedded on its hardware. Your phone, router, desktop, laptop, everything has one.
DHCP → Dynamic Host Configuration Protocol. This is what gets (leases) you a dynamic IP every time you connect to the internet.
NAT → Network Address Translation. It’s what turns private addresses into public and vice versa.
ARP → Address Resolution Protocol. ARP request is nothing but broadcasting a packet over the network to validate whether we came across the destination MAC address or not.
IPv4 → IP version 4 is 32 bit address containing four octets (4x8bits). Example: 12.244.233.165. This is still very much in use.
IPv6 → It’s 128 bit address containing eight hextets (8x16bits) separated by colons. Example: 2001:0db8:0000:0000:0000:ff00:0042:7879. This is still pretty new.
CDN → Content Delivery Network. The idea is to distribute/cache your content around the world at different servers and serve it to the client from the nearest server (resulting in faster delivery).
Subnetting & CIDR → Subnetting is the process of dividing a network into smaller network sections. CIDR (Classless Inter Domain Routing) is an alternative to traditional subnetting.
BGP / OSPF → Border Gateway Protocol, Open Shortest Path First are routing protocols. To oversimplify, BGP (an exterior gateway protocol) is used at the edge of your network to connect your network to the Internet. OSPF (an interior gateway protocol) is usually used internally inside your network.

Finish

There's so much more to cover but it can't be done in one single post. Please let me know if you find this helpful and if you'd like me to dive deeper into any of these topics. Thanks.

How to useContext in React?

Omkar Bhagat — Wed, 06 Oct 2021 16:14:33 +0000

In this post I'll quickly explain why and how to useContext in React. First let's look at the why!

Let's say we want to pass a value from the root component to a nested component 3 levels down in the following structure:

App
  - Child
    - ChildChild
      - ChildChildChild

We know it can be done using props as follows:

function App() {
  const myColor = 'blue'
  return (
    <>
      <Child color={myColor}/>
    </>
  )
}

function Child(props) {
  return (
    <>
      <ChildChild color={props.color} />
    </>
  )
}

function ChildChild(props) {
  return (
    <>
      <ChildChildChild color={props.color} />
    </>
  )
}

function ChildChildChild(props) {
  return (
    <>
      {props.color}
    </>
  )
}

But what if we could skip the first and the second child and go straight to the third child? We could do that with useContext as follows:

const AppContext = React.createContext()

function App() {
  const color = 'blue'
  return (
    <>
      <AppContext.Provider value={color}>
        <Child/>
      </AppContext.Provider>
    </>
  );
}

function Child() {
  return (
    <>
      <ChildChild/>
    </>
  )
}

function ChildChild() {
    return (
      <>
        <ChildChildChild/>
      </>
    )
  }

function ChildChildChild() {
  const newcolor = React.useContext(AppContext)
  return (
    <>
      {newcolor}
    </>
  )
}

Isn't this much cleaner? We start to see its utility once we separate the components into their individual files.

As mentioned in the React docs, a component calling useContext will always re-render when the context value changes.

Here's a quick example of that:

const AppContext = React.createContext()

function App() {
  const [color, setColor] = React.useState('blue')
  setTimeout(() => {
    setColor('green')
  }, 2000);

  return (
    <>
      <AppContext.Provider value={color}>
        <Child />
      </AppContext.Provider>
    </>
  );
}

function Child() {
  return (
    <>
      <ChildChild />
    </>
  )
}

function ChildChild() {
  return (
    <>
      <ChildChildChild />
    </>
  )
}

function ChildChildChild() {
  const newcolor = React.useContext(AppContext)
  return (
    <>
      {newcolor}
    </>
  )
}

When we use color as a state and then update the state after 2 seconds, the ChildChildChild component re-renders to say green.

I hope this helps to make useContext a bit easy to grasp for anyone learning React.