[CareerCup][Google Interview] Given two arrays A & B of length l - chkkch - 博客园
Given two arrays A & B of length l, containing non negative integers, such that the sum of integers in A is the same as sum of integers in B.( The numbers need not be the same in both the arrays.)
Now if you start with an index 'k' in each array and do the following summation, SUMMATION (Ak-Bk), where Ak is the value at index k of array A, and Bk is the value at index k of array B, where 'k' increments and wraps back all the way to k-1, the final sum value will be zero.
Question: Find a suitable 'k' such that during any point in the summation, SUMMATION(Ak-Bk) is always non negative. Find such a 'k' in O(n) time.
http://www.careercup.com/question?id=6360675
Read full article from [CareerCup][Google Interview] Given two arrays A & B of length l - chkkch - 博客园
Given two arrays A & B of length l, containing non negative integers, such that the sum of integers in A is the same as sum of integers in B.( The numbers need not be the same in both the arrays.)
Now if you start with an index 'k' in each array and do the following summation, SUMMATION (Ak-Bk), where Ak is the value at index k of array A, and Bk is the value at index k of array B, where 'k' increments and wraps back all the way to k-1, the final sum value will be zero.
Question: Find a suitable 'k' such that during any point in the summation, SUMMATION(Ak-Bk) is always non negative. Find such a 'k' in O(n) time.
http://www.careercup.com/question?id=6360675
Read full article from [CareerCup][Google Interview] Given two arrays A & B of length l - chkkch - 博客园