## Zillow Microsoft Interview Question for Software Engineer / Developers

• 0

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

Sort the array

Two pointer - one to the begining and the other to the end of the array.

Compare the values pointed by the pointers untill the pointers collide
If the sum is lesser than m then increment the left pointer by one
If the sum is greater than m then decrement the right pointer by one
If the sum is equal to m then return "YES"

Comment hidden because of low score. Click to expand.
0

If you are sorting the array, why don't you just use binary search in the rest of the array(elements ahead) for each element until you come across an element that is greater than the requited target itself.
Another stopping criteria you can use is when the first element in the rest of the array is greater than target-current element

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

For all the geniuses who were happy with hash table and two pointer soln. THINK TWICE....

i/p array => 2,2,2
sum => 4

By Hash method you say 2 pairs, ACTUAL ANSWER 3 pairs [0,1][1,2] [0,2]

Comment hidden because of low score. Click to expand.
0

In your case, the integers at the two ends are equal. Since it's a sorted array, if the integers at the ends are equal, so are the ones in between. So all you need to do is add an extra condition to see if the two end values being compared are equal. if that is so and if their sum is equal to the required sum then you will return all pairs possible in between the two ends.

Comment hidden because of low score. Click to expand.
0

Not sure why a hashtable wont work in your situation. The hashtable can be
key: the number
value: count

As you iterate through the array, check pair number (sum - num) against the hashtable, if found, then take the count and print the current number, and pair number however amount the count is in the hashtable.

So in your example, it'll print out the pairs (2,2) (2,2) (2,2) which is correct

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

Ask the interviewer if the values are in a particular range say 1-n. If yes, use an array of size n to implement a simple hash and u can have the solution in O(n);

Also we can improve the solution given by KB, you need to check the who array if there are values in the array which are greater than m then we can simply disregard that part of the array. This is worthwhile if we know that the range is random and that there could be a lot of values which are greater than m. We can find the point till which to use the array using binary search.

Comment hidden because of low score. Click to expand.
0

Actually, removing larger than 'm' wouldnot work, as sum could mean involving a negative number as well

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

Thought that I would take a shot at hash version.
I am simplified the sample a bit, but it seems to be working fine !

int main()
{
int arr={5,7,1,2,3,4,6,8};
int count = 8;
int sum = 10;
int hash;
int i=0;
// generate hash range 1-10
for(i=0;i <10;i++)
hash[i] = 0;

for(i=0; i< count; i++)
hash[arr[i]] = 1;

for(i=0; i<= sum/2; i++)
if(hash[i])
if(hash[sum-i])
printf("\nFound %d-%d ", i, sum-i);

return(0);
}

my 2 cents ...

Comment hidden because of low score. Click to expand.
0

Rakesh u r code will not give a combination more than 2 numbers for example for this mentioned question pairs may be [7,1,2],[5,3,2] etc etc .

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

Rakesh , You could keep a running check instead of computing the entire hash table initially.

``````while (i<10) {if (hash[sum - arr[i]] > 0) return 1;
else hash[arr[i]]++ ;``````

And your code wont work for some cases say, int arr = {5,0,0,...}. Also what if I give a value in the arr equal to 11. Hash out of bounds. Please check your code before submitting.

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

I would sort the array first. Then I would have one pointer at the start of the array (the smallest element) and one at the end of the array (the largest element)If the sum of the two integers is less than the required sum, you can get rid of the the first array element because it will be too small to add up to the sum with any of the other array elements. If the sum is too big, you can get rid of the last array element. If the sum matches the sum you are trying to acheive, store the two integers in the seperate data structure. Assuming there are no repeats in the array, you can now get rid of both the first and last element in the array. Keep working your way in from both ends of the array until you reach the center. Once the sort is done, the finding of pairs would be done in O(n) time.

If there are repeats in the array, you would have to do an extra check before you get rid of elements from the array, but otherwise it would be similar.

Comment hidden because of low score. Click to expand.
0

Sorting will add more complexity to the problem!! Better to clarify with interviewer if this is sorted or not!!

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

cant we do ti this way?

S=sum
for ( i =0;i<size of array,i++)
{
k=Array[i]
T=S-K
if(Binary search(T,Array))
if(pair(K,T) not in the datastructure)
enter pair(K,T) in datastructure

}

Comment hidden because of low score. Click to expand.
0

You can do it this way too, but in this case there will be sorting of the array required (because binary search works on sorted input). Average case for an efficient sorting algorithm would be O(nlogn). Also the binary search operation (logn) in the loop (n times) would be of complexity O(nlogn). So total time complexity - O(nlogn + nlogn). Whereas in the previous example the complexity would be O(nlogn + n).

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

Create a bit stream of length= largest element
This would take O(n).
Now for each element in the array
y = sum-element.
check if yth bit in the bit stream is true
then print the element
else
set i th bit = true where i = value of the element.

this would take O(n).

--Tara
set the bit no. = value of the element as true.

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

One more solution to this problem.
suppose there are two no. a and b whose sum = a+b.
For a given sum if a> (a+b)/2 then b<(a+b)/2.
You can prove this inequality easily.
Now there are three kind of numbers.
<(a+b)/2 | >=(a+b)/2 | >(a+b)

if A[i]< (a+b)/2 then paired number A[j]>(a+b)/2 and a[j] can't fall into >(a+b).
suppose there are l number < (a+b)/2, m numbers >= (a+b)/2 and n numbers are >(a+b).

Assuming no space constraints.
create another array with the above conditions.
that will take O(l+m+n) time.
sort elements < (a+b)/2 --- O(l.log(l))
sort numbers > (a+b)/2 but < (a+b)/2---O(m.log(m)).

now keep two indices i and j
for( i=0,j=l+m;i<l && j>l;)
if(A[i]+A[j]>a+b) j--;
else if(A[i]+A[j]<a+b) i++;
else
print A[i], A[j];
this will take
O(l+m);

total complexity = O(l+m+n) + O(l.log(l)) + O(m.log(m)) + O(l+m);

Analysis of algo.
case 1. l~m and n<<l,m;
complexity = O(2l) + 2O(l.log(l)) + O(2l);
~ O(l.log(l))
or in general
O(nlogn).

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

yup....I think, hashing would me right thing to do:)

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

His can be done in O(n). Each time you look at the number "num" in the list, search the hash table to find sum - num. If its there, you found the pair. In any case, insert this number in the hash. By the time you complete the pass to the unsorted list, you will have all the pairs. This solution assumes that search/insert into hash table is O(1) in which case total complexity is O(n) since we are only doing one pass to the input list.

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

Simplest Solution:

Hash The Input Array...Ignore duplicates...

Take difference from first array and the sum for each element and store result in corresponding location in second array...
The Second array now has same number of elements as the first one..
Now Hash Elements from Second array.. if they collide then the index of this element from second array and same index from first array gives you the pair.

This will also consider GreatOnes Case and prints 3 pairs.

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

while inserting in hash, if u find a pair whose sum is equal to given sum,
then reverse the pair and insert it again into hashtable, to get exact no. of pairs..as said by THE GREAT ONE.

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

Here is my working code. Hope you guys like it :)

using System;
using System.Collections.Generic;
using System.Text;

namespace Careercup
{
class Arraysum
{
static void Main()
{
int[] arr = new int[] {1,2,3,2,5,4,1,7,3,9,10,12 };
int sum = Convert.ToInt32(Console.ReadLine()); //say 5
int tempsum = 0;
int i = 0, j = 0;
while (j < arr.Length)
{
tempsum += arr[j];
if (tempsum == sum)
{
Console.WriteLine("{0}, {1}",arr[i], arr[j]);
j = j + 1;
}
else if (tempsum < sum)
j = j + 1;
else if (tempsum > sum)
{
i = i + 1;
j = i;
tempsum = 0;
}
}
}
}
}

Output:
2,3
3,2
4,1

Comment hidden because of low score. Click to expand.
0

would this work, if sum is 4? doesnt look like

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

Numbers in the array will act as keys and their index will act as values. So, if you have an array like 2,2,2 insert 2 the first element as (2,1). When adding second 2 check if it is there in the hashtable, if yes go to that location and update the value as (1,2) so now it will look like (2,(1,2)) and when third is added (2,(1,2,3)). So, if some number pair up with 2 then we can form 3 pairs with 2 at index 1,2 and 3.

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

3 Solutions

1. Everyone knows about the ineffecient O(n2) solution
2. Sort the numbers and keep two pointers one to the start and the other at the end and move them accordingly.
3. See the above post of using hash tables in O(n) time.

Comment hidden because of low score. Click to expand.
0

Good Job Gaurav...
This helps ppl more than other kinds of responses.

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

you can solve this by O(nlogn) time

1. sort
2. two pointer, one in front, one at end; then u know what to do

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

vector<list<int>> FindPair(int* array, int size, int sum)
{
//suppose the array has sorted already

vector<list<int>> r;
int j=size-1;
for(int i=0;i<size/2;i++)
{
if(sum-array==array[j])
{
list<int> temp=new list<int>();
temp.push_front(array[i]);
temp.push_front(array[size-i-1]);
r.push_back(temp);
}
else if(sum-array<array[size-i-1])
{
j--;
}
}
return r;

}

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

It takes O(nlgn) time and O(1) space

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

given: arr[0..n]
create a hash table with key = sum - arr[i] where i=0..n and value = arr[i].
then for each arr[i] check if its present in keys, if yes fetch the record print it.

if i am not wrong this solution handles duplicate, -ve, +ve in an array.

Comment hidden because of low score. Click to expand.
0

bai

Comment hidden because of low score. Click to expand.
0

shut up maai

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

this function in c# can do the job
public void findPair(int valueToFind,int[] arrayToLook){
System.Collections.Hashtable a = new System.Collections.Hashtable();
for (int i = 0; i < arrayToLook.Length; i++)
{
a[arrayToLook[i]]=true;
}

System.Collections.ICollection cbase = ((System.Collections.Hashtable)a.Clone()).Keys;
foreach (int i in cbase)
{

if(a.Contains (valueToFind-i))
{
if ((bool)a[valueToFind - i])
{
Console.WriteLine("({0},{1})", i.ToString(), (valueToFind - i).ToString());
a[i]=false;
}
}
}
}

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

One simple O(n lg n ) algorithm -

for each number say k in the array, do a binary search for sum-k. Binary search will take lg n time and there will be n calls to binary search so n lg n

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

One simple O(n lg n ) algorithm -

for each number say k in the array, do a binary search for sum-k. Binary search will take lg n time and there will be n calls to binary search so n lg n

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

here is the solution:
interviewcodesnippets.com/?p=181

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

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

class Program
{
public void Numbers(int[] arr, int testNumber)
{
Hashtable ht = new Hashtable();

for (int i = 0; i < arr.Length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.ContainsKey(arr[i]))
{
if (ht.ContainsKey(secondNumber))
{
}
else
}

}
foreach (DictionaryEntry de in ht)
{
if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
{
Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);

}
}

}
static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);

}
}

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

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

``````class Program
{
public void Numbers(int[] arr, int testNumber)
{
Hashtable ht = new Hashtable();

for (int i = 0; i < arr.Length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.ContainsKey(arr[i]))
{
if (ht.ContainsKey(secondNumber))
{
}
else
}

}
foreach (DictionaryEntry de in ht)
{
if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
{
Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);

}
}

}
static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);

}
}``````

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

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

``````class Program
{
public void Numbers(int[] arr, int testNumber)
{
Hashtable ht = new Hashtable();

for (int i = 0; i < arr.Length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.ContainsKey(arr[i]))
{
if (ht.ContainsKey(secondNumber))
{
}
else
}

}
foreach (DictionaryEntry de in ht)
{
if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
{
Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);

}
}

}
static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);

}
}``````

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

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

``````class Program
{
public void Numbers(int[] arr, int testNumber)
{
Hashtable ht = new Hashtable();

for (int i = 0; i < arr.Length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.ContainsKey(arr[i]))
{
if (ht.ContainsKey(secondNumber))
{
}
else
}

}
foreach (DictionaryEntry de in ht)
{
if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
{
Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);

}
}

}
static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);

}
}``````

Comment hidden because of low score. Click to expand.
0

``Sir i have problem in GW-Basic program to print 20 names in descendind order``

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

void sumCompare (int a[], int size)
{
int i = 0;
while (a[i] > 0 && i < size) {
int j = i;
while (a[j] > 0 && j < size) {
loop_count++;
if (a[i] + a[j] == 10) {
printf ("%d, %d\n", a[i], a[j]);
a[i] = -1;
a[j] = -1;
}
j++;
}
i++;
}
}

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

above solution works for all +ve num

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

``````/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package findsumfromarray;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

import java.util.Hashtable;

/**
*
* @author Sushant
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);

}

}
class Program
{
public void Numbers(int[] arr, int testNumber)
{
int i = 0;
Hashtable ht = new Hashtable();

for (i = 0; i < arr.length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.containsKey(arr[i]))
{
if (!ht.containsKey(secondNumber))
{
ht.put(arr[i], secondNumber);
}
else
ht.put(arr[i], ' ');
}
//else
//                ht.put(arr[i], ' ');
//System.out.println("Hastable list "+ht.get(arr[i]));

}
System.out.println("Hastable key " +ht.keySet());
System.out.println("Get value at "+ht.get(9));
}
}``````

The code works fine ..... Try running it ..

Comment hidden because of low score. Click to expand.
0

Sorry, Minor change..... second if will have

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

public static void findPairEqualtoSum(Integer[] num, int sum){
List<Integer> numList = Arrays.asList(num);
List<Integer[]> numPair = new ArrayList<Integer[]>();

for(int i = 0;i<numList.size();i++){
if(numList.contains(numList.get(i)-sum)){
Integer[] temp = {numList.get(i), (numList.get(i)-sum)};
Integer[] temp1 = {(numList.get(i)-sum), numList.get(i)};
if(!numPair.contains(temp) ||!numPair.contains(temp1))
}

}

}

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

Write A program that takes an array with maximum 20 characters and find the product of the elements in array

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

class Program
{
public void Numbers(int[] arr, int testNumber)
{
for (int i = 0; i < arr.Length; ++i)
{
if (arr.Contains(testNumber - arr[i])
{
Console.WriteLine("(" + arr[i].ToString() + ", " + (sum - arr[i]).ToString() + ")");
}
}
}

static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };

int testNumber = 5;

Program p = new Program();

p.Numbers(arr, testNumber);
}
}

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.

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