Pavan Dittakavi
BAN USER- 1 Answer Resources on Tries,Suffix Trees, Suffix Arrays
Hi All,
- Pavan Dittakavi June 06, 2012
I want to understand the data-structures like TRIE, SUFFIX TREES and SUFFIX ARRAYS. I googled about tries but could not find good rtesources. Could you pls tell mw any books or links that cover these topics very well with examples.
Any help is most appreciated,
thanks,
Pavan.| Flag | PURGE
How about using a hashmap here.
First list, parse the list and add to hashmap such that key=address of node and value=value of node.
For each of the second list elements' check if its address is already there in the hash table. If it is not available, then continue to the next element of the second linked list.
If at any point an entry is present in the hashtable=> Merge occurred.
Space Complexity O(m)
Time Complexity O(n).
No need bro. If one of any two balls in a set is heavier than the other it would implicitly mean that, the ball in picture is the bulkiest one.
- Pavan Dittakavi May 08, 2012@Gunendu and Monish: I think from a given page of text, this hash table was formed. And the interviewer is asking to reconstruct the original text from the hastable.
@bb
This can't be done. HashTable does not preserve the order. So, there is no way the original text could be restored.
@Above,
I think this question is all about positive integers and did not mention about negative integer scenario.
With that you would be able to identify if there are the letters a,m,a,z,o,n. But, Im afraid you wont be able to validate it.
- Pavan Dittakavi May 03, 2012Code:
int len = strlen( str );
for(int i = 0; i< len; i++)
{
if(a[i] != a[len-1-i])
flag = 1;
}
if( flag )
Not a palindrome
else
A palindrome.
Complexity:
O(n)
This would do.
Code:
for(int i=0;i<n;i++)
sum = sum + a[i][n-1-i];
Complexity:
O(n)
Good logic.
- Pavan Dittakavi May 03, 2012
This is copied from here "linkedin.com/groups/How-partition-array-integers-into-2067732.S.47224169". But, it seems to be working.
- Pavan Dittakavi May 08, 2012Algorithm:
Let {A []} be the array to be partitioned, and the sub-arrays X1[] and X2[]
Now – sort A[],
Take biggest element and insert in X1
Take biggest left - and insert in X2
Keep inserting biggest element to the array with the smaller sum.
In the end get two sub-arrays with sum that is as close as possible.