Search Results

14 matches found for 'sorted array'

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.

February 13, 2019

Algorithm Interview Problems

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

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

February 17, 2019

Algorithm Handbook

Introduction Welcome to the algorithm handbook wiki! In this wiki you will find a mini-cheat sheet overview of data structures, and examples of their usages in modern languages. Algorithm problems can be found here.

June 18, 2017

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

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.

February 8, 2019

Topological Sorting

There are two ways to do topological sorts: DFS To perform a topological sort via DFS, you will need the following: Adjacency Lists A "visited" set Recursion Recall that DFS itself will not give you nodes in topological ordering.

March 6, 2021

B-Trees vs. LSM Trees

B-Trees Modern databases are typically represented as B-Trees or LSM Trees (Log structured merge trees). B-trees are "tried and true" data structures that are popular in database usage, most notably SQL databases.

March 14, 2018

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

Bloom Filter

A set data structure uses a hashing function to store values and to verify if a value exists. Bloom filters are similar in that it uses multiple hashing functions to store values and to verify if a value exists.

October 14, 2019

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.

July 11, 2020

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.

May 7, 2017

Java Essentials

JVM Java is a statically typed language that is compiled into bytecode (i.e. with javac) and understood only by the JVM, or Java Virtual Machine. The JVM is an interpreter that reads the Java bytecode and translates them into machine code before execution.

March 29, 2019

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