DEV Community: Braeden Smith

Writing some JavaScript classes for interviews (Heap, Trie, etc)

Braeden Smith — Fri, 08 Jan 2021 07:29:59 +0000

JavaScript is a fantastic language for writing leetcode-style solutions. But unlike Python, C++, etc, it's missing a few critical data structures.

During a recent interview, I found myself scrambling to find a JS implementation of a min-heap online. As I was explaining to the interviewer the correct solution, I had to explain my interview language of choice did not have the native data structure I needed.

I never wanted to find myself in the same situation in the future.

And I didn't love any of the existing implementations online. I felt like they were either too complex to quickly drop into an interview or too simple and missing basic features.

braeden / interview.js

🧑‍🏫 A few useful JS classes (Heap, Disjoint Set, Trie) for drop-in use during interviews

Requirements:

Every class needed to execute in Node v10, but should use ES6+ practices
- This means no private functions, no nullish coalescing etc.
Each class should be easy to read and understand by an interviewer
Include the minimum viable function set but otherwise keep it short

Building a heap class

The heap was the most critical since it's a fairly common occurrence in problems and has some complexity.

We will use a zero-indexed array as the heap.

Constructor:

All arguments should be optional.

A comparator should be an input to decide heap type and heapify custom objects (like .sort()).
An input array which can be O(n) heapified should also be optional.

constructor(comparator = (a, b) => a - b, input = [])

We heapify down each node from the parent node to the root of the heap.

class Heap {
    constructor(comparator = (a, b) => a - b, input = []) {
        this.arr = input;
        this.comparator = comparator;
        if (this.size() > 1) {
            for (let i = Heap.parent(this.size() - 1); i >= 0; i--)
                this.heapifyDown(i);
        }
    }
}

Push, peek, size, pop

The easiest functions to implement:

size(): returns the length of the internal array.

peek(): returns 0th element if it exists, otherwise it returns null

push(): pushes like usual to the end of the array, and then calls heapifyUp on the last element to maintain the heap invariant.

pop(): swaps the first and last elements of the heap, pops() from the array (previously the highest priority element). And then heapifyDown() from index 0 to maintain the heap invariant.

push(elem) {
    this.arr.push(elem);
    this.heapifyUp(this.size() - 1);
}

peek() {
    return this.size() > 0 ? this.arr[0] : null;
}

pop() {
    if (this.size() === 0)
        return null;
    Heap.swap(this.arr, 0, this.size() - 1);
    const result = this.arr.pop();
    this.heapifyDown(0);
    return result;
}

size() {
    return this.arr.length;
}

heapifyUp and heapifyDown

These are recursive internal functions that are used to swap heap elements to keep the heap valid.

heapifyUp(): Base case = heapifying up from the root (0).
Otherwise, we grab the parent of element we're heapifying, and if the parent is lower priority then the current element, we swap them and recurse on the parent index.

heapifyUp(idx) {
    if (idx === 0)
        return;
    const parentIdx = Heap.parent(idx);
    if (this.comparator(this.arr[idx], this.arr[parentIdx]) < 0) {
        Heap.swap(this.arr, parentIdx, idx);
        this.heapifyUp(parentIdx);
    }
}

heapifyDown(): Base case there are no children nodes for our index (no where to heapifyDown into).
We grab the child with the maxmimum priority from our current location, and swap with our current index if that child is of higher priority. And then we recurse on the child index.

heapifyDown(idx) {
    if (Heap.leftChild(idx) >= this.size())
        return;
    const childIdx = this.maxPriorityChild(idx);
    if (this.comparator(this.arr[childIdx], this.arr[idx]) < 0) {
        Heap.swap(this.arr, childIdx, idx);
        this.heapifyDown(childIdx);
    }
}

This is the gist of our heap class, with a few static functions to move indices from parent to child and vice-versa!

The full class can be found here.

Building a dead-simple Trie class

A Trie is a super awesome data structure that I find myself using all the time in coding challenges.

The idea is that it's a tree of characters for various words, in our case, we'll be using standard JS objects to allow O(1) access to check characters at each level in the Trie.

We need three functions:

The ability to insert into the Trie
The ability to check if a full word exists in the Trie
The ability to check if a prefix of a given word exists in the Trie

These last two can be combined with an optional argument in the function.

Insert

Given a base object, we want to walk the tree with each character, creating an empty object, walking into it and then inserting the next character. But we also don't want to override existing data at the same level in the tree, ex: help, hello.

{"h":{"e":{"l":{"l":{"o":{"end":true}}}}}}

We can use the spread operator to make a shallow copy of existing object data, otherwise it's undefined and will create the empty object we want.

insert(word) {
    let temp = this.o;
    word.split('').forEach(e => {
        temp[e] = { ...temp[e] };
        temp = temp[e];
    });
    temp.end = true;
}

Find

The find function is very similar, we just walk down the object, and if at any point, the character we're looking at next doesn't exist, we return false.

If the user wants the full word match only, we will return the status of the .end property on the final node. Otherwise, once we've exhausted the character walk, the prefix find is true.

find(word, full = true) {
    let temp = this.o;
    let arr = word.split('');
    for (let i = 0; i < word.length; i++) {
        if (!temp[arr[i]])
            return false;
        temp = temp[arr[i]];
    }
    return full ? !!temp.end : true;
}

The full class can be found here.

I won't delve into the details, but I also included a disjoint set class that also comes in handy!

Hopefully this helps anyone else in the process of interviewing that needs some quick JS classes!

braeden / interview.js

🧑‍🏫 A few useful JS classes (Heap, Disjoint Set, Trie) for drop-in use during interviews

Why JavaScript is actually a great LeetCode/Interview language

Braeden Smith — Fri, 18 Sep 2020 06:26:24 +0000

In reality, the best language is the one you're comfortable with.

But if you're debating learning a non-strictly typed language, or stuck between several choices, I want to present a couple of reasons why JS might be worth a try.

Everyone is on the LeetCode grind these days.

If you're unfamiliar with LeetCode, it's a way to practice interview-type coding challenges in a short time frame. This article applies to actual interview services too, whether that's HackerRank, CodeSignal, HireVue, or any of the other numerous testing services.

For beginners, it's often parroted that Python, Java and C++ are the "big 3" to learn for LeetCode.

It's often said that C++/Java are great choices because they're super fast, have wide standard libraries, and strictly typed. C++ has a bit more convolution with memory management and iterators, but trades that for speed. Java is notoriously verbose, which is often against the spirit of fast iteration during interviews.

On the other hand, people often like Python since it's similar to writing pseudocode, it has a super beginner friendly community, and is fast to iterate upon.

I'm going to present some reasons (in no particular order) why JavaScript might be the best of both worlds for coding challenges (but especially as an alternative to Python).

I'm going to avoid dissing other languages in my reasoning, because I'm not quite as familiar and wouldn't want to misspeak about features.

#1) - Everything is objects (and that's awesome)

const object = {"key": "value"}

object.key // 'value' -- O(1) access/insertion time obv.
object.newKey = 'newValue'
object['key'] == object.key // true
// Easy to iterate (and it has fixed ordering)
Object.entries(object) // [ [ 'key', 'value' ], ... ]

Objects are awesome, flexible, and arguably the most important data association in software development.

I'd argue that "HashMap" type data structures are more valuable and more widely used than arrays. Fun fact: In JS typeof([1]) // 'object' -- even arrays are objects, just with some special additional properties.

But essentially we can use them as replacements to Sets/Maps/Dictionaries in other languages (which I'm sure a crazy high percentage of LeetCode-type problems require). And for problems that need to maintain insertion order we can use Map() and Set() in JS.

We can also easily use objects to represent Linked Lists, Trees, Graphs, Tries and more! This is essential when problems require to build out more complex algorithms.

let graph = {
'1': {
   edges: [2,4,5]
},
'2': {
   edges: [...]
}
....
}

let trie = { 
a: {
   b: { c: {} },
   d: {}
}

#2) Sometimes strict, static typing is awesome (but not for speed)

> [] + []
''
> {} + []
0
> [] + {}
'[object Object]'
// wtf https://www.destroyallsoftware.com/talks/wat

For real maintainable, testable, reliable code, it's almost always to have some typing assistance, whether that's a bit lighter (TypeScript) or super heavy (Rust).

But oftentimes that comes with the trade-off of fast iteration (or writing nothing but auto).

Learning how type coercion and non-static typing works in JS and similar scripting languages (Python, Ruby) makes it super easy to do fast tricks.

Essentially our JS engine does a best-effort type coercion when we're comparing or operating different types (eg. Number, String, Object, Array) -- that can give us some initially strange side effects. But let's show an example of how we can use this to our advantage!

// Do a frequency count on an array 'a'
// and store it in a object 'o' {key: count}
const o = {}
a.forEach(e => { o[e] = o[e] + 1 || 1 } )
// if o[e] doesn't exist, it's 'falsy'
// we short-circuit logical OR to return 1

I use this code basically all the time -- but there's plenty of other instances where this type coersion (especially knowing 0, '', null, undefined are all fasly values).

Reason #3) JSON = JavaScript Object Notation (and the web <3s it)

This advantage applies less to LeetCode problems, but more to take-home assessments. Build a small app to hit and API and do some data manipulation and POST it back to another endpoint.

This is what JS was built for, manipulating and handling data between web services. Almost every API or take-home assessment will involve JSON in some way or another -- and the built-in methods like JSON.stringify() and JSON.parse() make it a breeze.

From personal experience, I've done assessments with HubSpot and many others -- their whole focus is on real-world work for their assessment -- nothing is more real-world then GET requests and parsing JSON.

I was able to work extremely fast through the problems because I don't have to think twice about setting up libraries or schemas -- I just use Axios/Node-fetch and get back a fully usable object that I can manipulate to my heart's content.

And even for testing, being able to just paste JSON into an IDE and it immediately being a valid object to work with is extremely valuable.

#4) Built in array methods make life easy

Array questions are just about the most common input data structure, so you'll be manipulating and iterating through them often.

I'll just quickly enumerate some awesome array methods that I find myself using all the time in LeetCode and interviews (interviewers are often impressed by how quick and easy it makes certain problems).

Basic data manipulation (we can reduce mental complexity and use arrays as stacks and queues in JS)

1) pop()

['1','2'].pop() // a = ['1'], returns '2'

2) push()

['1'].push('2') // a = ['1','2']

3) shift()

['1','2'].shift() // a = ['2'], returns '1'

4) unshift()

['2'].unshift('1') // a = ['1','2']

5) slice()

[1,2,3].slice(1,2) // a = [2, 3]
// selects from index start -> end (optional) -- negative start index works too

Some iterative array manipulation (by order of most useful)

1) forEach()

a.forEach((e,i) => console.log(e, i)) // [1,2,3] -> prints 1 0 2 1 3 2
// iterates through each element

2) map()

a.map(e => e+1) // [1,2,3] -> [2,3,4]
// returns a new array with per element manipulation

3) reduce()

a.reduce((accum,e) => accum += e, 0) // [1,2,3] -> 6
// returns value that results from the reduction

4) sort()

a.sort((a,b) => b-a) // [1,2,3] -> [3,2,1] 
// returns a new array sorted based on the call-back comparison

5) filter()

a.filter(e => e%2!==0) // [1,2,3] -> [1,3] 
// returns a new array based on elements where the return is truthy

Extras

1) Turning strings into arrays and vice-versa (super common)

> "string".split('')
[ 's', 't', 'r', 'i', 'n', 'g' ]
> [ 's', 't', 'r', 'i', 'n', 'g' ].join(' ')
's t r i n g'

2) reverse()

[1, 2, 3].reverse() -> returns [3,2,1]

3) every()

a.every(e => e > 0) // [1,2,3] -> true
// [-1, 2, 3] -> false 
// returns true if every element evaluates to true for the expression

4) some()

a.some(e => e > 4) // [1,2,3] -> false 
// returns true if any element evaluates true for the expression

Read about every array method here

#5) JavaScript execution (V8) is ridiculously quick

Language specific time-outs are supposed to be adjusted to fit the execution model. But I've heard on the internet and from friends, sometimes you'll hit the optimal solution in HackerRank, but still get TLE (time limit exceeded) timeouts for larger test cases in Python.

Worry no longer about execution on larger datasets -- you'll be competing speed-wise with C++ and Java when you use JavaScript (where the V8 JavaScript engine reigns supreme (Chrome, Node.js)).

Essentially if you're able to get an optimal solution, or even something close to it, you'll get through all hidden test cases from a timing perspective.

JS vs Python
JS vs C++
JS vs Java

Misc advantages:

These don't necessarily fit neatly in a category, but I felt it was important to bring up these positives.

1) Object destructuringconst { result } = { result: "answer" }
2) Optional chaining animal?.color?.hexcode
3) NPM/Yarn -- package.json and large access to libraries for take-home assessments, make package managment a breeze
4) Spread operator Math.max(...a)

A few downfalls or dislikes:

1) Lack of heap structure (at least built-in)
2) Direct string manipulation feels hacky: charAt(), split(), splice()
3) Array slicing feels less clean than Python implementations.

Thanks for reading! Let me know if you have any thoughts, why JS is great or not-great for coding interviews/LeetCode!

A micro API in Firebase and Cloudflare Workers

Braeden Smith — Mon, 27 Jul 2020 03:06:41 +0000

Intro

This project started as a late-night inspiration after reading a Hackernews article -- I set out to build a tiny REST(ish) API using Firebase!

To put it succinctly, Github added a feature which allows you to embed Markdown on your profile page. Obviously a core feature of Markdown is the ability to embed images, and although Github throws images behind their own CDN, critically, they obey Cache-Control headers from the source.

My Github with profile Markdown

This let's us do fun stuff like count visitors or deliver randomized images a-la "hit counters" from websites of the early 2000s!

That is, of course, only if we include Cache-Control: max-age=0, no-cache, no-store, must-revalidate in our response image headers.

Building with Firebase

Wanting to get my feet wet with Firebase, I explored building a serverless API with 3 4 endpoints (plus who wants to spend money on EC2 or App Engine):

setImage (POST)
- The user should pass a valid image URL that they'd like to embed -- in response they will receive a random ID token
getImage (GET)
- This is the image link you would embed in Markdown, with your ID token as a query parameter. The image gets fetched and streamed back as a response -- while also keeping track of hit counts
getStats (GET)
- Requires the same ID token as a query parameter and returns the current visitor count as JSON.
randomEmoji (GET)
- Delivers a random emoji from Twitter's FOSS emoji set

I really wanted to write this in TypeScript and Firebase provides fantastic documentation on how to setup serverless TS functions.

The gist of it is that you handle each function is just like a Express.js endpoint with a request and response.

export const randomEmoji = functions.https.onRequest(async (req, res) => {
    res.set('Cache-Control', 'max-age=0, no-cache, no-store, must-revalidate');
    const target = emoji[Math.floor(Math.random() * emoji.length)];
    const url = `https://raw.githubusercontent.com/twitter/twemoji/master/assets/svg/${target}.svg`
    const response = await fetch(url);
    if (response.ok) {
        res.setHeader('content-type', response.headers.get('content-type') || '');
        return streamPipeline(response.body, res);
    }
    res.status(404).end()
});

I wanted to delve briefly into how the serverless functions work -- but it's not that complicated and can be found in this repo.

Additionally I needed a quick persistent database for this API -- Firebase Real-time Database worked great for this. It again has fantastic documentation and since the serverless functions already have "Admin" access to the DB, it required minimal configuration.

Firebase K/V Setup

Here's the core of setimage:

const db = admin.database();
const id = [...Array(5)].map(() => Math.random().toString(36)[2]).join('')

await db.ref(`${id}`).set({
    url: req?.body?.url || '',
    count: 0
})

Here's the core of getImage:

const db = admin.database();

const d = await db.ref(`/${req.query.id}`).once('value');
const url = d?.val()?.url || '';

const response = await fetch(url);
if (response.ok) {
    await db.ref(`/${req.query.id}/count`).transaction(c => c + 1)
    // We use transactions here to avoid DB issues w/ concurrent requests
    return streamPipeline(response.body, res);
}

As you can see: it's dead-easy to interface with the DB and setup these serverless functions (Firebase provides incredible velocity to create new projects and APIs).

Feel free to hit the API yourself! Docs are in the postman collection in the above repo. Here's your random emoji.

https://us-central1-gh-img.cloudfunctions.net/

braeden / braeden

👀 Serverless API in Firebase/Cloudflare to track profile views on Github

Hi there 👋

Enjoy this random emoji -

View on GitHub

Problems with Firebase (with 'serverless' in general)

Serverless is dead cheap and dead easy -- you don't have to manage containers, servers, Kubernetes, or fancy CI/CD -- you just write your code and go!

The problem arises with the "Scale to zero" mentality which affects AWS Lamdas, GCP Functions (Firebase) and Azure Functions. It keeps users paying per invocation/seconds of execution, but it means there's a cold-start time payoff.

Especially in a time critical event, like fetching images in one-off events, having 3000ms delay for the first invocation response absolutely kills UX.

Check out this awesome article comparing cold-start times between cloud providers: https://mikhail.io/2018/08/serverless-cold-start-war/

The Fix?

Cloudflare is best known for their dominance over the CDN market, but they have a really neat product I stumbled upon a few days ago!

Cloudflare Workers

It's serverless compute but with these enticing promises:

Cold starts up to 50× faster than other platforms

Your code runs within milliseconds from your users worldwide

Service Workers are background scripts that run in your browser, alongside your application. Cloudflare Workers are the same concept, but super-powered: your Worker scripts run on Cloudflare’s edge network, in-between your application and the client’s browser.

Building randomEmoji in Cloudflare was fairly easy -- although there is definitely room for improvement in the local testing and automatic deployment.

The example 'template' workers that litter Cloudflare's website are a godsend to get started with any use-case!

addEventListener('fetch', event => {
    event.respondWith(
        (async () => {
            const target = emoji[Math.floor(Math.random() * emoji.length)];
            const url = `https://raw.githubusercontent.com/twitter/twemoji/master/assets/svg/${target}.svg`
            const image = await fetch(url)
            const {
                readable,
                writable
            } = new TransformStream()
            // I <3 object destructuring
            image.body.pipeTo(writable)
            const r = new Response(readable, image)
            r.headers.set('Cache-Control', 'max-age=0, no-cache, no-store, must-revalidate')
            return r
        })()
    );
});

We just need to provide a IIFE inside an event listener -- this wipes the floor with GCP's serverless speed.

The code content is very similar, some documentation searching is required but only for the response creation and piping.

Hitting the randomEmoji endpoint speed comparison:

Cold-start
- GCP: 3500ms
- Cloudflare: 400ms
Warm-start
- GCP: 330ms
- Cloudflare: 160ms

An attentive reader would notice we skipped migrating 3/4 of our 4 HTTP endpoints

Here's the caveat, if you need some sort of Key-Value store (which we do), Cloudflare offers a tempting solution, but you'll have to pay $5/mo for the pleasure.

A few more details:

Workers KV is a global, low-latency, key-value data store. It supports exceptionally high read volumes with low-latency, making it possible to build highly dynamic APIs and websites which respond as quickly as a cached static file would.
Workers KV is generally good for use-cases where you need to write relatively infrequently, but read quickly and frequently.

This sounds exactly like our use-case! (Obviously it's a scale overkill, but we're exploring cool tech.)

Checking out Cloudflare KV to migrate completely away from Firebase

We want to store a unique ID as key, and have url and count as properties on that object.

We must first create a KV Namespace either using wrangler or an online interface -> we can share this between different workers if we wanted. (It will be called 'gh' in the examples below.) This namespace needs to bound to our worker again via web interface or wrangler.toml via wrangler kv:....

As far as I can tell, URL params are not supposed to be used with Workers -- but they seem to work if you manually parse them.

I found a super helpful community post that included a snippet on parsing out query strings.

For simplicity's sake we'll move the (image/visitor count) API under one worker: getStats will just be a POST with a getStats: true

Handling Routes

addEventListener('fetch', event => {
  const { request } = event
  if (request.method === 'POST') {
    return event.respondWith(postResponse(request))
  } else if (request.method === 'GET') {
    return event.respondWith(getImage(request))
  }
});

postReponse() (getStats and setImage)

async function postResponse(request) {
  const body = await request.json()
  if (body.url) {
    // setImage
    const id = [...Array(5)].map(() => Math.random().toString(36)[2]).join('')
    await GH.put(id, JSON.stringify({
      url: body.url || '',
      count: 0
    }));
    return new Response(JSON.stringify({
      id
    }))
  } else if (body.id) {
    // getImage
    const kvObject = JSON.parse(await GH.get(body.id));
    return new Response(JSON.stringify({ count: kvObject.count }));
  }
  return new Response('Not a valid POST request')
}

getImage()

async function getImage(request) {
  const params = {}
  const url = new URL(request.url)
  const queryString = url.search.slice(1).split('&')
  queryString.forEach(item => {
    const [key, value] = item.split('=');
    if (key) params[key] = value || true;
  })
  const kvEntry = await GH.get(params.id)
  if (kvEntry) {
    try {
      const kvObject = JSON.parse(kvEntry);
      const image = await fetch(kvObject.url);
      const {
        readable,
        writable
      } = new TransformStream();
      image.body.pipeTo(writable);
      const r = new Response(readable, image)
      r.headers.set('Cache-Control', 'max-age=0, no-cache, no-store, must-revalidate')
      kvObject.count++;
      await GH.put(params.id, JSON.stringify(kvObject));
      return r;
    } catch (e) {
      console.error(e);
      return new Response('URL was invalid');
    }
  }
  return new Response('ID not found');
}

As you can see this move from Firebase to Cloudflare Workers was fairly easy and only required a minimal rewrite. There's still tons of room for improvement -- not returning just plaintext, better error handling, TypeScript rewrite and more. Also not having to stringify and parse JSON in the KV store, an necessity based on the value type restriction to: string, ReadableStream, ArrayBuffer.

The performance benefits of Cloudflare work fantastically for porting this particular micro API!

Thanks!

Thanks for reading and I hoped you learned something about some of the serverless market!

All of the code mentioned in this article, and the API details if you would like to use this in your own README can be found here: