This is a pretty nice question because it requires you to show
knowledge in many different areas. In business settings, logs can
make the difference between success and failure, not to mention
complying with law.
Here are some dimensions of the design space:
* Convenience of the programmer's
This is a well-known algorithm :- Knuth Shuffle.
read it on wikipedia
en.wikipedia.org/wiki/Fisher–Yates_*shuffle
*
On Wednesday, 23 May 2012 14:40:36 UTC+5:30, Ramindar Singh wrote:
Write a method to shuffle a deck of cards. It must be a perfect shuffle -
in other words, each 52!
I m surprised that ur whole explanation is for me :-o
Check ur previous post and then last post...
i think u r confused
On Tue, Aug 23, 2011 at 3:10 PM, WgpShashank shashank7andr...@gmail.comwrote:
@sagar,
A self-balancing balancing binary search tree(Its *BST not BT )*containing n
items
Its Both of the BST and Heap...
Prem
On Tue, Aug 23, 2011 at 5:01 PM, sagar pareek sagarpar...@gmail.com wrote:
I m surprised that ur whole explanation is for me :-o
Check ur previous post and then last post...
i think u r confused
On Tue, Aug 23, 2011 at 3:10 PM, WgpShashank
Ok then answer must be both of them :)
actually finding min is O(1)
but to re-heapify after deletion is log(n).
On Mon, Aug 22, 2011 at 9:55 AM, Amol Sharma amolsharm...@gmail.com wrote:
BST should be the answer..agree with the reason by dumanshu
--
Amol Sharma
Third Year Student
Only Balanced BST (its guaranteed that we can search element in o(logn) ,
i am assuming its maxheap .In a max heap, the smallest element is always
present at a leaf node. So we need to check for all leaf nodes for the
minimum value. Worst case complexity will be O(n)
12
/ \
/ \
8 7
/ \ / \
@shashank
what about min heap?
Check this out -- http://en.wikipedia.org/wiki/Heap_%28data_structure%29
On Mon, Aug 22, 2011 at 4:13 PM, WgpShashank shashank7andr...@gmail.comwrote:
Only Balanced BST (its guaranteed that we can search element in o(logn) ,
i am assuming its maxheap .In a max
We can't use a heap. Balanced BST is correct because Deletion of the
smallest element Insertion of an
element if it is not already present in the set - for this we need
to search for the element and searching in heap is O(n).
On Aug 21, 6:16 pm, priya ramesh love.for.programm...@gmail.com
wrote:
+1 Dumanshu
This question was asked by amazon :D
And answer is BST only
coz deletion in heap(min heap) is O(1).
And if it is max heap then deletion of min element is O(n).
On Sun, Aug 21, 2011 at 9:13 PM, Dumanshu duman...@gmail.com wrote:
We can't use a heap. Balanced BST is correct because
@sagar : deletion in logn, check
http://en.wikipedia.org/wiki/Heap_%28data_structure%29
i would say that the re-heapify is implicit just as the re-balance is
implicit in balanced bst
On Mon, Aug 22, 2011 at 12:58 AM, sagar pareek sagarpar...@gmail.comwrote:
+1 Dumanshu
This question was asked
BST should be the answer..agree with the reason by dumanshu
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99
On
@Rajeev:
How will you update the position of each element in the linked list after
removing a particular element? Won't you have to traverse the list
completely in which case your algo will be O(n^2) ??
--
You received this message because you are subscribed to the Google Groups
Algorithm
@Tayler : That's y i am using Java ArrayList instead of linked list where
arrayList maintains element position.But problem is when an element is
removed from the list,all subsequent elements to be moved forward
Please check javadoc of arrayList :
@Rajeev: Okay, I am using C which has no such facilities of auto indexing
the list..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/BsMmVwxw_T4J.
To post
extra memory allowed... and n log n and resultant array should
have values f(x) in the same order as x in the first array (before
sort)
now, sort the first array and take distinct (another array)... create
a dictionaryint,int. add each element in the sorted list and it's
index as key and
Hey ankit, i gave java code also...didn't u check it in the link...anyway i
am explaining here.
*Note : Position count starts from 0. *
*ex: {1,2,3,4} ...position of '1' is zero*
*
*
*In the below approach,we are checking element position in the modified
list(after deletion
The binary search trees can be used ...arrange the given elements in
binary search tree ...search for each element in the tree count
the number of nodes along its left successors until the leaf node is
reached ...!! thats the ans !!
On Jul 26, 6:53 pm, Someshwar Chandrasekaran
@vivin : Your algo seems to be wrong. Plz take an example and
explain. I may hv misunderstood u ..
--
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
*
Algorithm :
1)Conside original array a[]
2)Construct a sorted list with the array elements(O(nlogn))
3)Traverse across all elements of the original array 'a' and find it's
position(right occurence) in the sorted list using binary search.
-position in the sorted list returns the number of
We can use count sort to solve this. Assuming each element is the
array is in range 1-k (k=O(n)).
for (i=0 to n)
C[A[i]]=C[A[i]]+1
for (i=1 to k)
C[i]=C[i]+C[i-1]
Array 'C' will have the resultant array.
On Jul 26, 9:20 pm, Rajeev Kumar rajeevprasa...@gmail.com wrote:
*
Algorithm :
@rajeev:ur algo does not give the correct answer.
--
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
@bharath :I think array C is not the resultant array. Take an example and
explain
--
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
Oops, my bad. I missed that lowest in a[i+1...n] part.
On Jul 26, 10:17 pm, ankit sambyal ankitsamb...@gmail.com wrote:
@bharath :I think array C is not the resultant array. Take an example and
explain
--
You received this message because you are subscribed to the Google Groups
Algorithm
@ankit : can u give me a case where it fails...
On Wed, Jul 27, 2011 at 8:33 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@rajeev:ur algo does not give the correct answer.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@ankit : can u give me a case where it fails...
On Wed, Jul 27, 2011 at 8:33 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@rajeev:ur algo does not give the correct answer.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@Anyone worked on this before?
I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)*
I've to prove on this..
If someone have time.. can you *prove that, the T'th fibinocci number is
always greater than 'N'*
*where T = (log N)^2 *
--
You received this message because you
what about precomputation and then binary search...?
On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
@Anyone worked on this before?
I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)*
I've to prove on this..
If someone have time.. can you
its equal to calculating the Fibonacci numbers till we get a number
which is closest to and lesser than N...anything better??
On 5/24/11, Aakash Johari aakashj@gmail.com wrote:
what about precomputation and then binary search...?
On Tue, May 24, 2011 at 6:37 AM, sravanreddy001
if u have many test cases, this approach is helpful.
On Tue, May 24, 2011 at 6:42 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
its equal to calculating the Fibonacci numbers till we get a number
which is closest to and lesser than N...anything better??
On 5/24/11, Aakash Johari
yes, that depends on what limits u have been given. for the unknown one, i
ll have to think..
On Tue, May 24, 2011 at 6:48 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
@Aakash Sir...if it is so, can u elaborate ur logic??i mean what
should be maximum limit on the precomputation??
On
suppose its maximum limit is unsigned int onlythen u mean to say
we need to precompute till the maximum limit of unsigned which is
unnecessary taking up size if we give input say 50
On 5/24/11, Aakash Johari aakashj@gmail.com wrote:
yes, that depends on what limits u have been given. for
@all
it is simple binary search problem
we can write
f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get
formula when n is odd.
f(3), f(4), f(5) f(6)
f(6), f(7), f(8) f(12)
.
.
.
as soon as you got a fibnocci number greater than n suppose p-- than you
have two
@ps: no, suppose for given N testcases, get the maximum one, and generate
fibs greater than that. and then for others u can get with binary search
only,
u will have to improve the fib generator, so basically matrix expo, can
help. other way of doing this is described in above post.
On Tue, May
@Aakash Sir...can u clarify giving some exampleslike i give input
N=10,it should O/P 8if N=51,O/P=34
On 5/24/11, Aakash Johari aakashj@gmail.com wrote:
@ps: no, suppose for given N testcases, get the maximum one, and generate
fibs greater than that. and then for others u can get
@bittu: yes, this can be the way. just make ur fib generator faster(using
matrix expo.) for less complexity.
On Tue, May 24, 2011 at 7:33 AM, bittu shashank7andr...@gmail.com wrote:
@all geeks
I have already posted it 2-3 forums..here let me post it again its
O(n) but the basic idea is
@all geeks
I have already posted it 2-3 forums..here let me post it again its
O(n) but the basic idea is clear if got the problem stmt correct then
we have to find out the largest Fibonacci number that is small then
given number n so say if n=10 then should be 8
for n=13 i=8
n=14 i=13 similarly
U r using he same approach which I mentioned it before...I knew about
this approach but it sounded to me too naive solution...so I was
thinking whether there exists any shortcurt method/mathematical
formulae for it or not..
On 5/24/11, bittu shashank7andr...@gmail.com wrote:
@all geeks
I have
search OEIS.. and tell if you find something interesting :)
On Tue, May 24, 2011 at 7:37 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
U r using he same approach which I mentioned it before...I knew about
this approach but it sounded to me too naive solution...so I was
thinking whether
@aakash...so above algo is fine working fine i forget to put else
stmt after if otherwise unnecessary comparison so
you can add if(finalc)then final=c
else break; in above program will post
O(logn) program soon
Thanks
Shashank
--
You received this message because
yes, as to my knowledge. there's a similar problem on SPOJ also. I can
remember that i solved that in similar way (with matrix expo.). If anyone
finds better way, please post here.
On Tue, May 24, 2011 at 8:02 AM, bittu shashank7andr...@gmail.com wrote:
@aakash...so above algo is fine working
int fibArray[INTEGER_MAX_VALUE] = {0};
int fibonacci (int n) {
if (n = 0) {
return 0;
} else if ( n 0 fibArray[n] != 0) {
return fibArray[n];
} else {
if (n == 1) return (fibArray[n] = 1);
return (fibArray[n] = fibonacci(n - 1) + fibonacci(n-2));
@piyuesh..i posted the naive because geeks are so confused about this
quest. i have seen some geeks saying terrible time complexity of it.
so above approach will make 1st of all every1clear optimization 2ndary
step...
As i have told earlier its similar to find nth Fibonacci number can
be done
Ur algo's complexity will not be O(logn)..it will be O(nlogn)..
On 5/24/11, bittu shashank7andr...@gmail.com wrote:
@piyuesh..i posted the naive because geeks are so confused about this
quest. i have seen some geeks saying terrible time complexity of it.
so above approach will make 1st of all
43 matches
Mail list logo
