Amazon Interview Question Software Engineer / Developers
Actually, this was a very naive solution after I thought about it some more. The solution seems now so deceptively obvious and simple that it's actually hard to find because one's tendency is to look for something complex:
for each number x in the array
y = k-x;
if y is in the array, print out x + y = k
if y is not in the array, then it cannot be part of a pair, period.
Since it's only a pair of numbers, you can only have one solution. For example if k = 57, and y = 33, your combination is always going to be 57 - 33 = 24. The pair will always be 24 + 33, and no other way about it.
Now if instead of a pair, it was three numbers, then things get more complicated, but I think the solution would be along similar lines (probably recursive).
Amazon doesn't normally ask more than 2 questions on telephone. Usually one coding and one design. I find it strange they asked you all that.
1 and 2 you may google to find the detail
3) The question is not clear, two or more students may end up having same marks therefore they must be on same rank[this is the assumption i'm going by].
Sol'n a) sort the input and increase the rank as input value increase. Time O(nlogn), space O(1)
Sol'n b) Hash <mark, numStudents> then run a loop from 0 to 100 and hash lookup and assign rank. Time O(n), space O(n)
4) Discussed many times sort then have two index pointing to 0, and n-1, increase/decrease accordingly
<pre lang="" line="1" title="CodeMonkey46984" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey46984" input="yes">
1</pre>
4)#include<stdio.h>
main()
{
int x=1,a[20]={7,7,7,1,1,1,2,2,2,3,3,4,4,4,4},i,j,k=8;
for(i=0;i<20;i++)
{
for(j=0;j<20;j++)
{
if((a[i]+a[j])==k)
{
if(i==j) printf("%d\n",i);
else printf("%d %d\n",i,j);
}
}
}
Could somebody helpme out dis please , i wrote dis code tell me whether it is correct one or not?
The solution is simple and correct. It is exhaustive by nature. you could also simplify this, by integrating the solution that was previously posted:
main()
{
int x=1,a[20]={7,7,7,1,1,1,2,2,2,3,3,4,4,4,4},i,j,k=8;
for(i=0;i<20;i++)
{
possiblePair = k - a[i];
for(j=0;j<20;j++)
{
if(a[j] == possiblePair)
{
printf("%d %d\n",i,j);
break; //if you dont have to find all pairs, just one pair is ok
}
}
}
#include<stdio.h>
#include<conio.h>
void main()
{
int arr[] = {1,7,4,8,2,9,3} , k , n , ctr1 , ctr2 , sum;
n = 7;
k = 10;
clrscr();
printf("the subsets with the sum = k (10)");
for(ctr1 = 0; ctr1<n ; ctr1++)
{
for(ctr2 = ctr1+1 ; ctr2<n ; ctr2++)
{
sum = arr[ctr1]+arr[ctr2];
if(sum==k)
{
printf("arr[%d]+arr[%d] = %d \n", ctr1 , ctr2 , sum );
}
}
}
getch();
}
public static int largestContinuousSum(int[] A){
int maxSum= A[0];
int sum =0;
for(int i:A){
sum= sum+i;
if(sum>maxSum){
maxSum = sum;
}
}
return maxSum;
}
public static void main(String[] args) {
int[] A = { 1, 2, 5, -8, 11, 12, -16, 6, 7, 1, 11 };
System.out.println(largestContinuousSum(A));
}
public class PairSum {
public static void pairSum(int[] A, int k) {
Set<Integer> arraySet = new HashSet<>();
for (int i : A) {
arraySet.add(i);
}
for (int i : arraySet) {
int diff = k - i;
if (i != diff && arraySet.contains(diff)) {
System.out.println("Pair: " + i + "--" + diff);
}
}
}
public static void main(String[] args) {
int[] A = { 1, 2, 5, 8, 11, 12, 16, 6, 7, 1, 11 };
pairSum(A, 13);
}
}
The easiest solution would be to go exhaustively through the array by doing a double loop:
- Anonymous November 24, 2011/*pseudocode*/
int digits[] = {1,2,3,...n}; /*n can be whatever*/
int k = m; /*m can be whatever*/
for (int firstNumberIndex=0; firstNumberIndex < digits.length; firstNumberIndex++)
{
int tempResult = 0;
for(int secondNumberIndex=0; secondNumberIndex < digits.length; secondNumberIndex++)
{
/*My assumption is adding a digit located at an array position to itself
does not count*/
if(!firstNumberIndex == secondNumberIndex)
{
tempResult = digits[firstNumberIndex] + digits[secondNumberIndex];
if(tempResult == k)
{
//print first and second digit
System.out.println(digits[firstNumberIndex] + " plus " + digits[secondNumberIndex] + " equals " + k)
}
tempResult = 0; //resetting to zero out of paranoia. :)
}
}//Close inner loop
} //Close outer loop
I think this would do the job, even though it would be slow. It could be sped up a bit if we have more information such as if negative numbers are allowed, if zeroes are allowed, etc. Then you could have logic to exclude those right off the bat by sorting the array first, getting rid of negatives, zeroes, and any numbers where n >= k depending on what conditions are true.
It could also be sped up if you know whether you need to print out every instance of a pair n+ m or whether it would be sufficient to print it out once and ignore it when you find it again (say you find 1 + 3 equals 4, do you need to print it out every time you find a new 3 in the array?)
If anyone finds a mistake in my pseudo-code, I'd appreciate input if you're reading. :)