Re: [algogeeks] Re: spy in the city
O(N) if everybody knows everybody. O(N^2) if there is no such condition. (i.e. Ask for each person to everybody.) On Mon, Dec 20, 2010 at 9:43 PM, Bhavesh Chauhan chauhan.bhave...@gmail.com wrote: Every question can eliminate 1 person so you can identify the spy in N-1 questions. Bhavesh On 19 December 2010 23:46, Dave dave_and_da...@juno.com wrote: Here is an algorithm: spy = 1 for i = 2 to N do if person[spy] knows person[i] then person[i] is not the spy. else if person[i] knows person[spy] then person[spy] is not the spy, set spy = i end if end for for i = 1 to spy-1 do if (person[spy] does not know person[i]) or (person[i] knows person[spy]) then there is no spy, set spy = undefined, break end if end for If there is a spy, you find him in at least 2*N - 2 questions and at most 4*N - 4 questions. Dave On Dec 19, 8:01 am, snehal jain learner@gmail.com wrote: There is a city of N people. The government learnt that some unfriendly nation planted a spy there. A spy possesses unique characteristics: he knows everybody in the city, but nobody knows him. You are a counteragent sent by the government to catch the spy. You may ask the people in the city only one question: Do you know the person X? You may ask as many people as you wish, and one person may be asked as many times as you wish. All the people, including the spy, always answer honestly. How many questions you need to find out who is the spy? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send 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 algoge...@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 algoge...@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] Amazon Interview
http://en.wikipedia.org/wiki/Run-length_encoding On Wed, Sep 15, 2010 at 5:51 PM, bittu shashank7andr...@gmail.com wrote: A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm
How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required... On Wed, Jul 28, 2010 at 7:46 AM, Gene gene.ress...@gmail.com wrote: I think you have confused the statement of this problem. The (in sorted order) comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@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 algoge...@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: Largest even length palindrome in a string!!
Suffix tree is obviously there but 1. It requires more lots of space. Just draw a suffix tree and you will know. 2. Pre-processing takes time. We cant ignore this time because its proportional to N. There is one linear solution described here: http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ Still trying to understand O(N) algo.. On Sun, Jun 6, 2010 at 2:15 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: i think it can be done in O(n) using suffix trees. but making suffix tree also requires O(n) space and O(n) time... attached is the ppt (it has the same example)... On Sun, Jun 6, 2010 at 1:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but actually we need something better as per prob, cannot be done in O(n). so we need to think of something like O(n lg n) or O( n ^ 3/2) :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@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 algoge...@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] Best Data Structure for this?
Use hash table with customer ID as key. There can be three components in value: 1. num_days 2. pages 3. flag For each line, calculate hash, find value for given key. Increment appropriate values (i.e. pages or num_days). If num_days 1 pages 1, add this customer to result array, mark this customer's flag and don't process that customer further. On Sun, Jun 6, 2010 at 2:52 PM, amit amitjaspal...@gmail.com wrote: Google has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff. Lets say you store the data of customer id and the page id as a record in a log-file. Now assuming that you have created one log file for each day with that above data- format. Give me the way to find all the customers who made a visit on day1 and day2 and visited atleast two different pages. Say a customer visited two different pages on day1 and then comes back on day2 and visited some other page on day2 he should be listed. Lets say the logfile1 has contents like: c1 p1 c2 p2 c1 p3 c3 p4 c5 p6 And logfile2 has contents: c10 c7 c4 p4 c3 p4 c5 p1 c1 p2 c2 p1 Then the customers you print out are c1, c2, c5. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send 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 algoge...@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: Find Max Number of Elephants
1. have an array of N years. starting with first year and ending at last year. O(N) space here. initialise all elements to zero. 2. Take array of E and birthyear first. Whenever you encounter new birthyear, do array[year]++. 3. Take array of E and deathyear now. Whenever you encounter new deathyear, do array[year]--. 4. Parse this array of year. sum_for_given_year += array[year] To me, it looks like O(N). Correct me if I am wrong. On Sun, Jun 6, 2010 at 7:56 PM, Anurag Sharma anuragvic...@gmail.com wrote: I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote: I think you can do this in O(n) time. Feel free to correct me where I'm wrong. Create a 2D array with years on one side and elephant's time alive on the other. example: 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 E1 1 1 1 1 1 1 1 1 1 E2 1 1 1 1 1 1 1 1 1 E3 1 1 1 1 Now for every years add vertical indices example 2006 = 3, 2007 = 3, 2008 = 3 and so on. This will give you the year with max elephant population. The array can be init with 0 or a static array can be used. @Anurag: How will you approach this problem by using LCA algorithm that your link leads to? On Jun 5, 6:16 am, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send 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 algoge...@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 algoge...@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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send 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 algoge...@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] question
step 1: Sort array in place. Lets call it A. (N log N)
step 2: Create two additional copies of array, lets call them B and C. (this
is just for explanation, we can operate on same array A).
step 3: Take first element from array A. lets say its value is X. Find pair
from B and C whose sum is nearest to -X.
This step of finding pair is similar to Binary Search as array is sorted.
step 4: Repeat step 3 for entire array A.
On Mon, May 17, 2010 at 9:58 PM, Anurag Sharma anuragvic...@gmail.comwrote:
oops!
Anurag Sharma
On Mon, May 17, 2010 at 5:00 PM, Navin Naidu navinmna...@gmail.comwrote:
@anurag:
-99 -2 -1 3 +99
The min sum (=0) for value pair (-99, 99)
Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1
Actual result: -2, -1, 3 : 0
On Mon, May 17, 2010 at 8:48 AM, Anurag Sharma anuragvic...@gmail.comwrote:
@Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
1. Sort the array in nlogn time: array={-99,-1,0,2,99}
2. consider all possible pairs of numbers and keep track of the sum
closest 2 zero:
-99+-1=-100, |-100|=100
-99+0=-99,|-99|=99
-99+2=-97,|-97|=97
-99+99=0,|0|=0 --- this is the minimum sum(=0) for value pair
(-99, 99)
-1+0=-1,|-1|=1
-1+2=1,|1|=1
-1+99=98,|98|=98
0+2=2,|2|=2
0+99=99,|99|=99
2+99=101,|101|=101
3. Now traversing the array skipping the values -99, 99 and trying to get
minimum sum after including it in the existing sum :
array={-99,-1,0,2,99}
take -99: skip
take -1: 0+-1= -1 and |-1|=1
take 0: 0+0=0 and |0|=0 this is the minimum so the third number
is 0
take 2: 0+2=2 and |2|=2
take 99: skip
this way we got the three numbers as -99,99 and 0. Were you expecting
some other combo?
In step 3 we can skip checking the rest of the elements when we find the
sum increasing as the array is already sorted.
Let me know if there is still some issue in it.
Regards,
Anurag Sharma
On Sun, May 16, 2010 at 9:26 PM, Navin Naidu navinmna...@gmail.comwrote:
@anurag: wont work, consider the following case: -99 0 2 -1 99
On Sun, May 16, 2010 at 9:12 PM, Rohit Saraf
rohit.kumar.sa...@gmail.com wrote:
@anurag : won't work
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
- NMN
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send 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 algoge...@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.
--
Thanks Regards,
- NMN
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send 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 algoge...@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 algoge...@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.
