Common Algorithms and Their Complexity
Sorting: Quicksort – O(n logn), O(n^2) worst case Merge sort – O(n logn) Heap sort – O(n logn) Bubble sort – O(n^2) Insertion sort – O(n^2) Selection sort – …
Category: algorithms
Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem (Largest Sum of Non-Adjacent Numbers)
April 15, 2015
algorithms, BFS, Breadth First Search, c / c++, Depth First Search, DFS, Dynamic Programming, dynamic programming, Memoization, python, Recursion
3 Comments
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each …
C++ and Python to Compute the Pascal Triangle
Given an index k, return the k-th row of the Pascal’s triangle. For example, given k = 3, Return . Could you optimize your algorithm to use only O(k) …
Compute the Number of Trailing Zeros for a Factorial in C++
Given an integer n, return the number of trailing zeroes in Factorial N! Your solution should be in logarithmic time complexity. Naive/Bruteforce Solution It is easy to get the …
Greedy Algorithm to Reach the Last Index of the Array
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that …