second algorithm mock interview

second algorithm mock interview

Given a number "n", find the least number of perfect square numbers sum needed to get "n" 

Example: 
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1) 
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

keywords:
given number n, 

ask: least number, each number is perfect square
sum = summ(number)

example: 12, 4 + 4 + 4, return 3
  integer        1, 2 ,3, 4, ...
  perfect square 1, 4, 9, 16, ...
  
                 1, 4, 
                 1  2, 3, 4
  given number n -> 17, 1 -> 16 
  
  minimum number -> greedy -> coin change 
  dynamic programming -> 
  
  1, 4, 
  
  n = 12, return 3 
  dp[n]
  
  dp[0] = 0
  dp[1] = 1
  dp[2] = 1 + 1 = 2 
  ..
  dp[n] = ...
  
  dp[n] = 1 + min( dp[n - 1 * 1], dp[n - 4], dp[n-9], ..., dp[n - perfectSquare[i]] -> optimal solution 
                  
                  dp[n] = 1 + dp[n - 1];
                  
                  for i = 1 to sqrtn + 1  // 
                  {
                     dp[n]  = min( dp[n] , 1 + dp[n - i * i])
                  }                  
                
                  // dp[n] is ready
              Time complexity: 1 + (1 to N sqrt)    
              given number = 16, 4
                upper bound: 1 + 2 + 3 + 4  = n(n+1), n is square root of given number 
                
  n -> maximum 
  
the interviewer: 

 1^0.5 + 2^0.5 + ... + n^0.5 < n * n^0.5 = n^1.5
 
 7:45am - 9:33 am -> 

	dp[i] dp[j] i > j
  
  // dp[i] = min(1 + dp[i-j^2]) for j^2 <= i