10
4 5
2 7 6 11
1 39 8 12 13 14 15
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
@Gaurav: you are taking ia and ib as int so they will have 32 bits in
Java. So you can not set the bits for numbers in the array greater
than 32.
e.g if you have a[i]=59876 so you would want to set the 59876th bit in
ia : ia=ia | (159876) but that is not possible. How do you handle
this?
Also how
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[]
path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
No way u can do it in O(1) space and O(n) time.sols above are not
gonna work..yeah, it is possible in O(n) space and O(n) time.
On May 20, 12:29 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is a
permutation of a.
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else
^not an O(n)
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero
in space
On May 21, 6:53 pm, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for
@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation
constant space vs no additional space and then O(n) time complexity not
possible..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: Using a hash table violates the O(1)
* given a number and its permutation, how can we find out the number of
transformations by which the number could be transformed into its
permutation ?*
*
*
*eg: 2315 and 5213 are given. 2315 can be transformed into 5213 in a series
of 2 transformations. first swap 2 and 3. then swap 3 and 5.*
*
*
Given a string. Tell its rank among all its permutations sorted
lexicographically.
--
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
levenshtein distance
---
Seshu Madhav Chaturvedula
తమసోమా జ్యోతిర్గమయా...
On Mon, May 21, 2012 at 10:53 PM, rahul venkat rahul911...@gmail.comwrote:
* given a number and its permutation, how can we find out the number of
transformations by which the number could be transformed into its
basically question is asking for edit distance with transposition
implementation only.
no need of adding delete,replace condition
On Mon, May 21, 2012 at 10:53 PM, rahul venkat rahul911...@gmail.comwrote:
* given a number and its permutation, how can we find out the number of
transformations
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted string
abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1 elements in
(index-1) ! and right elements from found
I think adjacency list can be implemented by vector of vector.
vector vectorint Nodes;
The size of vector Nodes is total no of nodes.
Every element of the vector will store all its adjacent edges.
Nodes[i] is a vector containing all the edges adjacent to node i.
So, we can copy the graph easily.
I think a better approach can be :- using suffix array.
Suffix array is an array data structure which stores all suffixes of the
input string, sorted in lexicographical order.
Now we need to consider that substring which is repeated m times.
Now since all the suffixes starting with same
You can use Suffix Arrays or Suffix Trees.
On Mon, May 21, 2012 at 8:17 AM, Ashish Goel ashg...@gmail.com wrote:
soln pls
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal
We can consider the 2-d matrix as a heap(also called Young Tableau).
We just need to heapify(Youngify) it k-1times,then the element at 0,0
will be kth smallest element.
This means we need to remove the k-1 smallest elements from matrix and
still maintaining its Row-Col sorted property.
Shouldn't having 2 queues one storing the node and other corresponding
level should be sufficient and do level order traversal?
-mithun
On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote:
bool firstCousins(struct node * pRoot, struct node *pThis, (struct
node*)[] path,
using bit array we can sort elements in O(1)
-mithun
On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.comwrote:
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
By doing Ex-OR we can find if b is permutation of A
suppose a -- 3 5 4
b -- 4 3 5
if A ^ B = 0 then both are permutation or else not
shout loud if this has flaws :P
-mithun
On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote:
given 2 unsorted
@ashish.. it wont be constant space then.. surely it will be o(n) though
On Mon, May 21, 2012 at 7:23 PM, Ashish Goel ashg...@gmail.com wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over
a[] = [-1,-3,4,0,7,0,36,2,-3]
b[] = [0,0,6,2,-1,9,28,1,6]
b1[] = [0,7,0,36,4,-6,3,0,0]
b2[] =[-1,-3,11,0,0,0,35,0,0]
suma = 42 proda = -84*72*3
sumb = 51 prodb = -84*72*3
sumb1 = 44 prodb1 = -84*72*3
sumb2 = 42 prodb2 = 33*35
do the sum and prod operation w/o 0s and compare the values..
//considering node who's cousins need to be find as start..
node * a[10];
while(root!=start)
{
a[i]=root;
i++;
if(root-data start-data)
root=root-left;
else
root=root-right;
}//we can do this using recursion
node *grand=a[i-2];
if(start-data grand-data)
@Partha
try with:
A = {2, 2, 9}
B= {1, 6, 6}
On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
a[] = [-1,-3,4,0,7,0,36,2,-3]
b[] = [0,0,6,2,-1,9,28,1,6]
b1[] = [0,7,0,36,4,-6,3,0,0]
b2[] =[-1,-3,11,0,0,0,35,0,0]
suma = 42 proda = -84*72*3
then waht will be it's recurrence relation
On Mon, May 21, 2012 at 10:44 AM, atul anand atul.87fri...@gmail.comwrote:
basically question is asking for edit distance with transposition
implementation only.
no need of adding delete,replace condition
On Mon, May 21, 2012 at 10:53 PM, rahul
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index -
start_index) *
@mithun: Try
A = 1, 6
B = 4, 3
A ^ B = 0.
Alone Ex-OR cant solve this in O(n) time.
On Monday, 21 May 2012 21:48:30 UTC+5:30, mithun wrote:
By doing Ex-OR we can find if b is permutation of A
suppose a -- 3 5 4
b -- 4 3 5
if A ^ B = 0 then both are permutation or else
How to check if a given binary tree is structurally symmetric ie. the
left sub tree should be mirror image of right sub tree and vice-versa.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
31 matches
Mail list logo
