alex
BAN USER- 0of 0 votes
AnswersRemove duplicates from a string inplace. The algorithm should be as efficient as possible.
- alex in India
I gave two approaches. First, the simple comparison O(n2) and second, sorting O(nlgon). But the interviewer did not seem satisfied.
Can someone please suggest a better algorithm?| Report Duplicate | Flag | PURGE
Microsoft Intern Algorithm
Assign every alphabet a prime number. For eg- a=2, b=3, c=5 and so on. For both the strings calculate the product of the prime representation of every number. If the product is equal, they are anagrams.
string1 = abc=2*3*5=30
string2 = bca=3*5*2=30
so they are anagrams.
Prime nos can be calculated using seive method.
Time- O(n)
Space- O(1)
Hope that'll do.
Seems like a linear programming problem to me. Let x1,x2...xn be the no of coins of each type required to make the given sum. So, we have to minimize x1+x2+...+xn with the constraints,
k1x1+k2x2+.....knxn=sum, k1..kn being the exchange values
x1, x2..xn are positive integers
x1<=m1, m1 is the no of available coins of 1st type..and so on
x2<=m2
....
xn<=mn
@cobra: haven't you skipped the case, when we get a very long ladder at some next point, which will need even a fewer number of throws? For eg: if there is a ladder at 5 which takes you to 25 and a ladder at 12 which takes you to 72? Wouldn't your algorithm take the ladder at 5 and hence result in larger no of steps?
- alex December 26, 2012Let str[] denote the given string. I am creating an array arr[] which stores the words as I read them.
i=0,k=0,count=0
while(str[i++]!='\0')
do
if(str[i]!=' ')
arr[k++]=str[i]
count++
else
if(count==1)
arr is one of the ans and continue finding for others
k=0
empty arr again
@SanBits: The memory allocation of static variables and static classes is different. The Y object (of class W) is like a static variable to Class X and is like a static variable to class X. So, this Y (the object) is allocated in the heap. The allocation of an inner class is not in the heap (I don't remember the name of the area where it is stored). So, when Y is called, the compiler first searches for a Y in the heap (according to the normal flow). If it does not find a Y in the heap (case when the object name of W is changed), it accesses the Z of the static inner class. You can try all the above if you have a JVM.
- alex December 14, 2012@bvg rao: If I perform the push operation on stack1 for more than n/3 times, it'll overflow, won't it? None of the stacks should overflow till the no. of elements is less than or equal to n. For example when you implement two stacks, one which is filled from left to right and the other from right to left, none of them overflows until the no. of elements becomes greater than n.
Correct me if I am wrong.
@Dr. Andrew: What you are saying is not applicable for the array: 1,1,1,3,4,5
The value of n is 6. Hence the n/3(or 2nd) largest element is 3 and 2n/3(or 4th) largest element is4. And neither of them is repeated more than n/3 times. Instead, 1 is repeated more than n/3 times!
Correct me if I am wrong.
@Wayne: Yeah, got the problem with my idea. Thanks for pointing it out. :)
- alex January 29, 2013