A solution given below taken from cracking the Coding interview book...
Solution is create a Comparator and a small change in compare method is
that u sort the characters of that string and then compare.
and just sort the arrays, using this compareTo method instead of the usual
one.
@jalaj :- we will be sorting a copy of the word and then matching the
sorted_sequence with the sorted_sequence of the copy of other words.
It will still be in-place, because we are using a space of Word size where
the input is a dictionary.
This is an amortized in-place.
--
Navin Kumar Gupta
I have a doubt. If u r doing inplace sorting of a word during checks for a
word, wouldnt that change that word there itself? then how will the
original anagram get restored to arrange in the output in sorted manner?
On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote:
The
Hi, here i maintained two pair of indexes with respect to a and b, reply if
u found any test case which fails..
int npairs()
{
int a[] = {0,1,4,5,9,11,20};
int b[] = {0,2,3,6,8,11,15};
int c[20];
int len = sizeof(a)/sizeof(a[0]);
int i1,j1,i2,j2;
i1=len-1;
j1=len-2;
i2=len-2;
j2=len-1;
Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in
time O(n) and then take their cross in time sqrt(n)^2 ie O(n).
--Shambo
On Mon, Jul 11, 2011 at 12:37 PM, surender sanke surend...@gmail.comwrote:
Hi, here i maintained two pair of indexes with respect to a and b,
@Shambo: That doesn't work.
Consider:
A = 1 10 100 1000
B = 1 2 3 4
The top 4 pairs are: (1000,4), (1000,3), (1000,2) and (1000,1)
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
unfeasible to me.
@Piyush: Are you sure an O(N) algo exists?
Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
algo as it doesn't generate duplicates)
For arrays
A = a1 a2 ... an
B = b1 b2
@Dk..i dint frame the question buddy...:P
I found it over here
http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75
On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote:
@Sunny: Thanks for this counterexample. The O(N)
small mistake change a to b
if( (a[i1-1]+b[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) )
surender
On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote:
@surender: Your algo fails. See the counterexample posted by Sunny.
--
DK
http://twitter.com/divyekapoor
@DK sir
I was just assuming n^2 values as the 2D matrix..not creating
although i am using a O(n^2) space that keep track of which cell is already
in heap and need not be inserted againso initially all the need to
be initialized..that will make it O(n^2)
Now I have a Doubt - Is
Well, technically, if you have to initialize O(N^2) space with *any*
value, then your algo is O(N^2).
In practice, memset is pretty fast, however, that just reduces the constant
factor - it will not (eventually) beat an O(N) algo.
BTW, my solution is O(N).
--
DK
http://twitter.com/divyekapoor
A = 0 1 4 5 9 11 20
B = 0 2 3 6 8 13 15
(20, 15) (20, 15) - (20,15)
(20,13) (11,15) - (20,13)
(20,8) (11,15) - (20,8)
(20,6) (11,15) - assume (20,6)
(20,3) (11,15) - (11,15)
(20,3) (9,15)-
On Mon, Jul 11, 2011 at 1:06 AM, sunny agrawal sunny816.i...@gmail.comwrote:
A = 0, 1, 4, 5, 9, 11, 20
B = 0, 2, 3, 6, 8, 13, 15
(20, 15) (20, 15) - (20,15)
(20,13) (11,15) - (20,13)
(20,8) (11,15) - (20,8)
(20,6) (11,15) - assume (20,6)
(20,3) (11,15) - (11,15)
(20,3) (9,15)- (9,15)
(20,3) (5,15)- (20,3) .problem (11,13) has higher
Thanks Dave.
On Wed, May 18, 2011 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Saurabh: You look at the top elements in the two heaps. If the new
number is between the values of the top of the heaps, you add it to
the shorter of the two heaps, or to either heap if they are of equal
@ Dave. Nice explanation
On Fri, May 20, 2011 at 6:06 AM, saurabh agrawal saurabh...@gmail.comwrote:
Thanks Dave.
On Wed, May 18, 2011 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Saurabh: You look at the top elements in the two heaps. If the new
number is between the values of the top
Preprocess the Dictionary into a hash table where the key is the sorted
string of each word and the value being the A list that contains that
particular word.(O(nlogn * linked list insertion time some k) )
Now for each given word, sort it(O(nlogn)) and find get the list of words
that are
On Sat, May 14, 2011 at 12:55 PM, pacific :-) pacific4...@gmail.com wrote:
Will not a balanced binary tree do the job ? if we will pick the root each
time for the median.
You cannot do it with a vanilla balanced binary tree.
But you can, if you use an augmented tree in the following sense -
If we were given two strings and asked to check if they have the same
characters (anagrams) :
@ gene : you are sorting them both ,and trying to match.
cost : sort the first string + sort the second string + compare i.e k * k +
k * k + k .. k is the length of the string.
I presume that bubble sort
Dave,
u said: a max-heap of the smallest
half of the elements
but if the number are randomply generated, then how will you get to know
whether a number belongs to smallest half OR lager half..
i didnt got it...
On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
@Ashish:
Same method as Gene told.
Only enhancement u can made is start from the word nearer to sorted string
and compare till the nearest word of the reverse of sorted string.
You don't need to check the whole dictionary.
Anuj Agarwal
Engineering is the art of making what you want from things you can
Your sliding window should not be small enough to get the median. For a free
running stream, your window should be of size not less than 100.
On Sun, May 15, 2011 at 7:35 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Anand:
if the stream is let 1,2,3,4,6,7,9
and let we choose k=3
@Dave:
without using comparison operator,
int sign = (a (sizeof(int) * CHAR_BIT - 1));
sign=0 if a is +ive or 0
else sign=-1;
int mult(int x, int y)
{
int p = 0, s = y;
int sign = (y (sizeof(int) * CHAR_BIT - 1));
if(sign) y = add(~y,1);
while(y)
{
if(y 1) p = add(x,
perfect.
Thanks for the effort in explanation.
On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote:
@Pacific: A balanced binary tree is commonly defined as a binary tree
in which the height of the two subtrees of every node never differ by
more than 1. Thus, there could be
1. Create a BST for first K elements of the running stream.
2. Find the median of first K elements.
3. With every new element from the stream, Insert the new element in Binary
search Tree.
4. Delete the first element from BST.
5. if the new element is greater than the current median value, find
Complexity will be O(logK) to insert, delete and finding the predecessor or
successor of current median value in the BST.
On Sun, May 15, 2011 at 4:08 PM, Anand anandut2...@gmail.com wrote:
1. Create a BST for first K elements of the running stream.
2. Find the median of first K elements.
3.
Will not a balanced binary tree do the job ? if we will pick the root each
time for the median.
On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: The idea is to keep two heaps, a max-heap of the smallest
half of the elements and a min-heap of the largest elements.
26 matches
Mail list logo