Search Results

40 matches found for 'array'

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

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

... nice trick for iterating through neighbors of a block (horizontal, vertical, diagonal) Create an array of pairs that represents coordinates: coords = [(0, -1), (-1, 0), (1, 0), (0, 1), (-1, -1), (1, 1), (-1, 1), (1, -1)] Iterate through each coordinate Add the current indices to the coordinates to get the row and column that you're considering Check the validity of the row and column variables: for c in coords: row, col = i + c[0], j + c[1] if 0 <= row < len(board) and 0 <= col < len(board[0]): neighbors += board[row][col] If we need to mutate the original 2D array but somehow need to keep track of the old state of the 2D array, consider changing the data in the 2D array to signify state transitions temporarily.

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.

April 13, 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

Next Permutation

... force solution is to generate all permutations of nums and sort all of them, and retrieve the array that is sorted right after nums. This can easily be about \(n!\) time and space complexity, so this is not the ideal solution.

February 17, 2019

Rotate a 2D Matrix

... var n = jsav.ds.matrix([[6, 3, 0], [7, 4, 1], [8, 5, 2]]); Problem Given a 2D array, rotate the array by 90 degrees. Input A: 2D array of size greater than \(n\) \times \(m\) \(n\geq0, m\geq0\) Approach This is a very commonly asked problem, with a conceptual approach that is easy to visualize but difficult to implement in code.

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

... to somehow mark the future numbers as not prime? We can implement this by having a boolean array flag, which will cost us a bit more in space complexity, but save us a good deal of performance in time complexity.

October 5, 2017

Algorithm Interview Problems

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

... Intervals [1,4] and [4,5] are considered overlapping. Input intervals - an array of Interval objects # Definition for an interval. # class Interval: # def __init__(self, s=0, e=0): # self.

February 13, 2019

Longest Substring Without Repeating Characters

... string Approach The brute force approach is to have double for-loops and convert each sub-array into a set, recording the count of the set each time whenever we find a greater count.

February 21, 2019

Javascript Essentials

... call immediately with another this reference. apply is the same as call, except that it takes an array of arguments as a parameter. let vs var let is a block-level declaration, meaning that it is not accessible by anything outside the block scope.

November 12, 2017

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.

September 13, 2017

Build a Trie in Python

... 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. Build a trie. Input A class Trie, with an empty constructor and three empty methods insert(word) search(word) startsWith(prefix): Assume that all word inputs are lowercase alphabets Approach The key to building a trie is to define a class that has a container which can house up to 26 keys (1 for each lowercase alphabet).

February 3, 2019

Topological Sorting

... not give you nodes in topological ordering. You have to modify DFS so that you push nodes into an array when they have no neighbors left (leaf nodes). This ensures that the children gets added before the parent, which if done recursively, will present you with a list of nodes in topological order.

March 6, 2021

Bloom Filter

... functions to store values and to verify if a value exists. Conceptually, they use an internal array to store values into indices and to check indices against. As a whole, they are useful for proving two things: It checks if something is not there, guaranteed.

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

... args) First argument takes the object that should be treated as this. Second argument is an array of arguments. Invokes the function right away. constructor.call(o, [arg1, arg2, .

October 29, 2017

Unique Permutations

... brute force approach is to generate all permutations of \(nums\) and store them into an array. After storing all of the permutations, delete the duplicate permutations. This is a \(O(n!)\) solution, with very expensive space usage.

February 18, 2019

Perfect Squares

... that is, a bottom-up solution. In this optimization, instead of opting for recursion, we use a 2D array to pre-compute values, and use the recurrence relation formula above as the basis to populate the entire 2D array.

February 18, 2019

Python Essentials

... machine running the Python code. Duck Typing TODO Data Structures Empty array list = [] Array with values list = [1, 2, 3] Empty hash map hashmap = {} Hash map with values hashmap = {'a': 'b'} Empty set s = set() Set with values s = set([1, 2, 3]) Min heap import heapq q = [] heapq.

April 3, 2019

CNN - Convolutional Neural Networks

... 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. Intuitively this makes sense, since certain properties of the 2D data are lost when flattening it into a 1D array.

November 23, 2020

Kefir.js - Reactive Javascript

... stream is a sequence of events made available over time. In other words, it can be seen as an array of events. Each index in this array describes a point in time.

March 13, 2017

B-Trees vs. LSM Trees

... about 4 KB in size, and have key value pairs sorted by the key. A single B-Tree node is like an array with references to a page range. The max. number of references in the array are known as the branching factor.

March 14, 2018

Java Essentials

... put("B", "1"); }}; Lambda Functions WIP Data Structures Empty array ArrayList<T> list = new ArrayList<>(); Array with values ArrayList<Integer> list = new ArrayList<>(Arrays.

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

... ignore newline inputStream.read(img.threeChan, img.width * img.height * 3); //Read data into array } Step 3 - The grayscale function The way the grayscale function works is simple enough.

March 24, 2015

Merge k sorted linked lists

... 2->6 ] Output: 1->1->2->3->4->4->5->6 Input lists - an array of linked list pointers # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.

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

... see, after 3 iterations, both pointers will point to the same node. Solution def rotate_2d_array(A): for j in range(0, len(A) // 2): for i in range(j, len(A) - 1 - j): old = A[j][i] A[i][~j], old = old, A[i][~j] A[~j][~i], old = old, A[~j][~i] A[~i][j], old = old, A[~i][j] A[j][i] = old return A # Note that this function returns a boolean def has_cycle(head): slow = fast = head while slow and slow.

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

... so no `parent` per se parent[node] = None dfs(parent, node) Inputs: nodes: An array (or list) of vertices Strategy: dfs-top is a function that starts the entire process of DFS in a graph.

May 7, 2017

Design Concepts

... based storage (MongoDB) or key-value stores (DynamoDB). Key-Value Stores: Data is stored in an array of key-value pairs. The ‘key’ is an attribute name which is linked to a ‘value’.

November 20, 2019

Queue Reconstruction by Height

... [7,0], [5,2], [6,1], [4,4], [7,1]] Notes: The k value represents the index of the output array for some of the pairs. For example, [5,2] is at index 2, [5,0] is at index 0, [4,4] is at index 4.

January 27, 2019

A primer on MapReduce

... ff := func(r rune) bool { return !unicode.IsLetter(r) } // split contents into an array of words. words := strings.FieldsFunc(contents, ff) kva := []mr.KeyValue{} for _, w := range words { kv := mr.

July 11, 2020

DataFrames (a software engineer's perspective)

... one type of metadata would be the column name. In comparison, a traditional 2-dimensional array does not contain column or row specific metadata. DataFrames are quite helpful in this regard, but the additional metadata also means more memory overhead.

May 2, 2022