Programming Problems: Advanced Algorithms Part 2

Question 1

Given an unordered sequence of numbers between 1..N, with 1 value missing. Find the missing value with O(1) space complexity, and O(n) time complexity.

Answer 1

The sum of numbers between 1..N is equal to n*(n+1)/2.

Iterate over the sequence and add up the numbers. Then subtract it from n*(n+1)/2 and you get the missing number.

Note: Beware of overflow! The data type required should be twice as much in bits as the size of n.

Question 2

Given an unordered sequence. Find the maximum difference between s[i] and s[j], such that i<j.></j.>

<p>Give an O(n) solution.</p>

</j.>

Answer 2

iterate over the array. store the minimum value preceeding s[j] in a variable. At each step update the minimum if necessary. At each step calculate the current value minus the min value. If it is larger than the last maximum then update the maximum.

Question 3

Find the maximum sub submatrix of a given n*n matrix in O(n^3) time.

Answer 3

For each 2 column calculate the sum of rows between them. It results in a 1d array of length n. Find the max subarray in the array. If it is bigger than the current max, update max.