pavankumar.thati
BAN USER- -1of 1 vote
AnswersQ1. Given two arrays of size n1, n2, sum up the two arrays in such away that the resultant array is computed in the below way.
- pavankumar.thati in India
arr1 : {a1,a2,a3}
arr2 : {b1,b2,b3,b4}
resultant array : {a1+b1, a1+b2, a1+b3. a1+b4, a2+b1, a2+b2, a2+b3, a2+b4, a3+b1, a3+b2, a3+b3, a3+b4}
find the median of the resultant array in n1 + n2 time .| Report Duplicate | Flag | PURGE
Algorithm
If you are sure it is hard enough to solve in O(n+m) then prove me that we can't solve it. Don't just throw the words.
- pavankumar.thati May 31, 2013how can you treat Binary tree as a graph. for a binary tree you can move in left and right directions but not parent direction. coming to graph you can move in any of the three directions (left, right and parent).
Can you explain with an example how can you treat a binary tree as a graph and do BFS on it and find nodes k hops away from it.
Hi shashi,
Don't you think that you need to mark your visited nodes to avoid infinite loop.
Thanks famee. It seems my approach is totally wrong.
- pavankumar.thati January 30, 2013@suryaamsh: you are correct. btw. can't we use XOR operator. My idea is as below.
I'll do the XOR of both the strings. Next i'll select one of the strings to pick the characters one by one. each time i pick a character i'll do a XOR of character with both strings if both results are equal then i can say i pick a character that is common in both strings. I'll continue this approach and if i pick all the characters then i'll say they are anagrams else they are not.
Example :
string 1 : abcdabc = a+b+c+d+a+b+c
string 2 : acbdcba = a+c+b+d+c+b+a
Now i'll pick characters from string 2 and do XOR with both the strings.
result 1 : a+b+c+d+a+b+c XOR a
and
result 2 : a+c+b+d+c+b+a XOR a
if the result 1 and result 2 are equal then i'll continue with result 1 and result 2 as new strings and pick next character from string 2. if the result 1 and result 2 are not equal then i'll stop and say they are not anagrams.
Please provide me the counter-example if my approach is wrong in anyway.
@alex : I'm looking for a solution with constant space as well.
- pavankumar.thati January 29, 2013
I guess "count" variable should be a reference variable, otherwise you can't keep track of count on the left subtree.
- pavankumar.thati June 03, 2013