Adobe Interview Question Software Engineer / Developers
actually, among the numbers that is less than 1000, only 999, 989, 998, 899 have the sum larger than 25. As such, the answer is very straight forward.
i don't think there's a clean mathematical solution here. the result matrix is quite messy.
based on simple Math, you can nail down all the possible values are between (1000, 1000) and (1698, 1698) as any move below 1000 need to go through either x on 999 or y on 999, not allowed, any move beyond 1698 need to go through 1699 either on x or y.
after narrow that down, all I can do is to write a simulator to calculate the possibilities.
the number i had is 147451
import java.io.*;
public class antInMatrix{
public static int doAntCrawl(int[][] m) {
int count = 0;
for (int i = 0; i < 699; i++) {
m[i][0] = 1;
m[0][i] = 1;
}
for (int i = 1; i < 699; i++) {
for (int j = 1; j < 699; j++) {
if (m[i-1][j] == 1 || m[i][j-1] == 1) {
if (sum(i,j) <= 25) {
m[i][j] = 1;
count ++;
}
}
}
}
System.out.println(count);
for (int i = 699; i >1; i--) {
for (int j = 699; j >1; j--) {
if (m[i+1][j] == 1 || m[i][j+1] == 1) {
if (sum(i,j) <= 25 && (m[i][j] == 0)) {
m[i][j] = 1;
count ++;
}
}
}
}
System.out.println(count);
return count;
}
public static int sum(int i, int j) {
return i/100 + (i%100) /10 + i%10 + j/100 + (j%100) /10 + j%10 + 2;
}
public static void main(String[] argv) {
int[][] m = new int[1000][1000];
doAntCrawl(m);
for (int i = 0; i < 1000; i ++) {
for (int j = 0; j < 1000; j++) {
if(m[i][j] > 0) {System.out.print(1);} else {System.out.print(0);}
}
System.out.println("P");
}
}
}
your solution also adds points which could be accessible to the ant but there is no way to that point. For example (1550,1670) satisfies the condition but there is no path to this point as all adjacent points are inaccessible.
I think recursive solution should be good enough. where you call function recursively for 4 adjacent points so that there is always path to these points. and keep track of points in a 2d array for duplicity. answer I got is 148848.
#include<iostream>
#include<cmath>
using namespace std;
int pcount;
int points[2000][2000];
int sumDig(int x){
int sum = 0;
do {
sum += x % 10;
x = x / 10;
} while (x > 0);
return sum;
}
void doCount(int x, int y){
if (sumDig(x) + sumDig(y) > 25) // check the constraint.
return;
if (::points[x][y] == 1) // check for duplicate.
return;
::points[x][y] = 1;
::pcount++;
doCount(x - 1, y);
doCount(x + 1, y);
doCount(x, y - 1);
doCount(x, y + 1);
return;
}
int main()
{
::pcount = 0;
for (int i=1000; i<1700; i++)
for (int j=1000; j<1700; j++)
::points[i][j] = 0;
doCount(1000, 1000);
cout << "number of points ant can walk to is: " << ::pcount << endl;
return 0;
}
Let's say N(x,y) be the number of points the ant can access if it starts at (x,y).
Since the ant starts at (x,y), the point itself is certainly accessible.
In a procedure form,
N(x,y){ // sum(x) represents the sum of the digits in x
if(sum(x) + sum(y) > 25)
return 0;
return 1 + N(x-1,y) + N(x+1,y) + N(x,y-1) + N(x,y+1);
}
run the program for (1000,1000) to get the answer. Haven't taken care of the edge cases here ,e.g. when x = 1 or max_row ,y=1 or max_col etc. Those checks need to be put in the above algo.
You need to take care of certain issues.The solution you just posted does not terminate. It will end up calling the same function again and again. N(1000,1000) will call N(1000,1000) again. So dfs does not work here.Instead use a queue and keep track which states have been visited
this solution don't work
reason is
return 1 + N(x-1,y) + N(x+1,y) + N(x,y-1) + N(x,y+1);
so for (1000,1000)it will return
1+N(999,1000)+N(1001,1000)+N(1000,999)+N(1000,1001)
fine
but check the case of N(1001,1000)
it will return 1+N(1000,1000)+N(1002,1000)+N(1001,999)+N(1001,1001)
and also case N(1000,1001)
it will return
1+N(1001,1001)+N(1000,1000)+N(999,1001)+N(1000,1002)
so we are counting N(1000,1000) , N(1001,1001) twice
there are many such repeated inclusions in final ans you get.
algorithm goes as follows...
1>initially x=1000,y=1000; so ant can not goes below the line x=1000( becoz below this x has value 999 i.e. >25) and left of y=1000( becoz of the same reason)
2> int count=0;
3>while ( y_access >0){
count=count+ y_acess(x, y);
x=x+1;
}
/// y_access is the function which return the max y value which can be accessed //keeping x const;
nyone need complete code ?
How about this
static count = 0;
void calculatePoints(int p1,int p2)
{
if(sumof(p1) + sumof(p2) >25)
{
return;
}
else
{
count++;
if(sumofdigits(p1) >25 )
p1 = p1-1;
else if(sumofdigits(p2) >25)
p2 = p2-1;
calculatePoints(p1,p2);
}
}
though it will take a hell lot of time to get completed..
@aditi your solution have some errors.
Lets consider mid point of 1000,1698 and 1698,1000 which is (1349,1349). Sum of this point is 34 which should not be accessible to the ant. and there are lot of points too.
So only solution I see is using Dynamic programming. Have an array of (699,699)
A[i][j] = co-ordinate i,j is accessible.
A[0][*]=1;
A[*][0]=1;
loop through 1 to 698;
A[i][j] = ((sum of digit of i + sum of digit of j) < 25) && (A[i-1][j] || A[i][j-1])
Hi,
As it is clear that the ant cant move left or below (1000, 1000). The working java code is as follows:
public class CalcPossibleMoves {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(calc(1000, 1000));
}
private static long calc(int x, int y) {
long count = 0;
for(int i = x; ; i++) {
if(sumDigits(i) + sumDigits(y) > 25) {
break;
}
for(int j = y; ; j++) {
if(sumDigits(i)+ sumDigits(j) > 25) {
break;
} else {
count++;
}
}
}
return count;
}
private static int sumDigits(int num) {
int sum = 0;
while(num != 0) {
sum += num % 10;
num = num / 10;
}
return sum;
}
}
I think there would be a good mathematical solution to this problem. But we can solve it in another way. Simply run a bfs from (1000,1000) until the queue becomes.While you dequeue from the queue keep incrementing the number of points visited.
- python.c.madhav November 01, 2010