Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Interviewer expected the longest sub-array or just any sub-array?
For finding the longest sub-array whose sum of elements is divisible by 7, we can follow a Breadth First Search approach.
For any array we can have either of two states -:
i) The sum of elements is divisible by 7. So, we just return the array
ii) The sum of elements is not divisible by 7. So we remove either the first or the last element and begin from top.
(1, 2, 3, 4, 5)
(Sum=15, not divisible by 7)
/ \
(1, 2, 3, 4) (2, 3, 4, 5)
(sum=10, not divisible by 7) (Sum=14, divisible, return array)
Below is the working C++ code
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> fun(vector<int> &a);
bool divisible_by_7(vector<int> &v);
int main()
{
vector<int> a;
vector<int> result;
int n;
int temp;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>temp;
a.push_back(temp);
}
result=fun(a);
for(int i=0; i<result.size(); i++)
cout<<result[i]<<" ";
cout<<endl;
return 0;
}
vector<int> fun(vector<int> &a)
{
queue<vector<int> > q;
vector<int> temp;
if(a.size() == 0)
return temp;
q.push(a);
while(!q.empty())
{
temp.clear();
temp=q.front();
if(divisible_by_7(temp))
return temp;
if(temp.size() != 0)
{
temp.erase(temp.begin());
q.push(temp);
temp=q.front();
temp.erase(temp.end() - 1);
q.push(temp);
}
q.pop();
}
return temp;
}
bool divisible_by_7(vector<int> &v)
{
int sum=0;
for(int i=0; i<v.size(); i++)
{
sum=sum+v[i];
}
if(sum%7 == 0)
return true;
return false;
}
So, we want to find sub-set [i, j], such that
( a[i]+a[i+1]+ ... a[j] ) % k = 0
with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:
s[i] = (a[1] + a[2] + ... + a[i]) % k
And we can note that, if there is such [i, j] that we are looking for, then:
s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0
So, for each s[i] == s[j], sum of sub-set [i, j] is divisible by k.
Now we need to find the most appropriate range.
If we are looking for the longest set, then
struct Range
{
int first_position = -1;
int last_position = -1;
void add(int position)
{
if(first_position == -1)
last_position=first_position = position;
else
last_position = position;
}
friend bool operator<(const Range& r1, const Range& r2)
{
int r1_lenght = r1.last_position-r1.first_position;
int r2_lenght = r2.last_position-r2.first_position;
return r1_lenght < r2_lenght ;
}
};
for each modulo of k: we need find first and last position (in sum-array), and select the largest range from them.
Range searchRange[k];
int sum = 0, max_range_id = 0;
for(int i=0; i<n; ++i)
{
sum=(sum+data[i])%k;
searchRange[sum].add(i);
if(searchRange[max_range_id] < searchRange[sum])
max_range_id = sum;
}
Here is working full code: http://ideone.com/VvWSkT
+1 Nice.
Maybe I'm wrong, but do you have an off by one error on finding the real start of the range?
How about handling case of the array [ 0 1 7 7 7 ] ?
sum array will be: 0 1 1 1 1
longest sub-set is from 1 to 4
you can find an explanation by looking closely at the function Range::add
first time we will set both - first && last positions to the current. and the lenght of array will be 0.
then we will set only last position.
s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j])
this does not seem correct statement.
I think it should be:
s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i+1]+...+a[j])
Correct me if I am wrong.
for
s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0
should it be
(s[j]-s[i])%7 == ((a[1]+...+a[j]) - (a[1]+...+a[i]))%7 == (a[i]+...+a[j])%7 == 0
and also need to consider the case when the a[0]%7==0 but that's trivial.
good algorithm
Nice one Darida! +1
From Wikipedia on the properties of the Modulo (%) :
1. (a+b)mod n = ((a mod n) + (b mod n))mod n
2. ((a mod n) + (-a mod n))mod n = 0
This means, for (a+b)mod n to be equal to zero, we need
((a mod n) + (b mod n))mod n = 0
In our case, b is also negative (since we are calculating sums from 1...i, the sum of any numbers from [i,j] as Darida says, is S[j] - S[i]. So here, our a is S[j], our b is -S[i])
But from (2), this can happen only when |b| = |a|
And so, remember that |b| = S[i] and |a| = S[j], we have the amazing result
S[j] = S[i] for any sum of integers in [i. j] modulo n to be equal to zero!
Fascinating math, fascinating result.
Python one liner -
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print([A[i:j] for i in range(len(A)) for j in range(1+i,len(A)) if sum(A[i:j])%7 ==0 ])
O(n^2) solution.
Minor Correction -
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print([A[i:j+1] for i in range(len(A)) for j in range(i,len(A)) if sum(A[i:j+1])%7 ==0 ])
Output -
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6, 7], [2, 3, 4, 5], [2, 3, 4, 5, 6, 7, 8], [3, 4], [3, 4, 5, 6, 7, 8, 9], [4, 5, 6, 7, 8, 9, 10], [5, 6, 7, 8, 9], [6, 7, 8], [7]]
void LongestContinuousDivisible_by7(int *a, int n)
{
if(a==NULL || n<=0)
return;
int i,j,sum=0;
for(i=0;i<n;i++)
sum+=a[i];
i=0;
j=n-1;
while(i<j)
{
sum-=a[i];
i++;
if(sum%7==0)
break;
sum-=a[j];
j--;
if(sum%7==0)
break;
}
for(int k=i;k<=j;k++)
cout<<a[k]<<"\t";
cout<<endl;
}
The below code is a variation to Kadane's algorithm.
maxSumSubArrayDivisibleByNumber(int[], int) - finds the maximum sum in the sub sequence of the array that is divisible by the given number
longestSubArrayWhoseSumDivisibleByNumber(int[], int) - finds the longest subsequence whose sum is divisible by the given number
public class MaximumSubArray {
public static void main(String[] s) {
int a[] = new int[] {-2,-4,-3,5,-2,2,2,-5,4,2,2,3,1,-7,-1, 11};
maxSumSubArrayDivisibleByNumber(a, 7);
longestSubArrayWhoseSumDivisibleByNumber(a, 7);
}
// returns the maximum sub sequence sum that is that is divisible by the given number
public static void maxSumSubArrayDivisibleByNumber(int[] a, int k) {
int max_so_far = a[0];
int max_ending_here = a[0];
int begin = 0;
int end = 0;
int begintemp = 0;
int kbegin = 0;
int kend = 0;
int ksum = 0;
for(int i=0; i<a.length; i++) {
if(max_ending_here < 0) {
max_ending_here = a[i];
begintemp = i;
} else {
max_ending_here = max_ending_here + a[i];
}
if(max_ending_here >= max_so_far) {
max_so_far = max_ending_here;
begin = begintemp;
end = i;
if((max_so_far % k)==0) {
if((end-begin) > (kend-kbegin)) {
kbegin = begin;
kend = end;
}
ksum = max_so_far;
}
}
}
System.out.println("Max sum in subsequence divisible by " + k + " is " + ksum + "\tfrom:" + kbegin + " to:" + kend);
}
public static void longestSubArrayWhoseSumDivisibleByNumber(int[] a, int k) {
int max_so_far = a[0];
int max_ending_here = a[0];
int begin = 0;
int end = 0;
int begintemp = 0;
int kbegin = 0;
int kend = 0;
int ksum = 0;
for(int i=0; i<a.length; i++) {
if(max_ending_here < 0) {
max_ending_here = a[i];
begintemp = i;
} else {
max_ending_here = max_ending_here + a[i];
}
if(max_ending_here >= max_so_far) {
max_so_far = max_ending_here;
begin = begintemp;
end = i;
}
if((max_ending_here % k)==0) {
kbegin = begintemp;
kend = i;
ksum = max_ending_here;
}
}
System.out.println("Longest subsequence sum divisible by " + k + " is " + ksum + "\tfrom:" + kbegin + " to:" + kend);
}
}
The program result:
Max sum in subsequence divisible by 7 is 14 from:3 to:12
Longest subsequence sum divisible by 7 is 7 from:3 to:13
The code below is as follows:
1. for any index i of array, take mod of sum so far i.e from 0 to i
2. if mod = 0, print from 0 to index
3. else search for any index with same value and print no from index + 1 to another index
private static void findAllCombinationOfZero(int[] a) {
getMod(a);
for (int i = 0; i < a.length; i++) {
if(a[i] == 0)
{
for (int k = 0; k <= i;k++){
System.out.print(b[k]+" ");
}
System.out.println();
}
for (int k = i + 1; k < a.length; k++) {
if (a[k] == a[i]) {
for (int l = i + 1; l <= k; l++){
System.out.print(b[l]+" "+"("+l+")"+" ");
}
System.out.println();
}
}
}
}
private static void getMod(int[] a) {
int sumSoFar = 0;
for (int i = 0; i < a.length; i++) {
sumSoFar += a[i];
sumSoFar = sumSoFar % N;
a[i] = sumSoFar;
}
for (int i : a) {
System.out.print(i+ " ");
}
System.out.println();
}
append a 0 at the start of the array,say arr..so arr[0]=0
1.now build a sum matrix such that
sum[i]=arr[0]+arr[1]+...arr[i].
this step takes o(n) time
2. now you need to search 2 elements in sum matrix with diff divisible by 7.Following algos can be used
i)2 loops-naive approach-o(n2) time
ii)hashing--
maintain a hashmap of only 7 elements
insert sum[0]%7 entry into hashmap as 0
hash[sum[0]%7]=0;
now i=1 to n
search for 7-sum[i]%7 in hashmap..if found subset is found
else insert sum[i]%7 entry in hashmap as i
hash[sum[i]%7]=i
this step will take o(n) time.
Hence using 2nd algo,we can do the task in o(n) time and o(n) space(for sum matrix)
bool seen[7];
sum=0;
seen[0]=true;
for(i=0; i < a.length; i++)
{
sum += a[i];
if( seen[sum%7] ) return true; //found
seen[sum%7] = true;
}
return false; //not found
Minor change (a line or two) if you want to return indices of array
struct {bool flag; int index; } seen[7];
sum=0;
seen[0].index=-1, seen[0].flag=true;
for(i=0; i < a.length; i++)
{
sum += a[i];
if( seen[sum%7].flag )
printf("found here a[%d : %d]\n", seen[sum%7].index +1, i), return;
seen[sum%7].flag = true, seen[sum%7].index=i;
}
printf("Not found\n"), return;
Not compiled nor tested.
Probably totally wrong lol.
I don't usually use % with negatives on either side, but I looked up a version of C standard, related to a%b :
" If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined. "
[ from ISO14882:2003(e) is no longer present in ISO14882:2011(e) ]
And we are guaranteed:
" (a/b)*b + a%b == a "
[The earlier statement has to be compared against this guarantee]
So it seems, for example, -9%4 can return -1 or 3 depending on compiler.
So we would need to create our own "mod7" wrap around %7 to make sure it always gives something in range 0, ..., 6 on different compilers:
unsigned int mod7(int x)
{
return (r = x%7)>=0 ? r : r+7 ;
}
Now which version of the problem are we solving?
1) Test for existence true/false
2) Test and return any evidence of existence
3) Test and find longest subarray with that property?
1) to 2) to 3) are only incremental modifications of code.
unsigned int mod7(int x)
{
int r;
return (r = x%7)>=0 ? r : r+7 ;
}
void findlongest7(int a[])
{
struct { bool seen; int first; int last; } h[7]; //special "direct" hash
int i, sum=0, p; //p: prefix sum mod down to {0,...,6}
int maxp, maxlen; //used in 2nd for loop
h[0].seen=true, h[0].first=-1;
for(i=0; i<a.length; i++) {
sum+=a[i], p=mod7(sum);
if(h[p].seen) h[p].last=i; //seen before, current is last seen
else h[p].seen=true, h[p].first=i; //seen for first time
}
//find max. len. subarray (only ~C*7, not O(N))
maxlen=0, maxp=-1;
for(i=0; i<7; i++)
if(h[i].seen && (h[i].last - h[i].first) > maxlen )
maxp=i, maxlen=(h[i].last-h[i].first);
//results announced
if(maxp==-1) { printf("No such subarray found\n"); return; }
printf("Subarray of maximal length %d found at [%d : %d]",
maxlen, h[maxp].first+1, h[maxp].last);
}
How it works:
**) define s[i] as prefix sum of array <= index i
If a subarray from a[x:y] has sum divisible by 7, then
sum(a[x:y]) = s[y] - s[x-1] is divisible by 7
But a[x:y] is divisible by 7 means exactly that mod7(sum(a[x:y]))==0
Translate it onto above equation:
0== mod7( sum(a[x:y]) ) = mod7( s[y] - s[x-1] )
= mod7( s[y] ) - mod7( s[x-1] ) == 0
last line true if and only if (take to other side)
mod7( s[y] ) == mod7( s[x-1] )
So we do not have to care about prefix sums, but only prefix sums mod7 (i.e., "p" in the code above). This makes it easy, because there are only 7 possible values for mod7_prefix_sums, in {0,...,6}.
use modified kadane's algorithm ...
i think best solution ...single scan of array
O(n) solution
public class Seven {
/**
* @param args the command line arguments
*/
public void Seperate(int b[][]){
int c = 0;
String sr = "";
for(int i = 0;i<b.length;i++ ){
for(int j =0;j<b[i].length;j++){
c = c+b[i][j];
sr = sr+b[i][j];
}
if(c%7 == 0){
System.out.println(sr+" = "+c);
}else if(c%7 != 0){
// second level
int m =0;
String sr1 = "";
for(int x=1;x<sr.length();x++){
m=m+Integer.parseInt(sr.charAt(x)+"");
sr1=sr1+sr.charAt(x);
}
if (m%7 == 0){
System.out.println(sr1+" = "+m);
}else if(m%7 != 0){
m = 0;
sr1 = "";
for(int y=0;y<sr.length()-1;y++){
m=m+Integer.parseInt(sr.charAt(y)+"");
sr1=sr1+sr.charAt(y);
}
if(m%7 == 0){
System.out.println(sr1+" = "+m);
}
}
}
sr = "";
c=0;
}
}
public static void main(String[] args) {
// TODO code application logic here
int a[][] = {{1,2,3,4,5},{1,5,5,9,1},{7,8,9,1,2},{4,4,4,1,1},{2,3,4,5,6},{8,9,1,9,1}};
Seven sv = new Seven();
sv.Seperate(a);
}
}
Here is O(n) solution
- zahidbuet106 December 16, 2013