[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

Adding to the question. See inline. On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: > > There are n Intervals. *1 <= n <= 1,000,000.* *Limits of interval are > within 64 bit signed int.* Given a set of m numbers, tell in how many > intervals does each number exists. > Example:

Re: [algogeeks] Re: Google Interview Question: In how many intervals does a number exists

Can you tell the 'size' of your array 'f' if the intervals are [0, 10], [10, 9223372036854775808] ? Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

Monish, please take a look at a similar problem about poor elephants in the neighboring topic started today. I believe the problem has a similar solution. Each start point increases the no. of active intervals by one; each end point decreases it. So, we do the following: 1. Convert the inpu

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

typo mistake "take prefix sum of f and see each index value..."continue On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: > > There are n Intervals. Given a set of m numbers, tell in how many > intervals does each number exists. > Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Nu

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

yeah interval tree and binary indexed tree is a one solution which will give you answer in log(n) time for each query ,but if i got all the interval at the beigning of time i can get solution in O(1) time by O(n ) preprocessing take array f initialize with zero,now for each interval(l,r) do f[l

Re: [algogeeks] Re: GOOGLE Q1

In the first pass create a difference array of size n-1 where n is the size of the input array. D[i] = A[i+1] - A[i] Look for for the longest consecutive no. of times an element is repeated in the difference array. public void longestAP(int[] a, int n) { int[] diff = new int[n-1];

[algogeeks] Re: GOOGLE Q1

On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote: > Given an array of integers A, give an algorithm to find the longest > Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, > such that > > A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the > largest

Re: [algogeeks] Re: GOOGLE Q1

http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf On Fri, Nov 16, 2012 at 8:55 PM, rajesh pandey wrote: > I think its the stricter version of LIS , where when you see for the > increasing number , just see the number which is greater with the number k > than the previous one. > > Thanks , >

Re: [algogeeks] Re: GOOGLE Q1

I think its the stricter version of LIS , where when you see for the increasing number , just see the number which is greater with the number k than the previous one. Thanks , Rajesh Pandey On Fri, Nov 16, 2012 at 7:55 PM, bharat b wrote: > @deepak : all the numbers in the array should be con

Re: [algogeeks] Re: GOOGLE Q1

@deepak : all the numbers in the array should be continuous or those k elemenst can be any where ? On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra wrote: > > > On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: >> >> Given an array of integers A, give an algorithm to find the longest

[algogeeks] Re: GOOGLE Q1

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: > > Given an array of integers A, give an algorithm to find the longest > Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, > such that > > A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the > larg

[algogeeks] Re: GOOGLE Q1

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: > > Given an array of integers A, give an algorithm to find the longest > Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, > such that > > A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the > larg

Re: [algogeeks] Re: GOOGLE Q1

sdfsdfsdfsdfsdf On Monday, 11 July 2011 17:01:36 UTC+5:30, Sunny wrote: > > @Divye sir > yeah that will work fine if D is in reasonable limits .. > > On Mon, Jul 11, 2011 at 4:26 PM, DK >wrote: > >> @Ritu: Your solution is incorrect. >> >> Consider >> >> 1 3 41 43 47 49 90 100 110 >> >> Maximu

[algogeeks] Re: GOOGLE Q1

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: > > Given an array of integers A, give an algorithm to find the longest > Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, > such that > > A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the > larg

Re: [algogeeks] Re: Google Q : all anagrams next to each other

A solution given below taken from "cracking the Coding interview " book... Solution is create a Comparator and a small change in "compare" method is that u sort the characters of that string and then compare. and just sort the arrays, using this compareTo method instead of the usual one. Arrays.s

[algogeeks] Re: [Google question]

@ above small correction.. /* By O(n^3), in this case it means O((N/K ^ K)) . */ Therefore, N = 9, K=3.. hence (9/3)^3 = 27 On Aug 4, 4:24 am, Lucifer wrote: > @vikas > I believe that if we generalize the question saying that there are N > students and K schools, such that each school can acc

[algogeeks] Re: [Google question]

@vikas I believe that if we generalize the question saying that there are N students and K schools, such that each school can accommodate at max (N/K) students (which means each school needs to accommodate exactly (N/K) students. Given this we need to find the minimum distance. By O(n^3), in this

[algogeeks] Re: [Google question]

What is N? This is a fixed-size problem so by definition, every solution will be constant time. Don On Aug 1, 2:48 am, vikas rai wrote: > There is a set of 9 students and 3 schools Every school can be alloted > atmax 3 students .Every school and student has its coordinates .Now we have > to allot

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

I think it can be done by using some randomized algorithm. Divide the array into subarrays of equal size and then pick a random element from each group.Do it 3-4 times,if random number comes out equal for most of the times,return that element. I haven't tried it. On Fri, Jul 13, 2012 at 10:53 AM,

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

I guess the linktalks about modified quick sort approach. Remember, if your choise of pivot is bad everytime, this will have a worst case performance of O(n). You should refer to Selection Algorithm

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

can some body please explain voting algo to me . On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar wrote: > @sachin: > > > http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html > > On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal > wrote: > >> To Mr. B >> how will you find media

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

@sachin: http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal wrote: > To Mr. B > how will you find median in O(n) time? please elaborate. > > > On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: >> >> I found a sim

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

@sachin: you can find median in linear sort. http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal wrote: > To Mr. B > how will you find median in O(n) time? please elaborate. > > > On Wednesday, July 11, 2012 4:01:43 AM UTC+5

[algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: > > I found a similar solution looking somewhere else. > > The solution for this problem is: > a. There can be atmost 3 elements (only 3 distinct elements with each > rep

[algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

My previous email got sent accidentally.. Assume if we have 90 elements and need to find 30 elements that are repeating..as per Sanjay's algo,divide it to 45 elements.. To find majority in 45 elements, the number should repeat >= 23 times.. This might not be valid since the number could repea

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

i think the concept of majority elemnt can be applied here . 1.divide array into 2 halves 2.apply majority in each 3.den from d two majority found do linear counts of dere frequency?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To pos

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

we can use voting algorithm this.. maintain a variable count and a variable index.now make a scan for 1 to n-3.during a scan initialize count with 1 and index with 0.now if a[i]==a[index] then increment count else decrement count.when count reached 0.start again incrementing it when u get a new ele

Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

@above > > On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: >> >> >> Design an algorithm that, given a list of n elements in an array, finds >> all the elements that appear more than n/3 times in the list. The algorithm >> should run in linear time >> >> ( n >=0 ). >> >> You are exp

[algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

Keep reading from stream/array until you have three distinct numbers. Once you have them, throw one occurrence of each of the three distinct element away. At the end of the stream, you should have only such elements who occur more than n/3 times. (You don't actually have to store all the number

Re: [algogeeks] Re: Google Q : all anagrams next to each other

@jalaj :- we will be sorting a copy of the word and then matching the sorted_sequence with the sorted_sequence of the copy of other words. It will still be in-place, because we are using a space of Word size where the input is a dictionary. This is an amortized in-place. -- Navin Kumar Gupta C

[algogeeks] Re: Google Q : all anagrams next to each other

This will work in fine, but multiplying primes requires arbitrary precision arithmetic for keys of any significant length. You don't need to compute a hash at all. Just maintain two buffers long enough to hold the longest word and an O(n) sort like counting sort. If you are using Latin (8-bit) c

Re: [algogeeks] Re: Google Q : all anagrams next to each other

I have a doubt. If u r doing inplace sorting of a word during checks for a word, wouldnt that change that word there itself? then how will the original anagram get restored to arrange in the output in sorted manner? On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar wrote: > The complexity will be (

Re: [algogeeks] Re: Google Q : all anagrams next to each other

The complexity will be (N^2)W because the sorting can be done linear time O(W) for strings. On Thu, May 24, 2012 at 3:44 PM, WgpShashank wrote: > Yeah , its the in-place approach strikes in mind at first look , just > slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of > words in

[algogeeks] Re: Google Q : all anagrams next to each other

Yeah , its the in-place approach strikes in mind at first look , just slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of words in array & W is length of longest word in array , let me know i missed something ? original eat I ate att I the eel eth het after sorti

[algogeeks] Re: Google Q: longest word made of subwords within the list

@prem: can you please explain the approach clearly, I did't get the approach. regards Abhishek On May 23, 7:43 pm, Doom wrote: > I am trying to understand the question.. please let me know the answer for > the following cases.. > > case1: > test > testlong > testlongtest > testlongtestlong > tes

[algogeeks] Re: Google Q: longest word made of subwords within the list

I am trying to understand the question.. please let me know the answer for the following cases.. case1: test testlong testlongtest testlongtestlong testtesttest case2: test testlong testlongtest case3: test longest case4: test testtes ttes testtesttes On Tuesday, 22 May 2012 18:15:16 UTC+5:3

[algogeeks] Re: Google Q : all anagrams next to each other

It can be done inplace, then Time Complexity will be O( N^2 x W ) where N is no. of words and W is word size. Start from the left and sort the current word. Keep a pointer PTR to the first index of the element left to process. Initially it will be 0.As we add words this pointer moves forwards.

[algogeeks] Re: Google Question Invoice -bills

Atul, I think that your approach will work, although it may take a huge amount of time. One way to potentially make it faster is to select the invoices with the smallest number of combinations first. If you first select all of the invoices with exactly one possible combination, this will prevent yo

[algogeeks] Re: Google Question Invoice -bills

If there is a way to do this in polynomial time I would like to see it. Don On Mar 26, 3:04 am, Ankush Bagotra wrote: > There are 210 Invoices and 1700 bills – these bills add up to these invoices > > The association between  bills and invoices is lost . The only way to > match them is by adding

Re: [algogeeks] Re: Google written test

@Hemesh : dats would be an over kill , you are converting O(n) solution to a subset sum problem which NP On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh wrote: > Isn't it a standard subset sum problem? You can generate the Fibonacci > numbers and put them in an array. Now just apply the standard al

Re: [algogeeks] Re: Google written test

Isn't it a standard subset sum problem? You can generate the Fibonacci numbers and put them in an array. Now just apply the standard algorithm to find that which Fibonacci numbers add up to make the given sum. Please correct me if I am wrong. On Mon, Mar 19, 2012 at 8:58 PM, atul anand wrote: >

Re: [algogeeks] Re: Google written test

@Gene : yeah i skipped ur updated code...its dere @shady : it is similar to fib encoding...you just need to reverse the output from gene code and append '1' at the end... while decoding it ...this extra '1' is not considered.. i am nt sure but maybe the reason for adding '1' at the end is to m

Re: [algogeeks] Re: Google written test

@gene it does show your updated code. @atul from the given input it seems different from Fibonacci encoding. On Mon, Mar 19, 2012 at 5:32 PM, Gene wrote: > Thanks. > > I noticed this too. If the n'th 1/0 digit is supposed to correspond > with the n'th fibonacci number, then my original code wo

[algogeeks] Re: Google written test

Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is

[algogeeks] Re: Google written test

It looks from the example like you pick the largest (as if the digits were a binary number). Here's what I get: #include unsigned f(unsigned n, unsigned fi, unsigned fim1) { if (fi > n) return n; unsigned r = f(n, fi + fim1, fi); if (r >= fi) { putchar('1'); return r - fi; } p

[algogeeks] Re: Google written test

It looks from the example like you pick the largest (as if the digits were a binary number). Here's what I get: #include unsigned f(unsigned n, unsigned fi, unsigned fim1) { if (fi > n) return n; unsigned r = f(n, fi + fim1, fi); if (r >= fi) { putchar('1'); return r - fi; } p

Re: [algogeeks] Re: Google

VCE hyderabad On Mon, Mar 5, 2012 at 3:28 PM, adarsh kumar wrote: > Which college? > > On Sun, Mar 4, 2012 at 10:16 AM, teja bala wrote: > >> Google is visiting our campus 4 different roles As of now IT field >> technician is confirmed so how to approach 4 written test. ?? >> >> -- >> Y

Re: [algogeeks] Re: Google

Which college? On Sun, Mar 4, 2012 at 10:16 AM, teja bala wrote: > Google is visiting our campus 4 different roles As of now IT field > technician is confirmed so how to approach 4 written test. ?? > > -- > You received this message because you are subscribed to the Google Groups > "Algo

[algogeeks] Re: Google

Google is visiting our campus 4 different roles As of now IT field technician is confirmed so how to approach 4 written test. ?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegro

Re: [algogeeks] Re: google question

@Dave : is it a working code?? i have executed your code but getting wrong output...and value of s is becoming -ve inside loops. -- 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.

[algogeeks] Re: google question

Well the OP is not clear. You could be right. I solved this problem once before, and there the glasses were arranged in a pyramid like they do at weddings in my country (this will only look right if you set the fixed-width font in Groups: U U U U U U U U U U U U U U U --- Y

Re: [algogeeks] Re: google question

0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h - 1, i+1) ) i am not clear why the parents of a cup in upper row are consecutive? Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Feb 28, 2012 at 10:43 AM, Gene wro

Re: [algogeeks] Re: google question

@Gene , @dave : +1 +1 On Tue, Feb 28, 2012 at 10:49 AM, atul anand wrote: > @Dave : yeah sorry its O(n) where n is number of nodes. > yeah as i said before its a nice approach... > > > On Tue, Feb 28, 2012 at 10:15 AM, Dave wrote: > >> @Atul: I don't have an n in my algorithm, so I'm not sure wh

Re: [algogeeks] Re: google question

@Dave : yeah sorry its O(n) where n is number of nodes. yeah as i said before its a nice approach... On Tue, Feb 28, 2012 at 10:15 AM, Dave wrote: > @Atul: I don't have an n in my algorithm, so I'm not sure what your > assessment that my algorithm is O(n^2) means. My algorithm is O(h^2), > where

[algogeeks] Re: google question

G is just a helper function. You can "in line" this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 <= i-1 <= h-1 and F(h-1,i-1) > C else 0 and r = F(h-1,i) - C if 0 <= i <= h-1 and F(h-1,i) > C else 0 Here l is the left

[algogeeks] Re: google question

@Atul: I don't have an n in my algorithm, so I'm not sure what your assessment that my algorithm is O(n^2) means. My algorithm is O(h^2), where h is the height of the triangle of cups, but the number of cups is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is yours. You'll have to adm

Re: [algogeeks] Re: google question

@Dave : my code is not that complicated ...if you ignore the helper function and check fillCup(); it just similar to preorder travesal and pour half to left and right child. here is the explanation :- node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) ret

Re: [algogeeks] Re: google question

Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene wrote: > G(h - 1, i - 1) + G(h - 1, i) -- You r

[algogeeks] Re: google question

Dave's code is good. Here is a more abstract way of thinking about it. Maybe helpful? Number the rows starting at the top with h=0, and the left i=0. Then the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When h<0, i<0 or i >h, the parent does not exist. Let F(h, i) be the amount

[algogeeks] Re: google question

@Ashish: I didn't make any assumption that nothing comes from the left. Does my code give the wrong answer? Dave On Feb 27, 10:36 am, Ashish Goel wrote: > Dave, why the assumption that nothing is coming from left side. > > Every cup gets something from cup left above and right above itself when

Re: [algogeeks] Re: google question

Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dav

[algogeeks] Re: google question

The previous proposed solutions all seem far too complicated. It is not necessary to use a graph data structure. We can simply use an array to store the quantities of the cups in a row, and update the array to move to the next row. It would look something like this: double cupQuan(double L, double

Re: [algogeeks] Re: google question

@Ravi: checkout this code...i have created tree where there is sharing of nodes.. here is my code :- please let me know is case you find any bug. #include typedef struct tree{ int idx; float data; struct tree *left; struct tree *right; }node; node *createNode(int index) { node *temp; temp=(n

Re: [algogeeks] Re: google question

@all same doubt qstn appears to be of binary tree DS but the diagram given in between qstn is not like Binary tree so sharing is there so how sharing is done plz explain?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this

[algogeeks] Re: google question

You are assuming is to be a binary tree, its not. Some nodes will share a common "pour". On Feb 25, 9:24 pm, atul anand wrote: > i guess this would work... > n=number of nodes > h=height; > pour=quantity poured; > capacity = capacity of each cup > > n=pow(2,h+1) -1; > call(capacity,pour,0,n) > >

Re: [algogeeks] Re: Google-Puzzle

it will the diff is of fuel and dist forms the content of array which moves from 1 to 2n-1 elements(break the circle and instead of elem like 1,2,n have 1,2,n,1,2,...n-1 i.e. total 2n-1 so that mod stuff is not required. now find maxsubSum such that sum>=0 and count of nodes is n not clear ehy i

[algogeeks] Re: Google-Puzzle

buddy i said that kadane's algo(max subsum) wouldn't work.. On Feb 25, 1:31 pm, Ashish Goel wrote: > max subsum problem > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s > wrote: > > > >

Re: [algogeeks] Re: google questions

@all: how is the problem solved using a heap...can someone explain. did not understand what was on the net... On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra wrote: > I am proposing a solution for problem 2.. > >2. > > Given a text file, implement a solution to find out if a pattern > > similar to wi

[algogeeks] Re: Google Question--Suggest Algo

Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking at N/ K (3n/2k - n/2k) sub problems.. Hence, the running time will be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin

[algogeeks] Re: Google Question--Suggest Algo

Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking at N/ K (3n/2k - n/2k) sub problems.. Hence, the running time would be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin

[algogeeks] Re: Google Question--Suggest Algo

Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking N/K (3n/2k - n/2k) sub problems.. Hence, the running time would be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin Gar

[algogeeks] Re: Google Question--Suggest Algo

Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking N/K (3n/2k - n/2k) sub problems.. Hence, the running time would be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin G

Re: [algogeeks] Re: Google Question--Suggest Algo

I don't think it is O(N*K) It is O(N^2) Just to confirm if i have understood correctly Lets say n and k are given and are global to all subproblems Subproblem Definition F[i,j] -> maximum expected sum that we can get by partitioning array from 0 to i into j subarrays. Each subarray satisfies the s

[algogeeks] Re: Google Question--Suggest Algo

Hi I may not have understood your solution properly. But i think that your solution is an implementation of brute force where you are dealing with all cases valid in the range n/2k and 3n/2k without any optimization with regard to DP. Am i right? On Nov 28, 2:17 am, sourabh wrote: > Consider the

[algogeeks] Re: Google Question--Suggest Algo

O(N*K) On Nov 28, 1:04 pm, Nitin Garg wrote: > @Sourabh - whats the running time? > > > > > > > > > > On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg wrote: > > Cool Solution...I was thinking of DP but wasnt clear on the recurrence... > > > Nice thinking man and thanks :) > > > On Mon, Nov 28, 2011

Re: [algogeeks] Re: Google Question--Suggest Algo

@Sourabh - whats the running time? On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg wrote: > Cool Solution...I was thinking of DP but wasnt clear on the recurrence... > > Nice thinking man and thanks :) > > > > > On Mon, Nov 28, 2011 at 2:47 AM, sourabh wrote: > >> Consider the example that you have

Re: [algogeeks] Re: Google Question--Suggest Algo

Cool Solution...I was thinking of DP but wasnt clear on the recurrence... Nice thinking man and thanks :) On Mon, Nov 28, 2011 at 2:47 AM, sourabh wrote: > Consider the example that you have given: > [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 > > Now we need to partition the array into 3

[algogeeks] Re: Google Question--Suggest Algo

Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this cons

Re: [algogeeks] Re: Google Question--Suggest Algo

Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh wrote: > Looks like a dynamic programming problem > > Say F(n,k) denotes the maximum expected sum value f

[algogeeks] Re: Google Question--Suggest Algo

Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) <= r <= floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base conditio

[algogeeks] Re: Google Question--Suggest Algo

Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover wrote: > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 > why this is not the optimal split??? > > > > > > > > On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg wro

[algogeeks] Re: Google Interview Question

How was your interview? Can you please share the questions for benefit of others? On Oct 1, 3:37 pm, Siddhartha Banerjee wrote: > lol!!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@

Re: [algogeeks] Re: google os ques on pipelining

Thats right. Clock speed is governed by slowest processing stage + register delay. With clock cycle of (160+5) ns even the faster stages will be forced to run slowly. As a result 1st instruction will take 165*4 ns and rest of following 999 instructions will take 165*999 ns. On Tue, Sep 27, 2011 a

Re: [algogeeks] Re: google os ques on pipelining

clock period=(slowest stage delay)+(Buffer delay). slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will always be there between two stages . clock period=165ns. In the pipelining the time it takes =(k+n-1) * (clock period) k=number of stages and n=number of instructions(data

Re: [algogeeks] Re: google os ques on pipelining

585 + (160 + 5)for slowest transactions *999 for the rest of the instructions! On Tue, Sep 27, 2011 at 12:49 AM, Gene wrote: > You guys have the right idea except that since it's multiple choice > you can do this with no math. With 1000 data items and only 4 stages, > the bottleneck has to be t

[algogeeks] Re: google os ques on pipelining

You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:

[algogeeks] Re: google os ques on pipelining

@bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana wrote: > for the first instruction : 150+5+120+5+160+5+140=585 ns > for the rest of the instructions ,

Re: [algogeeks] Re: google maps

@Dave : Very smart answer.. On 20 September 2011 09:31, Dave wrote: > @Sukran: Well, I would hire about 1000 smart people and let them do > it. :-) > > Dave > > On Sep 20, 2:12 am, sukran dhawan wrote: > > How do you implement google maps ? > > -- > You received this message because you are su

Re: [algogeeks] Re: google maps

Well, I think its not that the algorithm be written with all Google maps features in place. Rather it is a open ended question, where interviewer is trying to find the candidates view of algorithm design. @Deepak: It should be fine even if some reasonably good algo is given. my 2 cents: For the sh

Re: [algogeeks] Re: google maps

they are using a highly optimized A* algo for rout finding On Tue, Sep 20, 2011 at 10:01 PM, Dave wrote: > @Sukran: Well, I would hire about 1000 smart people and let them do > it. :-) > > Dave > > On Sep 20, 2:12 am, sukran dhawan wrote: > > How do you implement google maps ? > > -- > You

[algogeeks] Re: google maps

@Sukran: Well, I would hire about 1000 smart people and let them do it. :-) Dave On Sep 20, 2:12 am, sukran dhawan wrote: > How do you implement google maps ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send emai

Re: [algogeeks] Re : google groups

*no, there is no such limit *regards - Sumit Kumar Pathak (Sumit/ Pathak/ SKP ...) *Smile is only good contagious thing.* *Spread it*! On Fri, Sep 9, 2011 at 1:59 PM, shady wrote: > hi, > I am not able to add a person to the algogeeks group. Is there a limit on > the number of people who c

[algogeeks] Re : google groups

hi, I am not able to add a person to the algogeeks group. Is there a limit on the number of people who could join a particular google groups ? At present there are 7960 people :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this

[algogeeks] Re: Google Question:Given a BST and a number, Find the closest node to that number in the BST.

It seems Dipankar Algo is appropriate at this point of time. each time successor and predecessor check needs to be done at each node and the value need to be updated, This is O(log n) approach because once we check, we move into particular direction. On Aug 21, 4:59 pm, rahul aravind wro

[algogeeks] Re: Google Interview Question

This is a well-known problem called "Perfect Shuffle" which has been discussed here before. You should be able to find it with a search. Gene On Aug 1, 4:15 am, Abhishek Gupta wrote: > A is an array of size 2n such that first n elements are integers in any > order and last n elements are charac

Re: [algogeeks] Re: Google Interview Question

@Diniz I guess they asked to do in inplace ( with no extra array ) On Mon, Aug 1, 2011 at 2:41 PM, Douglas Diniz wrote: > This is a simple merge, so what is the trick? Did you forget something? > > On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella wrote: > > Here is O(n) alg... > > Does Waste Mem

Re: [algogeeks] Re: Google Interview Question

This is a simple merge, so what is the trick? Did you forget something? On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella wrote: > Here is O(n) alg... > Does Waste Memory Though :) just don't have an array over 4G, and you > should be good. > > proc Merge_Partition(A) > > B = {}; > index = 0; > count

[algogeeks] Re: Google Interview Question

Here is O(n) alg... Does Waste Memory Though :) just don't have an array over 4G, and you should be good. proc Merge_Partition(A) B = {}; index = 0; count0 = 0; count1 = (n/2); while index to A.length B[index++] = A[count0++]; B[index++] = A[count1++]; end while return B end proc On Aug

Re: [algogeeks] Re: Google interview question

@Dave awesome..! On Sat, Jul 16, 2011 at 7:15 PM, Dave wrote: > @Anand: Assuming that the file contains unsigned 32-bit integers. Set > an integer array a[65536] to zero, read through the file and tally the > numbers based on their low-order 16 bits: a[j&0x]++. Since 4.3 > billion exceeds 2^

  1   2   3   4   >