[algogeeks] Re: Amazon Q : Design a logWritter for server kind of application
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 interface. * Flexibility in controlling how much and what kind of information is written. * Synchronization and sequencing of input coming from many processes and threads, including from different hosts on a network. * Searchability. * Compliance with existing format standards so that third party tools can be used. * Efficiency, including when logging is turned off. * Compression of log information (storage efficiency). * Spare, backup, and archiving schemes. On May 26, 4:49 am, Ashish Goel ashg...@gmail.com wrote: Design a logWritter for server kind of application Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Q
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! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.http://shashank7s.blogspot.com/2012/02/write-method-to-shuffle-deck-of-cards.html -- 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/-/GV5_GgOs2b8J. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
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 allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). please note that if it would have been simple BST not Balnced BST then our complexity to lookup will changes to O(n) in worst case when tree is skewed but as question say balanced BST (check out AVL/RB Tree) they gureentte that look-up will O(logn) only why its true will work you need to go through tree rotation (thats used to make tree balanced reduce height ). Since Heap is a balanced binary tree (or almost complete binary tree but not balanced BST ), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapifyhttp://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present because of this constraint we can't use min-heap as well . For a heap, we cannot find out in O(logn) if an element is present or not as its balanced Binary Tree(BT) , we have to search all the elements e.g.in both left right sub-tree up-to leaf so in worst case it will take O(n) time to search an element weather ist present or not , then its present leave it else insert as a last node call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) =O(n) search+heapify =O(search) so why correct answer is only Balanced Binary Search Tree Do Notify me if i missed something or wants more clarification ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- 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/-/65k0xGJY6ZoJ. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
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 shashank7andr...@gmail.comwrote: @sagar, A self-balancing balancing binary search tree(Its *BST not BT )*containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). please note that if it would have been simple BST not Balnced BST then our complexity to lookup will changes to O(n) in worst case when tree is skewed but as question say balanced BST (check out AVL/RB Tree) they gureentte that look-up will O(logn) only why its true will work you need to go through tree rotation (thats used to make tree balanced reduce height ). Since Heap is a balanced binary tree (or almost complete binary tree but not balanced BST ), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapifyhttp://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present because of this constraint we can't use min-heap as well . For a heap, we cannot find out in O(logn) if an element is present or not as its balanced Binary Tree(BT) , we have to search all the elements e.g.in both left right sub-tree up-to leaf so in worst case it will take O(n) time to search an element weather ist present or not , then its present leave it else insert as a last node call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) =O(n) search+heapify =O(search) so why correct answer is only Balanced Binary Search Tree Do Notify me if i missed something or wants more clarification ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- 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/-/65k0xGJY6ZoJ. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
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 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 Mon, Aug 22, 2011 at 6:52 AM, Akash Mukherjee akash...@gmail.comwrote: ay that the re-heapify is implicit just as the re-balance is im -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon q
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 / \ / \ try to search 5 in this using Heap balanced BST / \ / \ 2 3 4 5 As searching is main constraints on complexity we can't use Heap to achieve O(logn) it will take linear time but using Balanced BST (e.g. AVL/RB Tree) we can search element in O(logn) :) Shashank CSE,BIT Mesra -- 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/-/fmXlF2-kcFwJ. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
@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 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 / \ / \ try to search 5 in this using Heap balanced BST / \ / \ 2 3 4 5 As searching is main constraints on complexity we can't use Heap to achieve O(logn) it will take linear time but using Balanced BST (e.g. AVL/RB Tree) we can search element in O(logn) :) Shashank CSE,BIT Mesra -- 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/-/fmXlF2-kcFwJ. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon q
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: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
+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 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: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
@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 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 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: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon q
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 Mon, Aug 22, 2011 at 6:52 AM, Akash Mukherjee akash...@gmail.com wrote: ay that the re-heapify is implicit just as the re-balance is im -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Jylnk0KFxy0J. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 : http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html On Thu, Jul 28, 2011 at 11:58 AM, Tyler Durden abhishek.khattr...@gmail.com wrote: @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 Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Jylnk0KFxy0J. 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
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 value.
now, for each element in the original array, lookup it's sorted index
in the dictionary...
On Jul 26, 6:48 am, Piyush Sinha ecstasy.piy...@gmail.com wrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 operation in the previous iteration).*
given array is : ar[]= {1,3,2,4,5,4,2}.
construct a list with array elements and sort it.Now list contains
:1,2,2,3,4,4,5
Now traverse through array elements from i=0 to n-1(start to end)
store result in result[] array.
list is *1*-2-2-3-4-4-5
for i=0, a[0]=1,search for a[0] position in the list(right
occurrence).a[0]=1 position in list is '0'
add '0' to result.===result[0]=0;
remove the element a[0] from the list.now list contains 2-2-*3*-4-4-5
for i=1,a[1]=3,search for a[1] position in the list(right occurence).a[1]=3
position in list is '2'
add '2' to resultresult[1]=2
remove the element a[1] from the list.now list contains 2-*2*-4-4-5
for i=2,a[2]=2,search for a[2] position in the list(right occurence).a[2]=2
position in list is '1'
add '1' to resultresult[2]=1
remove the element a[2] from the list.now list contains 2-4-*4*-5
for i=3,a[3]=4,search for a[3] position in the list(right occurence).a[3]=4
position in list is '2'
add '2' to resultresult[3]=2
remove the element a[3] from the list.now list contains 2-4-5
for i=4,a[4]=5,search for a[4] position in the list(right occurence).a[4]=5
position in list is '2'
add '2' to resultresult[4]=2
remove the element a[4] from the list.now list contains 2-*4*
for i=5,a[5]=4,search for a[5] position in the list(right occurence).a[5]=4
position in list is '1'
add '1' to resultresult[5]=1
remove the element a[5] from the list.now list contains 2
for i=6,a[6]=2,search for a[6] position in the list(right occurence).a[6]=2
position in list is '0'
add '0' to resultresult[6]=0
remove the element a[6] from the list.now list is empty.
resultant array contains :
from all conditions :
add '0' to result.===result[0]=0;
add '2' to resultresult[1]=2
add '1' to resultresult[2]=1
add '1' to resultresult[3]=2
add '2' to resultresult[4]=2
add '1' to resultresult[5]=1
add '0' to resultresult[6]=0
expected result {0,2,1,2,2,1,0}
actual result =={0,2,1,2,2,1,0}
I hope u r clear now.Please let me know if you still have
doubts...
U can execute the java code given in link :
http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elements-on-right.html
I will be more happy if you give me failed cases...
On Wed, Jul 27, 2011 at 11:25 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@rajeev :try the example given in the question. And explain ur algo with
that example
--
Thank You
Rajeev Kumar
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
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 somseka...@gmail.com
wrote:
On Tue, Jul 26, 2011 at 7:18 PM, Piyush Sinha ecstasy.piy...@gmail.com
wrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
A straight forward question
for i in 0 to n-1:
temp = 0;
for j in i+1 to n-1:
if arr[j]= arr[i]:
temp++;
ar_low[i] = temp
But the trick is to find a better algorithm with better complexity
Regards,
B.C.Someshwar
--
'Talk sense to a fool and he calls you foolish.' - Euripides
My Blog: somsekaran.wordpress.com
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
* 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 elements in the less than the current element on right side. -after remove the current element from the sorted list. PS: list is preferred datastructure because there are so many insertion and deletion operations. check this link : http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elements-on-right.html * On Tue, Jul 26, 2011 at 11:08 AM, ankit sambyal ankitsamb...@gmail.comwrote: @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 group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
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 : 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 elements in the less than the current element on right side. -after remove the current element from the sorted list. PS: list is preferred datastructure because there are so many insertion and deletion operations. check this link :http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elemen... * On Tue, Jul 26, 2011 at 11:08 AM, ankit sambyal ankitsamb...@gmail.comwrote: @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 group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
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 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@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 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 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 *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 aakashj@gmail.com wrote: 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 *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 5/24/11, Aakash Johari aakashj@gmail.com wrote: 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 aakashj@gmail.com wrote: 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 *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 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 5/24/11, Aakash Johari aakashj@gmail.com wrote: 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 aakashj@gmail.com wrote: 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 *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 ranges p, p/2;
now apply binary search in range (p/2 p)
that is cal f(p+p/2) compare the value from n. accordigly move left or
right.
till (p - p/2 != 1)
solution is o(log(n));
hopefully i am clear.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 24, 2011 at 6:52 AM, anshu mishra anshumishra6...@gmail.comwrote:
@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 ranges p, p/2;
now apply binary search in range (p/2 p)
that is cal f(p+p/2) compare the value from n. accordigly move left or
right.
till (p - p/2 != 1)
solution is o(log(n));
hopefully i am clear.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 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 24, 2011 at 6:52 AM, anshu mishra
anshumishra6...@gmail.comwrote:
@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 ranges p, p/2;
now apply binary search in range (p/2 p)
that is cal f(p+p/2) compare the value from n. accordigly move left or
right.
till (p - p/2 != 1)
solution is o(log(n));
hopefully i am clear.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@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 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 for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@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 for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 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 for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 there exists any shortcurt method/mathematical
formulae for it or not..
On 5/24/11, 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 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 for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@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 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 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 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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));
}
}
int findNearestFibLessthanK(int k) {
int upper = INTEGER_MAX_VALUE;
int lower = 0;
int incr = 1;
int fibLower = 0;
while (lower upper) {
fibLower = fibonacci(lower + incr);
if (fibLower k) {
incr = 1;
} else if (fibLower == k) {
return fibLower;
} else {
upper = incr;
lower += incr 1;
incr = 1;
}
}
return fibLower;
}
Thanks,
Immanuel
On Tue, May 24, 2011 at 8:09 PM, Aakash Johari aakashj@gmail.comwrote:
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 there exists any shortcurt method/mathematical
formulae for it or not..
On 5/24/11, 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 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 for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@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 in O(logn) using Matrix Representation that i also know will post later..its little modification of nth Fibonacci number. Thanks Shashank Reach Me +99-9739002481 -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
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 every1clear optimization 2ndary step... As i have told earlier its similar to find nth Fibonacci number can be done in O(logn) using Matrix Representation that i also know will post later..its little modification of nth Fibonacci number. Thanks Shashank Reach Me +99-9739002481 -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
