Commits

Ivan Savov committed 49280f1

Two new writeups, both inspired by recent intreview questions i had to face

Comments (0)

Files changed (2)

lessons/lesson3--interest-rate-calculations-using-recursion.js

+
+
+Interest calculations
+=====================
+
+One application of functions is to perform vairous complicated (tedious) tasks for us.
+For example a mortgage calculation is a complicated to do by hand,
+but we can make the computer do the calculation for us using `JavaScript`.
+
+
+Definitions
+-----------
+
+Consider a mortgage payment calculation.
+
+    
+    / // n = number of years    # not used
+
+    / // k = number of months
+    / // S = initial sum borrowed
+    / // P = monthrly payment amount 
+    / // I = monthly interest rate (= 1/12-th of the nominal annual percentage rate (I=0.05 for nAPR of 6%)
+    / // Zr(k,S,I,P) = amount owed after k-th payment P on a monthly loan of initial amount S at interest rate I 
+
+    Zr = function (k, S, I, P) {
+       if (k == 0) { return S };
+       return Zr(k-1,S,I,P)*(1+I)-P;
+    }
+
+
+
+Example calculations
+--------------------
+
+For a loan of 1000 the money owed after zero monthsis:
+
+    Zr(0,1000,0.005,100)  // 6% nAPR = 0.005% monthly 
+    1000
+
+After one months has passed, and a payment of 100 has been made:
+
+    Zr(1,1000,0.005,100)  // 6% nAPR = 0.005% monthly 
+    905.00
+    / // the interest for one month was $5 but a payment of $100 cut the sum down a bit
+
+
+After two months, you owe:
+
+    Zr(2,1000,0.005,100)
+    809.5249999999997
+
+
+
+Monthly payment calculation
+---------------------------
+
+Assuming a 25 year mortgage of $315000, we can manually plug different values of 
+the payment until we find the payment amount P which reduces the amount owed to zero
+after 25*12 months.
+
+The monthly payment for a 3% nomian annual percentage rate is $1497.77 
+
+    Zr(25*12,315000,0.0025,1493.76)  // 3% nAPR = 0.0025% monthly 
+    2.514882748763739
+
+The monthly payment for a 4% nomian annual percentage rate is $1662.69 
+
+    I = 0.04/12
+    Zr(25*12,315000, I,1662.69)
+    -2.0323859706841176
+
+The monthly payment for a 5% nomian annual percentage rate is $1841.54
+ 
+    I = 0.05/12             // = 0.004166666666666667
+    Zr(25*12, 315000, I, 1841.54)
+    -4.739123044493454
+
+
+The monthly payment for a 6% nomian annual percentage rate is $2029.55
+
+    I = 0.06/12     //  =  0.005
+    Zr(25*12,315000, I,2029.55)
+    -0.4056236855105908
+
+
+Exercise
+--------
+
+Ajouter condo fees ??  et taxes ville de montreal + taxes scolaires.
+
+
+Third-of-a-million dollar quesion
+---------------------------------
+
+Assuming interest rate goes up to 5%, condo fees + taxes of 300,
+can your rent that condo for 2141.54 par mois pour couvrir les fais.
+

lessons/lesson4--bin-search-in-py.js

+Binary search
+-------------
+Searching an unsorted list of length n is an O(n) procedure.
+Searcing a sorted list is O(log(n)) thanks to binary search.
+
+    array = [ 1, 3, 6, 8, 9, 17, 20, 23, 25, 18, 11, 2 ]
+    array.index(6)     // 2
+
+    
+Consider now a list whose first half is sorted in increasing order
+and whose second half is sorted in decreasing order.
+You want to find the index in the list of a given entry.
+
+Can you write a indexOf function that takes advantage of the
+mountain-peak-sorted nature of the list:
+
+    def getMountainIndexOfBinSearch(array, peak, target):
+        """ Double-binary search-based mountain Index """
+        i=0                                       // idx into array
+        
+        if array[0] == target:                    // edge case 1
+            return 0
+        
+        # first search 
+        left, right = 0, peak
+        while left != right-1:                    // BinSearch loop
+            i = left + int( (right-left)/2 )
+            if array[i] == target: 
+                return i
+            elif target > array[i]:
+                left, right = i, right
+            elif target < array[i]:
+                left, right = left, i
+
+        if array[peak] == target:                 // edge case 2
+            return peak
+                    
+        # second search
+        left, right = peak, len(array)-1          // edge case 3 
+        while left != right-1:                   
+            i = left + int( (right-left)/2 )
+            if array[i] == target: 
+                return i
+            elif target < array[i]:
+                left, right = i, right
+            elif target > array[i]:
+                left, right = left, i
+
+        if array[-1] == target:                   // edge case 4
+            return len(array)-1
+
+    
+Does it work?
+
+    print getMountainIndexOfBinSearch(array, 8, 6)  // 2 
+
+
+You sure?
+
+    def test(size):
+        """ fuzzy test mountain search function w.r.t. list index method """
+        prearray = unique( [randint(size) for i in range(0,size)]   )
+        array = sorted( prearray[0:len(prearray)/2] )
+        array = array + sorted( prearray[len(prearray)/2:-1], reverse=True)
+        peak = argmax(array)
+        for item in array:
+            assert array.index(item) == getMountainIndexOfBinSearch(array, peak, item)
+        print "Seems good"
+     
+    test(10000)         
+    Seems good
+
+
+
+