57 matches found for '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.

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

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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 .

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

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.

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.

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.

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

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.

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.

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 .

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.

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.

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

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

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

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.

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.

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

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.

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.

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.

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

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

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.

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.

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.

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.

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

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

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.

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.

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