Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

Here is O(n) solution

public static void SubArraySumModK(int A[], int K)
{
	int sum = 0;
	Map<Integer, ArrayList<Integer>> candidates = new HashMap<Integer, ArrayList<Integer>>();

	for(int i=0; i<A.length; i++)
	{
		sum += A[i];
		if(!candidates.containsKey(sum%K))
			candidates.put(sum%K, new ArrayList<Integer>());

		candidates.get(sum%K).add(i);
	}

	//output all the pairs for each of the key
}

- zahidbuet106 December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You code fails for case like K=3 and arr= {0,1,2};

- Yatin Sharma January 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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;
}

- Akhilesh Pandey October 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

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

- Darida October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

+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 ] ?

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Darida October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

So by design decision, the range you output is ]x, y] . That's cool. Same thing.
:)

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- elber.kam November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- meow November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nishant Kelkar January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

- Anish Tambe October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]]

- Anish Tambe October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For input sequence {1, 1, 1, 1, 5} your code gives the output as {1}.

- Akhilesh Pandey November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ksjeyabarani November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
		
	}

- nishant November 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- Amit October 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain little more about 2nd algorithm.

- KnowledgeSeeker October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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}.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Reviewed own code: Overflow bug for "sum" :)

Exercise: Small change to fix that.

- Urik's twin Cookie Monster (dead now) October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

use modified kadane's algorithm ...
i think best solution ...single scan of array
O(n) solution

- omprakash98527 October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can you please elaborate, and if possible, post the code....

- Akhilesh Pandey October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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);    
    
    }
}

- Mohan October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is already mentioned the sun array should be continuous...

- yogi.rulzz October 27, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More