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
This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.
You don't need to compute a hash at all. Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort. If you are using Latin (8-bit)
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
It can be done inplace, then Time Complexity will be O( N^2 x W ) where N
is no. of words and W is word size.
Start from the left and sort the current word.
Keep a pointer PTR to the first index of the element left to process.
Initially it will be 0.As we add words this pointer moves
@prem: can you please explain the approach clearly, I did't get the
approach.
regards
Abhishek
On May 23, 7:43 pm, Doom duman...@gmail.com wrote:
I am trying to understand the question.. please let me know the answer for
the following cases..
case1:
test
testlong
testlongtest
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
how about this?
take pointer p1 set to end of array A and pointer p2 set to end of
array B.
while(you get n values)
{
print A(p1),B(p2)
now if( A(p1-1)+B(p2)A(p1)+B(p2-1) ) then print A(p1-1),B(p2)
followed by print A(p1),B(p2-1)
decrement p2 and p1 both
}
m i missing something?
On Jul 9,
Largest value is of course A(n) + B(n).
Second largest value is either A(n) + B(n-1) or A(n-1) + B(n).
Select the largest among both and continue down that array.
Maintain 2 pairs:
Pair 1: Hold first value constant, go down the second array. Pair 2: Hold
2nd value const. and go down the first
@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
Study Trie Then Apply It..It Will Work
PS: We already have dictionary congaing all the possible words if its
not given then we can make the dictionary then we can find out the
all possible anagram of word in constant time O(K) where K is length
of each anagram of word W.
Hope i m correct
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:
@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
length. If the new number is larger than the min of the min-heap, you
add it to the min-heap.
Sort the characters in the string. Go through the dictionary sorting the
characters in each word in turn. Print the words whose sorted versions
match the sorted string.
You can quickly print all equivalence classes of anagrams in the dictionary
by hashing with the sorted strings as keys. It
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.
@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. You
insert incoming elements into the appropriate heap. If the result is
that the number of elements in the two heaps differs by more than 1,
then you move the top
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.
@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 more nodes in one subtree than in
the other. E.g., a balanced binary tree with 11 nodes could have 7
nodes in the left
@Ashish: Here's addition, subtraction, and multiplication with bit
manipulation and comparisons. I doubt if you can do them without
comparisons.
int add(int x, int y)
{
int c;
while(y)
{
c = x y;
x ^= y;
y = c 1;
}
return(x);
}
int sub(int x, int y)
37 matches
Mail list logo
