aka
BAN USERis not the visited array we maintain to avoid cycles?
Regarding the longest path below should do?
dfs(source ,destination, graph)
{
if(source == destination)
we have a path here.What is the size?
if(size > present_size)
update present_size;
visited[source] = 1;
for(all the connected nodes to source)
if(visited[connected_node] == 0)
dfs(connected_node, destination)
visited[connected_node] = 0;
}
@algos: nice logic and I am upvoting this.Just to clarify more
for remainder array verify below conditions:
1. there should be even number of 0's
2. for every element a[i] in remainder array there should be K-a[i] exists in array. To verify this hash all elements and check only till the size/2 (size is array size).
example:
9 15 21 4 5 6 and K=10, and N=6
here remainders are 9 5 1 4 5 6
Hash all the remainders and check for N/2 elements if it is equal to K-a[i].
9 5 1 4 5 6
9+1=10 so remove 1 from the hash.
5+5=10 so remove 5 from the hash
and 4+6= 10 remove 6 from the hash
We are done as there is nothing in the hash.
So we return TRUE as all the pairs are adding up to K.
"sum is 30 and is equal to K*N/2" -this condition verification is not required.
This doesn't handle the duplicate characters.If someone can suggest a way to handle that ?
#include <stdio.h>
#include <string.h>
#define SIZE 4
#define CHAR_SIZE 256
struct co{
int i;
int j;
};
struct c_r{
struct co s[CHAR_SIZE];
char track[CHAR_SIZE];
};
struct c_r main_;
int search(char mat[SIZE][SIZE], char c, int i, int j)
{
/* search in top if it exists */
if(i-1 >= 0)
if(mat[i-1][j] == c)
return 1;
/* search in top right if it exists */
if(i-1 >= 0 && j+1 < SIZE)
if(mat[i-1][j+1] == c)
return 1;
/* search in top left if it exists */
if(i-1 >= 0 && j-1 >= 0)
if(mat[i-1][j-1] == c)
return 1;
/* search in current down if it exists */
if(i+1 < SIZE)
if(mat[i+1][j] == c)
return 1;
/* search in current left if it exists */
if(j-1 >= 0)
if(mat[i][j-1] == c)
return 1;
/* search in current right if it exists */
if(j+1 < SIZE)
if(mat[i][j+1] == c)
return 1;
/* search in down left if it exists */
if(i+1 < SIZE && j-1 >= 0)
if(mat[i+1][j-1] == c)
return 1;
/* search in down right if it exists */
if(i+1 < SIZE && j+1 < SIZE)
if(mat[i+1][j+1] == c)
return 1;
return 0;
}
int find_word(char mat[SIZE][SIZE], char *word, int i, int size)
{
if(i >= size)
return 1;
if(main_.track[word[i] -'0'] == word[i]){
if(i+1 >= size)
return 1;
if(search(mat, word[i+1], main_.s[main_.track[word[i] -'0'] - '0'].i, main_.s[main_.track[word[i] -'0'] - '0'].j)) {
find_word(mat, word, i+1, size);
} else {
return 0;
}
} else {
return 0;
}
}
int main()
{
int i, j;
char *word = {"TDIN"};
char mat[SIZE][SIZE] = {
'S', 'M', 'E', 'F',
'R', 'A', 'T', 'D',
'L', 'O', 'N', 'I',
'K', 'Z', 'P', 'B',
};
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
main_.track[mat[i][j] - '0'] = mat[i][j];
main_.s[mat[i][j] - '0'].i = i;
main_.s[mat[i][j] - '0'].j = j;
}
}
if(find_word(mat, word, 0, strlen(word)))
printf("found\n");
else
printf("not found\n");
return 0;
}
Not sure about the correctness in boundary cases but seems to work.
#define INFINITY UNIT_MAX
int min_x = INFINITY;
int check_min(treeNode *root)
{
if(root->left)
check_min(root->left);
if(root->right)
check_min(root->right);
if(root->left && root->right && root->left->data && root->right->data && min_x > root->left->data+root->right->data)
min_x = root->left->data+root->right->data;
return min_x;
}
#include <stdio.h>
#define CHAR_SIZE 26
#define PERMUTE_SIZE 1000
static char *permu[PERMUTE_SIZE]; /*Right now I am interested in only 3 chars */
static int k;
void swap(char *string, int i, int j)
{
char temp = string[i];
string[i] = string[j];
string[j] = temp;
}
void permute(char *string, int i, int n)
{
int j = 0;
if(i == n) {
permu[k] = malloc(strlen("1122"));
strcpy(permu[k], string);
k++;
} else {
for(j=i;j<=n;j++) {
swap(string, i, j);
permute(string, i+1, n);
swap(string, i, j);
}
}
}
int main()
{
int i, j, count = 0;
char a[CHAR_SIZE+1] = {0};
char *string = malloc(strlen("1122"));
strcpy(string, "1122");
/*let's permute now*/
permute(string, 0, strlen("1122")-1);
/*make hashtable*/
for(i=0;i<=CHAR_SIZE;i++)
a[i] = 'a' + i; /*TOD0:Take care of CAPS*/
for(i=0;i<k;i++) {
int decimal;
decimal = atoi(permu[i]);
//printf("string %d\n", decimal);
for(j=0;j<2;j++) {
if(decimal%100 > CHAR_SIZE){ /* take 2 elements */
decimal = decimal/100;
} else {
if(a[decimal%100 - 1] != -1) {
printf("%c", a[decimal%100 - 1]);
count++;
}
a[decimal%100 - 1] = -1;
decimal = decimal/100;
}
}
printf("\n");
}
printf("total count %d\n", count+strlen("1122"));
return 0;
}
Algorithm: Keep two pointers for this work
While(string != '\0') {
1. "GOING" is the string.Initially both will point to 'G'.
2. Move first pointer if it 'a' or 'i'.If it is not then don't move first pointer.
3. Copy first pointer data in second pointer and increment second pointer.
return second pointer.
}
char * string_removal(char *string, char a, char i)
{
char *first = string;
char *second = string;
char *temp = string;
while(*string != '\0') {
if(*first == a || *first == i)
first++;
else {
*second = *first++;
second++;
}
string++;
}
*second = '\0';
return temp;
}
First of all CSR asks always stupid questions and this question is not any different.I hope they stop asking stupid questions which they themselves are not clear about.
volatile means the value of that variable is always read from its memory location on access and written to its memory location on mutation.So any optimization(by the compiler) that doesn't affect this can still be used.
Compiler uses all the tricks to make your code faster such as 'tail call'.
Most of the time the compiler would read the memory to get the value but in below code it may not do that as it can find out(probably by static analysis) that this value is not going to change so it will optimize it.
foo()
{
cpsr_reg = 30; /* this is cpu register */
printf("%d\n", cpsr_reg);
}
Compiler will optimise it as below:
foo()
{
cpsr_reg = 30; /* this is cpu register */
/* but cpsr_reg can change between the above and below instruction */
printf("%d\n", 30);
}
So by adding volatile you are just instructing the compiler to not do this and compiler.
How does it do that would be specific to compiler.
So let's do a dryrun for min heap approach:
a. Insert from the first row {2 5 7 9 14 16} first in the heap.
b. At this point the root node of the heap contains element 2.
c. Start inserting from second node {3 6 8 10 15 21}.So let's pick the first element of the second node which is 3.So we will check if 2<3 and it is so we will just add the 3 in the leaf node of the heap.
'C' step will be repeated for all the rest of the nodes in the row 2.
This whole thing will end once we have accounted for all the rows in the heap.
I wonder how will we take care of repeats?
-------
1 3 2
-------
So as I understand:
a. if you grow '3' and if it reaches '2' there will be collision
b. you will again rebase '3' to be between '1' and former '3' starting place(bottom of the stack).
c. However if we grow '2' and it hit '3' then also you will rebase '3' as explained in above point and re-arrange all the elments of '3' stack and once after re-arrangement you will get space which will be used for growing '2'.
Am I right?
Concept is below:
10, 17, 6, 5
10 compare 17 ok
17 compare 6 not-ok array{10, 6, 5, 17}
10 compare 6 not-ok array{6, 5, 17, 10}
6 compare 5 not-ok array{5, 17, 10, 6}
5 compare 17 ok
17 compare 10 not-ok array{5, 10, 6, 17}
10 compare 6 not-ok array{5, 6, 17, 10}
6 compare 17 ok
17 compare 10 not-ok array{5, 6, 10, 17}
so output 5, 6, 10, 17 and number of times swap is called 6.
include <stdio.h>
#define SIZE(x) sizeof(x)/sizeof(x[0])
void swap(int a[], int i, int j)
{
int temp = j - i;
int store = a[i];
j = i + 1;
/* first shift */
while(temp){
a[i] = a[j];
i++;
j++;
temp--;
}
a[i] = store;
printf("called\n");
}
int main()
{
int a[] = {10, 5, 7, 6, 4};
int i = 0;
int j = 1;
while(i != (SIZE(a) - 1)) {
if(a[i] < a[j]) {
i++;
j++;
} else {
swap(a, i, (SIZE(a) - 1));
if(i) {
i--;
j--;
}
}
}
return 0;
}
With the rock in the boat, the entire weight of the rock pushes the boat into the water. But when the rock is submerged, only its volume and not its weight is displaced. Since the rock is denser that water (presumably), then less water is displaced when the rock is submerged. The boat rises, and the water level falls.
- aka October 16, 2012You can do this with hashing.Example below:
Start with an empty hash.
5 -0 = 5 does this exist in hash?No so put in array[5]
5 -1 = 4 does this exist in hash?No so put in array[5, 1]
5 -2 = 3 does this exist in hash?No so put in array[5, 1, 2]
5 -6 = -1 does this exist in hash?No so put in array[5 ,1, 2, 6]
5 -3 = 2 does this exist in hash?Yes so put in array[5 , 1, 2, 6, 3] note here the 3+2
5 -4 = 1 does this exist in hash?Yes so put in array[5, 1, 2, 6, 3,4] note here 4+1
Logic:do dfs and with backtracking find out all the paths and store it.
Do a search for the maximum number of nodes in the paths stored during backtracking
and print it.
It is not that efficient but this is what I came up with.
- aka March 30, 2013