Microsoft Interview Question 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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.. on 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 on 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. on 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 on 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 on 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 on 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 on 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 on 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 on 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 on October 10, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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