Search Results

21 matches found for 'recursion'

Phone Number Mnemonics in Python

... Approach There are various ways to do this, but I think one of the easier approaches is to use recursion and an integer index to keep track of which digit you need to convert. Start by having an empty list.

Recursive multiply function in Python using + and binary shifts

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.

Counting the path of sums

... can be solved by recursively going through each path in a tree and tallying up the sum at each recursion level, checking if the sum matches the target sum. This means that the current sum or the accumulating sum has to be passed down to its recursive calls.

Perfect Squares

... such that it gives us the least numbers to sum. The time complexity here is exponential. The recursion is based off of the following recurrence relation: \( leastSquares = min(f((total - perfSquares[j]), i+1), f(total, i)) \) One optimization is to cache results, using a hash table, and recursively iterate from the smallest perfect square to the biggest perfect square.

Coin Change Denominations

... and instead, choose the next coin at index \(i+1\). Solution With the power of Scala and recursions, we can make a function that calculates the total number of money denominations, given 2 parameters -- the amount of money and the list of allowed coins to use.

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.

Summation with rationals

Given some lower bound a = na/da and upper bound nb/db, write a function that calculates the summation of f(nk/dk), where k is the index, n represents numerator, and d represents denominator. An example: if a =1/2 and b = 4/5, then you should calculate f(1/2)+f(2/3)+f(2/4)+ f(3/4)+ f(3/5)+f(4/5) def sum (f: Rational => Rational)(a: Rational, b: Rational) : Rational = { val k = a val total = new Rational(0, 1) def innerSum (f: Rational => Rational) ( k: Rational, total : Rational) : Rational = { if (a <= k && k <= b && k.

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.

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.

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 .

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.

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.

Git the Essentials

Checkouts and Commits Scenario: I want to check out some branch B git checkout <branch B> Scenario: I want to add some files that I updated and commit them git add -i ... (Add your files interactively) git commit Scenario: I created some brand new files and need to commit them.

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.

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.

Paint adjacent boundaries with distinct colors

... if result is not None: return result # this iteration of the recursion loop did not pass the goal test, so we terminate it return None coloredMap = backtrackingSearch(countries) print "\ncoloredMap = \n\n", coloredMap Update 1: Fixed formatting of code.

Find the maximum min path

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.

Square each element of a Scala list

There are two practical ways to square each element of a list, and return the new list. For example, if we input a List(5, 10), we should have a List(25, 100). Method 1: Pattern Matching def squareList(xs: List[Int]): List[Int] = xs match { case Nil => xs case y :: ys => y * y :: squareList(ys) } If xs is empty, case Nil will trigger, simply returning the list that was passed in to squareList.

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.

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.

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.