Google Interview Question for Testing / Quality Assurances






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

10 digits (non repeated digits): Does that mean using all 0-9 digits.
So basically find a number which is a perfect square that contains all digits without repetitions?
So why not just check all squares of numbers from sqrt(1023456789) to sqrt(9876543210)
i.e. check if squares of numbers from 31991 to 99380 contain any repetitions.

- GekkoGordan February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems reasonable.

- memo February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wellsaid!!

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

Exactly. Have no idea what's confusing some of the other folks.

- Bullocks July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If any number in between that range contains 0 as its last digit ignore all those. Because it will all generate atleast 2 zeros when we square it.

- Psycho October 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same idea as mine.
And I think we should clarify the following assumption with interviewer first:
(Assumption) '0' can't be the leading digit

The following is the Java implementation:

class G214
{
	public static void main(String[] args)
	{
		System.out.println("firstPerfectSquare10digits: " + firstPerfectSquare10digits());
	}

	public static long firstPerfectSquare10digits()
	{
		for (long i = 31991; i <= 99380; i++)
		{
			boolean[] used = new boolean[10];
			for (char c : ((i * i) + "").toCharArray())
			{
				used[c - '0'] = true;
			}
			boolean ok = true;
			for (boolean b : used) if (!b) {ok = false; break;}
			if (ok) {return (i * i);}
		}
		return (-1);
	}
}

- Alva0930 February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this problem can be solve efficiently using bisection method,
> if a number is n digit number then its squareroot must be of n/2 digit,
> take low=1 and hight =n/2 digit largest number
> find the mid=(low+high)/2
>if mid^2== number return
> if mid^ 2> number then high=mid-1
>else low=mid+1
>repeat above process recursively untill low>high

this gives solution in (log n) time
please tell me if I m' wrong..!!!
Thnx

- abhaypandey1008 July 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this problem can be solve efficiently using bisection method,
> if a number is n digit number then its squareroot must be of n/2 digit,
> take low=1 and hight =n/2 digit largest number
> find the mid=(low+high)/2
>if mid^2== number return
> if mid^ 2> number then high=mid-1
>else low=mid+1
>repeat above process recursively untill low>high

this gives solution in (log n) time
please tell me if I m' wrong..!!!
Thnx

- abhaypandey1008 July 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Get the number of digits. Say n
High = Int(Sqrt(pow(n, 10)-1))
Low = Int(Sqrt(pow(n-1, 10)))+1
So the number will be in between Sqr(Low) and Sqr(high)
And the sum of digits should be 45

- Anonymous February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sum to 45 is wrong. Cos there can be sequence with repeated digits which can sum to 45

If i were to do it in Mathematica, this would be the solution. I am not sure if these methods are there in any programming APIs. Let me know if you know of any.

Given number of digits n...

Length[Union[IntegerDigits[m^2]]] == n,
Print["Number = ", m^2]],
{m, Floor[Sqrt[pow(10, n-1)]], Floor[Sqrt[pow(10, n)]]}];

- Anonymous February 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand what google want to test... Is it expecting a programmer to be mathematical or logical...
What is the position for which this interview query is posted?

- Not for non-math guys February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be done by simple mathematical approach
where in we create a loop of 10 digits no. with non repeated digits (simple P& C)
and check their square roots are float or int and if it is int then it will be shown as out put.

- anonymous February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That would be super-inefficient. Think about how big 10! is. If you start from the possible square roots and square to see if you have a permutation, that's only about 70K numbers to check.

- Bullocks July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

start with int num = 1 and keep doing num = num << 1 until num has 10 digits.

- Anonymous February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can't understand

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I made a mistake in the above answer, should be:

int num = 1;

while ( num has less than 10 digits){
num = num << 2; //equivalent of multiple by 4
}

Basically this algorithm is checking to see if 2^0, 2^2, 2^4, 2^6....2^n, where n is even is a perfect square root of 10 digits. Note that 2^n is always perfect square root.

The question only ask you to find a number of 10 digit with perfect square root, it didn't ask you to find the First perfect square root, so you can use bitwise operation to emulate 2 to the power of 2s to obtain a very efficient solution.

Also note that the above algorithm will always find a number with 10 digits because if you multiple X by 4, that X can grow maximum 1 digit (think about 99999*4).

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what r u trying to do, dude?
give psuedo-code to explain ur idea.

- anon February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

while ( num has less than 10 digits){
num = num << 2; //equivalent of multiple by 4
} this is the psuedo code lol, it's using bitwise operation to get power of 2s.

Think about this:

2^0=1, 2^2=4, 2^4=16, 2^6=64, 2^8=256 are all perfect squares. Now, think about the binary representation of these number:

1=0000000001, 4=0000000100, 16=000010000, 64=001000000, 256=100000000

See the pattern? I'm just trying to shift the only 1 in the binary number to the left by 2 positions each time, and each time I do that the resulting number in base 10 representation is always a perfect square.

So the idea is to keep shifting until you get a number with 10 digits.

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pls READ question first. If you DON'T understand the question ask someone to clarify (before attempting to respond). In a real interview you might give answer instantly without even understanding the question first.

The question asks "10 digit number such that the number has all of [0,9] digit, i.e. NO REPEAT"

- anon February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start with smallest 10 digit number:
1. Find the sum of digits of the number
2. If the sum can be expressed as the sum of odd numbers like, sum = 1+3+5+7+....,
then it is a perfect square.
3. Else increment the number by 1.

Use loop with base as smallest 10 digit number and limit as largest one, with an increment of 1 at each iteration (this may not be needed)

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

2^32

- S February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL

- LOL February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how many perfect squares are there in 100 is sqrt(100)!!!

sqrt(9876543210) - sqrt(1023456789)

- Anonymous February 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong... it is not checking the repeated digits in number

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

as lower limit = sqrt(1023456789)
upper limit = sqrt(9876543210);
loop i in lower to upper
if(sqr(i) == all distince digit)cnt++;

can anyone have better idea

- pankaj February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

above solution by GekkoGordan looks good. because calculating square is much much faster than sqrt.
for this problem with squares o/p comes with in 1 second.... with sqrt it is taking more than 5 mins

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a better idea - because we know that the sum of all the digits of the (10 digit) number is 45 - its divisible by 9, therefore the square root of that number is divisible by 3. Hence we dont have to square each number to find the solution, only square the multiples of 3 to find the solution. So the max numbers that you will have to square to arrive at the solution will be reduced from 67k to 23k.

- YBS February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

out of box thinking!!

- Anonymous June 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class perfectSquare {

/**
* @param args
*/

public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;

while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;

}
else
return 0;

}
return 1;
}


public static void main(String[] args) {
// TODO Auto-generated method stub

//int b= (int)Math.sqrt(1000000000);
long b=(long) Math.sqrt(1000000000);
long bn= 99999999999L;
long e=(long) Math.sqrt(bn);
int count=0;

for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}

System.out.println("count::"+count);


}


}

- Nohsib February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class perfectSquare {

/**
* @param args
*/

public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;

while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;

}
else
return 0;

}
return 1;
}


public static void main(String[] args) {
// TODO Auto-generated method stub


long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;

for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}

System.out.println("count::"+count);


}


}

- Nohsib February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class perfectSquare {

/**
* @param args
*/

public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;

while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;

}
else
return 0;

}
return 1;
}


public static void main(String[] args) {
// TODO Auto-generated method stub


long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;

for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}

System.out.println("count::"+count);


}


}

- Nohsib February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Nohsib: post code on ideone.com or make an account so that you can edit your code
Posting code again and again with little changes is "bad for environment"

- GekkoGordan February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically we have to compute all permutations of the number 1023456789. (exclude those having 0 as Most Significant digit). There will be around 10! - 9! numbers and we have to check whether they have a whole number sqrt or not.

- Hji February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Prelude Data.List> filter (\x -> x == nub x) (map (show.(^2)) [100000..316227])
[]

- haskell February 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

GXCHGXCHXGHGGXCHXGCHCGH

- THCGHCFGH February 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One line solution in Python. 87 such solution exists. Start from 0 to 10^5. Check if the square contains all unique digit from 0-9, best way is to put in a set and check whether length is 10.

>>> [i for i in range(99999) if len(set(str(i**2))) == 10]
[32043, 32286, 33144, 35172, 35337, 35757, 35853, 37176, 37905, 38772, 39147, 39336, 40545, 42744, 43902, 44016, 45567, 45624, 46587, 48852, 49314, 49353, 50706, 53976, 54918, 55446, 55524, 55581, 55626, 56532, 57321, 58413, 58455, 58554, 59403, 60984, 61575, 61866, 62679, 62961, 63051, 63129, 65634, 65637, 66105, 66276, 67677, 68763, 68781, 69513, 71433, 72621, 75759, 76047, 76182, 77346, 78072, 78453, 80361, 80445, 81222, 81945, 83919, 84648, 85353, 85743, 85803, 86073, 87639, 88623, 89079, 89145, 89355, 89523, 90144, 90153, 90198, 91248, 91605, 92214, 94695, 95154, 96702, 97779, 98055, 98802, 99066]
>>> len([i for i in range(99999) if len(set(str(i**2))) == 10])
87

- l0nwlf March 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sweet ... that's the way to go.

- Bullocks July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this works... but dunno if this is the optimal...
-----------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

void permute(char *a, int start, int end)
{
static int found = 0;
int idx = 0;
char tmp;
if(found == 0)
{
if(start == end)
{
long int number = strtol(a, NULL, 0);
float sqrtno = sqrt(number);
if((pow(sqrtno,2) - number)== 0)
{
printf("The 10 digit number is %ld is a perfect square and the square root is %f\n", number,sqrtno);

found = 1;
}
else
{
printf("The 10 digit number is %ld is not a perfect square\n", number);
}
}
else
{
for(idx = start; idx <= end; idx++)
{
tmp = a[start];
a[start] = a[idx];
a[idx] = tmp;

permute(a, start+1, end);

tmp = a[start];
a[start] = a[idx];
a[idx] = tmp;
}
}
}
}


int main()
{
char a[] = "1234567890";
permute(a, 0, strlen(a) - 1);
}

- Anonymous March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to the previous, I believe.

Find the 10 digit permutations. There are 10! permutations, but this is still much smaller than roughly 10^10 10 digit numbers.

Check each to see if they are a perfect square

digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

import math

def isPerfectSquare(num):
    s = math.sqrt(num)
    i = int(s)
    if ( (i*i) == num):
        return True
    else:
        return False
    
def permute(soFar, remaining):
    if not remaining:
        num = 0
        for d in soFar:
            num = num * 10 + d
        if isPerfectSquare(num):
            print num
        return
    
    for r in remaining:
        rem = [x for x in remaining if x != r]
        sf = soFar + [r]
        permute(sf, rem)

permute([], digits)

- Dave March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now that you're done with your code, maybe you can check out a solution from the above that does it in ... oh ... 23K? Why don't people think harder about problems before putting down code?

- Bullocks July 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<number/2;i++ ) {
Double y = pow(i,2); //i<<2
if(y > number ) continue ;
else if (y==number) prnt (true), break;
else break;

}

- Anonymous March 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for non repeated numbers ... it is
int j = number / 3^2 ;


and for this number, do the following


for(int i=0;i<number/2;i++ ) {
Double y = pow(i,2); //i<<2
if(y > number ) continue ;
else if (y==number) prnt (true), break;
else break;

}

- Anonymous March 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//C# code

class Program
{
static bool check(long num)
{
sbyte[] mas = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };
sbyte temp = 0;
while (num != 0)
{
temp=(sbyte)(num % 10);
if (mas[temp] == temp)
return false;
mas[temp] = temp;
num /= 10;
}
return true;
}


static void Main(string[] args)
{
long n, min = 31990, max = 99381;//sqrt(1023456789) and sqrt(9876543210)
for (long i = min; i <= max; ++i)
{
n=i*i;
if(check(n))
Console.WriteLine("num = {0}, i = {1}", n, i);
}

Console.ReadKey();
}
}

- topcoder April 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.*;
import java.util.*;

public class GoogTest{
	public static void main(String[] args) 
	{
		long startNum = 31991;
		long endNum   = 99381;
		for(long i=startNum; i<=endNum; i++){
			if(findRepeat(i)){
				System.out.println("I is "+ i);
				System.out.println(i * i);
			}
		}
	}
	public static boolean findRepeat(long n){
		long nsq = n * n;
		String num = Long.toString(nsq);
		
		boolean flag = false;
		ArrayList<Long> hm = new ArrayList<Long>();
		int m=0;
		for(int j=0; j< num.length(); j++){
			long r = nsq % 10 ;
			nsq/= 10;
			if(!(hm.contains(r))){
				hm.add(r);
				m++;
			}
		}
		if(m == num.length()) {
			return true;
		}else{
			return false;
		}
	}
}

- Geek September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why don't we use the basic mathematical way to find if a number is a perfect square or not.

The code below illustrates that:


#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;

void findNearest(char s[], char q[])
{
char s1[20];
int t = atoi(s);
cout << t << endl;
int val;
int x, y, xVal;
int temp;

for(int i = 0; i < 10; i++)
{
if(q[0] != '\0')
{
sprintf(s1, "%s%d", q, i);
x = atoi(s1) ;
}
else
{
x = i;
}

y = x * i;
if(y <= t)
{
val = y;
temp = i;
xVal = x;
}
}

sprintf(q, "%d", xVal + temp);

y = t - val;
sprintf(s,"%d",y);
}

bool PerfectSquare(char s[])
{
int l = strlen(s);
char s1[20];
char q[10];
q[0] = '\0';

if(l == 0) return false;

for(int i = 0; i < l;)
{
if( l % 2 != 0 && i == 0)
{
sprintf(s1, "%c", s[i]);
i++;
}
else
{
if(i == 0)
sprintf(s1, "%c%c", s[i], s[i+1]);
else
sprintf(s1, "%s%c%c", s1, s[i], s[i+1]);
i+=2;
}
findNearest(s1, q);
}
int x = atoi(s1);
if(x != 0)
return false;
return true;
}


int main(void)
{
char s[20];
cin >> s;
if(PerfectSquare(s))
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}

- jackass October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Zero value added question...!!!

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

int i; // assume i is 64 bit.
for ( i = 100000; pow(i,2) < 9,999,999,999; i++) {
cout<< Pow(i,2);
}

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

number of combinations for 10 digit number is 9*(10-1)*(10-2)*(10-3)*...*(10-9)=3,265,920

- guest January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think:
1. compute: sqrt(1000000000) = 31622.78 and sqrt(9000000000) = 94868.33;
2. from 31623 to 94868:
first compute the squire of every integer between this range;
check if the value is non repeated 10 digits, if yes, then put it in an array.
3. The result is the array
The total times of computation equals to 94868 - 31623 = 63245.

- rw7026 May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry guys, I made a mistake in my first steps instead of compute sqrt(9000000000), we should compute sqrt(9999999999). lol

- rw7026 May 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The smallest number with 10 digits will be 1023456789 and largest will be 9876543210
Start from any one number form these two..rotate right once only if 0 is not the leading digit and perform square root on it..if it an integer then that is the answer...hardly 9 rotations will be required

- A learner June 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-We need to find a number that is 10 digits long with non repeats, that means it has to be a permutations of the '0123456789' sequence.
-In python we use itertools.permutations to generate an iterable of all possible permutations of that sequence.
-Next we iterate through each element, convert it to an int (itertools.permutations iterables in form of tuples) and check wether it is a perfect square or not. For that we can write a small function that we can invoke to check in the form of : return int(sqrt(x))**2 == x

- badr August 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TenDigitNumPerfSquare {
	public static void main(String args[]){
		long i;
		boolean m=false;
		TenDigitNumPerfSquare t=new TenDigitNumPerfSquare();
		for(i=1000014128;i<9999999999L;i++){		
		if(Math.sqrt(i)==Math.round(Math.sqrt(i))){
			 m=t.good(i);
			}
			if (m==true){
				break;}		
		}	
	System.out.println("The number is" +i);
	}
	
	
	boolean good(long i){
		long num1L=i;
		boolean re;
		int count=0;
		int len=Long.toString(i).length();
		int[] arr=new int[len];
		for (int y=0;y<len;y++){
			arr[y]=(int)(num1L%10);
			num1L=num1L/10;
		}	
		for (int x=0;x<len;x++){
		for(int j=x+1;j<=len-1;j++){
			if (arr[x]==arr[j]){
				count++;
				break;				
			}}
		}
		if(count==0){
			return true;
		}else
		return false;
	}
	
}

- Raghavendra March 18, 2017 | Flag Reply


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