"To get a job in machine learning, you must have the programming and mathematical knowledge to create artificial intelligence that is capable of learning new tasks without being explicitly coded. In an interview you may be asked about your experience with pertinent coding languages such as Java and C++ as well as with writing algorithms. The interview will be comprised mainly of technical questions that test your knowledge of the fundamental concepts of machine learning such as data mining and signal processing."
Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this?
It can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming.
Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!?
Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j).