1.) Find the pivot point. to find pivot – for a sorted (in increasing
order) and pivoted array, pivot element is the only only element for which
next element to it is smaller than it.
2.) divide the array into two subarray and apply binary search.
for calling binary search in two subarray - if
@Rahul: Please tell us what you mean by a pivoted array.
Dave
On Tuesday, August 28, 2012 12:56:03 PM UTC-5, rahul sharma wrote:
plz provide me algo for this,thnx
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on
smthng like this...
*if*(arr[mid] arr[mid + 1])
return mid;
if(arr[low] arr[mid])
return findPoint(arr, low, mid-1);
else
return findPoint(arr, mid + 1, high);
On Sat, Jun 9, 2012 at 12:36 AM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi pharta :
find the point where
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0]
Yes,
Thanks Dave. for non-distinct items It's not possible.
On Fri, Jun 8, 2012 at 6:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with
It is easy.. find the point where it is rotated to get 14-1 O(log(n))
since 214 that means u have to find it in subarray [123].. do a binary
search here o(long(n))
final 2*O(log(n))...
On Fri, Jun 8, 2012 at 7:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without
In BST the height can be made as bad as u can but in case of btree the
height can not be more than log n base 2 because for each internal node it
is necessary to have at least 2 child and here all the leaf nodes must be
at the same label.
On Sun, Apr 1, 2012 at 8:34 PM, arun kumar
hi i just like to know when you will go for binary search tree over
btree. advantage and disadvantage, application of both of them.
thank you in advance
Regards,
Arun kumar
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
These may be of interest as well:
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582
https://webcache.googleusercontent.com/search?q=cache:onpOivQX668J:googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html+cd=1hl=enct=clnkclient=ubuntu
On Sunday, January 8, 2012
In binary search,
mid = start + (end-start)/2 is used to avoid overflow, as said by a book.
why can't we use mid = (start + end)/2, it says this statement may result
in overflow ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
not clear what you are trying to ask...can you quote exactly from the book?
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sun, Jan 8, 2012 at 4:34 PM, Sanjay Rajpal srn...@gmail.com wrote:
In binary search,
mid = start + (end-start)/2 is used to
actually book pages are images.
My question is why second statement may result in overflow ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286, +91-9729683720
*
On Sun,
@Sanjay: suppose Max_INT range is 300
now suppose
end=300 and start =2
now using (start+end)/2 i.e *302*/2 but 302 goes out of range for and
interger type as assumed...
but if we use start + (end-start)/2 THEN 2 + (300-2)/2 , i.e 2+ *298*/2
here 298 300 hence it within int_Max range which
@Atul : got it. thanx :)
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Sun, Jan 8, 2012 at 3:27 AM, atul anand atul.87fri...@gmail.com wrote:
@Sanjay: suppose
@atul:
+1, i too thought the same
this comes handly esp, when the derived datatypes are used with a range
limitations.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
What is the logic on choosing power of two as search indexes ?
On Oct 24, 12:56 am, Ankur Garg ankurga...@gmail.com wrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
hint 1: try to find 2
nopes, you need to know where the hell it ends even if this is a
string , it ends with convention of ending 0. in case it is stream ,
we know the data length. in case of array, above mentioned approach
should work. sizeof(arr)/sizeof(arr[0])
if you are given only a pointer and no length, you
@saurabh
u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second
one is integer...both's size is 4
do it
without passing
http://www.ideone.com/8olTP
On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.com wrote:
nopes, you need to know where the hell it ends
Well sir I am fully aware why this is hapening.Kindly reread what I wrote
.*what if we are given only the address of the array.*
I personaly feel anyone who asked the question never expected this to be the
answer.(using sizeof).
On Tue, Aug 23, 2011 at 2:42 PM, sagar pareek
hmm ok
my mistake of reading
On Tue, Aug 23, 2011 at 6:56 PM, saurabh singh saurab...@gmail.com wrote:
Well sir I am fully aware why this is hapening.Kindly reread what I wrote
.*what if we are given only the address of the array.*
I personaly feel anyone who asked the question never
@dave or anyone??? response please
On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote:
kkk...not sure
assume no number is greater than 1000(I mentioned There has to be some
additional constraints to make the problem solvable)
Now check 1st element if not the
If i am not wrong, the only possible solution can be
len=sizeof(arr)/sizeof(arr[0])
i.e. find the length from the array itself.
On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote:
@dave or anyone??? response please
On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh
That would take all the fun awaywhat if you are given only the address
of the array?This wont work in that case
On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote:
If i am not wrong, the only possible solution can be
len=sizeof(arr)/sizeof(arr[0])
i.e. find the length
Just a small code to back up my point...
http://www.ideone.com/woRiT
On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote:
That would take all the fun awaywhat if you are given only the address
of the array?This wont work in that case
On Mon, Aug 22, 2011 at 10:39
kkk...not sure
assume no number is greater than 1000(I mentioned There has to be some
additional constraints to make the problem solvable)
Now check 1st element if not the desired element keep multiplying with 2 the
previous range till either one of these condition is satisfied
*1.An exception
@dave may be its a bit offtopic,(and may be stupid) but if the numbers are
in a small range (say 1 to 1000) isn't the probability that the absolute
garbage value would be greater than the array elements(assuming garbage to
be bits of random 0's and 1's)?Assuming we have not entered into some other
@Everyone: The problem says that the array is of UNKNOWN length, but
all of the solutions presented assume that the array is of INFINITE
length. Suppose, e.g., that the length is 987, but you don't know
that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc,
or 1, 2, 4, ..., 512, 1024
Well
sorry but i forget to mention exceptions in the solution.
Here is the complete solution :-
The key idea here is to simultaneously do a binary search
for the end of the array as well as the key. We try to look for A[2k ] in
the
k-th step and catch exceptions for successive values of k till
Well in that case additive approach will work.
Sanju
:)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@Sagar: So far so good, but you are not guaranteed to get an
exception. Example, int a[987] is followed in memory by char
b[1000], which is a dictionary. You won't detect an exception
until you get to at least a[262144] (2 to the 18th). But you will pick
up plenty of garbage which may throw
thanks for pointing it out
On Sat, Aug 20, 2011 at 12:16 AM, Dave dave_and_da...@juno.com wrote:
@Sagar: So far so good, but you are not guaranteed to get an
exception. Example, int a[987] is followed in memory by char
b[1000], which is a dictionary. You won't detect an exception
until
How to optimise binary search so dat it makes only one comparison
instead of 2 dat it generally does??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this
int Modified_BinarySearch(int A[], int N, int value) {
int low = 0;
int high = N;
while (low high) {
int mid = (low + high)/2;
if (A[mid] value)
low = mid + 1;
else
Please tell the solution of this question
Given a Binary Search Tree, write a program to print the kth smallest
element without using any static/global variable. You can’t pass the value k
to any function also
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
Guys i always have this doubt.Please tell me whether stack frames allocated
for each recursive call will be cleared if we return in the middle of a
recursive call?
On Tue, Jul 12, 2011 at 10:22 PM, Don dondod...@gmail.com wrote:
// Similar to other suggestions, but without tail recursion.
ptr
On Wed, Jul 13, 2011 at 1:40 PM, sameer.mut...@gmail.com
sameer.mut...@gmail.com wrote:
Guys i always have this doubt.Please tell me whether stack frames allocated
for each recursive call will be cleared if we return in the middle of a
recursive call?
In normal condition, the return
There is no reason to use recursion to search a binary tree.
Don
On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com
wrote:
Hello,
Suppose you have to search a particular node in a binary tree.
The code is quite simple. Pick up any traversal and see if any node
matches the
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
TC O(N)
notify me via mail if anything wrong.?
Thanks
Shashank
CSE,BIT Mesra
--
You received this message because you are
@bittu
On 7/12/11, Aniket Dutta aniketdutt...@gmail.com wrote:
what will happen if node is not found?.
you are not checking it
On 7/12/11, bittu shashank7andr...@gmail.com wrote:
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
what will happen if node is not found?.
you are not checking it
On 7/12/11, bittu shashank7andr...@gmail.com wrote:
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
@Aniket: Just add a condition at the begining:
if(root == NULL)
return 0;
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@yeah right
On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Aniket: Just add a condition at the begining:
if(root == NULL)
return 0;
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@bittu
On Tue, Jul 12, 2011 at 8:09 PM, Aniket Dutta aniketdutt...@gmail.comwrote:
@yeah right
On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Aniket: Just add a condition at the begining:
if(root == NULL)
return 0;
--
You received this message
sorry @ankit
On Tue, Jul 12, 2011 at 8:10 PM, Aniket Dutta aniketdutt...@gmail.comwrote:
@bittu
On Tue, Jul 12, 2011 at 8:09 PM, Aniket Dutta aniketdutt...@gmail.comwrote:
@yeah right
On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Aniket: Just add a
// Similar to other suggestions, but without tail recursion.
ptr search(ptr root, int value)
{
ptr result = 0;
while(root !result)
{
result = (root-tag == value) ? root : search(root-left,
value);
root = root-right;
}
return result;
}
On Jul 12, 8:28 am,
An idea which strikes to mind is,
1.Initially to form a map based on the text and all related text to
it.[text,images]map
2.Also make a bitwise manipulation of every image and relate the texts to
it.[imagebitwise,texts] map
3.If a image is put forth for search, check the texts
from
There are specific algorithms for image matching. One of the more famous
ones is to use Wavelet coefficients.
Wavelet Coefficients are resolution independent ways of representing image
content (The image data is mapped
into a 0-1 2D space). You can perform a 2D difference analysis of the
Hi All,
A* search with consistent heuristics is supposed to ensure that an
optimal path to a repeated state is always the first path generated,
but consider the following example:
/---4---A(h=15)--30--\
S(h=18)G (h=0)
\
use skip list:)
On Thu, Mar 10, 2011 at 2:31 PM, ravi teja ravitejal...@gmail.com wrote:
@Utkarsh :
Yeah , that is when you can access any element in O(1) time and the
elements are sorted.This happens in a sorted array where you get an overall
complexisty of O(logn).
--
You received
what is skip list
On Fri, Mar 11, 2011 at 5:58 AM, priya mehta priya.mehta...@gmail.comwrote:
use skip list:)
On Thu, Mar 10, 2011 at 2:31 PM, ravi teja ravitejal...@gmail.com wrote:
@Utkarsh :
Yeah , that is when you can access any element in O(1) time and the
elements are sorted.This
but as far as i know binary search takes O(logn)time
tosearch an element
On Tue, Mar 8, 2011 at 9:35 PM, ravi teja ravitejal...@gmail.com wrote:
Yes , it is possible . But it does not make sense . The thing that matters
while doing binary search for arrays is that we can access any
Is it possible to implement
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
Yes , it is possible . But it does not make sense . The thing that matters
while doing binary search for arrays is that we can access any element in
O(1) time . But , for a linked list it becomes an average of O(n) . And on
average we have an O(nlogn) algorithm with highly confusing code and messy
please give your ideas for this
On Fri, Jan 21, 2011 at 2:28 PM, snehal jain learner@gmail.com wrote:
Magy! receives a huge amount of queries everyday. They don’t want to
store all of them, since many of the queries are unique (submitted
just one time by just one user). Anyway, for
First Approach,
0) the queries can be considered as an infinite stream. maintain a global
count of the number of queries coming from the stream (used for calc the
frequency %).
1) maintain a min-heap (has just top 100 queries by frequency) + hash table
(where we store frequency for each word in
@above in your second approach, in the worst case you need to traverse the
heap in O(n) time.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group,
Magy! receives a huge amount of queries everyday. They don’t want to
store all of them, since many of the queries are unique (submitted
just one time by just one user). Anyway, for caching reason they want
to understand what are the queries whose frequency exceed s=0.1%. How
do you solve the
Distance is measured on number of words. what is your meaning ? can you
explain it?
2010/12/29 Davin dkthar...@googlemail.com
Given set of words, find an area of the text where these words are as
close to each other as possible.
Distance is measured on number of words.
e.g. for words
Given set of words, find an area of the text where these words are as
close to each other as possible.
Distance is measured on number of words.
e.g. for words [rat”, “jat”, “pat”] and text “rat stop the pat blah
blah jat by pat jat tra la la” such area is “cat by mat bat”
--
You received this
WAP to create a binary search tree and search a node in it using
linked list representation
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
I guess this list is not to get your home works done.
Please use google before throwing anything and everything here.
On Wed, Oct 6, 2010 at 1:57 PM, addicted2abhishesh
abhishesh.srivast...@gmail.com wrote:
WAP to create a binary search tree and search a node in it using
linked list
Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2)
I feel the binary search approach as given by Saurabh Singh or like
moving from top right row, doing binary search in the row 0, find the
element being searched (say x) or one less than that (say y), followed
by binary search in the column below 'y' and proceeding in this way
can give a less than
Well, friend, we're both wrong.
The algorithm will find 6 just fine. It will choose 3 as the middle
element. Since 6 is bigger, it will throw away the subarray
1 2
2 3
and check the other 3 subarrays. When it checks
6 7
7 8
It will find the 6 on the first try. I just verified this by
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything
Hi , I was reading TST from this
http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/technical_artile/ternary_search_tree/terstree.htm
But I could not understand its two applications i.e the nearest
neighbourhood search and Pattern Matching Search...
If anyone of you know about it
take one pointer to start n another to the end say a n b
now if
a +b X
shift b towards left n so on
On Fri, Jun 18, 2010 at 9:03 AM, sharad kumar aryansmit3...@gmail.comwrote:
@arun:find out the difference x-arr[i] for all i=0..n hash it ...next
search for a number with difference .u can
Hi,
You are given a set of numbers and another number 'x'. You have to find
if there exists any two numbers, whose sum is equal to 'x'. I have done this
is o(n)log n. Need a more optimized solution.
regards,
Arun kumar S
--
You received this message because you are subscribed to the Google
Its a repeated question. I would suggest you checking the archives of this
groups for its solution.
Anurag Sharma
On Fri, Jun 18, 2010 at 8:05 AM, Arunkumar Sreenivasan
thegame.a...@gmail.com wrote:
Hi,
You are given a set of numbers and another number 'x'. You have to find
if there
Not a bad start, it can eliminate areas.
n n n n ?? ?? ?? ??
n n n n ?? ?? ?? ??
n n n n ?? ?? ?? ??
n n n n ?? ?? ?? ??
?? ?? ?? ?? n n n n
?? ?? ?? ?? n n n n
?? ?? ?? ?? n n n n
So it would involve searching in
the two remaing blocks, recursively
until you get an 1xN or Mx1
then a binary
Hmmm. Same idea, much more analysis.
I feel good, I spent a lot less time thinking
about it. Splitting the search areas into
squares is a great idea.
--
Geoff
On Nov 25, 8:43 am, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
A research article on this question..
Rohit Saraf
Sophomore
while(a.[mid].equals('city1') a[mid+1].equals('city2') ){
mid = low+high/2;
if(a[mid]=='city1' a[mid+1]=='city1')
low=mid;
else if (a[mid]=='city2' a[mid+1]=='city2')
high=mid;
}
On Thu, Nov 12, 2009 at 3:39 PM, Dennis tyra...@gmail.com
Wouldn't it be better to replace step 5 with
Travel 2^(n+1) distance on the fourth road. If you find your friend
DONE else
return back to the crossing
? After you have exhausted the first three roads to a distance 2^n,
there is no point to going only 2^n on the fourth road and then
returning
Anyway the solution is O(d) [:)] which is asked to be proved.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from
yes anil
your approach is rite..
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Hi
i want to construct a priority search tree but i don't know the algorithm
for construct and implement it can anyone help me please?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post
78 matches
Mail list logo
