DEV Community: Samarth Chitgopekar

A Simple Pascal's Triangle Solution

Samarth Chitgopekar — Sat, 01 Jan 2022 12:56:12 +0000

There's a well-known Google algorithm interview question out there that I think is a great beginner problem. For full discolsure, this video inspired me to create this writeup.

The Prompt

Return the first numRows rows of Pascal's Triangle, a triangle where each number is the sum of the two numbers directly above it, as shown:

credit: Brialliant.com (Hayes, Farhat, Vee)

My Thought Process

I like thinking of algorithm problems in math terminology, so that's what I'll do here. We'll start off hypothetical:

Given Pascal's Triangle: P = [[Z+]]

Assume we somehow have the infinitely large Pascal's Triangle, it could be stored in a two dimensonal array of positive integers. Here, each nested array represents a row, starting at the very top and going to the bottom.

Let N (∀ N ≥ 0) be an index within P, s.t P[N] represents the N+1th row of Pascal's Triangle.

We make this distinction because in programming, we use indicies (which start at 0). So, the 1st row is really represented by index 0, and so on.

Let I (∀ I ≥ 0) be an index within P[N], s.t. P[N][I] represents the element in the I+1th column of the N+1th row of Pascal's Triangle.

We make this distinction because in programming, we use indicies (which start at 0). So, the 1st column is really represented by index 0, and so on.

Therefore, the element E at P[N][I] = P[N-1][I-1] + P[N-1][I].

This is the key realization. What this is really saying is that the element at any position is the sum of the element in the previous row to the left and the element in the previous row to the right. The N-1 index makes sense, since it gets us the row before the current one. But why the positions I-1 and I? Look at a subsection of the Pascal's Triangle below, but with the numbers represented by their column indicies:

Row A:   0   1   2   3
Row B: 0   1   2   3   4

This is the pattern-recognition that is key to this problem. I like to imagine chopping off the last element of Row B so that they're symmetrical, kind of like this:

Row C: 0   1   2   3
Row D: 0   1   2   3

As you can see, we have three elements touching from the top row: the one directly above (I), the one above to the left (I-1), and the one above to the right (I+1). When we offset the triangle by that extra element, we 'push' the right one out of contact (since each row adds one element). So, our 2 touching elements above can be found at I-1 and I, what we used to create our definition.

Edge Cases: E = 1 ∀ I ≠ 0 ∪ I ≠ N.

When there aren't 2 elements directly above an E, Pascal's Triangle dictates that we default to E = 1 (we can see this on the very first row and the diagonals). We can handle the tip of the triangle and the left diagonal cases by having E = 1 ∀ I ≠ 0, since they're all at the very beginning of their rows (index 0). We can handle the right diagonal with E = 1 ∀ I ≠ N. We know that the Nth row has N+1 elements. So, the last element would be at the index N (subtract 1 from literal position to get index). Therefore, I ≠ N gets us all the elements except for the ones on the right diagonal (end of a row).

My Solution

There are obviously many ways to solve this problem, all with their own various time and space complexities. This is the one that makes the most sense to me and corresponds to the breakdown I gave, written in Python 3.

def getPascalsTriangle(n: int) -> 'list[list[int]]':

    # Handle edge cases
    if n <= 0:
        return []
    elif n == 1:
        return [[1]]
    elif n == 2:
        return [[1], [1, 1]]

    # At this point, we have a triangle with >= 3 rows
    triangle: 'list[list[int]]' = [[1], [1, 1]]

    # Start building the required rows on top of the first 2
    for i in range(2, n):

        # Create a new row
        row: list[int] = []

        # The first element is always 1
        row.append(1)

        # Every element here has two elements above it, so we can
        # use the sum of those to calculate its value
        for j in range(1, i):
            row.append(triangle[i-1][j-1] + triangle[i-1][j])

        # The last element is always 1
        row.append(1)

        # Add the new row to the triangle
        triangle.append(row)

    # Return the triangle
    return triangle

if __name__ == '__main__':
    # Pretty printed tester for Pascal's Triangle method
    numRows: int = 10
    triangle: 'list[list[int]]' = getPascalsTriangle(numRows)

    for row in triangle:
        for col in row:
            print(col, end=' ')
        print()

in-memory databases: a demo

Samarth Chitgopekar — Sun, 08 Aug 2021 06:22:38 +0000

Many of you might've heard a thing or two about Redis, an in-memory database that enables super fast reads and writes. But why is this?

We first need to understand what "in-memory" really means. A computer has RAM (Random Access Memory) that's super fast. This is where Redis lives, in the same place any variable or object you create in any language.

RAM is very fast, but it comes at a monetary cost - disk space (think your hard drive or ssd) is slower but cheaper. This is easily Redis' biggest pitfall, as RAM becomes a limiting factor regarding how much data you can store.

With that brief introduction out of the way, let's dive into a crude demonstration of just how much faster Redis can be in comparison to storage in a generic database. We'll just be using a simple Json file for this example, but the concept applies to virtually any database.

I'll be writing this in Python 3.10, but any modern version of Python 3 will work. No external dependencies are required.

Here's the step by step walkthrough

To start, I'm going to import a few modules: json (allows us to port between json <-> python dict) and time (allows us to keep track of time). Then, I'll create a dictionary called DATA, which will be cached in memory since it's a variable.

import json
import time

DATA: dict = {
    "key": "val"
}

Next, I'll define a quick method to create a Json file that represents the DATA variable in the current directory - this is what we'll compare our in-memory calls to:

def createJsonFile() -> None:
    "Creates a simple data.json in the current directory with the value of the dict DATA"

    with open('data.json', 'w') as f:
        json.dump(DATA, f)

Now I'll define a method that opens the Json file, converts it into a dict, and calls for the value of key:

def readFromJson() -> float:
    """Reads the value of "key" by opening data.json and parsing it into a dict,
    and then querying the in-memory dict.

    Returns:
        float: How long the operation took to complete in seconds (rounded to 6 dec.)
    """

    start = time.time()

    with open('data.json', 'r') as f:
        readData = json.loads(f.read())
    value = readData["key"]

    timeToComplete = round(time.time()-start, 6)

    print(f"Finished querying Json in: {timeToComplete} sec. (value: {value})")
    return timeToComplete

Here, I'm defining a method to get the value of key, but from the already cached in-memory dict DATA:

def readFromMemory() -> float:
    """Reads the value of "key" from the in-memory dict DATA (global)"

    Returns:
        float: How long the operation took to complete in seconds (rounded to 6 dec.)
    """
    start = time.time()

    value = DATA["key"]

    timeToComplete = round(time.time()-start, 6)

    print(f"Finished querying memory in: {timeToComplete} sec. (value: {value})")
    return timeToComplete

Finally, I'll define a quick tester method to compare the in-memory calls vs the file calls:

 def main() -> float:
    """Runs a call to readFromMemory and readFromJson and explains which was faster
    and by how much.

    Returns:
        float: the time difference between the readFromMemory and readFromJson calls (rounded to 6 dec.)
                (if pos. -> readFromMemory was faster, if neg. -> readFromJson was faster)
    """
    readFromJsonTime = readFromJson()
    readFromMemoryTime = readFromMemory()

    totalDelta = round(readFromJsonTime-readFromMemoryTime, 6)

    if totalDelta >= 0:
        print(f"Reading from memory was {totalDelta} sec. faster than reading from Json!")
    else:
        print(f"Wow! Reading from Json was actually {-totalDelta} sec. faster!")

    return totalDelta

As a bonus, I'm going to define a batch method to run lots of tests for us an aggregate the total results:

def runTests(numTests: int = 10000) -> None:
    """Runs lots of comparisons and explains the net delta,
    or how much time was saved by the in-memory calls.

    Args:
        numTests (int, optional): How many tests to run. Defaults to 10,000.
    """
    start = time.time()
    deltaCount = 0

    for _ in range(1, numTests):
        deltaCount += main()

    timeToComplete = round(time.time()-start, 6)
    print(f"Finished with a net delta of {round(deltaCount, 6)} seconds saved! (Runtime: {timeToComplete} sec.)")

Last but not least, the actual call:

if __name__ == "__main__":
    createJsonFile()

    # Try this out first to see a single test
    main()

    # Run this later to see a large comparsion - supply a custom value for numTests if you want!
    #runTests()

Here's the complete Python code (copy-pasteable)

import json
import time

DATA: dict = {
    "key": "val"
}

def createJsonFile() -> None:
    "Creates a simple data.json in the current directory with the value of the dict DATA"

    with open('data.json', 'w') as f:
        json.dump(DATA, f)

def readFromJson() -> float:
    """Reads the value of "key" by opening data.json and parsing it into a dict,
    and then querying the in-memory dict.

    Returns:
        float: How long the operation took to complete in seconds (rounded to 6 dec.)
    """

    start = time.time()

    with open('data.json', 'r') as f:
        readData = json.loads(f.read())
    value = readData["key"]

    timeToComplete = round(time.time()-start, 6)

    print(f"Finished querying Json in: {timeToComplete} sec. (value: {value})")
    return timeToComplete

def readFromMemory() -> float:
    """Reads the value of "key" from the in-memory dict DATA (global)"

    Returns:
        float: How long the operation took to complete in seconds (rounded to 6 dec.)
    """
    start = time.time()

    value = DATA["key"]

    timeToComplete = round(time.time()-start, 6)

    print(f"Finished querying memory in: {timeToComplete} sec. (value: {value})")
    return timeToComplete

def main() -> float:
    """Runs a call to readFromMemory and readFromJson and explains which was faster
    and by how much.

    Returns:
        float: the time difference between the readFromMemory and readFromJson calls (rounded to 6 dec.)
                (if pos. -> readFromMemory was faster, if neg. -> readFromJson was faster)
    """
    readFromJsonTime = readFromJson()
    readFromMemoryTime = readFromMemory()

    totalDelta = round(readFromJsonTime-readFromMemoryTime, 6)

    if totalDelta >= 0:
        print(f"Reading from memory was {totalDelta} sec. faster than reading from Json!")
    else:
        print(f"Wow! Reading from Json was actually {-totalDelta} sec. faster!")

    return totalDelta

def runTests(numTests: int = 10000) -> None:
    """Runs lots of comparisons and explains the net delta,
    or how much time was saved by the in-memory calls.

    Args:
        numTests (int, optional): How many tests to run. Defaults to 10,000.
    """
    start = time.time()
    deltaCount = 0

    for _ in range(1, numTests):
        deltaCount += main()

    timeToComplete = round(time.time()-start, 6)
    print(f"Finished with a net delta of {round(deltaCount, 6)} seconds saved! (Runtime: {timeToComplete} sec.)")

if __name__ == "__main__":
    createJsonFile()

    # Try this out first to see a single test
    main()

    # Run this later to see a large comparsion - supply a custom value for numTests if you want!
    #runTests()

The Demo

To start, just run the program. You'll see a single test that might print out something like this:

Finished querying Json in: 0.001 sec. (value: val)
Finished querying memory in: 0.0 sec. (value: val)
Reading from memory was 0.001 sec. faster than reading from Json!

As you can see, there's a difference. That might not seem like a lot, but try commenting out main() and uncommenting runTests(). Here's what it looked like when I passed in numTests=100000 to the runTests call:

<-- Hundreds of thousands of lines of individual test results -->
Finished with a net delta of 17.438135 seconds saved! (Runtime: 73.684126 sec.)

As you can see, those small differences add up. Now for most applications, I doubt you'll need something as powerful as Redis. But, there's a reason big tech companies that rely on speedy APIs like Twitter use it.

Be sure to like and let me know if you think Redis is worth it down below!

Deploying An App: 5 things I learned

Samarth Chitgopekar — Sun, 25 Jul 2021 23:51:02 +0000

Read this if you want details about the actual app - this will not impact your understanding of my tips!
6 months ago, I set out to develop the perfect evidence procurement tool for High School Debate. That 'perfect tool' happened to be Cuttr:

Pretty quickly, some friends gave me their two cents and the program evolved into Cut-It. This was the first application I wanted to deploy to thousands of regular people. Here's what our latest beta version looked like:

Finally, this summer, after months of work, I launched Cut-It 1.0, our first release version. If you thought the jump from Cuttr to Cut-It beta was cool, check this out:

I'm aware many of you have no idea what makes this project useful because High School Debate tech isn't exactly commonplace in dev circles. Luckily that's not the point of this post. When deploying Cut-It, I had to go through several hurdles and frankly, if I were rebuilding this project from scratch, I would do it completely differently. My advice should apply to anyone, so that's the point of this writeup.

Obligatory Promotion: Cut-It is open-sourced and we're looking for contributors! You can get it at cutit.cards.

Before we start, let me briefly explain the tech stack for Cut-It:

The project is written in Python
Qt (PyQt5) is used as a GUI framework (Cuttr used tkinter, though I quickly realized this was far too underpowered)
Binaries are built with PyInstaller

Now, here's my advice:

1. Don't use Python.

Although I like it's easy syntax, I found PyInstaller to be shaky at best. After working with Go (a compiled language), I got jealous of how easy it was to build and ship packages since it builds to a single binary. For reference, when I tried using the --onefile option with PyInstaller, it took me almost 20 seconds to run the program.

This comparsion might not be the fairest (Go is compiled, Python is interpreted), but the difference still stands. Even with other interpreted languages like Javascript, build processes still felt a lot cleaner. That could just be me, but regardless, I'd still go with Go over Python - especially now that it seems to have well-developed (albeit unofficial) Qt bindings.

2. Have multiple devices ready.

If you want to create a cross-platform desktop app, you're going to want to deploy on Windows and MacOS at a minimum, and probably Linux too. Windows and Linux are easy to do, but MacOS is a pain if you don't have a Mac. I tried using Scaleway, a Mac rental service, to rent a Mac to run PyInstaller on. It was a nightmare. The lag was unbearable and I had to end up building it on a friend's Macbook Air.

If you want to shell out $25/day (1 day minimum due to Apple's license) you can rent an instance from AWS. I'd imagine the lag would be minimal, since the servers would be in the US whereas Scaleway's are all in Paris. This project is open sourced and has no sponsorships, so I really didn't want to spend hundreds of dollars a year just to build it for MacOS, which is why I just decided to buy a Mac. This way, I can run Windows 10 with Bootcamp, Linux, and OSX on the same device.

3. Keep some cash on you.

Even if you're keeping your project free, you're still going to have to pay $99/yr. for Apple's Developer Program to get a Mac certificate (albeit Apple's price also gets you access to deploy to the iOS and Mac App Stores, among other things) and about $100 to get a 1 yr. Windows certificate from a provider. I consider these to be investments in yourself as a developer rather than a particular project, so I register them under my name. This way, I don't have to buy new certificates anytime I want to distribute something (though if you're building a major application you might want to consider doing so).

Keep in mind, this is a nice-to-have feature if you're building for developers - most of us will know the pains of getting certificates and it won't significantly harm your downloads to users conversion factor. However, if you're considering deploying to the 'general population', it becomes a requirement if you want people to actually use your program - those warning messages can be concerning. MacOS doesn't even immediately present you with the option to open an unsigned file, which is why I'd reccommend getting an OSX certificate through the Apple Developer Program over a Windows one if you have to pick.

4. Think ahead.

If you're going to be pushing any form of an update to your code, you need either an autoupdater or a built-in update notifier. Now the first option is still more difficult than it has to be - I haven't found a good cross platform autoupdater. I chose to implement a built-in update notifier instead. Here's a generic rundown of what I did:

On start:
1. Poll the GitHub releases page (using the GitHub API) for the latest release
 - If the latest release version == the current software version, ignore the rest of these steps and load directly to the program
2. In the release description, check for a throwaway tag marked '<req>' signaling that the update is required
 - If the update is required, don't offer a 'Continue without Updating' option
3. Find out what platform the code is running on
4. In the 'assets' section of the release on GitHub, find the target installer (Windows: dist-win.msi, MacOS: dist-mac.pkg).
5. Set the 'Update Now' button to open the 'browser_download_url' of the appropriate installer

Just like that, you can use GitHub's Releases API to maintain control over your codebase. The format for accessing your releases through the api is: https://api.github.com/repos/{USERNAME}/{REPO_NAME}/releases.

Here's what https://api.github.com/repos/http-samc/cut-it/releases looks like (various nonpretinent information omitted for brevity):

[
  {
    "url": "https://api.github.com/repos/http-samc/cut-it/releases/44302713",
    "node_id": "MDc6UmVsZWFzZTQ0MzAyNzEz",
    "tag_name": "v.1.0@Release",
    "target_commitish": "main",
    "name": "Cut-It Release Version 1.0",
    "created_at": "2021-06-08T19:23:24Z",
    "published_at": "2021-06-08T19:35:56Z",
    "assets": [
      {
        "url": "https://api.github.com/repos/http-samc/cut-it/releases/assets/40352177",
        "id": 40352177,
        "name": "dist-mac.pkg",
        "content_type": "application/octet-stream",
        "download_count": 35,
        "created_at": "2021-07-15T11:32:26Z",
        "updated_at": "2021-07-15T11:34:02Z",
        "browser_download_url": "https://github.com/http-samc/cut-it/releases/download/v.1.0%40Release/dist-mac.pkg"
      },
      {
        "url": "https://api.github.com/repos/http-samc/cut-it/releases/assets/40350931",
        "id": 40350931,
        "name": "dist-win.msi",
        "download_count": 40,
        "created_at": "2021-07-15T11:17:55Z",
        "updated_at": "2021-07-15T11:19:59Z",
        "browser_download_url": "https://github.com/http-samc/cut-it/releases/download/v.1.0%40Release/dist-win.msi"
      }
    ],
    "tarball_url": "https://api.github.com/repos/http-samc/cut-it/tarball/v.1.0@Release",
    "zipball_url": "https://api.github.com/repos/http-samc/cut-it/zipball/v.1.0@Release",
    "body": "<req> ... {omitted for brevity}",
  },
...
]

5. Know how to build installers.

This one's simple. No one wants to go through the pain of downloading, unzipping, deleting and replacing your program files/assets every time they update or install. Once again, there's obviously no crossplatform solution to this, but unfortunately, it's something you need to do reagardless. I'll keep it quick with what I used (both are free):

Windows: Advanced Installer
MacOS: pkgbuild (this is built in and shockingly easy to use)

Bonus Tip!!!

Don't build a desktop application. At least don't make it your go-to. After finishing up all of Cut-It's targeted functionality, I quickly realized the entire project could've been implemented quicker in vanilla JavaScript. Looking back, I remember reading the Qt docs thinking "What's the Qt method for window.getSelection()?".

I think the best way to build any GUI app is just with the HTML/CSS/JS stack. If you need a "real" desktop app (accesses filesystem, etc.), you can use a JS framework, with the most popular being Electron. I'm reimplementing Cut-It as a vanilla JS site that's a progressive web app. These are being championed by lots of big companies, and you can read about how Google is doing so in Chrome (v.70+) here.

This also solves the compilation and installer development issue. Because it's a web app, you never need an autoupdater. If you're using something like AWS Elsastic Beanstalk with their Code Pipeline to host your site, you can just push to main and instantly update your user's apps. Moreover, you don't need to worry about paying for certificates.

That's all I have for now, let me know what you think down below!