## Microsoft Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

Can be solved in O(N) using window sliding.

Just sum 1 + 2+ 3.. etc and if sum of first i numbers gets bigger than N (using right pointer), then just move left pointer and substract as long as you don't get one solution. when you get a solution, increment both pointers.

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

(k+1)*a + k(k+1)/2 = N
N = (k+1)(a + k/2)
2N = (k+1)(2a+k)

Then, for N not-too-big, we can use integer factorization to find all pairs (a,k).
Just find all pairs (u,v) that u*v = 2N, considering all positive and negative divisors, then k = u-1, a = (v-k)/2. Of course, v-k must be even, otherwise ignore them.

If a, k are integers, then N must be integer.
If N real, a must be real. But then for any k we can find a. Thus there's not finite #solutions.

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

On the real number N case, the trick was with rounding errors. There, the interviewer said that we should think of step size (e.g. e=0.00001) to remove the rounding errors.

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

Windows sliding

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

``````public class sumCons
{

static int doesSum(int a, int N)
{
int sum = a;
while(sum<N && a>0)
{
sum = sum+(a-1);
a--;
}

if(sum==N)
{
return a;
}
else
{
return -1;
}}

public static void main(String args[])
{
int X = args[0];
int b;
int a = X/2;
while(a>1)
{
b = doesSum(a,X);
if(b!=-1)
{
System.out.println("("+b+","+a+")");
}
a--;
}
}
}``````

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

This is a variation on the Sliding Window algorithm without a fixed window size. Code is a bit messy but works. Appreciate comments and feedback
PS: This will print the consecutive sums (not the pair a,k)
Doesn't take into account the -ve numbers or real numbers scenarios.

``````public class SumOfConsecutives {

private static List<String> result = new ArrayList<>();

public static List<String> process(int n)
{

//Corner cases, assumes n is +ve
if(n < 0)
if(n == 0)
else if(n == 1)
else if(n == 2)
else // >1
{
String consecutive = "";
int sum = 0;
int start = 0;
int nextStart = 0;
//Naive approach
while(start <= Math.floor(n/2)) //for example: n = 20, start = 10.
{
while(sum < n)
{
sum += nextStart;
consecutive += nextStart + " + ";
nextStart++;
}
if(sum == n)
{
}
//reset
start = start+1;
nextStart = start;
consecutive = "";
sum = 0;
}

}

return result;
}

}``````

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

``````//For positive numbers.
public void printConsecNums(int n)throws InvalidInputException
{
if(n<=0)
{
throw new InvalidInputException();
}
int sum=0;
for(int i=1;sum<n;i++)
{
sum+=i;
consecSums.enqueue(sum);
}

int start=1;
//if sum is larger then n, try removing values from the queue until you get a value less than or equal to n.
while(sum>n)
{
int top=consecSums.dequeue().intValue();
sum=sum-top<=n?sum-top:sum;
start++;
}
sum==n?printConsecValues(start,n):System.out.println( n + " cannot be expressed as the sum of consecutive values ");

}

private void printConsecValues(int s,int target)
{
int sum=0;
for(int i=s; i+sum<=target;i++)
{
System.out.print(i + " ");
sum+=i;
}
}
/**Time complexity is O(m+k) where m is the number of operations needed to get a sum>=n, k is the number of values to be removed from the queue to get the sum
to be less than or equal to n.**/
//For negative integers, we have to change the loops and the start variable (ie. for (int i=-1; sum>n;i--), while (sum<n), start=-1).``````

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

private static void getConsecutives(int num) {
// TODO Auto-generated method stub
int sum = 0, i=0, j=0;
for(i=0, j=0; sum != num;)
{

if(sum < num)
{
j++;
System.out.println("sum: " + sum + " adding: " + j);
sum += j;

}
else
{
i++;
System.out.println("sum: " + sum + " subtracting: " + i);

sum -= i;
}
}
System.out.println("The consecutive numbers are: ");
i++;
while(i < j)
{
System.out.print(i + ", ");
i++;
}

System.out.println(j);
}

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

Based on the sliding window concept, a O(N) solution.
1. Maintain two pointers
2. When SUM is equal to given N, then print the range and increment both the pointers.

``````public static void slidingWindow(int n){
int ptr1=1;
int ptr2=1;
int sum=1;
while(ptr2 < n/2){
if(sum>n){
sum -= ptr1;
ptr1++;
}
else if(sum < n){
ptr2++;
sum += ptr2;
}
else{
sum(ptr1,ptr2);
sum -= ptr1;
ptr1++;
ptr2++;
sum += ptr2;
}
}
}

public static void sum(int a, int b){
StringBuilder sb = new StringBuilder();
for(int i=a;i<=b;i++){
sb.append(i);
if(i != b) sb.append(" + ");
}
System.out.println(sb.toString());
}``````

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

``````#include <stdio.h>
#include <math.h>

// set N input here
double N = 5.0;

int
main(void)
{
int half;
int bottom;

half = 	ceil(N / 2); // note that we dont ever have to sum numbers > ceil(N/2)

bottom = 1;

while (bottom < half)
{
int i;
int sum;

sum = 0;

for (i = bottom; i <= half; i++)
{
sum = sum + i;
if (sum == N)
{
// found consecutive numbers! print them
int j;
for (j = 0; j < answer_n; j++)
{
}
printf("\n");
break;
}
}
sum = 0;
bottom++;
}

return 0;
}``````

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

#include<iostream>

using namespace std;

int main() {
int i=0, n=0, s=0, prev=0, next=0;
cout << " Enter n " ;
cin >> n;

while(i<n)
{
if(s == n) {
cout << " Sum is found for " << prev << " to " << next << endl;
break;
}

while(s > n ) {
s = s - prev;
prev++;
if(s == n)
{
cout << " Sum is found for " << prev << " to " << next << endl;
break;
}
}

if(s == n)
break;
s = s + i;
next = i;
i++;
}
if( s > n)
cout << " Sum for " << n << " not exist " << endl;
return 0;
}

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

The solution is sqrt(n)

then add i=1, 2, 3, 4, ....
at each addition check if n - sum is dividable by i

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.