Re: [algogeeks] find out all pairs of numbers a,b such that a^2+b^2 = N
Replace all elements of array by its square.and sort it Now question is to find two nos in the array such that their sum is N. For this take two pointers min and max Initialize min to 0 and max to n-1(n-size of array) 1.find the sum a[min]+a[max] 2.if sumN max=max-1 if sumN min=min+1 if sum==N we have a sol Now in case of nonunique values all possible pairs must be displayed eg for 2 2 3 3 N =5 min=0,max 3 is a sol but u need to display all combination of 2 and 3 for that i used tempmin=position till which we have a value a[min] and temp max postion till which we have a value a[max] and display all possible combinations. P.S. This was asked to me in Amazon -- 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
in above algo primary index is no of times that value is repeated till now -- 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
I can think of an o(n^2) algo for 2n question Make a heap formed acctoring to two indexes 1.Primary -value 2.Secondary - index Now for each new incoming value first search in head if exist inc its index else make a new node -- 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] Modified String Searching
the difference array for range 4-7 is [1,1,0,1] it is not a sol [2,2,1,1](index no 7) -[1,1,1,0](index of 3)
Re: [algogeeks] maximum disjoint sets
Make a directed graph out of the set of edges where an edge indicates the the sets are not disjoint . Now question is to remove min no of sets so that no sets exist. for this apply the following algo 1.Select the edge with of min degree(nonzero) delete its parent. 2.repeat the step 1 on the modified graph. --
Re: [algogeeks] Modified String Searching
@Sairam i m 100 % sure about the correctness of the algo.i have proven it with test case.. Only way u can prove it wrong is to give a counter case not by intutive feeling. if u find the diffence of count arrays for two indexes i and j then it indicates the count of the string starting from i and ending at j.Now whats wrong in that --
Re: [algogeeks] MS Question
not possible unless u use augmented bst..which itself takes o(n) to built --
Re: [algogeeks] Modified String Searching
This is a test This is a programming test This is a programming test in any language 1 1 1 122 2 2 233 3 3 3 3 33(count of this) 0 0 1 111 2 2 222 3 3 3 3 33 (count of a) 0 0 0 111 1 1 222 2 2 3 3 33 (count of test) 0 0 0 000 0 1 111 1 2 2 2 22 (count of programming) 0 1 2 345 6 7 8910 11 12 13 14 15 16 (index) now we need to select 2 indexes such tha the diff array i greater or equal to [1,1,1,1] (0,7) (1,7) (6,9) etc are some sol out of which (6,9) is min --
Re: [algogeeks] Modified String Searching
to make it O(n logn) 1.Chose one index O(n) 2.For this index do a bsearch on remaining array to find the postion bsearch can be done as the array is an increasing function(it donotes no of occurrence of each word,so=previous index value) bsearch will be done like this 1.make a new temp array that is sum of the array to be found([1,1,1,1])and the chosen index array 2.now take the middle element array if all values of array are eual to temp array u have ans; if any one value is lesser go to right half else goto left half finally while returnin(after while loop) do chck greater than condition again --
Re: [algogeeks] matrix Multiplication
consider code to find n^k where n is an integer int power() { int ans=1,val=1; while(k) { val=val*n; if(k1)ans=ans*val; k=k1; } return ans; } now if n is is a matrix all you have to do is replace * by matrix multiplication algorithm --
Re: [algogeeks] Modified String Searching
O(nlogn) algo for each postion in paragraph store the frequency of the given words(from start point to this point) . now in resultant array you need to two indexes that have =1 value in the difference of the frequency of two points. eg hello hello are you hello ,you hello hello are you 1 2 22 (freq of hello) 0 0 01 (freq of you) for index 0 we get index 3 for index 1 we get index 3 for index 2 we have no value for index 3 we have no vale ans=3-1+1=3 NOTE:INDEX represents word no. --
Re: [algogeeks] matrix Multiplication
both recursive and iterative codes are O(nlogn) algos.. but memory will be more in recursion.. so we will prefer iteration --
Re: [algogeeks] matrix Multiplication
@dave thanks for correcting :) --
Re: [algogeeks] Remove duplicates from min-heap.
yaar i can think of only 2 methods for this 1. O(nlogn) o(n) sol traverse the heap...and hash the elements..if it exist then delete it 2.make another heap but transfering elements from 1st to 2nd heap...if the element is equal to the last inserted element then discard it -- 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] print spiral
void spiral(int a[][],int m,int n) { int c=1; -- 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] Microsoft Interview Question
void change(int a[],int n) { int i,j; i=0; j=1; while(injn) { if(ji) j=i+1; else if(a[j]0a[i]0) { swap(a,j,i); } else { if(a[j]0) j++; else i++; } } } -- 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: Power(n^n)
@abhisheikh read the problem statement again...it says 1000 digits not 1000 value.. -- 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] plz reply quickly
loop in a link list doesn't necessarily mean a circular link list(d one u hav assumed) eg in this case 1-2-3-4-5-3 there is a loop which in order to detect requires d use of hair tortoise rule -- 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] affect of change
the value of d expression i++ is a integer constant.so u cant assign to a value 20 to it same is d case if u execute (i++)++; On 8/30/11, rahul vatsa vatsa.ra...@gmail.com wrote: @nidhi, if u change the i++ to ++i in D, it will compile, bt off course it will keep on printing 20 in an infinite loop. i just tried it, nd it compiles. invalid lvalue in assignment will be when it is i++. On Tue, Aug 30, 2011 at 1:06 PM, nidhi jain nidhi.jain311...@gmail.comwrote: @rahul: it is still giving an error (invalid lvalue in assignment). -- 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. -- 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: Let's see if U can find the bug...
@Don Which compiler r u usingi m getting d correct o/p for pow as well On 8/31/11, Don dondod...@gmail.com wrote: pow works with double (floating point) values, not integers, and when you assign the result to an integer, it truncates. You will be better off, both in speed and correctness, to just use r*r*r instead of pow(r, 3). Don On Aug 30, 1:06 am, Mohit Gupta mohitgupta.n...@gmail.com wrote: *1.* /* Print armstrong numbers from 1 to 500 */ /*1st version of prgrm: I am using pow function*/ #includestdio.h #includeconio.h #includemath.h int main() { int num=1,temp,sum,r; while(num=500){ sum=0; temp=num; while(temp){ r=temp%10; sum+=pow(r,3); temp/=10; } if(sum==num) printf(%d\n,num); num++;} getch(); return 0; } It prints : 1 370 371 407 But it does not print 153 which is also armstrong number. WHY??? BUT if I change: pow(r,3) to r*r*r in codethen it prints: 1 153 370 371 407 WHY 153 was not printed if i use pow() function??? -- 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.