## Amazon Interview Question for SDE1s

• 0

Country: United States
Interview Type: Phone Interview

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

Just calculate index performing arithmetic operations.
Range is limited from 1 to 10000 so in my opinion arithmetic operations are best way.
Code:

``````public static int findIndex(int n) {
if (n < 10) {
return n - 1;
} else if (n < 100) {
return (n - 10) * 2 + 9;
} else if (n < 1000) {
return (n - 100) * 3 + 90 * 2 + 9;
} else if (n < 10000) {
return (n - 1000) * 4 + 900 * 3 + 90 * 2 + 9;
} else {
return 9000 * 4 + 900 * 3 + 90 * 2 + 9;
}
}``````

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

I understood the program, but was this according according to some formula and if yes, can you please mention the formula or the detailed logic.

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

This will fail to output the right index for "12" which is in 2nd if-else statement by your logic, but the program should actually input index as 0 .. since "12" first appears as 1234...

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

@ekta1007 you don't understand the question. It is not pattern matching.

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

@Nikhil Katre, I didn't use any sophisticated formula :) Here is simple explanation on example:
What we know:
1) There are 9 numbers consisting of 1 digit (range from 1-9)
2) There are 90 numbers consisting of 2 digits (10-99)
3) There are 900 numbers consisting of 3 digits (100-999)
and so on...
Now consider number 121. It is in range from 100 to 999 - 3 digits numbers
We have to compute how many digits consisting of 3 digits are located before this number - (n - 100) * 3
And add all remaining numbers 90 * 2 + 9
Hope this helps.
Here is more general solution for new requirements:

``````public static int findIndex(int n) {
int range = 1;
int numsBefore = 0;
int count = 0;
int temp = n;
while (temp > 10) {
int numsInRange = (int) (9 * Math.pow(10, count++) * count);
numsBefore += numsInRange;
range *= 10;
temp /= 10;

}
return (n - range) * (count + 1) + numsBefore;
}``````

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

To try to avoid the if statements and make it work for all N

``````static public int findIndex(int num)
{
int index = 0;
int divider = 1;
int factor = 1;

while (num / divider >= 10)
{
index = index + (divider * 10 - divider) * factor;
divider = divider * 10;
factor++;
}
// handle the last case
index = index + (num - divider) * factor;
return index;

}``````

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

You can use some basic string operations to get the index. Here i have used a string till 30 integers but it will work for N number of Integers too.

``````public static void main(String[] args) {
String input="123456789101112131415161718192021222324252627282930";
int index=21;
int j=1;
int k=0;
int l=1;
for(int i=0;i<input.length();i++){
String s1=input.substring(k, k+j);
if(Integer.parseInt(s1)==index){
System.out.println("Index is "+k);
break;
}
k=k+l;
if(Integer.toString(i+1).length()+1==Integer.toString(i+2).length()){
j++;
l++;
}``````

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

I have hardcoded value of string as well as the number (index) for which you want to know index.Don't confuse with it you can take input for these values too.

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

By the example, it seems the index begin with ZERO. (That is just a 1 value shift. :p)
There is just a simple formula to get the index.
0-9, just 1 char
10-99, 2 chars
100-999, 3 chars...etc..
So, for input number, you can calculate how many chars before it based on the range.

And BTW, it is more interesting if trying to find the first substring which present the number.
For example, input 202 should return 29 because "2021..." matching to 202.

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

what if its a really large number. What do you think is the best way. The substring method or the index calculation based on chars?
I wasn't quite sure what he was looking for and he wasn't giving more clues

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

well, if you consider number of digits as a parameter, the "202" problem can be overcome.

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

Slightly cleaner ( 1 fewer else statements )

public static int findIndex(int n)
{
if (n <= 10) {
return n - 1;
} else if (n <= 100) {
return (n - 10) * 2 + 9;
} else if (n <= 1000) {
return (n - 100) * 3 + 90 * 2 + 9;
} else {
return (n - 1000) * 4 + 900 * 3 + 90 * 2 + 9;
}
}

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

Actually the string can be upto any number N. Edited the question.

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

public static int indexOf(String str, int val) {

char[] a1 = str.toCharArray();
char[] a2 = String.valueOf(val).toCharArray();

int i = a2;
int j = (a1.length - a2.length);

for (int k = 0; k <= j; k++) {
if (a1[k] != i) {
do {
k++;
} while ((k <= j) && (a1[k] != i));
}

if (k <= j) {
int m = k + 1;
int n = m + a2.length - 1;
for (int idx = 1; (m < n) && (a1[m] == a2[idx]);) {
m++;
idx++;
}
if (m == n) {
return k;
}
}
}
return -1;
}

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

You can get number of digits of a number without converting it to string but I will do it that way because JavaScript.

If you have number of digits then your index can be calculated like this:

For example for index of 102 you have:

``````9 x 1 digit
(90) x 2 digits
2 x 3digits``````

which is equal

``(9*1)+(90*2)+(2*3)``

``````function indexOf(number){
var result = 0;
var digits = number.toString().length;
for(var i =1; i<digits; i++){
result += i * 9 * (Math.pow(10,i-1)) ;
}
var remaining = number - Math.pow(10, digits-1);
result += digits * remaining;

return result;
}``````

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

``````public static void getIndex(int number){
int numberLength = (int)(Math.log10(number)+1);
int index = 0;
for(int i=numberLength;i>;0;i--){
index = (int) (index + ((number - Math.pow(10,i-1)) * (i)));
number = (int) Math.pow(10,i-1);
}
System.out.println("Index :"+index);
}``````

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

This can be solve using following formula

Σ(9x10pow(i) ) + ((n-10.pow(d-1) ) x d) where i = 0 to i < d and d = no. of digits in n

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

Correction to earlier formula -

(Σ((9x10pow(i)).(i+1) )) + ((n-10.pow(d-1) ) x d) where i = 0 to i < d-1 and d = no. of digits in n

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

//d = No Of digits In Given number
//n = given number;
sum = 0;
while(d >0)
{
x = pow(10, d-1);
sum = sum + (n - x) * d;
n = x;
d--;
}

//sum gives the index position for given number in the string.

eg:
n = 1234
d = 4

sum = (1234 - 1000) * 4 + (1000 - 100) * 3 + (100 - 10) * 2 + (10 - 1) * 1

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

this will work -

``````public static int GetDigitax(int a)
{
if(a <= 0){ return -1;}
else
{
return GetDigitax(a - 1) + (a - 1).ToString().Length;
}
}``````

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

Hi,
What about if we have repetitive occurrences of the number, say 123 or 23, the I guess the first occurrence should be given as result.

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

just add the difference of the number N-10 and add to N to get the index value
ex:
for number 20, 20-10 = 10,add 20+10=30, so index is 29 and 30 for 20...

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

dim s:s="12345678910111213141516171819202122232425"

a=inputbox("enter a char:")

set oreg=new regexp
oreg.pattern=a
oreg.global=true

set omatch=oreg.execute(s)
For Each Match in omatch ' Iterate Matches collection.

if omatch.count<>0 then
exit for
end if

Next

msgbox "count is : "& omatch.count & "index is : " &match.firstindex
set oreg=nothing

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

rurururu

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

If we need to find the index of 20. Then find the first occurrence of the string "202122" /"2021" (the number || next number) which will be always unique.

``````public static void main(String[] args) {
String givenString ="123456789101112131415161718192021222324252627282930";
int index = givenString.indexOf("202122");
System.out.println(index);
}``````

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

public class FindIndex {

public static void main(String[] args) {
String str="";
for(int i=1;i<=1000;i++)
{
str+=i;
}
System.out.println("index of 20 is : "+str.indexOf("20"));
}

}

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

#include<iostream>

using namespace std;

int main(){
int result =0;
int div=10;
int count=2;

if(index<10)
{
result = index-1;
}
else
{
//find the greatest divisor
while(index/div>10)
{
div*=10;
count++;
}
//caluculate index for that specific position
result += (index-div)*count;
//keep on reducing divisor and generating rest of index
while(div!=1)
{
div/=10;
count--;
result+=(9*div)*count;
}
}
cout<<result;
return 0;
}

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

The logic depends over the number to be searched.
There are 9 numbers with one digit (1-9).
There are 90 numbers with two digit (10-99);
There are 900 numbers with two digit (100-999);
So the serach should start from 10 to power(n-1) where n is the number of digits in the number to be searched.

Please note that 10 to power (n-1) show the start range which will occupy *n number of index for each number from here.
((Num-(10* to power (n-1))) *n) will give the index which a number will occupy from this starting range of its range.

So to get the index of a number, we can use the formula
Index=10 to power (n-1) + ((Num-(10* to power (n-1))) *n) -1 [as array index start from 0]

Example: If we have to search 25,
Index=10 to power (2-1)+((25-(10 to power (2-1)))*2) -1
Index=10 to power 1 + ((25-10 to power 1))*2) -1
Index=10+((25-10)*2) -1
Index=10+30-1=39

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.