oh ya thanks now i got it
On Sun, Oct 24, 2010 at 9:54 AM, preetika tyagi preetikaty...@gmail.comwrote:
@Praveen- In this case, we will not ignore the right subtree of the root
(-10, which is less than zero) while traversing the tree.
On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar
@Ravindra: Can you explain the algorithm for step 3 in more detail? I
don't yet see how you do it in O(n^2), since it seems to me that
comparing one A[i,j] to all the A[j,k] is already O(n^2). What am I
missing?
Dave
On Oct 24, 12:05 am, ravindra patel ravindra.it...@gmail.com wrote:
Can be
We can do the following in 2-D plane where the pints are given in the
form of (x.y).
For each selection of three points do the following:
Find the area of the triangle of the three points. Let it be A.
If A is zero then Print Existence of Co-linear points Break.
This can be achieved in C(n,3)
The suggestion will work if the root is known to have entry equal to
zero. (Even it is less than 0, there is a chance that a negative an
reside in right sub-tree whose value is 0 but greater than the
negative value of the root). If the entry of the root is zero then we
can do the inorder
We can do the following.
We associate a variable with each of the node. let it be called level.
We now do BFS on the tree. Whenever we visit a node we do the
following:
node.level = blackNeigbor.level + 1.
Now we again do a BFS to find the number of nodes in each level.
--
You received this
We can follow an algorithm described below.
Set found:= FALSE
For each number n belong to array A.and until found != TRUE
For each number k in A not equal to n, do:
if k+n == m then
output The pairs are n and k
Set found:=TRUE.
Break.
The running time will be of
Consider the following adjacency-matrix representation of a graph,
R(V,E).
Let there be n number of vertices. So we create n*n matrix G[1..n]
[1..n]. Initially set G[i][j]=0 for all 1= i,j =n. This operation
will take O(V).
For each edge e of R let (a,b) be the adjacent vertices, set G[a]
[b]
for the 3th step,
for i=1 to n
for j=i+1 to n
for k=j+1 to n
compare A[i,j] and A[j,k]
if A[i,j]==A[j,k]
find i,j,k are collinear.
so we should need O(n^3), is it right?
On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel ravindra.it...@gmail.comwrote:
Can be done in O(n^2) time
@Dave
I was wrong. It can't be done in O(n^2) time. The best we can do is sort
each row like you suggested in your other post. That will still be
O((n^2)logn).
Thanks,
- Ravindra
On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan mengyan.fu...@gmail.com wrote:
for the 3th step,
for i=1 to n
for
@Dave
I hear ya. Im just saying in general, you would wanna have an
algorithm for all cases.
of coz, in this case, if the RAM isn't a consideration and heapsort is
what @Vinay wants, i guess we are coming up w/ one like that.
again, in general, you don't wanna have one version of program for
king
@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors
It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say the time
complexity is O(1), a pure theoretical concept. But the cost still remains
O(n), isn't it.
I guess now onwards we'll have to specifically ask interviewers whether they
are asking
I think we can sort the elements first and then start scanning from both
ends of the array. All the pairs can be found this way and the complexity
will be O(nlogn).
On Sun, Oct 24, 2010 at 6:08 AM, Avik Mitra tutai...@gmail.com wrote:
We can follow an algorithm described below.
Set found:=
@Mohit: What I understand that in your solution the sum and product array
contains the sum and products of contiguous sub-array starting from 0 to i
(index of array A). What happens when the expected sub array starts form an
index other than 0?
--
You received this message because you are
@ravindra
agree!
On Oct 24, 2:20 pm, ravindra patel ravindra.it...@gmail.com wrote:
@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1
The biggest weakness of the trie is the amount of space it wastes -
chances are there will be runs of characters with a word only at the
end, meaning a bunch of extra levels of the tree that aren't needed.
The PATRICIA trie, or radix trie, attempts to address this by allowing
the 'decision' at
What will be the input for the graph?
Kishen
On Thu, Oct 21, 2010 at 5:22 AM, Algorithimist yogi15...@gmail.com wrote:
Design an algorithm to determine whether a graph has any parallel
edges in time proportional to E + V.
--
You received this message because you are subscribed to the
@preetika : we can use hash table for O(n) complexity ..if array is not
sorted .. i am looking for that answer... how should i make that hash table
so that searching in hash table become O(1) complexity.
--
You received this message because you are subscribed to the Google Groups
Algorithm
MapReduce is the best option .
For the word count its explained here -
http://en.wikipedia.org/wiki/MapReduce
Interesting thing is that the Map step can easily be made parallel.
Once again I request the members of this group to go through all the
parallel constructs. ( Parallel sorting,
@Ravindra, Ligerdave
You guys are all right. But with GPUs, you can literally have thousands of
threads running in parallel.
Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
single processor system.
It was more towards making the members of this group to think on the lines
@saurabh koar : no it will give that sub array .. but kishan das solution
is good...
btw my code explanation is
A: 2 4 356
PRODUCT:2 8 24 120 720
SUM 2 6 9 14 20
suppose i want sum 8 and product 15
make hash table for product array (in hashtable
From Wikipedia:
Thus the MapReduce framework transforms a list of (key, value) pairs into a
list of values. This behavior is different from the functional programming map
and reduce combination, which accepts a list of arbitrary values and returns
one single value that combines all the values
@Mohit : Then insert all the elements in hashtable and scan the hashtable in
O(n) time. While scanning each elements, you have to search for
(sum-element) element in the hashtable (O(1) time). What do you think?
On Sun, Oct 24, 2010 at 12:51 PM, MOHIT mohit...@gmail.com wrote:
@preetika :
23 matches
Mail list logo
