Search Results

31 matches found for 'iterative'

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 .

December 31, 2018

Forall and Exists in Scala

def forall(s: Set, p: Int => Boolean): Boolean = { def iter(a: Int): Boolean = { if (contains(s, a) && !p(a)) false // If the predicate condition fails, return false and exit loop (all values don't satisfy the condition).

November 4, 2014

Buy and Sell Two Stocks

... 290, 280, 315}\), where the number represents the price, lets find the running profit in both iterative styles. Forward iteration: \({0, 5, 5, 10, 30, 30, 55}\) Backwards iteration: \({55, 55, 55, 45, 35, 35, 0}\)* *In the backwards iteration, we start at the last element, set it as the max_so_far and iterate the array to the left.

December 10, 2018

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

Javascript Essentials

Hoisting Hoisting is JavaScript's default behavior of moving declarations to the top. Given the following Javascript code, what is the expected output, and why? fcn2(); fcn1(); function fcn2(){ alert("hi"); } var fcn1 = function(){ alert("hey") } The expected output is a pop up alert that says "hi", followed by an error that fcn1 isn't defined.

November 12, 2017

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

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

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

Build a Trie in Python

... however, is faster in the long-run albeit it being trickier to write. Solution This is an iterative solution of the above approach. ord is used to retrieve the ordinal number of the ASCII characters and it is subtracted with the offset to get the indices 0-25, with 0 = 'a', 1 = 'b', and so on.

February 3, 2019

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

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

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

... since this is very heavy in space-complexity. Recursive calls will take up more space than iterative solutions (due to the call stack) and creating new sub-arrays inside each recursive call will take up even more space.

January 8, 2019

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

December 11, 2014

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.

September 26, 2017

4 Line Depth-first Search

... ways to implement DFS. For example, you can actually make use of a stack data structure, and use iterative code instead of recursive code. The entirety of DFS could also be implemented in one function, rather than splitting its logic into two like I have done here.

May 7, 2017

Python String Tricks - Performance considerations

If a string is changed to become bigger, consider trying to find the maximum size of the final string early on in a quick pass (strive for \(O(n)\)) Consider working from the tail of the string and iterating backwards if, say, 1 character needs to be replaced with 2.

September 17, 2017

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.

September 24, 2017

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

Phone Number Mnemonics in Python

... to come up with permutations of strings or elements. Not necessarily because of the performance (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.

September 21, 2017

Machine Learning Basics

... which is always a good thing. The basic idea is that it is used to minimize some function by iteratively moving in the direction of the steepest descent. It uses calculus and derivatives to find a negative gradient, with the output being coordinates for a new point.

January 5, 2020

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

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

Rotate a 2D Matrix

... optimization for this problem is to just reduce the loop range by half as the square to process iteratively gets smaller and smaller until it reaches the middle. This part however is easier than the actual rotation algorithm itself.

December 7, 2018

Intro to Python Lambda

Lambdas are simply anonymous functions for Python. We often don't want to write a whole new function with a name if the function itself only consists of one line of code. It is tedious, even though it might be less scary to see.

October 22, 2014

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.

October 28, 2018

AWS and MLOps

Machine Learning Development Lifecycle The lifecycle of the machine learning development process often follows these steps: 1. Data Collection In this step, we fetch data from various sources. Common examples include a data lake, a data catalog, or streaming data (like Kafka, Kinesis).

May 18, 2024

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

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

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.

January 30, 2021

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

Composite Pattern

The Composition design pattern helps you unify individual objects and nested objects. Here is one use case for the composition design pattern. Meet Frank A man named F. Frank decides to write an autobiography of himself.

May 15, 2017