prepbook
  • Introduction
  • Some common stuff
    • python __repr__
    • HackerRank input tips
  • Data Structures and Algorithms
    • Breadth first search
    • Depth First Search
    • Dijkstra
    • A* Search Algorithm
    • Binary Search
    • python counter
    • Sorting
      • Merge Sort
      • Quick Sort
    • Priority Queue
  • Multiprocessing vs Threading
  • Common Coding
    • Find loop in lin list
    • Maximum sum subarray
  • Coding
    • Valid palindrome
    • Palindrome number
    • Remove duplicates from sorted array
    • Island perimeter
    • Serialize and Deserialize Binary Tree
    • Valid Soduku
    • Word Pattern
    • Word Pattern II
    • Group Anagrams
    • Implement Trie
    • Deep copy list with random node
    • Palindrome Permutation
    • Combination Sum
    • Clone Graph
    • Generate parenthesis
    • Fibonacci Number
    • LRU Cache
    • Merge two sorted arrays in place
    • Hamming Distance
    • Merge K sorted arrays
    • Kth smalles element in BST
    • Kth largest element in an array
    • Remove duplicates from sorted list
    • Power of 2
    • Nested list weight sum
    • SIngle number in a list
    • Factor combinations
    • Delete node from BST
  • hacker Rank
    • Coding
      • print staircase
      • Drawing book
      • Challenge 0
      • Min-Max sum
  • WorkRelatedCoding
    • Rectangle Overlap
  • Python tips
Powered by GitBook
On this page

Was this helpful?

  1. Coding

Fibonacci Number

#!/usr/bin/python
import sys

#/////////////////////////////////////////////////////////////////
# Recursive version - revisits the same computation multiple times
#/////////////////////////////////////////////////////////////////
def fibRecurse(n):
    # Some boundary conditions
    if n < 0:
        print('Cannot find Fibonacci of -ve numbers. Returning -1')
        return -1

    if n < 2:
        return n

    return (fibRecurse(n - 2) + fibRecurse(n - 1))
#/////////////////////////////////////////////////////////////////
# Iterative version - optimal computation. Works on accumulation
#                     and moving forward
#/////////////////////////////////////////////////////////////////
def fibIterative(n):
    #
    if n < 0:
        print('fib of -ve number cannot be found')
        return -1

    if n < 2:
        return n

    a = 1 # (n-1)th element
    b = 0 # (n-2)th element
    for i in xrange(2, n+1):
        c = a + b
        b = a
        a = c

    return a
#////////////////////////////////////////////
# using dynamic programming with memoization
#////////////////////////////////////////////
fibCache = {}
def fibDP(n):

    if n in fibCache:
        return fibCache[n]
    else:
        if n < 2:
            fibCache[n] = n
        else:
            fibCache[n] = fibDP(n-2) + fibDP(n-1)
        return fibCache[n]
if __name__ == "__main__":
    if len(sys.argv) == 2:
        n = int(sys.argv[1])
    else:
        print 'Usage - requires 1 arguement (n): progName n'
        exit(0)

    result = fibRecurse(n)
    print("fibonacci - recursive of: ", n, " is: ", result)
    result = fibIterative(n)
    print("fibonacci - iterative of: ", n, " is: ", result)
    result = fibDP(n)
    print("fibonacci - DP of: ", n, " is: ", result)
PreviousGenerate parenthesisNextLRU Cache

Last updated 5 years ago

Was this helpful?