Microsoft Interview Question for Software Engineer in Tests

Team: Server tools division
Country: United States
Interview Type: In-Person

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

You can do it in o(n) time complexity by using additional space.
Store all the elements in a hashmap as key-value pair, where key is number and value is index.(this will take O(n) time.)
traverse through the list and for each number see whether (sum-num) is present or not in hashmap.(searching in hashmap will take O(1) time)
if(num is present in hashmap){
print both number with indexes
}else{
do nothing.
}

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

public static void printPair(int[] array, int sum)
{
if (array == null)
{
return;
}
for (int i = 0; i < array.Length; i++)
{
int currentSum = array[i];

for (int j = i + 1; j < array.Length; j++)
{
int newSum = currentSum + array[j];
if (newSum == sum)
{
Console.WriteLine("(" + currentSum + "," + array[j] + ")");
}
newSum = 0;
}
}
}

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

@pradegup: you should also maintain a count of how many times that value occurs in the array. for example, in the given array, 4 appears twice so when you look up 4, you will try to find if k-4 = 8-4 = 4 exists... and this returns true...

but consider an array where 4 appears only once... and when you do a search on 4, you will return true... but that's not solution...

does this make sense?

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

@JustCoding: Yes it make sense. Your point is valid.
But this case will arise only if sum is even and (sum/2) is present in array. So we can take care of this as a special case.

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

public static void printAllPairs(int[] a, int sum) {

HashMap<Integer, LinkedList<Integer>> list = new HashMap<>();

for(int i = 0; i < a.length; i++) {
if(list.containsKey(sum - a[i])) {
newList = list.get(sum - a[i]);
for(int j = 0; j < newList.size(); j++) {
System.out.println(a[i] + "(" + i + ")" + " ," + (sum - a[i]) +  "(" + newList.get(j) + ")");
}

}
if(list.containsKey(a[i])) {
newList = list.get(a[i]);
list.put(a[i], newList);
} else {
list.put(a[i], newList);
}
}
}

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

I have used a HashMap , key = value in array, List of all its indexes. this way u can keep track of all the indexes and print all pairs.

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

The solution given by @pradegup works fine with a little modification. We don't add all the keys initially. Instead,
2)check if sum-x is present in Hash.
3)If yes, then we print x and key (which is sum-x)
Else, we add x to the Hash table.

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

I have questions about the duplicates. for example, sum = 8; a[] = {3 3 4 4 4 5 5}, then i think you should return seven group of indice. (0 6) (0 5) (1 6) (1 5) (2 3) (3 4) (2 4). But I'm afraid your code cannot do this.

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

Use Hash
for int i=0; i < arr.length; i++

foreach(Key k in hash.keys)
if there exists hash[8-k] then print hash[k] and has[8-k]
overall complexity 2 o(n)

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

hash table is best one, but if no additional memory used then
1. we should sort an array in inplace with Quick sort..
2. then keep track of start and end index in array , sum of start + end > given sum then....start++, else end--.

this way, we can get two number without using extra memory

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

correction- Assuming that the array is sorted in increasing order:

if start+end > given sum, then end-- else start++...

if start + end == sum, return/print those 2 numbers and continue to find more such pairs...

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

If you sort the array you lost the initial index information. So you cannot sort the array.

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

I think using hashmap duplicates cannot be allowed. This works on log(n).When you add a duplicate it updates the value to later one. here is java code
public class SumInArr3 {
public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
valMap.put(arr[i], i); }
for (int i = 0; i < arr.length; i++) {
if (valMap.containsKey(key - arr[i])
&& valMap.get(key - arr[i]) != i) {
if (valMap.get(key - arr[i]) < i) {
int diff = key - arr[i];
System.out.println(arr[i] + " " + diff);}}}}
public static void main(String[] args) {
int[] arr = { 32, 40, 28, 37, 4, 12, 2, 51, 23, 50, 20, 56, 32,-50,110 };
int sum = 60;
findSumHashMap(arr, sum); }}

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

This one works on (N^2)/2
public class SumInArr2 {
public static void findSumHashMap(int[] arr, int key) {
for(int i=0;i<=arr.length-2;i++){
for(int j=i+1;j<=arr.length-1;j++){
if (key-arr[i]==arr[j]){
System.out.println(arr[i]+ "index:"+i+" "+arr[j]+ "index:"+j);}}} }
public static void main(String[] args) {
int[] arr={32,40,28,37,4,12,2,51,23,50,20,56};
int sum = 60;
findSumHashMap(arr,sum); }}

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

public class PairIndexSum {
public static void printIndexPair(int[] array, int sum) {
for (int i = 0; i < array.length; i++) {
if (map.containsKey(array[i])) {
} else {
map.put(array[i], list);
}
}
for (int i = 0; i < array.length; i++) {
if (map.containsKey(sum - array[i])) {
LinkedList<Integer> list = map.get(sum - array[i]);
for (Integer n : list) {
if(i != n){
System.out.println("Index:" + i + " " + n);
}
}
map.remove(array[i]);
map.remove(sum - array[i]);
}
}
}

public static void main(String[] args) {
int[] array = { 1, 4, 4, 3, 7, 5, 8 };
printIndexPair(array, 8);
}

}

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

output is :
Index:0 4
Index:1 1
Index:1 2
Index:3 5

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

Oh ya, you are right. The output should not include 1 1. Sorry. I have changed it. Thank you!

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

in python:

#!/usr/bin/python

a=[1,4,4,3,5,7,8]
sum=10
i=0
l=len(a)
while(i<l-1) :
j=i+1
while(j<l) :
s1=int(a[i])+int(a[j])
if (s1==sum) :
print("position of i and j:%d, %d" % (i,j))
j=j+1
i=i+1

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

In Ruby

# O(n)
def sum_of_index_values sum_arr = [], sum
sum_hash, i = {}, 0
sum_arr.each do |x|
sum_hash.store(i, x)
i+=1
end
0.upto(sum_arr.size-1) do |i|
remainder = sum - sum_arr[i]
puts "#{remainder} " + '(index '"#{sum_arr[i]}"')' if sum_hash.include?(remainder)
end
end

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

#include<stdio.h>
#include<conio.h>
void main()
{
int a;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
(
if(a[i]+a[j]=k)
{
printgf("position of indexes %d %d",i,j)
}
}
}

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

@Rohit: This is simply brute-force method.
Using other available data structure, you can optimize this code upto O(n).

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.