Maximum contiguous sub-matrix
Find the contiguous 2-dimensional sub-matrix with the maximum sum, in a given 2 dimensional matrix of n elements of signed integer type.
Given an N-dimensional matrix of n elements of signed integer type, find the contiguous sub-matrix with the maximum sum.
Simplified version: Given a 2 dimensional matrix of n elements of signed integer type, find the contiguous 2-dimensional sub-matrix with the maximum sum (see example figure).
Trivia: The simplified 1-dimensional array version of this problem was first posed in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images.
- Completeness of the pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution offered? (25%)
Maximum subarray problem . Wikipedia (accessed Feb. 2011) Improved Algorithms for the K-Maximum Subarray problem . Oxford Journals (accessed Feb. 2011)
Norman, a fellow engineer at Adify, asked me this question during a seven hour final round interview.
Fibonacci Series Dynamic Programming
Return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently without using any FOR or WHILE loops.
Time Complexity of ArrayList Insertion
Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.
Return true if input is a Prime number
You are given n, a positive integer. Return true if n is a prime number, and false if it's not.
- Amin Ariana
- February 2011