Amit
BAN USER- 0of 0 votes
AnswersFind x^y where y can be float. Any good algorithm for that?
- Amit in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - -1of 1 vote
AnswersBy mistake I wrote the following program and it compiles and runs without any error in gcc compiler. enter code here
- Amit in India
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i,**data;
data=(int **)malloc(sizeof(int)*1000000);
for(i=0;i<1000000;i++)
data[i]=(int *)malloc(sizeof(int)*1000000);
printf("done\n");
return 0;
}
But I don't understand how is it allocating an array of 1000000*1000000 bytes,almost equivalent to 1TB??| Report Duplicate | Flag | PURGE
SDE1 C - 2of 6 votes
Answersthere is an infinite line.you are standing at a particular point you can either move 1 step forward or 1 step backward.you have to search for an object in that infinite line.your object can be in any direction. Give optimal algorithm.
- Amit in United States| Report Duplicate | Flag | PURGE
Amazon
append a 0 at the start of the array,say arr..so arr[0]=0
1.now build a sum matrix such that
sum[i]=arr[0]+arr[1]+...arr[i].
this step takes o(n) time
2. now you need to search 2 elements in sum matrix with diff divisible by 7.Following algos can be used
i)2 loops-naive approach-o(n2) time
ii)hashing--
maintain a hashmap of only 7 elements
insert sum[0]%7 entry into hashmap as 0
hash[sum[0]%7]=0;
now i=1 to n
search for 7-sum[i]%7 in hashmap..if found subset is found
else insert sum[i]%7 entry in hashmap as i
hash[sum[i]%7]=i
this step will take o(n) time.
Hence using 2nd algo,we can do the task in o(n) time and o(n) space(for sum matrix)
We can use hashmaps to do it in O(n) time
algo::
1.copy the linked list with next pointers(arbitrary may be NULL)
All use a hash function
Say Pi denote original linked list pointers,Qi-cloned linked list pointers,h-hash fn
so,while creating cloned linked list...store h(Pi)=Qi for all pointers
2.Now,once the list is created.repeat for each Pi
h(Pi)->arbitrary=h(Pi->arbitrary)
Pi=Pi->next;
Go to last node,say y
x=head;
1.check whether x's string is palindrome with y's.
as there are N nodes in each of x,y...so if if those data is in array we can compare elements easily. If those nodes are also ll,then reverse y and then compare and finally reverse y to obtain original structure.
if not palindrome,return 0;
else goto step2
2.x=x->next;
if x==y
return 1;
y=y->prev;
if(x==y)
return 1;
go to step 1;
ok...lets try with an example
NULL-1-2-3-4-5-6-7-8-NULL
1.clearly root of tree will be the head
p,q,current node are say temp nodes
p=head(1 in this example)
now add 2 and 3 as left and right children of 1
2.q=last node added as a child
current node=q;
now while(current node is p)
add 2 children to current nodes
current node=current node->prev
3.p =q,
q=last node added as a child
go to step 2
hope this make sense.may be bit confusing,but atleast the approach,u can get
please note that once we need to make left child first and then right child,then vice versa, We can use a flag variable to ensure that
@avahuasca-if you search in both the subarrays for many cases,its o(n) not o(logn).
binary search is O(logn) search because in each iteration if reduce length by half.
will you say the following prog is also o(logn)?
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
no this is o(n) only..correct me if I am wrong
It doesn't seem possible to search the element in o(logn) without calculating the pivot
suppose case 1: arr[]={1,2,3,22,23,25,30,27,21,11,10}
case 2: arr[]={1,2,3,21,23,25,30,27,22,11,10}
and suppose key is 22
in both the arrays middle element is 25,and arr[low]=1,arr[high]=10,arr[mid-1]=23,arr[mid+1]=30.
so,it seems impossible to decide whether to look in left subarray or right..In 1st example 22 lies in left subarray while in 2nd it lies in right subarray. Correct me if I am wrong
not required,i guess...suppose you found any one position of required value x in array using bsearch say k
now use this modified binary search in left side
low=0;high=k-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
high=mid-1;
else low=mid+1
}
after this loop,the index value low will contain the first occurrence of x in array.
similarly you can search in other part for last occurrence too
RepAmit, None
Repmendezleah216, Analyst at Bosch
Hello,everybody,I'm Leah Mendez.I want to make some friends here.I’m a woman with ambition and ...
RepNatalieLutz, Applications Developer at Absolute Softech Ltd
Pitch trending story topics and continually look for ways to push breaking and/or viral stories forward with new angles ...
Rephinescarol45, +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana at 247quickbookshelp
I am Carol From San Diego USA, I am Working as a Personal assistant in a Castle Realty organization, I ...
geeksforgeeks.org/find-first-non-repeating-character-stream-characters/
- Amit February 01, 2014may be helpful