## Google Interview Question for Software Engineer / Developers

Country: United States

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

I didn't see a solution in this direction.

Python:

``````def getDigit (index):
digits = 0
min = None
max = -1
while (True):
digits += 1
min = max + 1
max = int ('9' * digits)
size = (max - min + 1) * digits
if (size > index):
break
index -= size
number = min + (index / digits)
digit = index % digits
return int (str(number)[digit])``````

Unit tested every index from 0 to 38890. aka numbers 0 to 9999 and it seems to be good.

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

Can you please explain the logic behind the algorithm?

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

nice solution :-)

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

is there a name for this algorithm or somewhere where this draws from? it's really quite nice...only 5 loops for the 38,890th character.

Comment hidden because of low score. Click to expand.
6
of 10 vote

the digits sequence is like 10,90*2,900*3,9000*4...
so it can be done iteratively

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

I think the idea is to return a single digit without having to generate the whole sequence since the sequence can be infinite and you can be asked for the position 1 million for instance.

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

I didn't mean you need to generate all the sequence. instead, you can base on this fact to calculate the bit. say 14, 14-9=5, it means the fifth digit of the two-digit number. 5/2=2, 5%2=1;
so it's the 1st digit of 10+2.

check the code below
public static int res(int x){
int count=2,base=90;
if(x<10) return x;
x-=10;
while(x>=base*count){
x=x-base*count;
count++;
base*=10;}

int res=x/count+base/9;
int s=count-x%count-1;
int bit=(res/((Double)Math.pow(10,s)).intValue())%10;

return bit;
}

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

this is a quick implementation of this strategy

``````public void printDigit(int num){
int numDig = 1;
int base = 1;
int current = 1;

System.out.println("base: "+ base+", current: "+current);
numDig++;
}
numDig--;

int additionalDigits = (num - current)%numDig;
int additionalNumbers = (num - current)/numDig;

System.out.println(base + ", " +numDig);

char[] theNumberDigits = new String(""+(base + additionalNumbers)).toCharArray();

System.out.println("The digit is: " + theNumberDigits[additionalDigits]);
}``````

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

``````private int digitAtIndex(int index){

if( index < 10 ){
return index;
}

index -= 10;

int seqValue = 10;
int multiplier = 10;

while( true ) {

int tempValue = seqValue;
int tempMultiplier = multiplier;
int digit = -1;

while( tempMultiplier > 0 && index >= 0 ){

digit = tempValue / tempMultiplier;

tempValue = tempValue % tempMultiplier;
tempMultiplier = tempMultiplier / 10;

--index;
}

if( index < 0 ){
return digit;
}

++seqValue;

if( seqValue / multiplier > 9 ){
multiplier *= 10;
}
}
}``````

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

brilliant dude

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

Whats the logic that you have used here?

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

My Algo Goes here.

1> float value= Index / 20;
2> if(index=="Even") {
if(value.decimals() is between 0.00 to 0.49)
{
cout<<"Value is "<<floor(value)
} else {
cout<<"Value is ""<<Celing(value);
}
}
3> if(index=="odd")
if(value.decimals() is between 0.00 to 0.49)
{
int least_index=index%20;
// Use following mapping
if (least_index==1)
cout<<"Value is 0"<<endl;
if (least_index==3)
cout<<"Value is 1"<<endl;
if (least_index==5)
cout<<"Value is 2"<<endl;
if (least_index==7)
cout<<"Value is 3"<<endl;
if (least_index==9)
cout<<"Value is 4"<<endl;
} else {
if(value.decimals() is between 0.50 to 0.99)
{
int least_index=index%20;
// Use following mapping
if (least_index==1)
cout<<"Value is 5"<<endl;
if (least_index==3)
cout<<"Value is 6"<<endl;
if (least_index==5)
cout<<"Value is 7"<<endl;
if (least_index==7)
cout<<"Value is 8"<<endl;
if (least_index==9)
cout<<"Value is 9"<<endl;
}
}

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

JAVA code. I have not gone through all the above replies. Sorry, if a similar code is already posted.

public static void main(String[] args) {
long n = Long.parseLong(args[0]);
double num = 0;
double pos = 1;

while(pos<n){
num++;
pos = pos + (Math.floor(Math.log10(num))+1);
}

long y = (long)((pos-n)+1);
// System.out.println(""+(long)num+", "+y);

long num_long = (long)num;
String num_str = Long.toString(num_long);

long digit = (num_long%((long)(Math.pow(10,y))))/(((long)Math.pow(10,y-1)));
System.out.println(""+digit);
}

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

This worked for me up to n ~ 10^11 range of numbers.

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

We can think in this way:
0-9 only digits means 10 single digits
10-99 90 double digits

So if i need to find out digit at 19 position then,
19 - (10 * single digits) + 1
left part is 10
divide 10/2 note: divide by 2 because no of digits is 2
add 9(biggest number in single digit) + 5 = 14
result will be 4.

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

``````int TellNumInSeq(int index) {
index = index - 1;
if (index <= 0)
return -1;
//Special Case
if (index <= 10)
return index;
if ((index % 2) == 0)
return ((index - 10) / 2) % 10;
return ((index / 20) % 10) + 1;
}``````

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

If you pass the index 99 to your method it will return 44, you should return a single digit and for the case of 99 the correct answer is 4.

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

Hmm i'll work on it.

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

How about now.. It's working for 99 atleast.

Its working for these..
index = 30, result = 2
index = 31, result = 0
index = 1000, result = 3

But for 100 it fails ... it gives 9 instead of 5...
I cant figure out why
As far as i can think of 100 should be 9

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

Finally got it to work ... it passes all test cases..

tested for 30,31,1000,100,99,1,9999

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

Is the code you have there working for all these cases?

With the code you currently have, In my testing index 1000 returns 10. The result must always be a single digit.

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

If you are interested in only the digit from the sequence then we can use pointer arithmetic on the string.

``````int getDigit(char* string, int position)
{
int digit = -1;

if ( NULL != string && position >= 0 )
{
char *ch = string + position;
if ( '0' <= *ch && *ch <= '9')
digit = (int) *ch - '0';
}
return digit;
}``````

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

sweet and simple

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

The string doesn't exist

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

This works for all two digit number sequences, but things start falling apart after that. Specifically, all tests pass until index 191, but not beyond.

Does anyone have suggestions?

``````public class IndexOnInfiiniteNumber {

public static void main(String args[]) {
int idx = 1000;
System.out.println("Answer must be: " + verifier(idx));
System.out.println("Actual Answer is: " + calcNumberAtIndex(idx));
}

public static char verifier(int idx) {
String str = "";
int count = 0;
if (idx < 0) {
throw new RuntimeException("Can not be a negative number");
}
while (str.length() <= idx) {
str += count++;
}
for (int i = 0; i < str.length(); i++) {
System.out.println(i + "->" + str.charAt(i));
}
return str.charAt(idx);
}

public static long calcNumberAtIndex(long idx) {
if (idx < 0) {
throw new RuntimeException("Index can not be negative");
}
if (idx < 10) {
return idx;
}
long distanceFrom10 = (idx - 10) / 2;
long number = 10 + distanceFrom10;
System.out.println("Number at index calc as: " + number);
long numDigits = howManyDigits(number);
long factor = (long) Math.pow(10, numDigits - 1);
if (idx % 2 == 0) {
return number / factor;
} else {
return number - ((number / factor) * factor);
}
}

public static long howManyDigits(long number) {
long numDigits = 1;
if (number < 0) {
number = number * -1;
}
while (number >= 10) {
number = number / 10;
numDigits++;
}
return numDigits;
}
}``````

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

``````This is giving the correct answer but is worst time possible

int TellSeq(int index) {
int i = 0, j = 0, k = 0;
for (; i < 10; i++) {
cout << "\n" << (i + 1) << " " << i;
if (i+1 == index)
return i;
}
index--;
for (i = 10; i <= 65532; i++) {
if (i % 2 == 0) {
cout << "\n" << (i + 1) << " " << (j++) % 10 << " ";
if (i + 1 == index)
return j % 10;
if (j % 10 == 0)
k++;
} else {
cout << "\n" << (i + 1) << " " << (k) % 10 << " ";
if (i + 1 == index)
return k % 10;
}
}
}``````

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

public static int each(int length){
if(length < 0) return 0;
if(length == 0) return 1;
else return 9*((int) Math.pow(10, length-1))*length;
}

public static String getNumber(int index){
if(index < 0) return null;
int length = 0;
while (true){
int temp = index -each(length);
if(temp >= 0){
index=temp;
length++;
}
else {
if(length == 0) return Integer.toString(index);
else {
int number =(index/length)+(int)Math.pow(10, length-1);
int pos = index%length;
String svalue = Integer.toString(number);
String value =svalue.substring(pos, pos+1);
return value;
}
}
}
}

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

``````int getDigit(int index)
{
int i=1, base=0;

while(1) {
if(index - (9*exp(10,i-1)) * (i)) < 0)
break;
index -= (9*exp(10, i-1) * i);
base += 9*exp(10,i-1);
i++
}

int val = base + index / i;
if(index % i == 0)
return val % 10;
else
return ((val+1) / (10 * (i - index % i))) % 10;
}``````

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

``````public class CountTest {
StringBuffer sb = new StringBuffer();

public String generateSequence() {
for (int i = 0; i < 1000; i++) {
sb.append(i);
}
System.out.println(sb.toString());
return sb.toString();
}

char getDigitAt(String seq, int index) {
char[] chars = seq.toCharArray();
return chars[index];
}

public static void main(String[] args) {
CountTest test = new CountTest();
String seq = test.generateSequence();
System.out.println(test.getDigitAt(seq,5));//5
System.out.println(test.getDigitAt(seq,13));//1
System.out.println(test.getDigitAt(seq,19));//4
System.out.println(test.getDigitAt(seq,100));//5
System.out.println(test.getDigitAt(seq,30));//2
System.out.println(test.getDigitAt(seq,31));//0
System.out.println(test.getDigitAt(seq,1000));//3
}
}``````

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

``````public static int getKthDigit(int k)
{
boolean possible = k > 9;
int i = 0;
while (possible)
{
if (k > ((i + 1) * 9 * (Math.pow(10, i))))
{
k = k - ((i + 1) * 9 * (Double.valueOf(Math.pow(10, i)).intValue()));
i++;
}
else
{
possible = false;
}
}
int left = k % (i + 1);
k = k / (i + 1);
for ( int j = 0 ; j < i ; j++)
{
k = k + (9 * (Double.valueOf(Math.pow(10, j)).intValue()));
}
if (left == 0) {
return k % 10;
}
k++;
return Integer.valueOf(String.valueOf(String.valueOf(k).charAt(left - 1)));
}``````

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

Tricky but works for sure.

``````public class StringBuilderExample {
StringBuilder sb = new StringBuilder();

StringBuilderExample() {
for (int i = 0; i<1000; i++) {
sb.append(i);
}
System.out.println("sb = " + sb);
}

public int getByIndex(int index) {
System.out.println("-- digit at " + index + " = " + sb.charAt(index));

if (index == 0) return '0';
int nd = 1, pre_nd = 0;
int i = 0;
while (index > nd) {
pre_nd = nd;
nd += 9 * Math.pow(10, i) * (++i);
}

int r = (index +1 - pre_nd) % i;
int number = (int)Math.pow(10, i-1) -1 + (index+1 - pre_nd) / i;

if (r == 0) return number%10;
else return (++number / (int) Math.pow(10, i-r)) % 10;
}

public static void main(String[] args) {
StringBuilderExample s =new StringBuilderExample();
System.out.println("digit at 19 = " + s.getByIndex(19));
System.out.println("digit at 100 = " + s.getByIndex(100));
System.out.println("digit at 30 = " + s.getByIndex(30));
System.out.println("digit at 1000 = " + s.getByIndex(1000));
System.out.println("digit at 31 = " + s.getByIndex(31));
System.out.println("digit at 1215 = " + s.getByIndex(1215));
}``````

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

``````#include<stdio.h>
int base [1000];

int turnBase()
{
for(int i = 0; i<1000 ; i++)
{
if(base[i]==-1)
{
return i-1;
}
}
return 1000;
}

void checker()//
{
for(int i = 0 ; i< turnBase()+1 ;i++)
{
if(10==base[i])
{
base[i] = 0;
if(base[i+1] != -1)
base[i+1]=base[i+1]+1;
else
base[i+1]=1;
}
}
}

int getNumber(int value)
{
int j=0;
for(int i = 0 ; i<1000 ; i++)
base[i]= -1;
do{
base[0] = base[0]+1;
if(base[0]==10)
checker();
for(int k = turnBase() ; k>=0; k--)
{
if(j==value)
{
return base[k];
}else
{
j++;
}
}
}while(true);
}

main()
{
getNumber(19);
return 0;
}``````

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

``````int GetDigit(int index){
if(index < 10){
return index;
}
int base = 10, i = 90, j = 2;
while(index >= base + i * j){
base += i * j;
i *= 10;
j++;
}
int num = base + (index - base) / j;
int numi = (index - base) % j;
for(int k = j - 1; k > numi; k--){
num /= 10;
}
return num % 10;
}``````

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

This has a bug when you get to 3 digit numbers

``````GetDigit(186)=9, correct=9
GetDigit(187)=8, correct=8
GetDigit(188)=9, correct=9
GetDigit(189)=9, correct=9
GetDigit(190)=1, correct=1
GetDigit(191)=9, correct=0 Wrong!
GetDigit(192)=0, correct=0
GetDigit(193)=1, correct=1
GetDigit(194)=9, correct=0 Wrong!
GetDigit(195)=1, correct=1
GetDigit(196)=1, correct=1``````

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

I found this one a little tricky. Took me a bit of experimentation to work out the transition between the number of digits.

There may be more efficient patterns, but this worked for me.

As others have mentioned, the basic pattern is:

10 x single digits (or 9 plus a 0 if it helps you)
90 x double digits
900 x triple digits
and so on.

Another way of thinking about that is
1 + 9 x 10**0 + 9 x 10**1 + 9 x 10**2 ... + 9 x 10**n

So to work out how many digits are in the number you're grabbing the index of:

you have n+1 digits where n is the power you're applying to 10 i.e.(9 x 10**n)

so applying that to our index,
index =
0-9 - 1 digit (10)
10-189 - 2 digits (2x90 + 10)
190 - 2890 - 3 digits (3x900 + 2x90 + 10)

Now to work out specifically which number we're dealing with, we take the index plus the count of numbers that have come in each band before, then divide by the number of digits

For example, let us say we want the number at index 203

we had 10 matches up to 10, 100 matches up to 190 so we add 110 to 213 then divide by three to get the actual number

323 / 3 = 107
use mod 3 to find out which position in the number you're returning
107 % 3 = 2

That being the case, we return 7 (index 2 of 107)

Here's the implementation in ruby:

``````def getIndex(index)
return index if index < 10

digit_count = 1
decimal_unit = 1
index_comparison = 1
difference = 0

while index > ( index_comparison + decimal_unit * digit_count * 9 )
index_comparison += decimal_unit * digit_count * 9
difference += 10 ** digit_count
decimal_unit *= 10
digit_count += 1
end

actual_number = (index + difference) / digit_count
position = (index + difference) % digit_count

return actual_number.to_s.slice(position).to_i
end``````

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

int calculateIndex(int index)
{
int mult=10;
int num=2;
int offset=0;
int prev=10;

if (index<11) return index-1;

while(1)
{
int base= 9*mult;
int range= base*num + prev;

if(index<range)
{
offset=index-prev;
if(offset%num==0)
{
int indexNumber= mult+(offset/num)-1;
return getlastdigit(indexNumber);
}
else
{
int indexNumber= mult+(offset/num);
int indexposition= num-(offset%num)+1;
return getdigit(indexposition,indexNumber);
}
}
mult=mult*10;
num=num+1;
prev=range;
}

return -1000;

}

int getlastdigit(int x)
{
return x%10;
}

int getdigit(int x, int y)
{
int digit;
int i=1;
while(y!=0)
{
digit=y%10;
y=y/10;
x=x-1;
if(x==0)
return digit;
}
}

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

``````/* Given a stream of numbers and index, find the digit at that index
* e.g. 01234567891011121314 index = 15, answer is 1 (of 12)
*/

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

/* Function to find number of digits */
int findNoOfDigits(int* index)
{
int no_of_digits = 1;
if(*index <= 10)
{
return no_of_digits;
}
int num = 90;
int temp = *index - 10;
*index = temp;
while(temp > 0)
{
no_of_digits++;
temp -= (num * no_of_digits);
if(temp < 0)
{
break;
}
*index = temp;
num *= 10;
}
return no_of_digits;
}

/* Function to find value at some position */
int position(int index)
{
int no_of_digits = findNoOfDigits(&index);
printf("%d %d\n", no_of_digits, index);

if(no_of_digits == 1)
{
return index - 1;
}
else
{
int temp = no_of_digits - 1;
int num  = pow(10, temp);
int rem = index % no_of_digits;
int quotient = index / no_of_digits;
num += quotient;
if(rem == 0)
{
return (num % 10);
}
else
{
int digit;
int count = no_of_digits + 1 - rem;
while(count > 0)
{
count--;
digit = num % 10;
num = num / 10;
}
return digit;
}
}
}

/* Main driver function */
int main(void)
{
int index;
scanf("%d", &index);
printf("\n");
printf("%d",position(index));
getch();
return 0;

}``````

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

applies for all p > 10

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

p = position
v = value

formula: v = p/2 + 5

example:
p = 30
v = 30/2 + 5 = 15 + 5 = 20

if v returns an int, take leftmost digit of v, so answer is 2.

if v returns a float, take rightmost digit of int(v). Example:

p = 31
v = 31/2 + 5 = 15.5 + 5 = 20.5

right(int(v)) = right(int(20.5)) = right(20) = 0

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

applies for all p > 10

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

Here is the pseudo code implemented:
Should be understandable.

``````int getDigit (int index) {

digitsCount = 0;
digitOnes = 0;
min = 0;
max = -1;
while (True) {
digitsCount += 1;
digitOnes = (10*digitOnes) + 1;
min = max + 1;
max = 9 * digitOnes;

size = (max - min + 1) * digitsCount;
if (size > index)
break;

index = index - size;
}

number = min + (index / digits);
digitPositionFromLeft = index % digits;

digitPositionFromRight = (digits - digitPositionFromLeft);
number = ( number / pow(10, digitPositionFromRight) );
return (number%10);
}``````

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

(pseudo-code only )
Say, the index value (started from 0) corresponds to (is one bit of) the original number Num.
We try to get the number of digits (n) for Num.

``````pair<int, int> GetBits (int index) {
int digits = 0;
int sum_of_digits = 0;
int pre_sum_of_digits;
while (sum_of_digits < index - 1) {
// we use index - 1 is because the array starts from 0.
++digits;
pre_sum_of_digits = sum_of_digits;
sum_of_digits += (pow(10, digits) - pow(10, digits - 1)) * digits;
}
return pair<int, int>(digits - 1, pre_sum_of_digits +1); // we add the index 0
}``````

Then for the total number of digits until Num, we have the following equation:

``total_digits = pre_sum_of_digits + (Num - 10^(digits - 1) + 1) * digits``

And what we need is:

``index <= total_digits``

we can solve the above equation to get Num.

``````int GetNum (int index, int digits, int pre_sum_of_digits) {
int Num = ceil((double)(index - pre_sum_of_digits) / digits) + pow(10, (digits - 1)) - 1;
return Num;
}``````

Then, we need to refine and get the specific digital value we want.
we first convert Num to a string and select the right one we want.

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

Solution in C++:

``````#include<iostream>
#include<cmath>

using namespace std;

int getDigit(int p)
{
int n = 1, c = -1;
while(true)
{
for (int i = (n==1?0:pow(10, n-1)); i < pow(10,n); ++i)
{
c += n;
if (c >= p)
{
int loop = c-p+1, digit;
while (loop-- > 0)
{
digit = i % 10;
i = i / 10;
}
return digit;
}
}
++n;
}
}

int main(int argc, char* argv[])
{
cout << "index = 100, result = " << getDigit(100) << endl;
cout << "index = 30, result = " << getDigit(30) << endl;
cout << "index = 31, result = " << getDigit(31) << endl;
cout << "index = 1000, result = " << getDigit(1000) << endl;
}``````

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

``````#include <iostream>

using namespace std;

int getdigit(int n)
{
int weight[]={10, 180, 2700, 36000, 450000, 5400000};
int add[]={1, 10, 100, 1000, 10000, 10000, 100000};

if(n<=10) return n-1;
int i=0;
while(n/weight[i]>=1)
{
n-=weight[i];
i++;

}
int len=i+1;
cout<<"len: "<<len<<endl;
int d[len];
for(int j=0; j<len; j++)
{
cout<<"n:  "<<n<<endl;
if(j==0)  d[j]++;
}
return d[n];

}
int main()
{
cout <<getdigit(1000) << endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*i m showing just for index 100 this way u can do same for any index/*
#include<iostream>
#include<sstream>
#include<string>

using namespace std;

int main(){

string s;
cin>> s;
cout << s[100] << endl;
return 0;
}

Comment hidden because of low score. Click to expand.

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.