Re: [algogeeks] Amazon interview Question
was trying to do something clever. Knew it couldnt be that simple. Missed some cases. I still feel with some hacks and handling some special cases this approach would work. But considering it still takes O(n) time I am not thrilled. I am still ok with my algo taking Space for time. But probably not the other way unless there are some special constraints. Hashtable it is. Srikar On Thursday, February 7, 2013 12:35:21 PM UTC+5:30, bharat wrote: @srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srika...@gmail.com javascript:wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet@gmail.com javascript: wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.an...@gmail.comjavascript: wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet@gmail.com javascript: wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
*APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: top search queries
@algoose I see what you are saying. what do you propose? checking out your link now... On Thu, Feb 3, 2011 at 11:44 AM, Algoose chase harishp...@gmail.com wrote: @Srikar In your first approach you cant simply ignore the queries that are not present in the heap because you have a stream of queries and you never know if the query that you are about to ignore is going be received frequently or not in future. Your approach is like find the top 100 queries from the stream and keep updating the frequencies of only those queries using heap and hash table. If you have to process some 1,00,000 , with a space for only 100 elements you cant find the frequencies correctly. this is a nice article related to this : http://www.americanscientist.org/issues/pub/the-britney-spears-problem On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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: minimum no. of clicks
hey dave! what do you mean naively clicking O(n)? Can you explain the
exact algo?
If you read the question properly, you should realize that it requires the
minimum clicks.
Naively clicking is not going to give you minimum clicks.
On Wed, Feb 2, 2011 at 3:21 AM, Dave dave_and_da...@juno.com wrote:
@Srikar: Isn't it sort of silly to propose an O(n log n) algorithm
when just naively clicking on the digits in order gives an O(n)
algorithm?
Dave
On Feb 1, 12:04 pm, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com
wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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.comalgogeeks%2bunsubscr...@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] Excel Sheet Question Asked
since the problem uses all 26 letters, we could use a number system with base as 26. 2 operations are - 1) Given number to string - Treat the number as number in base 26. 2) Given string to number. Credit goes here - http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-data-structure-strings On Tue, Feb 1, 2011 at 6:27 PM, bittu shashank7andr...@gmail.com wrote: Given a series A,B,C ...Z, AA, AB,AC,ADAZ,BA,BB...BZ,CA (Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series. also vice versa if given string prints its corresponding string...e.g given AC then its integer is 29 given 40774 its string value is ABZ.. 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.comalgogeeks%2bunsubscr...@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] minimum no. of clicks
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2bunsubscr...@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] top search queries
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 heap). the element at the top of the heap is the query having min-frequency. 2) once we get a query. we check if it is present in the hashtable. if yes then update this query frequency reorder the heap. if no then do nothing. here I assume we want top 100 most queries. this can be easily extended to include all queries having 0.1% frequency. Complexity: time: O(logn) + O(n) [for heap hashtable construction] here n=100 space: 2O(n) Will come up with something better. If extend n to say 1,00,000, the space complexity is going to be a problem. Second Approach, 0) We could use only one min-heap. Each node has the (query, frequency %). 1) get the query from the stream. Traverse the heap to see if this query is already present. If yes then re-calculate the frequency if needed reorder the heap. if query not present in the heap, then calc it's frequency see if the frequency of the node at min-heap is the current query freq. if (curr_query_freq min-heap node freq.) then swap the min-heap node reorder the heap. else continue. Time: O(logn) n=number of queries we want to consider. space: O(n) Srikar On Mon, Jan 31, 2011 at 6:57 PM, snehal jain learner@gmail.com wrote: please give your ideas for this On Fri, Jan 21, 2011 at 2:28 PM, snehal jain learner@gmail.comwrote: 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 problem? Remember we don’t want to store all the queries. Hint: split the stream into windows and accept some error in estimation. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
