Re: [algogeeks] VIDEO STREAMING

[Prateek Gupta]

@kartik +1:P :P

PS : pardon the pun.


On Sat, Nov 24, 2012 at 11:42 AM, Kartik Sachan wrote:

>
> hey anybody has any idea about video streaming using vlcj lib ??
>
>
> --
>
> *WITH REGARDS,
>
> *KARTIK SACHAN
>  B.Tech. Final Year
> Computer Science And Engineering
> Motilal Nehru National Institute of Technology,Allahabad
> Phone No: +91-9451012943
> E-mail: kartik.sac...@gmail.com
>
>
>  --
>
>
>

-- 

Re: [algogeeks] Re: time complexity of gcd euclid algo(recursive)

[Dave]

@Pralaybi: You've got it right. Since h is proportional to the log of the 
smaller number, we also can say that the complexity is O(log^2 (smaller 
number)).
 
Dave

On Friday, November 23, 2012 2:09:01 PM UTC-6, pralaybi...@gmail.com wrote:

> @Dave: Could you please correct me if am wrong here.
> 1) So we are looking out for the worst case, and that happens when m and n 
> are consecutive Fibo numbers, being mutually prime to reach other.
> 2) Its taking 5 iterations to reduce the number of digits in the smaller 
> of m and n, by one. Assuming there are "h" digits in the smaller number 
> from now on.
> 3) Also, the computation cost is proportional to the number of digits, 
> hence cost is proportional to h. (Could you please elaborate a lil more on 
> this)
> 4) So net complexity is h*h = O(quadratic)
>
> On Fri, Nov 16, 2012 at 8:50 PM, Dave  >wrote:
>
>> @Sonesh: Not so. The worst case for Euclid's algorithm is when the 
>> numbers are consecutive Fibonacci numbers. So (89,55) --> (55,34) --> 
>> (34,21) --> (21,13) --> (13,8) --> (8,5), so it took 5 steps to reduce the 
>> number of digits of the first number from 2 to 1. Asymptotically, the 
>> number of digits reduces by log_10(phi) =  log_10((1+sqrt(5))/2) ~= 0.209, 
>> where phi is the Golden Ratio, so it takes, on average, ~4.78 iterations to 
>> reduce the numbers by 1 digit, in the worst case. But still, we can say 
>> that Euclid's algorithm is O(log n).
>>  
>> Dave
>>
>> On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote:
>>
>>> you see, in each step of recursion, the number of digits in *n* is 
>>> decrease by one(at least in worst case), so the complexity you can decide.
>>>
>>> On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote:

 hi

 Can anyone help me find out the time complexity of recursive gcd 
 algorithm (using euclid's algo)
 i.e. for the following program :

 int gcd(int n,int m) //given n>m
 {
if(n%m==0)
return m;
else
 return gcd(m,n%m);

 }

 i think the soln is lg(a*b) but have no idea how..

  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msg/algogeeks/-/bCB-L41X6ukJ.
>>
>> To post to this group, send email to algo...@googlegroups.com
>> .
>> To unsubscribe from this group, send email to 
>> algogeeks+...@googlegroups.com .
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 

Re: [algogeeks] fastest sequential access

[shady]

assume there are no additional insertions, so we care about only accessing
an element.

On Sat, Nov 24, 2012 at 12:30 AM, Pralay Biswas
wrote:

> non synced data structure = not thread safe in most prog languages!
>
> On Fri, Nov 23, 2012 at 9:00 AM, Atul Singh wrote:
>
>> @Pralay.. can u give a more detail about "non synced data structure"
>>
>>  --
>>
>>
>>
>
>  --
>
>
>

-- 

Re: [algogeeks] Re: time complexity of gcd euclid algo(recursive)

[Pralay Biswas]

@Dave: Could you please correct me if am wrong here.
1) So we are looking out for the worst case, and that happens when m and n
are consecutive Fibo numbers, being mutually prime to reach other.
2) Its taking 5 iterations to reduce the number of digits in the smaller of
m and n, by one. Assuming there are "h" digits in the smaller number from
now on.
3) Also, the computation cost is proportional to the number of digits,
hence cost is proportional to h. (Could you please elaborate a lil more on
this)
4) So net complexity is h*h = O(quadratic)

On Fri, Nov 16, 2012 at 8:50 PM, Dave  wrote:

> @Sonesh: Not so. The worst case for Euclid's algorithm is when the numbers
> are consecutive Fibonacci numbers. So (89,55) --> (55,34) --> (34,21) -->
> (21,13) --> (13,8) --> (8,5), so it took 5 steps to reduce the number of
> digits of the first number from 2 to 1. Asymptotically, the number of
> digits reduces by log_10(phi) =  log_10((1+sqrt(5))/2) ~= 0.209, where phi
> is the Golden Ratio, so it takes, on average, ~4.78 iterations to reduce
> the numbers by 1 digit, in the worst case. But still, we can say that
> Euclid's algorithm is O(log n).
>
> Dave
>
> On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote:
>
>> you see, in each step of recursion, the number of digits in *n* is
>> decrease by one(at least in worst case), so the complexity you can decide.
>>
>> On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote:
>>>
>>> hi
>>>
>>> Can anyone help me find out the time complexity of recursive gcd
>>> algorithm (using euclid's algo)
>>> i.e. for the following program :
>>>
>>> int gcd(int n,int m) //given n>m
>>> {
>>>if(n%m==0)
>>>return m;
>>>else
>>> return gcd(m,n%m);
>>>
>>> }
>>>
>>> i think the soln is lg(a*b) but have no idea how..
>>>
>>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/bCB-L41X6ukJ.
>
> 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] fastest sequential access

[Pralay Biswas]

Also, vectors are not contiguously memory slotted "always". Its a expanding
array where the resizing takes place on demand. There are times when the
array backing the vector is resized and re-allocated, but even then the
amortized cost of insertion stays linear (O(n)).  Although it makes sense
to think that since all the microprocessor requires to do is an
index*datasize calculation in case of an array or a vector, it would be
interesting to note what happens to the execution runtime of two-way
sequential access when there are frequent
insertion-deletion-sequential-access cycles. My guess is that since there
would be frequent insertions, that would trigger a vector doubling
frequently (which translates to resizing and reallocation, an expensive
operation). I guess if the application does frequent random insertions and
random deletions and then looks for sequential accesses, DLL can beat
vector.

On Fri, Nov 23, 2012 at 9:00 AM, Atul Singh  wrote:

> @Pralay.. can u give a more detail about "non synced data structure"
>
>  --
>
>
>

-- 

Re: [algogeeks] Openings in Amazon

[vishwa]

On Friday 23 November 2012 09:29 PM, Vivek Ramamoorthy wrote:

Hi,
Amazon is hiring people for software development projects undergoing 
at Blore, Hyd and Chennai divisions.There are openings for Software 
Development Engineer, Software Development Engineer in Test, 
Application Engineer and for Quality Assurance Engineer positions 
.Send me your resume if you are interested.




--
/Vivek Ramamoorthy,
/SDE,
Amazon,
Chennai.
--


Are they have real concern for CGPA. mine is little less.. working 1+ 
year experience


--

Re: [algogeeks] Re: Largest contigious subarray with average greather than k

[Sachin Chitale]

@ bharat, koup

Sorry I missed this condition...
Algo can tweaked little bit further to cover all conditions..
Algorithm-->
1. Find out start and end index of contiguous subarray which* has sum >0 *
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
  2.1 other wise run a loop through start to end index and remove trailing
elements by increasing start
 2.2 simultaneously check avg..this will lead to proper subarray.
3. In similar fashion start reducing end valuse keeping start
constant.do it sub steps of 2...

Check out the code...Time Com.. O(n) Space  O(1)
compare result of 2 and 3 and choose d best one...

public class LongestConArrMaxAvg{
static int maxAvgSum(int a[], float k) {
int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
tsum;
boolean flag = false;

for (int i = 0; i < a.length; i++) {

if (max_ending_here == 0)
s = e = i;

max_ending_here = max_ending_here + a[i];

if (max_ending_here < 0) {
max_ending_here = 0;
s = e = -1;
}
if ( max_ending_here>0) {
max_so_far = max_ending_here;

e = i;
}

}

if (avgGreater(max_so_far, s, e, k)){
System.out.println("Result subarray start index:" + s
+ " End index:" + e);
return max_so_far;
}
/*This will generate two sequence use optimal time complexity of this algo
is O(n)
 *
 *
 */
 if (s >= 0 && !avgGreater(max_so_far, s, e, k)) {
max_ending_here = max_so_far;
ts = s;
te = e;

while (ts < te) {

max_ending_here -= a[ts];
if (avgGreater(max_ending_here, ts+1, te, k)) {
ts++;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
ts++;
}
ts = s;
te = e;
max_ending_here = max_so_far;
while (ts < te) {

max_ending_here -= a[te];
if (avgGreater(max_ending_here, ts, te-1, k)) {
te--;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
te--;
}

}

return max_so_far;
}

static boolean avgGreater(int sum, int s, int e, float k) {
float t= (float) (sum / (e - s + 1));
 return t>=k? true : false;
}

public static void main(String[] args) {

int[] a = {7,10,-1};
maxAvgSum(a, 5);
}

}


On Fri, Nov 23, 2012 at 4:14 PM, bharat b wrote:

> @ sachin : again u misunderstood the question .. question says *longest*..
>
> As per u'r algo ..
> 1. Find out start and end index of contiguous subarray which has max sum
> O(n)
> 2.Once u have start and end index calculate avg if it satisfies the
> condition then done O(n)
>   *NO -- > even if it satisifies, that may not be the longest *
> *Ex: {7,10,-1} and k=5 => as per u'r algo .. ans would be {7,10}-> avg is
> >5. But and is {7,10,-1}-> avg is >5.*
>
>
>
> On Wed, Nov 21, 2012 at 11:51 PM, Sachin Chitale <
> sachinchital...@gmail.com> wrote:
>
>> Implementation
>>
>> public class Kadanes {
>> static int maxAvgSum(int a[], float k) {
>> int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
>> tsum;
>>  boolean flag = false;
>>
>> for (int i = 0; i < a.length; i++) {
>>
>>  if (max_ending_here == 0)
>>  s = e = i;
>>
>> max_ending_here = max_ending_here + a[i];
>>
>> if (max_ending_here < 0) {
>>  max_ending_here = 0;
>> s = e = -1;
>> }
>>  if (max_so_far < max_ending_here) {
>>  max_so_far = max_ending_here;
>>
>> e = i;
>> }
>>
>> }
>>
>> if (avgGreater(max_so_far, s, e, k)){
>> System.out.println("Result subarray start index:" + s
>>  + " End index:" + e);
>> return max_so_far;
>>  }
>> /*This will generate two sequence use optimal time complexity of this
>> algo is O(n)
>>  *
>>  *
>>  */
>>  if (s >= 0 && !avgGreater(max_so_far, s, e, k)) {
>>  max_ending_here = max_so_far;
>> ts = s;
>> te = e;
>>
>> while (ts < te) {
>>
>> max_ending_here -= a[ts];
>> if (avgGreater(max_ending_here, ts+1, te, k)) {
>>  ts++;
>> System.out.println("Result subarray start index:" + ts
>> + " End index:" + te);
>>  break;
>> }
>> ts++;
>> }
>>  ts = s;
>> te = e;
>> max_ending_here = max_so_far;
>>  while (ts < te) {
>>
>> max_ending_here -= a[te];
>> if (avgGreater(max_ending_here, ts, te-1, k)) {
>>  te--;
>> System.out.println("Result subarray start index:" + ts
>> + " End index:" + te);
>>  break;
>> }
>> te--;
>> }
>>
>> }
>>
>> return max_so_far;
>> }
>>
>> static boolean avgGreater(int sum, int s, int e, float k) {
>> float t= (float) (sum / (e - s + 1));
>>  return t>=k? true : false;
>> }
>>
>>  public static void main(String[] args) {
>>
>> int[] a = { 100, 10, -1, -1, 4, -1, 7, 2, 8 };
>>  System.out.println(maxAvgSum(a, 5));
>> }
>> }
>>
>>
>> On Wed, Nov 21, 2012 at 10:07 PM, Sachin Chitale <
>> sachinchital...@gmail.com> wrote:
>>
>>> Hello,
>>>
>>> Algorithm-->
>>> 1. Find out start and end index of contiguous subarray which has max sum
>>> O(n)
>>> 2.Once u have start and end index calculate avg if it satisfies the
>>> condition then done O(n)
>>>   2.1 other wise run a loop through start to end index and remove
>>> trailing elements by increasing start
>>>  2.2 simultaneously check avg..this will lead to proper subarray.
>>> 3. In similar fashion start reducing end val

Re: [algogeeks] fastest sequential access

[Atul Singh]

@Pralay.. can u give a more detail about "non synced data structure"

-- 

Re: [algogeeks] Openings in Amazon

[SAL BOOSTER]

Any experience is needed for to apply this job..???


On Fri, Nov 23, 2012 at 9:29 PM, Vivek Ramamoorthy wrote:

> Hi,
> Amazon is hiring people for software development projects undergoing at
> Blore, Hyd and Chennai divisions.There are openings for Software
> Development Engineer, Software Development Engineer in Test, Application
> Engineer and for Quality Assurance Engineer positions .Send me your resume
> if you are interested.
>
>
>
> --
> *Vivek Ramamoorthy,
> *SDE,
> Amazon,
> Chennai.
>
> --
>
>
>

-- 

Re: [algogeeks] Number of keys in root of B Tree have?

[Trevor Fernando]

Maximum no. of nodes in a B-tree : ∑ from i=0 to h-1 of (n+1)^i = 1/n * (
(n+1)^h -1). This is the case as, each node can have a max. of n keys, then
it will have a max. of n+1 children. So then summing up the max. no. of
children from the root till the level h-1, gives the total no. of nodes
possible in a B-tree.

Since each node has a max. of k-keys then,
Max. no. of keys in a B-tree = n * 1/n * ((n+1)^h -1) = *(n+1)^h - 1*

On Tue, Nov 20, 2012 at 11:14 AM, Sonu  wrote:

> Whats the formula used here? Can someone explain please.
>
>
> On Mon, Nov 19, 2012 at 12:25 PM, Sambhavna Singh  > wrote:
>
>> n here denotes the degree of the btree
>>
>>
>> On Mon, Nov 19, 2012 at 12:25 PM, Sambhavna Singh <
>> coolsambha...@gmail.com> wrote:
>>
>>> maximum number of keys in root of btree with n=3 is 2.
>>>
>>>
>>> On Sun, Nov 18, 2012 at 6:54 PM, ankita  wrote:
>>>
  maximum number of keys can B Tree have if degree =3?

 --



>>>
>>>
>>  --
>>
>>
>>
>
>  --
>
>
>

-- 

Re: [algogeeks] fastest sequential access

[Pralay Biswas]

i)   vector = A non synced data structure good for random access and bad
for insertions,deletions and sequential scans.
ii)  Singly linked list = Bad for random access, good for one way
sequential access, good for insertions in the middle.
iii) Doubly linked list = Bad for random access, best for two way
sequential access, good for insertions in the middle.

Pralay Biswas
MS-CS, University of California Irvine

On Wed, Nov 21, 2012 at 6:51 AM, shady  wrote:

> which data structure among the follow has fastest sequential access ?
> i)   vector
> ii)  Singly linked list
> iii) Doubly linked list
>
> it won't be doubly linked list as it involves more pointer manipulations
> than singly linked list...
>
> --
>
>
>

-- 

Re: [algogeeks] fastest sequential access

[Pralay Biswas]

I am sorry, vectors are synced and hence slow (concurrency overhead,
arraylists are non synced). Rest remain the same, if your application
demands frequent two way sequential scans, go for DLL.

Pralay Biswas
MS-CS, University of California Irvine


On Wed, Nov 21, 2012 at 6:57 AM, Pralay Biswas
wrote:

> i)   vector = A non synced data structure good for random access and bad
> for insertions,deletions and sequential scans.
> ii)  Singly linked list = Bad for random access, good for one way
> sequential access, good for insertions in the middle.
> iii) Doubly linked list = Bad for random access, best for two way
> sequential access, good for insertions in the middle.
>
> Pralay Biswas
> MS-CS, University of California Irvine
>
> On Wed, Nov 21, 2012 at 6:51 AM, shady  wrote:
>
>> which data structure among the follow has fastest sequential access ?
>> i)   vector
>> ii)  Singly linked list
>> iii) Doubly linked list
>>
>> it won't be doubly linked list as it involves more pointer manipulations
>> than singly linked list...
>>
>> --
>>
>>
>>
>
>

-- 

Re: [algogeeks] fastest sequential access

[Atul Singh]

i would rather suggest vector for "FAST SEQUENTIAL ACCESS"
as Vector contain elements in contiguous memory locations...so cache
locality is good in case of it
as in case of Singly Linked List or Doubly Linked List,, cached locality is
not good,, Sequntial access would not be fast in a long run..


On Thu, Nov 22, 2012 at 1:12 PM, atul anand  wrote:

> @shady : as subject says "fastest sequential access " , then if i am not
> getting it wrong.we only care of sequential access a value not modifying
> the linked list.
> so i guess double linked list would be helpful
> 1) bcozz it can move in both the direction , so if linked list is sorted
> then it would be a great help
> 2) if you want to insert element at the end of linked list then if will be
> better than vector
> so i guess it required 1-2 more parameter to decide ,which one to use.
>
> On Wed, Nov 21, 2012 at 8:21 PM, shady  wrote:
>
>> which data structure among the follow has fastest sequential access ?
>> i)   vector
>> ii)  Singly linked list
>> iii) Doubly linked list
>>
>> it won't be doubly linked list as it involves more pointer manipulations
>> than singly linked list...
>>
>> --
>>
>>
>>
>
>  --
>
>
>



-- 

*ATul Singh** Software Engineer**, Interra Systems*
Mobile : +91-9410826039
www.interrrasystems.com
[image: Facebook]  [image:
Twitter]
 [image: LinkedIn] 

-- 

Re: [algogeeks] Openings in Amazon

[shady]

no more replies on this thread please.

On Fri, Nov 23, 2012 at 9:29 PM, Vivek Ramamoorthy wrote:

> Hi,
> Amazon is hiring people for software development projects undergoing at
> Blore, Hyd and Chennai divisions.There are openings for Software
> Development Engineer, Software Development Engineer in Test, Application
> Engineer and for Quality Assurance Engineer positions .Send me your resume
> if you are interested.
>
>
>
> --
> *Vivek Ramamoorthy,
> *SDE,
> Amazon,
> Chennai.
>
> --
>
>
>

-- 

[algogeeks] Openings in Amazon

[Vivek Ramamoorthy]

Hi,
Amazon is hiring people for software development projects undergoing at
Blore, Hyd and Chennai divisions.There are openings for Software
Development Engineer, Software Development Engineer in Test, Application
Engineer and for Quality Assurance Engineer positions .Send me your resume
if you are interested.



-- 
*Vivek Ramamoorthy,
*SDE,
Amazon,
Chennai.

-- 

Re: [algogeeks] Re: Largest contigious subarray with average greather than k

[bharat b]

@ sachin : again u misunderstood the question .. question says *longest* ..

As per u'r algo ..
1. Find out start and end index of contiguous subarray which has max sum
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
  *NO -- > even if it satisifies, that may not be the longest *
*Ex: {7,10,-1} and k=5 => as per u'r algo .. ans would be {7,10}-> avg is
>5. But and is {7,10,-1}-> avg is >5.*



On Wed, Nov 21, 2012 at 11:51 PM, Sachin Chitale
wrote:

> Implementation
>
> public class Kadanes {
> static int maxAvgSum(int a[], float k) {
> int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
> tsum;
>  boolean flag = false;
>
> for (int i = 0; i < a.length; i++) {
>
> if (max_ending_here == 0)
>  s = e = i;
>
> max_ending_here = max_ending_here + a[i];
>
> if (max_ending_here < 0) {
>  max_ending_here = 0;
> s = e = -1;
> }
> if (max_so_far < max_ending_here) {
>  max_so_far = max_ending_here;
>
> e = i;
> }
>
> }
>
> if (avgGreater(max_so_far, s, e, k)){
> System.out.println("Result subarray start index:" + s
>  + " End index:" + e);
> return max_so_far;
>  }
> /*This will generate two sequence use optimal time complexity of this algo
> is O(n)
>  *
>  *
>  */
>  if (s >= 0 && !avgGreater(max_so_far, s, e, k)) {
>  max_ending_here = max_so_far;
> ts = s;
> te = e;
>
> while (ts < te) {
>
> max_ending_here -= a[ts];
> if (avgGreater(max_ending_here, ts+1, te, k)) {
>  ts++;
> System.out.println("Result subarray start index:" + ts
> + " End index:" + te);
>  break;
> }
> ts++;
> }
>  ts = s;
> te = e;
> max_ending_here = max_so_far;
>  while (ts < te) {
>
> max_ending_here -= a[te];
> if (avgGreater(max_ending_here, ts, te-1, k)) {
>  te--;
> System.out.println("Result subarray start index:" + ts
> + " End index:" + te);
>  break;
> }
> te--;
> }
>
> }
>
> return max_so_far;
> }
>
> static boolean avgGreater(int sum, int s, int e, float k) {
> float t= (float) (sum / (e - s + 1));
>  return t>=k? true : false;
> }
>
>  public static void main(String[] args) {
>
> int[] a = { 100, 10, -1, -1, 4, -1, 7, 2, 8 };
>  System.out.println(maxAvgSum(a, 5));
> }
> }
>
>
> On Wed, Nov 21, 2012 at 10:07 PM, Sachin Chitale <
> sachinchital...@gmail.com> wrote:
>
>> Hello,
>>
>> Algorithm-->
>> 1. Find out start and end index of contiguous subarray which has max sum
>> O(n)
>> 2.Once u have start and end index calculate avg if it satisfies the
>> condition then done O(n)
>>   2.1 other wise run a loop through start to end index and remove
>> trailing elements by increasing start
>>  2.2 simultaneously check avg..this will lead to proper subarray.
>> 3. In similar fashion start reducing end valuse keeping start
>> constant.do it sub steps of 2...
>>
>> compare result of 2 and 3 and choose d best one...
>> give me some time to write code
>>
>>
>> On Wed, Nov 21, 2012 at 12:29 AM, Koup  wrote:
>>
>>> To be correct I need the longest subarray that has an average greater
>>> than k but my main problem here is to find the longest one. Thank you !
>>>
>>> --
>>>
>>>
>>>
>>
>>
>>
>> --
>> Regards,
>> Sachin Chitale
>> Application Engineer SCJP, SCWCD
>> Contact# : +91 8086284349, 9892159511
>> Oracle Corporation
>>
>
>
>
> --
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation
>
> --
>
>
>

--