## 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

geeksforgeeks.org/find-first-non-repeating-character-stream-characters/

- Amit February 01, 2014may be helpful