@rkenmi - Search Results

Merge k sorted linked lists

Problem Merge \(k\) sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Input lists - an array of linked list pointers # Definition for singly-linked list.

February 9, 2019

Overlapping linked lists

Given two linked list nodes, one might overlap the other. That is, one linked list might contain a sequence that is already in the other linked list. The two linked lists share a common node.

September 26, 2017

Reversing sublists of singly linked lists

Singly linked lists can be tricky in its own right. Without the convenience of having a pointer to the previous node that is provided in doubly-linked lists, it can be really easy to be wasteful in performance with singly linked lists.

September 24, 2017

Detecting a cycle in a linked list

Problem Detect a cycle in a linked list and return the node that represents the start of the cycle. Input head: a pointer to the linked list Approach First, lets concentrate on how to detect a cycle in a linked list.

September 26, 2017

Algorithm Handbook

... result is not a 0, then the bit at \(i\) is a 1. Strings When constructing strings, use a list in Python and add characters accordingly. The entire string can be returned via "".

June 18, 2017

Square each element of a Scala list

There are two practical ways to square each element of a list, and return the new list. For example, if we input a List(5, 10), we should have a List(25, 100).

December 8, 2014

Phone Number Mnemonics in Python

... and an integer index to keep track of which digit you need to convert. Start by having an empty list. The goal is to have a list representing a mnemonic; with digits and characters.

September 21, 2017

Algorithm Interview Problems

... all occurrences of a space with a string Linked Lists Reversing sublists of singly linked lists Cycles in singly linked lists Overlapping singly linked lists Merging two sorted singly linked lists Merge k sorted lists Recursion Counting the path of sums Money Denominations Phone Number Mnemonics Unique Permutation Dynamic Programming Perfect Squares Find the Maximum Min Path Binary Trees Tree Symmetry Iterative In-Order Traversal of a Binary Tree Construct a Binary Tree from Pre-Order Traversal and In-Order Traversal BST Validate a BST Binary Heaps Merge k sorted lists Graphs Find a path in a maze from start to finish Flip colors in a matrix Search Search in a rotated sorted array Find the Duplicate Number Greedy Algorithms Queue Reconstruction By Height Trie Build a Trie in Python Invariant Compute the max.

January 25, 2019

Merging Sorted Linked Lists

var jsav = new JSAV("ll"); jsav.label("Two sorted lists"); var ll1 = jsav.ds.list(); var ll2 = jsav.ds.list(); ll1.addLast("5").addLast("7").

January 24, 2019

Cyclic Permutation

This is an array/list trick that saves about O(n) in space complexity by taking advantage of a given array with integers representing indices. For this example problem, suppose that we want to apply some permutation P to an array A.

September 11, 2017

Coin Change Denominations

... the total number of money denominations, given 2 parameters -- the amount of money and the list of allowed coins to use. But not only that, we can also make this a one-liner! def countChange(money: Int, coins: List[Int]): Int = if(money == 0) 1 else if(money > 0 && !coins.

November 1, 2014

Unique Permutations

... since we don't want to store hash tables into hash tables 😦. A good compromise is to convert the list objects into immutable tuple objects. An alternative solution is a string, but converting a list to a string will involve a .

February 18, 2019

4 Line Depth-first Search

... C, D, E] We should also have our edges defined somewhere. Edges are best defined in an adjacency list, which should be used to represent the neighbors of a vertex. Starting Point Once we have our vertices defined, we can now define an algorithm that accounts for all vertices in the highest-level view so that all nodes and edges in the graph are accounted for.

May 7, 2017

Queue Reconstruction by Height

Problem Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h.

January 27, 2019

String Manipulation in Python 3+

... => `['a','b','c'] "a.b.c".split(".", maxsplit=1)` => `['a','b.c'] When you want a list with entries delimited by some separator. Note that, the delimiter will not be included in the result.

October 24, 2017

NumPy vs. Pandas, and other flavors (Dask, Modin, Ray)

... structure, which stands for n-dimensional array. The key difference between a traditional Python list and ndarray is Python lists can allow any type of object inside the list.

May 26, 2022

Python Essentials

... resumes code execution. This is useful when you are iterating through large sets of data (i.e. a list of billions of objects) which takes up more memory than you have available on your machine running the Python code.

April 3, 2019

Topological Sorting

... the children gets added before the parent, which if done recursively, will present you with a list of nodes in topological order. BFS To do topological sort via BFS, you will need two things: Adjacency Lists In-degree array (or map) The N-degree (or in-degree) array is a mapping of indices (the vertex ID) to the count of incoming graph edges.

March 6, 2021

Scanning for memory addresses with Cheat Engine and ZSNES

... users in the CE community provide cheat tables for games. These cheat tables are basically lists of memory addresses that directly correspond to certain data in a game, e.g. movement speed, or health points.

July 4, 2017

A primer on MapReduce

... on each element in some container and transform them. For example, if I want to convert a list of numbers to strings in Javascript: [0, 1, 2, 3].map(number => Integer.parseInt(number)); Reduce Reduce is also known as folding or aggregation.

July 11, 2020

RDBMS Indexing

... is. From the wiki: An index ( plural: usually indexes, more rarely indices; see below) is a list of words or phrases ('headings') and associated pointers ('locators') to where useful material relating to that heading can be found in a document or collection of documents.

January 24, 2021

Rotate a 2D Matrix

... = A[~j][i] return copy Note that ~j is equivalent to -(j + 1). When used as an index of a list, it could also be interpreted as j + 1 values from the right. This algorithm requires \(O(n^2))\) space complexity and \(O(n^2))\) time complexity Approach #2 The optimized approach has a very straightforward strategy that you can follow.

December 7, 2018

Javascript Essentials

... Firefox, and Internet Explorer. Event Loop The event loop is basically a loop that listens for an event and takes some action when an event is received. while (queue.waitForMessage()) { queue.

November 12, 2017

Java Essentials

... Data Structures Empty array ArrayList<T> list = new ArrayList<>(); Array with values ArrayList<Integer> list = new ArrayList<>(Arrays.

March 29, 2019

Buy and Sell Two Stocks

... the left) that is smaller than the current max_so_far, we calculate the profit and add it to the list -- more precisely at the index of the element we just looked at. All that needs to be done now, is to add the \(i\)th element in the forward iteration to the \(i+1\)th element in the backward iteration.

December 10, 2018

Primes

... means \(4\) is not a prime. Problem Given an integer \(n\), write a function that returns a list of all prime numbers up to \(n\) (inclusive). Input \(n\): Integer Examples prime_func(5) => [2, 3, 5] prime_func(10) => [2, 3, 5, 7] prime_func(0) => [] Strategy A quick, brute-force way to solve this is to go through all numbers from \(2\) to \(n\) and evaluate each number if it is a prime.

October 5, 2017

Iterative In-Order Traversal

... Thus, when thinking about the iterative approach, we should simply use a stack data structure. A list does the trick here. Even with a list however, it is still a bit tricky to represent recursive logic in an iterative fashion.

December 31, 2018

Merge Intervals

Problem Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

February 13, 2019

Find the duplicate number

... \(i = A[i]\), so we return \(i\). Fun fact: This is similar to detecting a cycle in a linked list. If you treat the integer values of the array as pointers, then running into the same pointer value implies that a cycle exists.

February 8, 2019

Composite Pattern

... of ChapterTitles. Frank wants to design a class now, called TableOfContents that houses a list of Chapter objects or ChapterTitle objects. But storing a list of entries isn't enough; Frank wants the TableOfContents class to be smart enough to know how to handle a Chapter or a ChapterTitle when needed.

May 15, 2017

Build a Binary Tree with Pre-order and In-order traversal data

Problem Given a pre-order traversal array of integers and an in-order traversal array of integers, construct a binary tree. Input preorder - array of integers inorder - array of integers # Definition for a binary tree node.

January 8, 2019

Tenets of Leetcode

... word space where you can (less typing) Step-by-step + bullet point style is better than numbered lists (i.e. 1. Draw, 2. Pseudocode 3. Run Test Cases). It is more work to update numbered lists if you miss a step.

January 27, 2021

Design Concepts

... sec = 60 minutes = 1 hour 24 * 3600 = 1440 minutes = 24 hours = 1 day Here is a ballpark list for various content: URLs: \(0.5 KB\) Images: \(250 KB\) (avg.), \(10 MB\) (max) Videos: \(2 MB\) (avg.

November 20, 2019

Paint adjacent boundaries with distinct colors

... assignment): # AC-3 """ initialize the queue with all the arcs in csp""" # queue = list of arcs (i.e. an arc from Chad to Egypt) queue = [] # tail represents a country for tail in csp : # curr represents a country adjacent to tail # add arcs from tail -> (adjacent countries to tail) to the queue for curr in csp[tail]: queue.

December 11, 2014

Storing passwords into a database

... the other two because it's a one-way street for input data, but what if someone already had a list of hashed passwords for the most commonly used passwords? (Hint: it's already exists somewhere on the web) Another key thing is that your typical hash (MD5, SHA-256) is incredibly fast to execute, because their purpose is to verify file hash checksum integrities.

January 30, 2021

Python String Tricks - Performance considerations

... to work with mutable strings We can use bytearray to manipulate strings in a fashion similar to lists. String index assignment can be done with bytearray. i.e. s[0] = ord('A') ord returns an integer representing the Unicode code point of that character.

September 17, 2017

Next Permutation

... to the right of \(swap_i\) were already in descending order; all we have to do is reverse that sublist to get them into ascending order. Solution def nextPermutation(self, nums: 'List[int]') -> 'None': """ Do not return anything, modify nums in-place instead.

February 17, 2019

Add SSL certificates to a website

... and public key. It then checks whether or not the SSL certificate is trusted, by checking against list of trusted CAs. If the certificate is trusted, the browser creates a symmetric session key using the server's public key and sends it to the server.

July 5, 2019

Data stores in Software Architectures

... are major scaling drawbacks to this, as well as resiliency issues. For that reason, it is hard to list that as a runner-up. :( Solutions: Object Store (ex: Amazon S3) + CDN Runner-ups: - Text Autocomplete Service Text autocomplete is so popular that a solution was made specifically for it - search engines.

July 19, 2021

Compute the max. water trapped by a pair of vertical lines

Problem An array of integers naturally defines a set of lines parallel to the Y-axis, starting from x = 0 as illustrated in the figure above. The goal of this problem is to find the pair of lines that together with the X-axis "trap" the most water.

February 5, 2019

Web Development 101

... fetch or update resources on the server. This standard allows two things: The server can whitelist a list of IPs so that any request from these IPs can access the resources.

November 9, 2017

Useful Links

This is a personal list of useful resources for improving web stacks, frameworks, development, UX, whatever that I come across! Software Engineering The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) Encryption vs.

September 4, 2017