raja roy
BAN USERHere is a sample program using five states
#include<stdio.h>
enum state
{
STATE_NONE,
STATE_ODDA,
STATE_EVENA,
STATE_ODDB,
STATE_EVENB
}s;
int
dfa(const char*str)
{
enum state ssa=STATE_NONE;
enum state ssb=STATE_NONE;
int i=0;
while(str[i]!= '\0')
{
if(str[i] == 'a')
{
if(ssa == STATE_NONE)
{
ssa = STATE_ODDA;
}
else if(ssa == STATE_EVENA)
{
ssa= STATE_ODDA;
}
else
{
ssa= STATE_EVENA;
}
}
if(str[i] == 'b')
{
if(ssb == STATE_NONE)
{
ssb = STATE_ODDB;
}
else if(ssb == STATE_EVENB)
{
ssb = STATE_ODDB;
}
else
{
ssb = STATE_EVENB;
}
}
i++;
}
if(ssa == STATE_EVENA && ssb == STATE_ODDB)
{
return 1;
}
return 0;
}
int
main()
{
int i=0;
const char *str = "babababaabaabab";
if(dfa(str))
{
printf("Passed dfa\n");
}
else
{
printf("Not passed\n");
}
return 0;
}
I guess...you could do it using binary search tree(or set if u wanted to use inbuild lib) with total complexity < O(n) ~ O(lg n)
Lets take two variables as
first_non_repetative=-infinity and second_non_repetative=-inifinity
take one element at a time and try to insert it in a binary search tree..so now if at any moment you get a collision(get same data in BST) (for a no say x)then don't insert it rather do
if(first_non_repetative == -infinity)
{
first_non_repetative = x;
}
else if(first_non_repetative!=x && second_non_repetative==-infinity)
{
second_non_repetative = x
return ///that would be the ans
}
step-1 create a max heap out of the array
step-2 create a min heap out of the array(only if the array contains -ve nos)
step-3 delete three elements(say maxa, maxb, maxc) from the max heap these elements would the 3 largest elements in the array
step-4 if the array contains -ve elements then delete TWO elements(say mina, minb) from the min heap.
step-5 If the array contains -ve elements then check
if((mina *minb) > (maxa*maxb))
then MaxProduct = mina *minb * maxc
else
MaxProduct = maxa*maxb*maxc
Total time would be = O(nlogn) which could be reduce to O(n) if you create using fast heap
maintain a min/max heap of k elements in RAM and fetch blocks of integers at a time and update the heap using the fetched block of integers.
Do this unless you are done with all the integers stored on disk.
At the end you will get the top K elements as in the heap.
store the avg of the nos in the array and if you found the avg to be repeated (say found same at index b, n), then the arrays between the first element and b the b+1 to n will have the same avg and thus the ans.
ex- consider the array
-4 27 1 9 -5 8 20
the sum array would be //calculated to elaborate
-4 23 24 33 28 36 56
the avg would be
-4, 4.75, 8, 8.12, 5.6, 6, 8
so here the avg(with value 8) is same at indexes 3 and 7 so the parts of the array would be between 1-3 and 4-7 as the output.
NO,i don't think so..what do you think the trie would do if you have an input of like /document/document/..it won't create two level rather it will create only one....
so the solution should be to get the names as tokens in a every single path(input) and build the n-array tree out of it.
here is an intelligent way(i guess..:P) to do it: I hope this helps!
#include<stdio.h>
union ip {
unsigned int int_val;
unsigned char c[4];
};
int
main()
{
union ip p;
p.int_val = 3232235786; //int val for 192.168.1.10
printf("%u.%u.%u.%u\n", p.c[3], p.c[2], p.c[1], p.c[0]);
return 0;
}
This checks for all the cases!! ie if mid value falls on one side along with lower bound or upper bound, then we have to adjust the range as well.
int
main()
{
int a[]={ 4, 5, 6, 7, 8, -1, 0, 1, 2, 3,};
int n=sizeof a/sizeof(int);
int lb=0, hb=n-1, mid;
while(1)
{
mid=(lb+hb)/2;
if(a[mid-1] > a[mid])
break;
if( a[mid] > a[0])
{
lb=mid;
if(a[hb] > a[0]) //make sure we span whole array
hb=n-1;
}
else
{
if(a[lb] < a[0])
lb=0;
hb=mid;
}
}
//print the mid value now
}
pretty good q to understand the stack...if following printf() prints same addr(for a[5] & i) then u will go in infinite loop..
int
main()
{
int i=0;
int array[5];
printf("addr a[5]:%p i:%p\n", &array[5], &i);
for(i=0;i<=5;i++)
array[i]=0;
printf("why this printf not working?");
return 0;
}
This might work...(simple logic)
#include<iostream>
#include<stdio.h>
int
main() {
int a[]={-10,-20,-30,-10,-50,-1,1};
int n=7, min=9999999;
for(int i=0; i< n; i++) {
if(a[i] > 0)
{
if( a[i] < min)
min=a[i];
}
else
if( (0-a[i]) < min)
min = 0-a[i];
}
printf(" %d\n", min);
return 0;
}
struct node
{
int a;
struct node*link;
};
struct node*head;
void rev_linklist()
{
struct node* prev_ptr , *temp , *for_ptr;
prev_ptr = head;
temp = for_ptr = head->link;
prev_ptr->link = NULL;
while(for_ptr->link != NULL)
{
temp = for_ptr;
for_ptr = for_ptr -> link;
temp ->link = prev_ptr;
prev_ptr = temp;
}
for_ptr->link = temp;
head = for_ptr;
traverse();
}
#include<stdio.h>
#include<stdlib.h>
main()
{
int array[10]= { -111, -9, -8, 7, -2, -3, 4, 5, 7, -6};
int max = -99999;
int curSum = 0;
int a=0 , b =0, s=0, i = 0;
for( i = 0; i < 10; i++ )
{
curSum += array[i];
if ( curSum > max )
{
max = curSum;
a = s;
b = i;
}
else
{
if(curSum<0)
{
curSum = 0;
s = i + 1;
}
else
{
s = i;
}
}
}
printf("Sum-> %d s=%d f=%d\n",max,a,b);
return 0;
}
one way you can think of it as the index of the array as the value and the address of the next to be stored on that index. The head var would store the address of the starting array index.
- raja roy March 31, 2012