Walmart Labs Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
This should be an extended form to find sum of two equal to some specified value.
1> Sort the array in ascend order.
2> Beginning from the end of the list, pick each number, as P1
3> from the rest of the numbers in the array try to find P2+P3 = -P1, which has O(n) complexity.
4> If find one in 3>, terminate the search.
Worst case complexity: O(n*n).
See the solution from @Gohawks to see how to solve P2+P3=n on a sorted list in O(n) time. You start with P2 as the min and P3 as the max, and then each iteration you either increment P2 or decrement P3, depending on whether P2+P3 is too small or too big, respectively. The magic here is that once P2+P3 >= n, you can stop finding pairs for P3, since all the remaining P candidates will be greater than P2 by virtue of the list being sorted. This is what prevents the inner loop of this algorithm from being N-squared.
List<int> array = new List<int>() { -7, -3, 2, 10, 3, 4, 6, 7 };
public void FindNumbers()
{
array.Sort();
for (int i = array.Count - 1; i >= 0; i--)
{
int number = array[i];
int signNumber = Math.Sign(number);
int j = 0;
while (Math.Sign(array[j]) * -1 == signNumber && j < array.Count)
{
int k = j + 1;
while (Math.Sign(array[k]) * -1 == signNumber && k < array.Count)
{
if (Math.Abs(array[j] + array[k]) == number)
{
Console.WriteLine("Found " + array[j] + " " + array[k] + " " + number);
Console.Read();
return;
}
k++;
}
j++;
}
}
Console.Write("Not found");
Console.Read();
return;
}
Further, the number of iterations can be reduced by having few checks:
1. If the large number is positive, the other 2 must be negative and the vice versa is also true
I don't know of any obvious way to do this faster than N squared time. To do it in N squared time, first create a reverse mapping of numbers to the index(es) of the array containing that number. Then do an N-squared pass on pairs of numbers, take their sum, then look in the reverse mapping to find the index of the additive inverse of the pair's sum.
You can prune the outer edges of the list by finding the most negative number and most positive number (in linear time), and then during your N-squared pass exclude numbers on the other side of the zero that have double the magnitude. For example, if your largest positive number is 6, then you can immediately reject -13 as being part of the solution, since you'd need at least one number > 6.5 to get back to zero.
One has to rule out all positive and all negative numbers. Then, sort the array O(log n). Now, pick the highest number P1. Then, scroll down the array finding a value with magnitude less than -P1; call it P2. Now, compute P3=P1+P2. Then, quick search for P3 O(log n). Repeatedly pick P1 until one runs out of positive numbers or finds P3.
static void Main(string[] args)
{
// first sort A (left out here)
int[] A = new int[] { -3, -2, 0, 2, 4 };
for (int i = 0; i < A.Length; i++)
{
int j = i+1; //start where i is
int k = A.Length - 1; // start at the end of array
while (k >= j)
{
if (A[i] + A[k] + A[j] == 0)
{
Console.WriteLine("{0}, {1}, {2}", A[i], A[j], A[k]);
return;
}
// no match.
// if sum is too big, decrement k
// if sum is too small, increment j
if (A[i] + A[j] + A[k] > 0) k--;
else j++;
}
}
Console.WriteLine("not found");
}
public class ThreeNumSum {
public static boolean areThreeNumPresent(int[] arr, int sum) {
int len = arr.length;
Arrays.sort(arr);
for(int i=0;i<len - 2;i++) {
int j = i + 1;
int m = len-1;
while(j < m) {
if(arr[i] + arr[j] + arr[m] == sum) {
return true;
} else if (arr[i] + arr[j] + arr[m] < sum) {
j++;
} else if (arr[i] + arr[j] + arr[m] > sum) {
m--;
}
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {3,5,2,7,15,3};
int sum = 25;
if(areThreeNumPresent(arr,sum)){
System.out.println("Elements are present");
} else {
System.out.println("Elements are not present");
}
}
}
public class ThreeNumSum {
public static boolean areThreeNumPresent(int[] arr, int sum) {
int len = arr.length;
Arrays.sort(arr);
for(int i=0;i<len - 2;i++) {
int j = i + 1;
int m = len-1;
while(j < m) {
if(arr[i] + arr[j] + arr[m] == sum) {
return true;
} else if (arr[i] + arr[j] + arr[m] < sum) {
j++;
} else if (arr[i] + arr[j] + arr[m] > sum) {
m--;
}
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {3,5,2,7,15,3};
int sum = 25;
if(areThreeNumPresent(arr,sum)){
System.out.println("Elements are present");
} else {
System.out.println("Elements are not present");
}
}
}
This almost gives the requried result.
import java.util.Arrays;
public class FindSumIsZeroFromThreeArrayElements {
public static void main(String[] args) {
int [] array = new int[] {-7, -3, 2, 10, 3, 4, 6, 7,0};
Arrays.sort(array);
System.out.println("Sorted Array Elements : ");
for (int i = 0 ; i < array.length ; i++) {
System.out.print(array[i] + " ,");
}
System.out.println("\n\nSum Of Zero from three array elements : ");
isSumZero(array);
}
public static void isSumZero(int[] array){
for (int i = 0; i < array.length; i++){
int iter = i + 1;
int reviter = array.length - 1;
int tmp = 0;
while ( reviter >= 0 && iter < array.length){
tmp = array[iter] + array[reviter] + array[i];
if( tmp > 0){
reviter--;
}
else if( tmp < 0) {
iter++;
}
else {
System.out.println(array[i] + ", "+ array[iter] +", "+ array[reviter] );
break;
}
}
}
}
}
Execution Result:
---------------------------
Sorted Array Elements :
-7 ,-3 ,0 ,2 ,3 ,4 ,6 ,7 ,10 ,
Sum Of Zero from three array elements :
-7, -3, 10
-3, 0, 3
0, 3, -3
3, 4, -7
private void checkArrayAndCalculateSmartForce(int[] numbersArray) {
Set<Integer> numbersSet = new HashSet<Integer>();
for(int digits:numbersArray) {
numbersSet.add(digits);
}
Integer[] uniqueNumbersArray = numbersSet.toArray(new Integer[0]);
boolean numberFound=false;
int firstNumber=0, secondNumber=1, thirdNumber=2, total=0,loopCounter=3;
for(firstNumber=0;firstNumber<uniqueNumbersArray.length;firstNumber++,loopCounter++) {
for(secondNumber=1;secondNumber<uniqueNumbersArray.length;secondNumber++,loopCounter++) {
for(thirdNumber=2;thirdNumber<uniqueNumbersArray.length;thirdNumber++,loopCounter++) {
total=uniqueNumbersArray[firstNumber]+uniqueNumbersArray[secondNumber]+uniqueNumbersArray[thirdNumber];
if(total ==0){
System.out.println("1st."+uniqueNumbersArray[firstNumber]);
System.out.println("2nd."+uniqueNumbersArray[secondNumber]);
System.out.println("3rd."+uniqueNumbersArray[thirdNumber]);
numberFound=true;
break;
}
}
if(numberFound) break;
}
if(numberFound) {
System.out.println("loop ran for "+loopCounter);
break;
}
}
}
Complexity: n logn + nlogn = nlogn
1- Sort array (nlo1g n)
2- start from both ends low and high,
sort(a);
int low =0,high = a.Length-1;
while(low<high)
{
int s = low + high;
if(BinarySearch(low,high,-s))
print(low,high,-s);
if(sum > 0)
high--;
else
low++;
}
print("elements not found");
public class ThreeSumZero {
/**
* @param args
*/
public static void main(String[] args) {
int[] A = new int[] { -3, -2, 1, 2, 4 };
HashMap<Integer,Integer> allVal=new HashMap<Integer,Integer>();
for (int i = 0; i < A.length; i++) {
allVal.put(Integer.valueOf(A[i]),Integer.valueOf(i));
}
for (int i = 0,j=1; i < A.length-1; i++) {
int temp= -A[i]-A[j];
if(allVal.containsKey(Integer.valueOf(temp)) )
{
int idx= allVal.get(Integer.valueOf(temp));
if ( idx!=i&&idx !=j)
System.out.println("Locations form threesum zero i,j,k :"+i+" :"+j+" :"+allVal.get(Integer.valueOf(temp)) );
}
j++;
}
}
}
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class CareerCup {
public static void main(String[] args) {
int sum=0;
int a,b,c;
int[] arr=new int[]{-5,3,2,5,0,8,9};
List<Integer>list = new LinkedList<Integer>();
Set<String>set = new TreeSet<String>();
for(int i=0;i<arr.length;i++)
{
list.add(arr[i]);
}
Collections.sort(list);
System.out.println(list);
for(int i=0;i<arr.length;i++)
{
for(int j=1;j<arr.length;j++)
{
a=list.get(i);
b=list.get(j);
sum=a+b;
if(list.contains(-sum))
{
if((-sum>a)&&(-sum>b))
{
set.add(a+" "+b+" "+(-sum));
}
else if((-sum<a)&&(-sum>b))
{
set.add(+b+" "+(-sum)+" "+a);
}
else if((b>-sum)&&(a>b))
{
set.add((-sum)+" "+b+" "+a);
}
}
}
}
System.out.println("The values the give a sum of zero are:"+set);
}
}
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class CareerCup {
public static void main(String[] args) {
int sum=0;
int a,b,c;
int[] arr=new int[]{-5,3,2,5,0,8,9};
List<Integer>list = new LinkedList<Integer>();
Set<String>set = new TreeSet<String>();
for(int i=0;i<arr.length;i++)
{
list.add(arr[i]);
}
Collections.sort(list);
System.out.println(list);
for(int i=0;i<arr.length;i++)
{
for(int j=1;j<arr.length;j++)
{
a=list.get(i);
b=list.get(j);
sum=a+b;
if(list.contains(-sum))
{
if((-sum>a)&&(-sum>b))
{
set.add(a+" "+b+" "+(-sum));
}
else if((-sum<a)&&(-sum>b))
{
set.add(+b+" "+(-sum)+" "+a);
}
else if((b>-sum)&&(a>b))
{
set.add((-sum)+" "+b+" "+a);
}
}
}
}
System.out.println("The values the give a sum of zero are:"+set);
}
}
Repost with formatting
- Gohawks March 16, 2013static void Main(string[] args) { // first sort A (left out here) //int[] A = new int[] { -2, 0, 4, 5, 6 }; int[] A = new int[] { -3, -2, 0, 2, 4 }; for (int i = 0; i < A.Length; i++) { int j = i+1; //start where i is int k = A.Length - 1; // start at the end of array while (k >= j) { if (A[i] + A[k] + A[j] == 0) { Console.WriteLine("{0}, {1}, {2}", A[i], A[j], A[k]); return; } // no match. // if sum is too big, decrement k // if sum is too small, increment j if (A[i] + A[j] + A[k] > 0) k--; else j++; } } Console.WriteLine("not found"); }