Search Results


57 matches found for 'algorithms'

Greedy Algorithms

There are many definitions of greedy algorithms, but in general, they have two properties: You build the solution by finding the most optimal answer at each local step. As you go through each local step, you do not backtrack; the answer you've picked for all of the previous steps remain the same.


Algorithm Handbook

... this option over classics like Quicksort. Great for very small datasets: The divide-and-conquer algorithms (Quicksort, Mergesort, etc.) have more overhead so they aren't quite as fast when working with tiny data sets (with less than 10 elements, for example).


Buy and Sell Two Stocks

Problem Given an array of integers representing stock prices, with each index representing a different day, find the maximum profit by selling at most two stocks. The buy/sell dates must not overlap.


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.


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.


Algorithm Interview Problems

Welcome This page contains solutions to common interview problems that may be encountered. Arrays Longest Substring Without Repeating Characters Rotate a 2D Matrix Buy/Sell Two Stocks Merge Intervals Next Permutation Random Permutation Replace 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.


4 Line Depth-first Search

Context Depth-first search (DFS) is a common searching algorithm for graphs, alongside Breadth-first search (BFS). DFS is useful for finding ways to solve mazes. It is also a vital ingredient for topological sorting.


Counting the path of sums

Description Given a binary tree with nodes containing integer values (positive or negative), how can you count up all the paths that equal to some target sum? Note, that the paths do not have to start from the root; it may start from any sub-tree and end at another sub-tree, as long as the path goes down the tree.


Misconceptions of Software Engineer interviews at FAANG

... for interview prepping may demotivate you. In reality though, there are only a handful of algorithms per category worth studying. Core concepts will always trump niche knowledge such as Math tricks with pow/modulo or searching substrings using Rabin-Karp.


Phone Number Mnemonics in Python

... (iterative styles are usually faster) but because of simplicity and organization - like many algorithms with functional programming languages like Scala, recursive functions in general look neater, nicer, and easier to categorize.


Rotate a 2D Matrix

var jsav = new JSAV("set"); jsav.label("Before rotation").css({"color": "gray"}); var m = jsav.ds.matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]]); jsav.label("After rotation").css({"color": "green"}); var n = jsav.


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. Problem Build a function that takes two singly linked lists and returns a boolean output that signifies whether or not the two linked lists share a common node.


Search in a rotated sorted array

var jsav = new JSAV("av-sym"); jsav.label("A sorted array rotated to the left by 3"); var arr = jsav.ds.array([25, 28, 29, 34, 1, 15, 20]); Problem Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.


Primes

Let's discuss primes! A natural number is considered a prime if it is: Greater than 1 Its divisors are only 1 and itself Examples: \(5\) has two divisors: \(\frac{5}{1} = 5\) and \(\frac{5}{5} = 1\) Which means \(5\) is a prime.


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.


Bloom Filter

... 3, 4, 5, 6]); arr.show(); In actuality, \(X\) doesn't exist. But unfortunately, our hashing algorithms have marked the same indices (from the other articles) that \(X\) maps to.


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.


Random Permutation

Problem Given an array of integers, and an integer index \(k\), randomly permute the array up to index \(k\). Input \(A\) - Array of integers \(k\) - integer index representing the indices to permute up to Approach Key insights into random permutation with arrays: If only k elements are permuted in an array of size n, the algorithm for random permutation should only cost k in time complexity.


Recursive multiply function in Python using + and binary shifts

Here is one way to do an arithmetic multiply on two positive integers only using <<, >>, and +, without using the * or / operators. The idea is to keep shifting n1 to the left by 1, as n2 is shifted to the right by 1.


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.


Unique Permutations

Problem Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] Input nums - Array of integers Approach The brute force approach is to generate all permutations of \(nums\) and store them into an array.


Build a Trie in Python

Problem In computer science, a trie (pronounced "try"), also called digital tree, radix tree or prefix tree, is a kind of search treeā€”an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.


Longest Substring Without Repeating Characters

Problem Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.


Symmetry in a Tree

var jsav = new JSAV("av-sym"); jsav.label("Symmetric tree"); var bt = jsav.ds.binarytree(); bt.root("5"); // set the value of the root bt.root().left("3"); // set left child bt.


Decode number of ways

Problem A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).


Iterative In-Order Traversal

Problem Return the values of a binary tree using in-order traversal, iteratively. Input node: Has 3 properties .val: Integer value of the node .left: A pointer to another node object, or None if null .


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].


Find the duplicate number

Problem Given an array nums containing \(n + 1\) integers where each integer is between \(1\) and \(n\) (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.


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.


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.


Next Permutation

Problem Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).


Reversing words in a string : the double reverse

Problem Reverse all words (separated by space) in a string Input \(s\) - a string Approach Nice case and point for really examining the examples. First, a few examples of reversing words in a string.


Perfect Squares

Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Examples: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.


Validate a BST

Problem With a binary tree as input, determine if the tree is a BST or not Input node: Has 3 properties .val: Integer value of the node .left: A pointer to another node object, or None if null .


Replace all occurrences of a space inside an array

Problem Given an array of characters, replace all occurrences of a space with another string. Assume that the array has enough space to contain all of the replacements. Input A - An array of characters which may or may not have spaces word - The string to replace spaces with.


Find the maximum min path

Problem Given a matrix of integers, there are many paths to take from the top left to the bottom right. For each path, the smallest number in the path is the min of the path. Of all the min paths, find the maximum min path.


Distributed scaling with Relational Databases

... missing from a lot of system design explanations that talk only about general purpose sharding algorithms and replication methods. The focus of this article is to talk about optimizing SQL databases in the context of distributed systems, before we decide to move on to NoSQL alternatives.


P vs. NP

... vs. NP When we talk about P or NP, we generally talk about decision problems, which means the algorithms always output a "yes" or a "no". Abstract versions of these problems can include things like a solution to a chess game, or figuring out if a number is a prime.


Machine Learning Basics

... labels are known as \(y\). Labels are known in supervised learning and semi-supervised learning algorithms. Models learn relationships between features and labels i.e. prices (label) are higher for houses with greater sq.


Data stores in Software Architectures

Use Cases There are many ways to store your data. In this article we'll walk through some examples of data storage in common system designs. Reminder: There is no single best storage choice and they may vary heavily depending on things such as access patterns and scale.


Design Concepts

In this article, I want to go over some fundamental design concepts that are useful for coming up with system design. Requirements Functional Requirements Describes specific behaviors i.e. If a URL is generated, it is composed of a Base64 encoded alias Non-functional Requirements Describes architectural requirements i.


Merging Sorted Linked Lists

... algorithm is quite basic but it is a building block to other trickier linked list algorithms. The most painless and intuitive approach here is to use a dummy node and assign the next pointer of the dummy node to whichever node is smaller -- L1 or L2.


Add SSL certificates to a website

Having a SSL certificate will enforce visitors to connect to a website via the HTTPS protocol, which runs on port 443. The server and the visitor will communicate and transmit encrypted data under this protocol.


Tenets of Leetcode

Disclosure I'm a simple guy who did a handful of interviews at tech startups and enterprise companies until I landed an offer at FAANG. I'm also fairly involved with interview loops at my FAANG company.


Web Development 101

HTTP vs. HTTPS HTTP stands for Hypertext Transfer Protocol. It typically runs on TCP port 80. It is a protocol for sending data through browsers in the form of webpages and such. One major flaw with HTTP is that it is vulnerable to man in the middle attacks.


2PC - Two Phase Commit and Why it Sucks

... be handled. Thus, better solutions for atomic, distributed writes are centered around consensus algorithms that have the ability to detect failed nodes. Zab and Raft are a couple of good examples.


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

... DataFrame is a special data structure used primarily by data scientists and machine learning algorithms. It contains row and column data in tabular fashion by storing metadata about each column and row.


CAP Patterns

The CAP Theorem dictates that only two of its three characteristics can be guaranteed at any given time. Intro to CAP Consistency Every read will be based off of the latest write Availability Every request will be given a response, although the response data might be stale Partition Tolerance It can handle network partitions or network failures MTV's The Real World If your service is in the cloud, the P in Partitioning has to always be accounted for.


Sharding User IDs of Celebrities

Problem When you are partitioning (or sharding) database writes across multiple nodes based on a User ID, a typical partitioning algorithm is to use a basic hash like MD5 to have a reasonably compact (as in, low number of bits) partition ID.


NFT from a Software Developer's perspective

What is a NFT? A NFT (non-fungible token) is: A unit of data for blockchains with smart contracts functionality (i.e. Ethereum, Cardano) Uniquely represents one entity One non-fungible token cannot be equivalent to another non-fungible token What does it contain? It contains these three bare essentials: An ID that guarantees uniqueness An owner The owner may change over time when NFTs are exchanged with buyers A link to the digital asset metadata Can be untrustworthy and centralized http links, or a link to darknet services / P2P distributed storages (i.


Storing passwords into a database

Don'ts Don'ts Don't put raw passwords in the database Don't put encoded passwords in the database (i.e. Base64) Don't put simple hashed passwords in the database (i.e. MD5, SHA-256) Whys For obvious reasons, putting raw passwords means that the DBA or anyone who has access to the database can steal the passwords.


Authentications

... access permissions on resources after Authentication. IDs IDs can be generated with many algorithms: Auto Increment Comes out of the box in most SQL databases Doesn't scale when you increase number of machines due to ID inconsistencies UUID ID is guaranteed to be unique, probability of creating just one duplicate is extremely low It's a randomly generated ID, so no input required Can scale as you increase number of machines Its 128 bits so it can be too big SHA256 It's a reliable and fast hash It's a hash so you need some input (i.


Basic Encryption

... use as opposed to the asymmetric alternative. AES is one of the most popular symmetric encryption algorithms. In asymmetric encryptions, two keys are generated; private and public. The public key is used to encrypt the data, and the private key is used to decrypt the data.


Coin Change Denominations

Problem Given some amount of money integer, and an array of integer coins, calculate the total number of ways to make change. Approach Suppose that we want to find the total number of denominations of 5 cents, using any U.


A primer on MapReduce

To first understand this very popular backend technology called MapReduce, let's take a look at Map and Reduce. Terminology The terms Map and Reduce are actually very popular higher-order functions used in functional programming.


Paint adjacent boundaries with distinct colors

In my recent A.I. class, I had an assignment where I had to write some code that will paint the countries of Africa with distinct colors. For the colors, I was given a domain of set(['red','blue','white','yellow','green']).


DataFrames (a software engineer's perspective)

... DataFrame is a special data structure used primarily by data scientists and machine learning algorithms. It contains row and column data in tabular fashion by storing metadata about each column and row.