@rkenmi - Search Results

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.

September 21, 2017

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.

July 26, 2017

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.

June 9, 2017

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.

February 18, 2019

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.

November 1, 2014

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

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.

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

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

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

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

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

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.

May 17, 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

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

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.

December 11, 2014

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.

April 3, 2019

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.

December 8, 2014

Search Results