Microsoft Interview Question for Development Support Engineers






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

We can use the following pattern:
2 @ unit's digit adds 1 '2' every 10 numbers (1/10)
2 @ TEn's place adds 10 '2' every 100 numbers (10/100)
2 @ hundred's place: 100/1000
and so on

So, we simply divide n by increasing powers of 10 until n/10^x < 1
in that case we check

if n>=3*10^(x-1) count+=10^(x-1)
else if n>=2*10^x-1 && n<3*10^x-1 count+=n-2*10^(x-1)+1

- Amit November 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thought on the same line...it works...

- Anonymous November 25, 2008 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>

int main()
{
int n,i,j;
int ctr=0;
scanf("%d",&n);
for(i=0;i<=n;i++)
{
for(j=i;j>0;j=j/10)
{
if((j%10)==2)
ctr++;
}

}

printf("The number of 2's is >> %d ",ctr);

}

- santosh July 12, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what about 20%10 = 0 ... it'll not count this similarly 120%10 .... and so on ...

- deepskt June 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

totally wrong solution ....

- Anonymous June 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This gives the right solution!

- darzen.23 August 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// returns no of 2's in values <= no...takes in only multiples of 10 starting from 10...

int getTwoCountFor10Multiples(int no)
{
int retVal = no/10;
if (no != 10 )
return retVal + (no/10) - 1;
else
return retVal;

}

void find2Count(int n)
{
int temp = n;
int start = 1;
int retVal = 0;

while(temp != 0)
{
// get the value....
int val = temp%10;

// if no units place...find number of ones for the 10th power you are
// at...and add it by val times...
if (start != 1)
retVal = retVal + val*getTwoCountFor10Multiples(start);
else if (val >= 2) // if units place...just see if greater than
// 2...add if yes
retVal += 1;

// move temp and start accordingly
temp = temp/10;
start = start*10;

}

// for nos like 50...above while will give 5 times no of 2s less than 10...

// this snippet will accomodate for all 2's in 10s place of 20
int base = 2*(start/10);
if ( n >= base )
if ( n <= (base + (start/10) - 1) ) // if between 20 and 30
retVal += n - base + 1;
else
retVal += (start/10) - 1; /// if greater than 30



cout<<retVal;
}

- king_k July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

getTwoCountFor10Multiples(int no)

if (no != 10 )
return retVal + (no/10) - 1;

should be
if (no != 10 )
return retVal + (no/10);

- king_k July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

king_k - Can you explain your solution?

- anon July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

convert the no into string
search for 2

- Rozy July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Converting the number into string would require the same logic of collecting the remainder and dividing by 10

- tb July 12, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not necessarily, use sprintf() or itoa() functions.

- KK April 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my algorithm...
each 10 contributes 1 2.

This is what the while loop does...
216:
6 --> 1 two before that

16 --> Consider 10 --> 1 two there

216 --> Consider 100 --> There is (100/10) 10's...each gives one 2...so 10...now below 100...there is also the whole 20 series...which has 10 occurences of 2...So each hundered gives 20 2s...
So this happens for 0-100 and 100-200...So multiply 20 by 2....40

Total so far 42.

Now, 216 also has a 2 for each number between 200 and 216...thats considered in the final snippet after the while loop...Look for 200-300.

- king_k July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int Count2th(unsigned int number)
{
unsigned int count = 0;
while (number > 1)
{
if (number == 2)
return count + 1;
unsigned int n = number;
while (n)
{
unsigned int rem = n % 10;
if (rem == 2)
++count;
n /= 10;
}
--number;
}
return count;
}

- vladd July 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#define NUMBER 200
main ()
{
/*This program calculates the number of 2's present in the number x*/

int arr[NUMBER];
int i=0,count=0;
while(i<NUMBER)
{
arr[i]=i+1;
printf("%d ",arr[i]);
i++;
}
for(i=0;i<NUMBER;i++)
{
while(arr[i]>0)
{
int rem,quo;
rem=arr[i]%10;
quo=arr[i]/10;
if(rem==2&&quo==2)
{
count=count+2;

printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;

}
else if(rem==2)
{
count++;
printf("Number is : %d\n",arr[i]);
}
else if(quo==2)
{
count++;
printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;
}
arr[i]=arr[i]/10;
}
}
/* complexity of this program : n* size of the number ( digits present in the number*/
/* Worst case O(n^2)*/

printf("\n\n\n");
printf("THe number of 2's are : %d\n",count);
printf("\n\n\n");
}

- Ashish July 12, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Find2s_(int r1, int r2)
{
int count2 = 0;
for (int i = r1; i <= r2; i++)
{
count2 += SplitNumberCacl2(i);
}
return count2;
}

int SplitNumberCacl2(int n)
{
if (n <= 0)
return 0;
int countTwo = 0;
while(true)
{
int rem = n % 10;
if (rem == 2)
countTwo++;
n = (n - rem) / 10;
if (n == 0)
break;
}

return countTwo;

}

this is O(n) not o(n^2) because the max value of int is 2,147,483,647 so thats the worst case with 10 iterations so its O(10n) = o(n)

- neoreaves August 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, the max value of integer can be 18446744073709551615 (if you define the integer as unsigned long long)which is of size 20..so the order would be O(20.n)

- noviceprog September 22, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main( )
{
long range,count,temp,sum=0;

cout<< "Enter the range :";
cin>>range;

for (count=0;count<=range;count++)
{
temp=count;
while(temp>0)
{
if(temp%10==2)
sum++;
temp/=10;
}
}

cout<<"The number of 2s is "<<sum<<endl;

return 0;
}

- ratheesh September 07, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Count2th(unsigned int num)
{
int count = 0;
while(num)
{
int n = num;
while(n)
{
char ch = n%10 + '0';
if (ch == '2')
count++;
n /= 10;
}
num--;
}
return count;

}

- Sum September 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Havent given it much thought but how about converting the number to a string and then using string operation to find the number of 2s in it. String compare should be better than division i feel....

- NL October 04, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

firstly:take a simple question: how many 2 between [ 1000, 2000 )?
ans is quite obvious, ( (2000-1000)*3 )/10 = 300
then how many 2 between [ 10000, 20000 )?
ans is quite obvious, ( (20000-10000)*4 )/10 = 4000
see the pattern?

now let's see how many 2 between [ 0, 1000 )?
[ 0, 1000 ) --> [ 0, 900) + [ 900, 1000 )
[ 0, 900 ) --> [ 0, 100) + [ 100, 200 ) + [ 200, 300 ) .... + [ 800, 900 )
divide and conquer.
I think my idea is helpful.
any comment is welcome!

- andy October 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This kind of problem should be answered based on how 2 can appear
in a range,at unit place,at tens place etc
It is middle school permutation/combination problem.

- Anonymous November 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dont just confine to 2 - Think in the terms of digit 'd' in the range [0-n]
We can get a recurrence relation.

100[w=n%10000?10:0 + ......] + 10[z=n%1000)>d?10:0 + z] + [(y=n%100)>d?10:0 + y]+[(x=n%10)>d?1:0]

One catch in the above approch is if for some 'x' (different from the above context) (x = n%100) == d, then you can't add 10, you need to see the n%10 and add Total number of 'd's = (n%10+1)

- Devil170 February 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The output should be 14 instead of 13, someone has to change it.

/*
Write a method to count the number of 2's between 0 and n.
EXAMPLE
input: 35
output: 13 [list of 2's: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32]
*/

- LaoBan February 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is what I came up with:

#include <iostream>
using namespace std;

int count_digit(int n, int dig)
{
    int count = 0;
    while (n)
    {
        int q = n / 10;
        int remainder = n - q * 10;
        if (remainder == dig)
        {
            ++count;
        }
        n = q;
    }
    return count;
}

void main()
{
    int count = 0;
    for (int i = 0; i != 35; ++i)
    {
        count += count_digit(i, 2);
    }
    cout << count << endl;
}

- cristi.vlasceanu May 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think cristi.vlasceanu 's solution is fine, would you please explain the approach a bit? @ cristi.vlasceanu

- LLOLer August 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Whats there to explain in this ?

Rewinding back to our school days, Formulae: [ Dividend = Divisor * Quotient + Reminder ]

In the count_digit function, Cristi has used this formulae to get very single digit in a number and then check if it 2.

- peace October 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count2(int n) {
int rem = n % 10;
int head = n/10;
int value = count2(head-1)*10 + head;
//count2(head-1)*10 count all 2s originated from the higher position
//head count all 2s originated from the current position
if (rem > 2) return value+1;
else return value;
}

- Anonymous October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oh, forget the ending condition:
if (n == 0) return 0;

- Anonymous October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python implementation: fast version checked against slow version for n up to 10000.

def count_digits_dumb(d, n):
    sd = str(d)
    return sum(str(i).count(sd) for i in range(n+1))

def count_digits_smart(d, n, ns, k):
    if not k:
        return 0
    b = int(ns[0]) # leading (position k) digit of n
    p = 10**(k-1)
    cnt = b*(k-1)*(p//10) # count d at non-k digit positions
    if b > d: # count all d at leading position
        cnt += p
    elif b == d: # count partial d at leading position
        cnt += n-d*p+1

    # At this point we have accounted for all d on digit position k
    # and all d below b*p, so we are reduced to the sub-problem
    # on [0, n-b*p], where n-b*p is k-1 digits long. So just apply
    # recursion and sum up all the counts on the way back up to get
    # the desired answer.
    return cnt + count_digits_smart(d, n-b*p, ns[1:], k-1)

d = 2
n = 1234321
ns = str(n)
k = len(ns)
print(count_digits_dumb(d, n))
print(count_digits_smart(d, n, ns, k))
# ans: 758686

- Bullocks December 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple solution : DP

store 1 digit number having 2 : 2
store 2 digit number having 2 : appending 0-9 after 2 and appending 1-9 before 2
store 3 digit number having 2: appending 0-9 after abv 2 digit numbers and appending 1-9 before abv 2 digit number

go on like this this till number of digits <= number of digts in n and number<n..


Answer in constant order if u get nay number less than n(for other test cases)

- Anonymous January 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not constant but O(number of digits of n)

- Anonymous January 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="python" line="1" title="CodeMonkey56705" class="run-this">#!/usr/bin/python

import sys

def numOf2Dumb(num):
count = 0
for n in range(num):
x = str(n)
for t in x :
if t == '2':
count+=1
return count


def numOf2Smart(num):
count = 0
n1 = str(num)
n = n1[::-1] #reverse the string
t1 = 0
t2 = 1
l = len(n)
for i in range(l):
y = int(n[i])
count += (y*t1)
if y > 2 :
count += t2
elif y == 2 :
if l>i and i>0:
count += int(n1[l-i:])
t1, t2 = t2+10*t1, t2*10

return count



# Gather our code in a main() function
def main():
print numOf2Dumb(120)
print numOf2Smart(120)


# Standard boilerplate to call the main() function to begin
# the program.
if __name__ == '__main__':
main()

</pre><pre title="CodeMonkey56705" input="yes">1
2
10
42
11

</pre>

- Anonymous June 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the answer:
interviewcodesnippets.com/2010/09/counting-2s-brute-force/

- moe October 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int CountNumberOf2s(int n)
        {
            int count=0;
            if (n < 0)
                return -1;
            else
            {
                string temp;
                for (int i = 2; i <= n; i++)
                {
                    int j = 0;
                    temp = i.ToString();
                    while (j < temp.Length)
                    {
                        if (temp[j] == '2')
                        {
                            count++;
                        }
                        j++;
                    }
                }
            }
            return count;
        }

- Andy Patil November 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumOfTwosBetZeroAndN {
static int count = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int b;
		int []a = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
	    for(int i=0;i<a.length;i++)
	    {
	    	if(a[i]==0)
	    	{
	    		count=0;
	    	}
	    	else {
	    	while((a[i]%2)==0)
	    			{
	    		count++;
	    		a[i] = a[i]/2;
	    			}
	    }
	    }
	    System.out.println("total number of 2's between 0 and n are: " +count);
	}

}

- Namisha February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findLength(n){

var arr = [];
while(n > 9)
{
var no = n%10;
arr.push(no);
n = n/10;
n = parseInt(n);
}
arr.push(n);
return arr.length;
}


function find2(n){
var l = findLength(n);
if(l == 1){
if(n > 1)
return 1;

return 0;
}
var f = parseInt(n/ (Math.pow(10, l-1)));
var two = Math.pow(10, l-2) * (l-1);
var count = 0;
if(f == 2){
count = 2 * two + (n - 2 *(Math.pow(10,l-1))) + 1;
}
else{
if(f < 2){
count = two;
}
if(f >= 3){
count = ((f ) * two) + (Math.pow(10, l-1));
}
}
count = count + find2(n % (Math.pow(10, (l-1))));
return count;
}


function find2Test(n){
var c = 0;
var i = 2;
function count2(number){

while(number > 1)
{
var no = number%10;
if(no == 2){
c++;
}
number = number/10;
number = parseInt(number);
}

}

while(i <= n){
count2(i);
i++;
}
return c;
//console.log(c);
}
function executeBoth(n){
console.log(find2 (n),find2Test(n));
}
function runTest(n){
return find2(n) == find2Test(n);
}

- rajansoft1 May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findLength(n){
   
  var arr = [];
  while(n > 9)
    {
      var no = n%10;
      arr.push(no);
      n = n/10;
      n = parseInt(n);
    }
  arr.push(n);
  return arr.length;
}


function find2(n){
   var l = findLength(n);
  if(l == 1){
    if(n > 1)
    return 1;
    
    return 0;
  }
  var f =  parseInt(n/ (Math.pow(10, l-1)));
  var two = Math.pow(10, l-2) * (l-1);
  var count = 0;
  if(f == 2){
    count = 2 * two + (n - 2 *(Math.pow(10,l-1))) + 1;
  }
  else{
    if(f < 2){
      count = two;
    }
    if(f >= 3){
      count = ((f ) * two)  + (Math.pow(10, l-1)); 
    }
  }
  count = count + find2(n % (Math.pow(10, (l-1))));
  return count;
}


function find2Test(n){
  var c = 0;
  var i = 2;
  function count2(number){
    
    while(number > 1)
    {
      var no = number%10;
      if(no == 2){
        c++;
      }
      number = number/10;
      number = parseInt(number);
    }
    
  }
  
  while(i <= n){
    count2(i);
    i++;
  }
  return c;
  //console.log(c);
}
function executeBoth(n){
  console.log(find2 (n),find2Test(n));
}
function runTest(n){
  return find2(n) == find2Test(n);

}

- rajansoft1 May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 0 vote

The cheap (and dirty) way would be create an array from 1-n. As you are creating it, inspect each number and see if it has a '2' in it. I agree, its not optimal.

- anon July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

range num_of_twos
0~99 20
100~199 20
...
900~999 20

so
0~999 20*10
1000~1999 20*10
...
9000~9999 20*10
...
//======================
#define num_of_twos 20

int countTwo(int num)
{
int count=0,mod1=0,mod2=0,mod=0;
int scale=1;
mod1=num%10;
num=num/10;
mod2=num%10;
num=num/10;

while(num>0)
{
mod=num%10;
num=num/10;
count=count+mod*num_of_twos*scale;
}

if(mod2<2)//less than 20
{
if(mod1>=2)
count+=mod2+1;
else
count+=mod2;
}
else if(mod2>2)//bigger than 29
{
if(mod1>=2)
count+=mod2+10+1;
else
count+=mod2+10;
}
else
{
if(mod1>=2)//between 20~29
count+=mod2+mod1+2;
else
count+=mod2+mod1+1;

}
return count;

}

- wangjiaqin July 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is absolutely not correct. from 200 to 299, there are 120 2's.

- Anonymous July 13, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is absolutely not correct. from 200 to 299, there are 120 2's.

- Anonymous July 13, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is absolutely not correct. from 200 to 299, there are 120 2's.

- Anonymous July 13, 2008 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Pattern idea is perfect.
Here is the code.

Total count of 2 in the range
2's count in 1-100 = 19
2's count in 1-1000 = 190
2's count in 1-2000 = 380
2's count in 1-4000 = 760
2's count in 1-8000 = 1520

/*
Write a method to count the number of 2's between 0 and n.
EXAMPLE
input: 35
output: 13 [list of 2's: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32]
*/
public static string CountNumberOf2sInGivenRange(int range)
{
// Few assumptions: Range is unssigned value
if (range < 1) return "0";

int pattern1 = 2;
int pattern2 = 20;
int pattern3 = 21;
ArrayList al = new ArrayList();

while (pattern1 <= range)
{
// Pattern1: 2, 12, 22, 32, 42, 52, 62, 72, 82, 92, 102, 112, 122, etc....
al.Add(pattern1);
pattern1 = pattern1 + 10;
}

while (pattern2 <= range)
{
// Pattern2: 20, 120, 220, 320, 420, 520, 620, 720, 820, 920, 1020, etc...
al.Add(pattern2);
pattern2 = pattern2 + 100;
}

while (pattern3 <= range)
{
// Pattern3: 21, 23, 24, 25, 26, 27, 28, 29, 121, 123, 124, 125, 126, 127, 128, 129, 221, 223, etc...
int count = 1;
if (pattern3 + 8 <= range)
{
for (int i = 1; i <= 9; i++)
{
if (i == 2) continue;
al.Add(pattern3);
pattern3++;
}

pattern3 = pattern3 + 100 - 8;
}
else
{
while (pattern3 <= range)
{
if (count != 2)
{
al.Add(pattern3);
}

count++;
pattern3++;
}
}
}

string returnStr = string.Empty;
foreach (int i in al)
{
returnStr += i.ToString() + ", ";
}

return "Total count of 2 = " + al.Count + " : " + returnStr.Substring(0, returnStr.Length - 2);
}

- SV January 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is actually 20 2s between 0-100. You are probably not counting that there are two 2s in `22`.

02, 12, 22, 32, etc.. = 10 in the 1s column
20, 21, 22, 23, 24 = 10 in the 10s from 20-29

- v July 14, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More