aka
BAN USERBFS won't work here but I think djikstra should work.
Here BFS is implemented in below code where input is 0,0 and target is 7,7.This program outputs 14 instead of 8.
#define SIZE 7
#define INFINITY 9999
struct q_i{
int i;
int j;
};
struct queue{
struct q_i q[100];
int size;
};
typedef struct queue qu;
int distance[100][100]={0};
void enq(qu *q, int i, int j)
{
q->q[q->size].i = i;
q->q[q->size].j = j;
q->size++;
}
struct q_i *deq(qu *q)
{
q->size--;
return &q->q[q->size];
}
int iE(qu *q)
{
return q->size?1:0;
}
int po[] = {1, -1, 1, 1, -1, -1, -1, 1};
int main()
{
int i, level=0,j;
qu *q=malloc(sizeof(qu)*100);
memset(q, 0, sizeof(qu)*100);
for(i=0;i<100;i++)
for(j=0;j<100;j++)
distance[i][j]=INFINITY;
enq(q, 0, 0);
distance[0][0] = 0;
while(iE(q)) {
int i, j, x_, y_;
struct q_i *e = deq(q);
printf("%d %d\n", e->i, e->j);
x_ = e->i;y_=e->j;
if(e->i == 7 && e->j == 7) {
printf("found %d\n", distance[7][7]+1);
return;
}
for(i=0;i+1<sizeof(po)/sizeof(po[0]);i+=2) {
int x, y;
x=x_+po[i];
y=y_+po[i+1];
if(x >= 0 && x < 8 && y >= 0 && y < 8) {
if(distance[x][y] == INFINITY) {
distance[x][y] = 1+ distance[x_][y_];
enq(q, x, y);
}
}
}
}
return 0;
}
@Dumbo: My algo also works the same but it doesn't work for all the cases.
I am also 100% sure that your algo will fail for some inputs.Sorry but can you try for below as well.
Input: 1,1
output: 8,8
Do you know of any online compiler where I can just copy paste your code and try different inputs?
I somehow feel that this should work but it is not working for all the inputs,howeever if you anyone has some corrections to make in this code than i WILL really appreciate.
#include <limits.h>
/* below is i and j target*/
#define T_I 0
#define T_J 4
#define TARGET(i, j) ((i==T_I && j== T_J)?1:0)
int min(int a, int b)
{
return a>b?b:a;
}
int track[100][100]={0};
int foo(int i, int j)
{
int value1, value2, value3, value4;
value1=value2=value3=value4=0;
if(i<0||j<0 ||i>7||j>7)
return 99999;
if(track[i][j]==1)
return 99999;
track[i][j]=1;
if(TARGET(i, j)) {
track[i][j]=0;
return 1;
}
value1 = 1+ foo(i+1,j+1);
value2 = 1+ foo(i-1,j-1);
value3 = 1+ foo(i+1,j-1);
value4 = 1+ foo(i-1, j+1);
track[i][j]=0;
return min(value1, min(value2, min(value3, value4)));
}
int main()
{
/* starting point is 1,1*/
printf("output %d\n", foo(1, 1));
}
Just use two pointers as explained by Dumbo and replace in the below program '_' with ' '.
'_' is used to see the output clearly.
#include <stdio.h>
void swap(char *s, char *d, int s_c, int d_c){
char temp = s[s_c];
s[s_c] = d[d_c];
d[d_c] = temp;
}
int main()
{
char string[] = {"__algor__rith_m_"};
char *s_p, *d_p; /* s_p is space pointer pointing to space */
/*d_p is data pointer pointing to any non-space */
int i, s_p_c, d_p_c;
/*s_p_c points to the space character which we are working on currently */
/*d_p_c points to the non-space character which we are working on currently */
s_p = string;
d_p = string;
s_p_c = strlen(string)-1;
d_p_c = strlen(string)-1;
while(s_p_c>=0 && d_p_c>=0){
while(s_p_c >= 0 && s_p[s_p_c] != '_'){
s_p_c--;
}
if(s_p_c <= 0)
goto end;
d_p_c = s_p_c-1;
while(d_p[d_p_c] == '_'){
d_p_c--;
}
if(d_p_c <= 0)
goto end;
swap(s_p, d_p, s_p_c, d_p_c);
s_p_c--;
d_p_c--;
}
end:
printf("%s\n", string);
}
@NAX: Though you have written the program and it works pretty well, but it is of no consequence to anyone as the logic behind this (i.e. how it works?) is not mentioned by you and is not apparent either, which is by the way is very important rather than this code!!!People can write code in whatever language they want if they know the strategy, can't they?
Strategy:
As we all know what is Arithmetic progression right?If not, then have a look at this en.wikipedia.org/wiki/Arithmetic_progression, so basically the logic used here comes from this arithmetic progression.
What NAX is doing is this:
He is increasing the counter(i+=2) in such a way that it becomes an arithmetic progression and which he is cleverly subtracting (n-=i) with the given number such that if the number is a square then the end result becomes 0.
To put in succinctly :
N=25
Output of the program:
[25] 1 = 24 (25-1)
[24] 3 = 21
[21] 5 = 16
[16] 7 = 9
[9] 9 = 0
and if you notice properly-
1,3,5,7,9 is arithmetic progression and it sums up to (5*(1+9))/2=25
So effectively we are subtracting 25 from 25 and showing the results, however it will not work for non-square number right?Hope you understood why it won't work for non-square number.
Why we can't simply store all the perfect squares in an array(What do you think about this size of array-it won't be big me thinks).
Now all we need to do is to find out if the given number exist in the array or not.That can be simply done by binary search.
array[] - {2,4,16,25,36,49,64,81,100,121,169,196,225.......}
This would be the fastest but I think this is not the answer your interviewer was looking for or is it?
@up: just to make it better.
- create a NxN matrix of doubles (or whatever the range of our values can be)
- on the diagonal put the i-th number of our array
- [0][0] is simply the first value in the array (the product in the range (0,0) inclusive)
- product [i][j] will be [i][j-1]*A[j]
- after the first row is populated.For second row start from 1,1 and do the same things as done for row 0.For third row start from 2,2 and so on....
In the end find the maximum by searching in the entire N*N matrix or when you are multiplying keep the max found till now in a variable and print it in the end.
@arun_lisieux: we don't even need any flag also.
I/P: I am a software programmer
A. Start from end i.e. 'programmer'.Print the last word.
B. Start reversing the alternate words. So you would reverse 'software' & 'am'.For reversing words just use stacks or whatever you want.
So output:
"programmer erawtfos a ma I"
@chris: here you go, i knew your code have bugs and here are below cases which fails.
{
{1, 2, 1, 1, 1, 1, 1, 1},
{2, 3, 4, 5, 1, 1, 1, 1},
{3, 2, 1, 6, 1, 1, 1, 1},
{4, 3, 4, 5, 1, 1, 1, 1},
{5, 4, 1, 1, 1, 1, 1, 1},
{6, 5, 6, 7, 8, 9, 10, 1},
{7, 1, 1, 1, 1, 1, 1, 1}
}));
18 instead of 22
{1, 2, 1, 1, 1, 1, 1, 1},
{0, 3, 4, 5, 1, 1, 1, 1},
{1, 2, 1, 6, 1, 1, 1, 1},
{1, 3, 4, 5, 1, 1, 1, 1},
{1, 4, 1, 1, 1, 1, 1, 1},
{1, 5, 6, 7, 8, 9, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1}
})
15 instead of 14.
Create a Directed acyclic graph(you can't get cyclic graph).
a: {b,c,d,e}
Where a is connected to b, c, d and e.
Once you have this graph ready use this technique to find out the maximum distance and return it.
moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/content/1/longest-path-in-dag.pdf
slight bug in earlier version.So new code:
int max3(int a, int b, int c, int d)
{
int temp = a>b?a:b;
int temp1 = c>d?c:d;
return temp>temp1?temp:temp1;
}
int main()
{
int maxi=0,i;
int a[] = {1,3,5,-1,12,6,7,11};
for(i=2;i<sizeof(a)/sizeof(a[0]);i++){
a[i] = max3(a[i-2], a[i-1], a[i]+a[i-2], a[i]);
//printf("%d\n", a[i]);
}
printf("%d\n", a[(sizeof(a)/sizeof(a[0]))-1]);
}
@Dumbo: Nice logic
Code in C:
int max(int a, int b, int c)
{
int temp = a>b?a:b;
return temp>c?temp:c;
}
int main()
{
int maxi=0,i;
int a[] = {1, 5, 3, 9, 4};
for(i=2;i<sizeof(a)/sizeof(a[0]);i++){
a[i] = max(a[i], a[i-1], a[i]+a[i-2]);
}
printf("%d\n", a[(sizeof(a)/sizeof(a[0]))-1]);
}
4
3 2
1
Start from 4 and add it in a queue.Dequ and add it's children i.e. 3 and 2 in queue.
Again dequ and get 3.Add it's children 1 in queue.Dequeu 2 and here you notice that it's children doesn't exist.Mark this level.Deque 1 and you see that it doesn't have any children and you also notice that the level is not save as the the one you marked so return 0(boolean value).
Basically do bfs and note down the level when you find out that a particular node doesn't have any children and compare with all the leaf node you find along the bfs way.
@Dumbo: Fixed the above program and now DFS also works and gives the correct result.
- aka June 20, 2013Bug was: I was not making path as unvisited when I was returning.