Re: [algogeeks] Re: MS Interview

2011-06-11 Thread Ashim Kapoor
Could someone illustrate the XOR for question 2. I am a beginner to this.

Many thanks!

On Thu, Jun 9, 2011 at 4:58 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:

 Xoring it twice ...once with the elements in the file and then from i=1 to
 4,000,000,000..the answer left is the missing number

 On Thu, Jun 9, 2011 at 4:46 PM, Dumanshu duman...@gmail.com wrote:

 I dont think numbers are sorted in the 1st question. btw
 @sunny: how will xor-ing give the ans? for 1st ques?


 On Jun 9, 3:34 pm, sunny agrawal sunny816.i...@gmail.com wrote:
  yes, but using xor no need of ULL :)
 
  2011/6/9 • » νιρυℓ « • vipulmehta.1...@gmail.com

 
 
 
 
 
 
 
 
 
   Sum wont overflow, ULL range will include sum.
 
   On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal 
 sunny816.i...@gmail.comwrote:

 
   sum can overflow
   Xor method can also be applied to Q1. no need of numbers to be
 sorted.
 
   2011/6/9 • » νιρυℓ « • vipulmehta.1...@gmail.com

 
   For 1.
   sum the numbers in the file, subtract it from sum of first 4 billion
   numbers.
 
   On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta 
 navneetn...@gmail.comwrote:

 
   The answer to second question is simple. XORing all the elements
   should do it for you.
 
On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu duman...@gmail.com
 wrote:
Q1. I  have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the
 missing
number.
 
Q2.  I have an array consisting of 2n+1 elements. n elements in
 it are
married, i.e they occur twice in the array, however there is one
element
which only appears once in the array. I need to find that number
 in a
single pass using constant memory. {assume all are positive
 numbers}
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7
 
--
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.
 
   --
   --Navneet
 
   --
   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,
   Vipul
 
--
   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.
 
   --
   Sunny Aggrawal
   B-Tech IV year,CSI
   Indian Institute Of Technology,Roorkee
 
--
   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,
   Vipul
 
--
   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.
 
  --
  Sunny Aggrawal
  B-Tech IV year,CSI
  Indian Institute Of Technology,Roorkee

 --
 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.


-- 
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, 

Re: [algogeeks] MS Q

2011-06-11 Thread Ashim Kapoor
I think RGGB is invalid as we have 4 different colors.


On Fri, Jun 10, 2011 at 10:10 AM, Harshal hc4...@gmail.com wrote:


 #includeiostream
 #includestring

 using namespace std;

 void mastermind(char* guess, char* sol, int *hits, int *pseudohits)
 {
   int temp[256] = {0};
   int len1=strlen(sol);
   int len2=strlen(guess);

   while(--len1+1)
   (guess[len1]==sol[len1]) ? ((*hits)+=1,temp[len1] = 1) : (temp[sol[len1]]
 += 1);

   while(--len2+1)
   if(temp[len2]!=1  temp[guess[len2]]  0)
(*pseudohits)++, temp[guess[len2]] -= 1;
 }

 int main()
 {
 int hits=0,pseudo=0;
 mastermind(RGGB,YRGB,hits,pseudo);
 couthits pseudo;
 }

 On Fri, Jun 10, 2011 at 2:31 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:


 Game of master mind: you have four balls, and four different colors, as a
 solution. The user tries to guess the solution. If they guess the right
 color for the right spot, it counts as a 'hit'. If it's the right color, but
 the wrong spot, it counts as a psuedo-hit. For example: if the solution is
 'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit.
 Write a program to, given a solution and a guess, calculate the number of
 hits and pseudo hits.
 --
 *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.




 --
 Harshal Choudhary,
 III Year B.Tech CSE,
 NIT Surathkal, Karnataka, India.



  --
 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] GOOGLE Q

2011-05-20 Thread Ashim Kapoor
How will BFS give a rearrangement ?

-- 
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] Application of Data Structure System Design

2011-04-06 Thread Ashim Kapoor
int max_calls[no_of_customers][30];

On any phone call -- max_calls[customer_id][day]++;
On hangup -- max_call[customer_id][day]--;

This would store max calls for each customer on each day. Does the length of
the call have to be taken into account ? Your question is not clear on that.



On Tue, Mar 29, 2011 at 3:51 PM, bittu shashank7andr...@gmail.com wrote:

 Pretend you work for a phone company. At your company, yoy u have a
 satellite that routes phone calls. We want to bill customers by the
 maximum number of simultaneous phone calls they make in a single day.
 ( clarifying questions with  the following information: assume no
 calls last more than 24 hours and that at midnight each night all the
 calls are automatically dropped. In the event that one call ends as
 soon as another starts).

 What information should the satellite store for each phone call?
 Define a data structure for this (e.g. write a struct).
 Write a function that finds the maximum number of simultaneous phone
 calls from a given customer.

 (Hint: typical solution is O(nlogn), but if you use an absurd amount
 of memory  it can be done in O(n)).

 Best Designing  DS, Approach Will b highly Appreciated

 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.



-- 
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] Application of Data Structure System Design

2011-04-06 Thread Ashim Kapoor
no this is wrong. maintain 2 arrays

int max_calls[no of cust][31]
int current_no_of_calls[no of customers]

both array of customers are initialized to zero.

on call
current_no_of_calls[cust_id]++;
if above  max[id][day] then max_calls[id][day] = above

on hangup
current_no_of_calls[cust_id]--;

On Tue, Mar 29, 2011 at 4:29 PM, Ashim Kapoor ashimkap...@gmail.com wrote:


 int max_calls[no_of_customers][30];

 On any phone call -- max_calls[customer_id][day]++;
 On hangup -- max_call[customer_id][day]--;

 This would store max calls for each customer on each day. Does the length
 of the call have to be taken into account ? Your question is not clear on
 that.


 On Tue, Mar 29, 2011 at 3:51 PM, bittu shashank7andr...@gmail.com wrote:

 Pretend you work for a phone company. At your company, yoy u have a

 satellite that routes phone calls. We want to bill customers by the
 maximum number of simultaneous phone calls they make in a single day.
 ( clarifying questions with  the following information: assume no
 calls last more than 24 hours and that at midnight each night all the
 calls are automatically dropped. In the event that one call ends as
 soon as another starts).

 What information should the satellite store for each phone call?
 Define a data structure for this (e.g. write a struct).
 Write a function that finds the maximum number of simultaneous phone
 calls from a given customer.

 (Hint: typical solution is O(nlogn), but if you use an absurd amount
 of memory  it can be done in O(n)).

 Best Designing  DS, Approach Will b highly Appreciated

 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.




-- 
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] finds a pair of close numbers

2011-04-06 Thread Ashim Kapoor
On Fri, Apr 1, 2011 at 6:02 PM, snehal jain learner@gmail.com wrote:

 For a set S of n real numbers, a pair of elements x, y belong to S,
 where x  y, are said to be close if
 y – x = ( max(S) – min(S) ) / (n-1)
 Suppose you are given an unsorted array A[1 : n] of distinct real
 numbers. Design an algorithm that finds a pair of close numbers in A
 in O(n) time.


Take any 2 no.s a and b say 1st and 2nd then a-b = max(S) - min(S)

divide by n-1

(a-b) / (n-1) = (Max - min) /(n-1)

Solution : Any 2 no.s will do

Am I incorrect somewhere ?

-- 
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: Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.

2011-04-06 Thread Ashim Kapoor
One more query, insert into bst is O(n) and then do inorder to get them in
sorted order. This is an example of sorting in O(n) time. is this correct?

On Mon, Mar 28, 2011 at 6:06 PM, Ashim Kapoor ashimkap...@gmail.com wrote:

 How do you use inorder traversal to find longest sub sequence?


 On Mon, Mar 28, 2011 at 6:03 PM, bittu shashank7andr...@gmail.com wrote:

 its (not aplicable).

 sorting nlogn  i said time O(n)   O(1) space

 i think we can use BST , put all elements in BST O(n) then  do inorderto
 find longest sub sequence  still O(n) ..no no no its Ol(ogn)

 suggest another way to solve it

 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.




-- 
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: Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.

2011-04-06 Thread Ashim Kapoor
How do you use inorder traversal to find longest sub sequence?

On Mon, Mar 28, 2011 at 6:03 PM, bittu shashank7andr...@gmail.com wrote:

 its (not aplicable).

 sorting nlogn  i said time O(n)   O(1) space

 i think we can use BST , put all elements in BST O(n) then  do inorder
 to find longest sub sequence  still O(n) ..no no no its Ol(ogn)

 suggest another way to solve it

 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.



-- 
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: finds a pair of close numbers

2011-04-06 Thread Ashim Kapoor
   Hi , Use Hashing for That , for sum =12  arr[]={2,4,3,6,5,8,7}; store

 in to hashtable  for each index=0 in loop find  sum-arr[index]  so
 fro sum =12 if we do index=1 a[1]=4  sum-a[1]=8 so stop it we have
 done..hope make d perfect code.

 time Complxity o(n) space size of hashtable
 Let me me if anything wrong ??


It's not clear to me. Can you please explain in simple words?

-- 
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: Application of Prime Number . An Interesting For Geeks

2011-03-26 Thread Ashim Kapoor
Dear Shashank,

What you are trying to do is called  Goldbach's conjecture . Google for
it. There is a million dollar prize to prove it.

Ashim

On Thu, Mar 24, 2011 at 8:03 PM, ligerdave david.c...@gmail.com wrote:

 I have to say: to prove the correctness of this hypotheses is a
 wrong question and there isn't an algorithm for proving something
 that's infinity.

 even number is 2n, where n=1 to infinity.

 you can only prove the hypotheses through mathematical methods.

 you can verify the correctness. it's like a P=NP kinda thing.


 On Mar 24, 1:49 am, bittu shashank7andr...@gmail.com wrote:
  yesterday one of the my friends asked this Q to me prove with
  correctness that
  Every even integer greater than 2 can be expressed as the sum of two
  primes
e.g
 
4 = 2 + 2
6 = 3 + 3
  10 = 7 + 3 or 5 + 5
  14 = 3 + 11 or 7 + 7
 
  Explain   Derive The Time ,Space Complexity of Algorithm
 
  it seems to be that we have to find all possible prime factor of
  number  prints it its not big task , so by checking that number we
  have to generate the all prime factor of it seems O(n) ..Hope i m
  clear corrcet me if i am wrong here.??
 
  But  problem come when even number become bigger say 1 billion  10^9
  so for this choosing the a number as a prime factor has probability of
  1/ln(n)
  so say if for 1 billion number out of 21 only 1 is prime. .y question
  is we have to prove the time complexity for two
  choosing a number nearby such big number is 1/ln(n)..??
 
  with Heuristic justification it can be explained ro induction might
  help but guarantee here  but i need some
  mathematical proof for this
 
  Thank  Regards
  Shashank Mani
  CSE,BIT Mesra

 --
 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] Pairwise Sum Array

2011-02-26 Thread Ashim Kapoor
I think the output is wrong. It should be

1 3 4 9 n in no call them ai's a[1] to a[n]

4 5 10 7 12 13 m in no call them bi's b[1] to b[m]

I assume starting from 1 to make manipulation easier

n(n-1)/2= m

n(n-1)=2m
n2 -n -2m=0

using quadratic formula:-
n=1 + sqrt( 1+8m)/2
This will always be a whole no if it isnt then error.

Once I know n then what remains is algebraic manipulation. fill in the
following matrix :-

 a1+a2 a1+a3 ... a1+an = b1 ..  bn NOTE! n not m
   a2+a3 ..  a2+an =  b(n+1)..b(2n)

 an-1+an=bm


12 13   1n
 23   2n

(n-1)n


1st ALL C[i][j]=0; i : 1 to n-1 and j : 2 to n
offset=0
Then
for( i=1; i=(n-1) ; i++)
for( j=i+1; j=n ; j++) {
 C[i][j] = b[ offset  + j - 1 ] ;
}
   offset= offset+j-1;
}

for( i=1; i=(n-1) ; i++)
for( j=i+1; j=n ; j++) {
 D[i][j] = C[i][j] - C[i+1][j];
}
}

now C[i][j] = a[i] + a[j]
   D[i][j+1] = a[i]-a[j]


We may solve for the a[i]'s.
( see rough figure below)

Subtract R i+1 from R i

a1+a2 (a1-a2) ... a1-a2 = RHS
   a2+a3  ...a2-a3 = RHS



  an-2+an-1   an-2-an-1 =RHS
 an-1+an=RHS


I am in a hurry as I have to go home now, sorry, but I think people will see
the solution. Is there a better way?

Ashim.




 On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan 
radhakrishnance...@gmail.com wrote:

 This s a topcoder problem :)

 On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote:
  If pairwise sums of 'n' numbers are given in non-decreasing order
  identify the individual numbers. If the sum is corrupted print -1
  Example:
  i/p:
  4 5 7 10 12 13
 
  o/p:
  1 3 4 9
 
 
  Thanks  Regards
  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.
 
 

 --
 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] Pairwise Sum Array

2011-02-26 Thread Ashim Kapoor
That is exactly what my solution is doing.

On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal 
ashish.cooldude...@gmail.com wrote:

 There must be another good solution..please let me know .
 Thanks

 On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal 
 ashish.cooldude...@gmail.com wrote:

 I think..
 As like no are a,b,c,d,e
 so sum will be
 a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e;
 so maximuum value will be d+e which is last element of array given

 take last three value
 1.c+d
 2.c+e
 3.d+e
 eq(1)-eq(2)=d-e;
 solving it with 3rd eq will give d and e
 and with these value we can get other values





 On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan 
 radhakrishnance...@gmail.com wrote:

 This s a topcoder problem :)

 On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com
 wrote:
  If pairwise sums of 'n' numbers are given in non-decreasing order
  identify the individual numbers. If the sum is corrupted print -1
  Example:
  i/p:
  4 5 7 10 12 13
 
  o/p:
  1 3 4 9
 
 
  Thanks  Regards
  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.
 
 

 --
 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] Application Data Structure In Collision Detection

2011-02-22 Thread Ashim Kapoor
also since each object is a rigid body each point in any one object will
have the same equation of motion.

On Wed, Feb 16, 2011 at 8:04 PM, Ashim Kapoor ashimkap...@gmail.com wrote:

 Here is my attempt it's very naive but maybe someone can improve

 each object be a pointer to a set of points { these points are the boundary
 of the object }

 Collision detection : Sweep through each pair of pointers to check for
 equality of the boundary points.

 an example , there are 3 objects a1,a2,a3.

 a1={p1,p2,,pn}
 a2={q1,,qn1}
 a3={r1,...,rn2}

 for each pair ai,aj we have to check if any 2 points in the corressponding
 lists are equal

 the question then becomes What is the fastest way to compare through n
 arrays.

 I dont have a sophisticated way of doing this. Maybe someone can help me ?



 On Wed, Feb 16, 2011 at 5:29 PM, bittu shashank7andr...@gmail.com wrote:

 many irregular shape objects are moving in random direction. provide
 data structure and algo to detect collision. Remember that objects are
 in million.

 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.




-- 
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] Application Data Structure In Collision Detection

2011-02-22 Thread Ashim Kapoor
Here is my attempt it's very naive but maybe someone can improve

each object be a pointer to a set of points { these points are the boundary
of the object }

Collision detection : Sweep through each pair of pointers to check for
equality of the boundary points.

an example , there are 3 objects a1,a2,a3.

a1={p1,p2,,pn}
a2={q1,,qn1}
a3={r1,...,rn2}

for each pair ai,aj we have to check if any 2 points in the corressponding
lists are equal

the question then becomes What is the fastest way to compare through n
arrays.

I dont have a sophisticated way of doing this. Maybe someone can help me ?



On Wed, Feb 16, 2011 at 5:29 PM, bittu shashank7andr...@gmail.com wrote:

 many irregular shape objects are moving in random direction. provide
 data structure and algo to detect collision. Remember that objects are
 in million.

 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.



-- 
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] program for evaluation of remainders

2010-12-08 Thread Ashim Kapoor
Let me try. Any thing involving n would leave no remainder.

so (1  + 2 ! + ... + n ! +  + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod
n

This should be computed from a loop. I don't know how to reduce it further.

Ashim.

On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok ankit4...@gmail.com wrote:

 Q) can anyboy find me the solution to this problem

 Given an integer N and an another integer n we have to write a program
 to find the remainder of the following problems
 (1! + 2! + 3! + 4! + . + N!)mod(n)

 N=100
 n=1000;

 please help me write a program for this problem
 thanx in advance

 --
 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 Question

2010-12-05 Thread Ashim Kapoor
What if we have an array :-

index - 1 2 3 4 5
value - 1 2 3 4 5

How will ANY logn solution determine all ALL elements are equal to it's
index value ? Maybe I misunderstand.

Thank you,
Ashim

On Sat, Dec 4, 2010 at 5:38 PM, ankit sablok ankit4...@gmail.com wrote:

 u can then move to other advance data structures

 On Sat, Dec 4, 2010 at 4:58 PM, mo...@ismu mohan...@gmail.com wrote:

 in worst case it takes o(n)time
 if all the elemets match with their indexes


 --
 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] Re: Amazon Interview Question

2010-12-05 Thread Ashim Kapoor
yaar I can use  simple O(n) sweep to find out who all are equal, I think it
can't be less than this

On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote:

 2010/12/4 ankit sablok ankit4...@gmail.com:
  as all the elements are sorted in the array make a min heap of the
  array elements and as min heap is a tree of keys querying a min heap
  or a binary search tree requires operations with time equal to the
  height of the tree which is log(n) hence time for querying a min heap
 I think you might be use a log(n) time to find out a element whose
 value is equal to some certain index, so the complexity could be
 n*log(n)?

 --
 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] Mathematics Puzzle

2010-11-21 Thread Ashim Kapoor
Do you mean if the rank of a student is better than the rank of the prev
student then he/she gets a lollipop?

Thank you,
Ashim

On Sun, Nov 21, 2010 at 6:57 PM, vamsee marpu marpu.vam...@gmail.comwrote:

 Does anybody know the solution for the following problem :


 *A headmaster of a primary school performs an activity with the students
 of a class to encourage them to perform better in academics. He asks them to
 stand in queue, starts calling the students out one by one and asks them
 their rank in class. Each one has a unique rank in class. If the rank of a
 student is better than his/her previous best rank, then he awards him/ her a
 lollipop (students love lollipops). Note that the first one in the queue
 will always get a lollipop and the students arrange themselves in random
 order in the queue. What is the expected number of lollipops the headmaster
 will have to distribute among students if the total number of students in
 the class is 69? Note that the answer can be a fractional number.*





 Thanks and Regards,
 M. Vamsee

 --
 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] student introduction problems

2010-11-07 Thread Ashim Kapoor
Is'nt this solvable by the majority vote algorithm already discussed in this
list?

Ashim.

On Sun, Nov 7, 2010 at 3:42 AM, lichenga2404 lichenga2...@gmail.com wrote:

 There are many secret groups in College A.Every student at college A
 is a member or these secret group, though membership in one excludes a
 student from joining any other group. You wish to determine if any one
 of these groups contains more than half of the student population. To
 achieve this , you will introduce 2 students to each other: if they
 are members of different group , they will smile. If different group ,
 they will nod. How to determine if any one group has more than half of
 the student population as members in O(n) introductions . And justify
 the answer.

 --
 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] Yahoo coding round question

2010-10-21 Thread Ashim Kapoor
I'm not sure what a 2 hash table is. Can you please explain ?

On Tue, Oct 19, 2010 at 10:36 PM, MOHIT  mohit...@gmail.com wrote:

 o(n)  soln

 Lets say A is the array of length N.
 Create an array sum of length N and initialize it to 0.
 Create an array product of length N and initialize it to 1.

 now sum[i]=sum[i-1]+A[i]; sum[0]=A[0];

product[i]=product[i-1]+A[I]product[0]=A[0];

 make a two hash table for product and sum array ;
 in product arrary traverse i=0 to n ;

 divide result=product[i]/P and check result is present in hash table or not
 if yes then  get index of result .
 suppose k then checkabsolute(sum[i]-sum[k])==S if yes then we got sub
 array.

 else ..keep do this untill array end ;



  --
 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] Re: Drawing a graph

2010-09-17 Thread Ashim Kapoor
what is this red book ?full name please?

On Fri, Sep 17, 2010 at 1:01 PM, vikas kumar vikas.kumar...@gmail.comwrote:

 use opengl library to draw the graph or whatever. take RED BOOK for
 reference.

 On Sep 14, 5:54 pm, Mithun avmit...@gmail.com wrote:
  Can anyone help me with the code for drawing a graph in C or CPP
  (using graphics)
 
  Input is an Adjacency matrix

 --
 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] Re: Amazon Question

2010-09-13 Thread Ashim Kapoor
How would  you define 50% or more similarity ?

On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote:

 trie

 On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote:
  pagerank algo
 
 
 
  On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com
 wrote:
   You are given the amazon.com database which consists of names of
   millions of products. When a user enters a search query for particular
   object with the keyword say foo , output all the products which have
   names having 50% or more similarity with the given keyword ie foo
 
   Write the most efficient algorithm for the same.
 
   --
   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
 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
 
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
  --
  yezhu malai vaasa venkataramana Govinda Govinda

 --
 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] Aricent question

2010-09-11 Thread Ashim Kapoor
The majority vote program ( discussed a couple of days ago ) would work in
this case I think. In the end we would have the modal element with count = 0
(n - n ). Please correct me if I am wrong.

On Sat, Sep 11, 2010 at 3:00 PM, bittu shashank7andr...@gmail.com wrote:

 Given an array of 2n elements of which n elements are same and the
 remaining n elements are all different. Write a C program to find out
 the value which is present n times in the array. There is no
 restriction on the elements in the array. They are random (In
 particular they not sequential).

 --
 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] cyclic String

2010-09-11 Thread Ashim Kapoor
I can do it in 2 O(n)sweeps if all elements are distinct.
12345
23451

Sweep one to find the 1st element of string 1 in string 2.
Sweep 2 to compare each element of the 2 strings from the position mod n
found in the 1st sweep.

I dont know how to do it if elements are repeated.

but the way Praveen does it is really cool i think.

Sat, Sep 11, 2010 at 1:54 PM, Praveen Baskar praveen200...@gmail.comwrote:

 str=hello;
 str1=lloeh;
 if (str+str).subString(str1) is true then the string is cyclic string of
 another


 On Sat, Sep 11, 2010 at 1:52 PM, bittu shashank7andr...@gmail.com wrote:

 How will you check if a string is cyclic string of another

 solution O(n)..???/?? or even less compraiosn..

 --
 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.




 --
 By B. Praveen

  --
 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] DeShaw Question....tough One

2010-09-06 Thread Ashim Kapoor
int a[]={11,9,8,2,10,7,3,4,5}
max_length = 1 ;
current_length = 1;
first_position=0 ;
last_position = 0  ;
first_position_max=0;
// Sweep one to find the length of the longest subsequence.

for ( i = 1 ; i  n ; i++ ) {
  if ( a[i]  a[i-1] ) {
 last_position=i-1;
 current_length=last_position-
first_position+1;
 max_length = current_length  max_length ?
current_length : max_length;
 first_position_max = current_length  max_length ?
first_position : first_position_max;
   first_position= i;
  }
}

// Sweep two to print the longest subsequence.

for ( i = first_position ; i  max_length ; i ++ ) {
   cout a[i];
}


On Mon, Sep 6, 2010 at 2:01 PM, bittu shashank7andr...@gmail.com wrote:

 u are given an array and u have to print the longest increasing
 scattered subsequence...eg..{11,9,8,2,10,7,3,4,5}.


 Solve it O(n);


 --
 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] kth smallest element in a heap x

2010-08-21 Thread Ashim Kapoor
sure, but the implementation is confusing.  My question is does not the 2nd
count overwrite the 1st value of count in side the function?

Thank you.

On Sun, Aug 22, 2010 at 1:04 AM, Harshal ..Bet oN iT!! hc4...@gmail.comwrote:

 if it is a min heap,, then traversing down from the root node, it takes
 O(k) time to reach the kth smallest element. so, i think its just that
 straight!!! plz correct me if m wrong???

 --
 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.



[algogeeks] kth smallest element in a heap x

2010-08-20 Thread Ashim Kapoor
Dear All,

I found this in the book by skeina.

Problem: Given an array-based heap on n elements and a real number x,
efficiently
determine whether the kth smallest element in the heap is greater than or
equal
to x. Your algorithm should be O(k) in the worst-case, independent of the
size of
the heap.

the solution is given as follows.


int heap_compare(priority_queue *q, int i, int count, int x)
{
if ((count = 0) || (i  q-n) return(count);
if (q-q[i]  x) {
count = heap_compare(q, pq_young_child(i), count-1, x);
count = heap_compare(q, pq_young_child(i)+1, count, x);
}
return(count);
}

The explanation is given as follows:
This procedure searches
the children of all nodes of weight smaller than x until either (a) we have
found
k of them, when it returns 0, or (b) they are exhausted, when it returns a
value
greater than zero. Thus it will find enough small elements if they exist.
But how long does it take? The only nodes whose children we look at are
those
 x, and at most k of these in total. Each have at most visited two
children, so we
visit at most 3k nodes, for a total time of O(k).

I dont see how it works. In particular I dont see why count is reset
according to the 2 children of the current node. I am new to this. can some1
explain me what's happening?

Many thank,
Ashim

-- 
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] minimum window containing charecters

2010-08-01 Thread Ashim Kapoor
I am not sure, but can I do this using a suffix trie ? any comments ?



On Sun, Aug 1, 2010 at 2:29 PM, Ashish Goel ashg...@gmail.com wrote:

 solution could be to find the charcter position from both sides for each
 char of s2
 then from the 2*n array, find the smallest index from left and largest from
 right, within these two indexes all chars would be there

 one case where one of the chars can be missing can be found if a row in
 this 2-d array remains unmodified



 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652



 On Sat, Jul 31, 2010 at 10:22 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:

 At the moment, I can only think of an O(n^3) algo.
 Maybe if you can find a hash function which computes the hash value
 depending on the unique characters the string contains, you can reduce it to
 O(n^2).


 On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote:

 given two string , find the minimum  width in string 1 containing the
 all characters of string 2 , they may present in different order
 string 1-HELLO
 string 2- LE
 answer-2

 --
 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.


 Please access the attached hyperlink for an important electronic 
 communications disclaimer: 
 http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php





 --

 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 
 algogeeks%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] Finding the mode in a set of integers

2010-04-17 Thread Ashim Kapoor
are you referring to the lectures by Dr Naveen Garg ? Or are these lectures
different? Please clarify.

Thank you,
Ashim.

On Sat, Apr 17, 2010 at 5:43 AM, rahul rai raikra...@gmail.com wrote:

 On 4/16/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
  Just got another O(n) solution.
 
  Find the n/2 th largest element in the array using the Median of Medians
  Selection algorithm.   =? takes O(n)
  That's It !
 
 
  --
  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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
 Work out the CDEEP Algorithms course lectures . It will give all basics

 --
 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]

2010-03-31 Thread Ashim Kapoor
I think it can be done in logn time ( I assume the list is sorted, is there
an order log n sorting algo, then i can even sort it in log n time ? ( I am
new to algorithms ) ).

1. binary search for low=x1.
2. binary search for high=x2.

both will take log n time. Print all values between them then in O(x2-x1)
time.

Is this correct?
On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:

 With only this info and without preprocessing , you need to scan all the N
 integers in the list atleast once. Hence cannot be better than O(n).
 If preprocessing is allowed you can compute the answers for all n^2 pairs
 of x1,x2 and when some one asks , return the corresponding list.
 In that case it would be better that O(n). !!

 -Rohit




 On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee 
 dona.1...@gmail.comwrote:

 Design an efficient algorithm to report all the points within x1 and x2
 from a list of N integers.
 What data structure will you use to implement this algorithm?
 Find the order of complexity . ( An O(N) solution is not asked)


 --
 Thanks  Regards,
 Priyanka Chatterjee
 Third Year Undergraduate Student,
 Computer Science  Engineering,
 National Institute Of Technology,Durgapur
 India
 http://priyanka-nit.blogspot.com/

 --
 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.