Microsoft student Interview Question for Students


Country: United States




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

There we are not considering one important point..say for example we can prune our search in following scenarios..
if we know that sum of cubes of say ( 001 ) is = 1 and number itself is 1 then there exists no possibility that there will be any armstrong number between 2-9.. so there by we can resume our search from 10 likewise.. for 1-100.. numbers which we will check are
1, 10-13,20-23,30-32,40 only... we indirectly cut short lot of checks ... this approach will help us discard large range of numbers... also we can use an array of size 10 or 9 .. with precomputed cube...in that way we will reduce even common / repetitive cubic operation...
One additional point of performance improvement is.. when we are changing digits say decimal or tenth then we don't want to compute the whole sum again.. we can store it may be simple on stack.. for current digits sequence of >=10, >=100, >=1000, >=10000,>=100000....etc...

please let me know if this makes any sense...

- ovjforu September 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

#include<stdio.h>
#include<conio.h>
void armstrong(int n)
{
     int i=1,k,d,s=0;
     k=i;
     while(i<=n)
     {
                if(k==0)
                {
                        if(s==i)
                        printf("%d\n",i);
                        i++;
                        k=i,s=0;
                }
                else
                {
                    d=k%10;
                    s=s+d*d*d;
                    k/=10;
                }   
     }     
}
main()
{
      int n;
      printf("Enter the value of n : ");
      scanf("%d",&n);
      printf("Armstrong numbers between 1 to %d are :\n",n);
      armstrong(n);
      getch();
}

- D3^!L September 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The mentioned algorithm is O(n*log(n)).
(For each i form 1 to n it performs log(i) calculations).

- Anonymous September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

This is not O(n)..This will be O(nd), where d is the max no of digits.

- alex September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

using Look Up Table?

#include <stdio.h>

static int lut[10][10];
void fillup_lut()
{
        int i,j;
        for(i=1;i<=9;i++)lut[0][i]=1;
        lut[0][0]=0;
        for(i=1;i<=9;i++)
        for(j=0;j<=9;j++)
        {
                lut[i][j]=lut[i-1][j]*j;
        }
}
int armstrong(int i)
{
        int a=i;
        int no_of_digits=1;
        while(a/=10)no_of_digits++;
        a=i;int sum=0;
        while(a)
        {
                sum+=lut[no_of_digits][a%10];
                a=a/10;
        }
        if(sum==i)return 1;
        else return 0;
}
main()
{
        int i;
        fillup_lut();
        for(i=0;i<99999999;i++)
        {
                if(armstrong(i)) printf("%d\n",i);
        }
}

- AB September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please explain the logic of how lookup table is being filled ?

- crystal.rishi2 October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if I say generate first 10 armstrong numbers?(i.e.you dont know value of 'n'.)Time complexity isn't of order of 'n'

- Sushant Gokhale November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) space ..or time?? and till what range?? could you please be specific with the question??

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

Complexity in the range of O(nLogn).

int armstrong(int n){
int i=0;
for(int i;i<n;i++){

int num=i;
int num_of_digits=(logi/log10)+1;
int sum=0;
while(num!=0){
int digit=num%10;
num/=10;
sum+=pow(digit,num_of_digits);
}
if(sum==i) cout<<"arm num"<<i<<"\n";
}

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

above algo is incorrect, as it is checking if given num if armstring or not, but above question is different as its asking to generate armstring numbers for given range.....

please read ques before posting algo

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

#include<iostream>

using namespace std;

main()
{
	int x,i,n,sum,p;
	cout<<"Enter upper range\n";
	cin>>n;
	cout<<"0\n";
	for(i=1;i<=n;i++){
		sum =0;
		x=i;
		while(x){
			p=x%10;
			x /= 10;
			sum += p*p*p;
		}
		if(sum ==i ) cout<< i<<endl;
	}
}

- j.a.b. September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kindly check the definition of Armstrong nos.

- Anonymous September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it's quite easy to show that an armstrong number must be less than 10^ 4 (think about how big the sum of digits can possibly be). So technically you can do this in constant time!

- Anonymous September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

rajeevpodar is right...
the series is bounded and all the numbers lie between 100 to 1000.
1 = 1^3... except the most obvious answer 1, all the other numbers will be captured with the range given in code

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

public class ArmStrongNumber {

	public static void armStrongNumber(int n) {
		if (n < 0) {
			return;
		}
		while (n > 0) {
			int sum = 0;
			int number = n;
			while (number > 0) {
				int remainder = number % 10;
				sum = sum + remainder * remainder * remainder;
				number /= 10;
			}
			if (sum == n) {
				System.out.println(n);
			}
			n--;
		}
	}

	public static void main(String[] args) {
		armStrongNumber(999);
	}

}

- Kevin March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<iostream>
#include<conio.h>


bool isArmstrong(const int number)
{
	int a,b,c;
	a = number%10;
	b = (number/10)%10;
	c = (number/100)%10;
	return ( ( (a * a * a) + (b * b * b) + ( c * c * c)) == number );
}

int main()
{
    std::cout<<"\n Armstrong number are : ";
    for ( int i =100;i<1000;i++)
    {
        if ( isArmstrong(i) )
        {
            std::cout<<"\t"<<i;
        }
    }
    getch();
}

- Ricky September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are considering that range will be between 100 to 1000. But according to the question range can be 10000 also. And also what about the armstrong nos. between 1 to 100. You have not considered that also

- xyz123 September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rajeevpodar is right...
the series is bounded and all the numbers lie between 100 to 1000.
1 = 1^3... except the most obvious answer 1, all the other numbers will be captured with the range given in code

- kalee October 10, 2012 | 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