Search Results

40 matches found for 'arrays'

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

... sub-array to the left and right of the root value in the in-order array are also in-order arrays for those sub-trees. With these observations in mind, it is clear that a recursive approach is the best way to tackle this problem.

January 8, 2019

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

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

Algorithm Handbook

... Advice 1: Split merge sort into two functions - one for diving an array into subarrays and another for the merge operation. Keep the function that divides an array into left and right subarrays simple - no need to pass in index counters into the function.

June 18, 2017

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.

April 13, 2019

Cyclic Permutation

... problem, suppose that we want to apply some permutation P to an array A. P and A will be both arrays with the same size, but different content. The two arrays as inputs: A or original array (one that contains characters that you want to permute) P or permutations (one that contains integers that represent how A should be ordered) For example, for the following input: A = ['a', 'b', 'c', 'd'] P = [1, 3, 0, 2] The output then should be >>> ['c', 'a', 'd', 'b'] The easy solution The easy solution to this problem is to have an additional list as a buffer.

September 11, 2017

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

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.

December 7, 2018

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.

December 10, 2018

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

NumPy NumPy is a Python library for numerical computing that offers multi-dimensional arrays and indices as data structures and additional high-level math utilities. ndarray The unique offering of NumPy is the ndarray data structure, which stands for n-dimensional array.

May 26, 2022

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.

October 5, 2017

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.

January 25, 2019

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

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.

February 21, 2019

Javascript Essentials

... this can work against you. For example, if you try to use in like you do in Python with arrays, you will be doing a property lookup, rather than a value lookup. 0 in ["make"] => true // index 0 is a symbol inside the Array object "make" in ["make"] => false // "make" is not a symbol (or property) inside the Array object In some sense, Python's in keyword has more magic built-in, where as with Javascript, you'll want to consider the property you're looking for from the object.

November 12, 2017

Random Permutation

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

September 13, 2017

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.

February 3, 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

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

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

Flip adjacent colors in a 2D matrix

Problem Given a 2D array of black-and-white points and an entry point, flip the color of all points connected to the entry point (including the entry point itself). Input A: 2D boolean array of size greater than \(n\) \times \(m\), where False represents the color black and True represents the color white.

December 5, 2018

Javascript Concepts

Objects new Object() and {} is semantically the same, but the {} is called object literal syntax. To do a deep-copy of an object, use Object.assign(target, src) or in ES6, use the spread syntax. Variables let is a block-level declaration var is a global-level declaration Functions Javascript functions are first-class objects because they can have properties and methods just like any other object.

October 29, 2017

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.

February 18, 2019

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.

February 18, 2019

Python Essentials

Scopes Python has closures, similar to Javascript, since functions are first class objects. But unlike Javascript, there are some subtle gotchas in regards to working with function scopes. nonlocal vs.

April 3, 2019

CNN - Convolutional Neural Networks

Intuition Compared to RNN, CNN tackles a different kind of issue. When working with images or data that has spatial structure, it turns out that the conventional way of converting the input data to a 1D array (a flattened version) produces some lackluster results.

November 23, 2020

Kefir.js - Reactive Javascript

Background Kefir.js is a Reactive Programming library for JavaScript inspired by Bacon.js and RxJS, with focus on high performance and low memory usage. Kefir works with objects called observables. observables could be two things; a stream, or a property (not to be confused with a Javascript object property) Streams A stream is a sequence of events made available over time.

March 13, 2017

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

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

Find a path in a maze from start to finish

Problem Given a 2D array which represents a maze, a start point, and an end point, find a path from the start point to the end point if it exists. Input maze: 2D boolean array of size greater than 1 x 1, where False represents a wall (not traversable) and True represents an empty space (traversable) start: an object with x, y coordinates end: an object with x, y coordinates Approach The key to solving this problem is DFS.

December 4, 2018

How to convert a PPM image to grayscale in C++

What is PPM? PPM is simply an image format that is very easy to work with, for modifying purposes. We'll create this image format from scratch, using C++. PPM Images can be opened with IfranView. Step 1 - The class for PPM image First, let's define a class for this PPM image.

March 24, 2015

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

Stack Memory vs. Heap Memory

... memory in the heap in C/C++. Includes objects that references (or pointers) point to Includes arrays Memory is allocated in non-contiguous blocks, so cache misses are frequent. C

May 28, 2019

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

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.

November 1, 2014

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

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.

November 20, 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

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

DataFrames (a software engineer's perspective)

What is a DataFrame? A 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.

May 2, 2022