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
If you are writing say for instance your application in c++, then you can expose the methods to customers who buy your product by declaring API of interest as extern.
An example of this can be something like this:
extern "C" void doSomething()
The "C" above tells that doSomething() is a C API that you are providing and that you would be hooking it up with your C++ applicatin code.
Eugene is right!
docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility
JConsole ultimately uses the new ThreadMXBean class's methods. One such method is findAllDeadLockedThreads(); This would give the list of threads that are in deadlock. If no dead lock is in plac,e then a null is returned.
This is one way of knowing the information programmatically.
Best example for theses stuff is the Embedded System. you might have a variable called temperature...but at the moment you try to read it, it might been modified by an external system. Making volatile means that this varaible needs to be re-read everytime.
- Pavan Dittakavi March 13, 2013"But it is also the average of the highest and the lowest element in the array."
This is only true if the array has all the elements present from start_element to end_element..more specifically,
1,2,3,4,5 = (1+5)/2=3; It ONLY works for this case.
So, we really cant go with that approach.
How about the below approach?
cust_id
Hashtable ---------> Linked List;
Hashtable
{
KEY = cust_id
VALUE = pointer to HEAD
}
Linked list might be as below:
HEAD
{
No. of days the user was seen;
Pointer to first node;
}
NODES
{
pageId
hitCount
}
Ashwin, arrays for this question wont be that useful.If you want to query a particular customer id, you would still need to scan the entire array for the id right...more over we definitely need to have dynamic stuff here.
- Pavan Dittakavi August 19, 2012wont work out as Idea suggested;..it would fail at lower levels.
- Pavan Dittakavi August 19, 2012that wont work out at all levels.
- Pavan Dittakavi August 19, 2012That example is missing the order that ideally should have been followed. You see for each node in a trie we have 26 possible pointers[26=size of alphabet]; And the need to have some ordering. Once ordering is followed, you would get sorted data.
- Pavan Dittakavi August 18, 2012if( no diagonal element is 1 ) && ( every row has only one entry '1' ) && ( every column has only one entry '1' )
will implicitly guarantee that the graph in question is connected and is in straight line.
Do we really need transitive closures for this one?. I mean i=the question is asking about nth neighbor..so cant we extract that information from adjacency matrix itself?
A B C D . . Z
A
B
C
D
.
.
.Z
So, for each row, we need to find out the nth entry that has a '1' marked on it and if it is available then return the corresponding column vertex.
Also, I dont see any modification needed for directed graph.
In case im mistaken,...please do correct me!.
Thanks,
Pavan.
Actually adjacency matrix and path matrix are not one and the same. I think we should be using path matrix here and not adjacency matrix.
- Pavan Dittakavi August 18, 2012If this is just a binary tree then we can add at the leaves. so, the complexity would be nothing but the addition of the second tree into the first tree.
If this is a bst, then we can add each of the nodes of the second bst into the first bst using the standard bst rules.
I think sooner or later, the developers or the project lead need to discuss over the continuous changing of requirements and need to convey the same to the client [ if it is a service industry ] and should agree that they are going to release the software with the currently agreed requirements.
If the client or the necessity really demands the addition of the new requirements, then that should be taken up as an enhancement project where the outstanding requirements will be met.
No way.
- Pavan Dittakavi July 23, 2012@Ali Baba, that works. Just an FYI, this can be done in O(n) using DP.
- Pavan Dittakavi July 06, 2012Not sure. This is what I could see towards the end.
"What remains is how to compute TN-1 efficiently. The most popular method is to use exponentiation by squaring method that works in O(log N) time, with this recurrence:
A^{p} = A \text{, if } p = 1,
A^{p} = A .A^{p-1} \text{, if } p \text{ is odd,}
A^{p} = X^{2} \text{, where } X = A^{p/2}\text{, otherwise.}
Multiplying two matrices takes O(K3) time using standard method, so the overall time complexity to solve a linear recurrence is O(K3 log N)."
Sujama, could you pls tell me your experience and location.
BTW, this needs to be done via DP...Dynamic Programming.
Are we sure that this is for log(n) complexty.
- Pavan Dittakavi July 06, 2012One way could be by dividing the file into say K chunks, each of which could fit in memory.
And now, sort each of the K chunks.
Finally apply K - way merge operation on them.
Shondik is correct. We would get different results on different machine and also on different compilers.
+1 for Griffindor!
This is the best algorithm for this problem..+1 from my side.
- Pavan Dittakavi July 02, 2012I think we can use an algorithm similar to the BFS algorithm.
- Pavan Dittakavi July 01, 2012How about counting the number of zeroes?. If the size of the array is 'n' and if you have 'p' zeroes, fill in the first 'p' elements with a '0' and the next n-p elements with a '1'.
- Pavan Dittakavi June 29, 2012In his case, 10 would definitely [ Ok most probably ] be a memory location that is allotted for the OS related basic operation..service routines etc. So, code trying to access them would fail.
- Pavan Dittakavi June 28, 2012Thanks Eugene. So, if we modify the double linked list approach with say ArrayList as suggested by Varun, we should be in a good shape.
- Pavan Dittakavi June 28, 2012@Anon, If you mark the constructor as private, if you extend that class,..then you wont be able to instantiate the derived class as well.
- Pavan Dittakavi June 27, 2012How about a combination of double linked list and a hash map?
While inserting any element, inset it in hast with the key as the element and value as the address in the double linked list. With this, insertion/deletion/searching/randomRetrieval all are possible.
Inserting is nothing but adding the entry to hashmap, creating a node for the double linked list.
Deletion means removing the entry from hashmap and node from the double linked list.
Searching means you input the value to the hashtable, and search the value part of the entry.
RandomSearch, get a random number and go to the start of the double linked list and traverse those many iterations, thus, giving a random value each time.
Not sure if this is an overkill,..but if anyone can point any inconsistencies/comments on this one, it would be great :).
I think we can accomplish this using 32 bytes.Since each byte has 8 bits, we can use
1. The Least significant 6 bits to store the location of a piece 2. The 7th bit to identify if it is present or not on the board.
3. The 8th bit can be used to specify if it is a black piece or a white piece.
Please correct me if Im wrong..or if I missed something here.
How about the below algorithm:
1.Scan from the beginning of the list, ignoring consonants.
2.If you have a vowel at hand, copy it and create a new node at the beginning, update the head pointer and then delete the old node adjusting the pointers.
This would be an O(n) solution as we just need to have a single iteration over the array.
Base 26 seems to be the best way here. But I wanted to know how the number say k=678 would map to the string aab. 678 would be nothing but 102 base 26. So, how can this equates to aab?
- Pavan Dittakavi June 24, 2012I think the fact that static variables are not thread-safe could also be mentioned in this context.
- Pavan Dittakavi June 24, 2012hi...could you please elucidate on thus one :)
- Pavan Dittakavi June 24, 2012This is similar to the fake coin problem. Can be solved in logn time complexity. We just need to weight by breaking the collection into three sub-collections at a time.
- Pavan Dittakavi June 23, 2012@Eugene..could you pls share a better solution in case you happen to know one. I could think of having a tournament tree for this one.
- Pavan Dittakavi June 23, 2012Search for the reset point [i.e., where the transition from high to low occurs ]. This can be done in O(log n);
Now, if the element that you need to search is
a.Greater than the value present at this location=>Doesnt exist;
b. Else, search a[o..this_index]..and a[ this_index+1...n-1];
O( log n ) on the whole for time complexity and O( 1 ) for space complexity.
*Any comments on this are most welcomed.
Thanks Anonymous for helping me out.
- Pavan Dittakavi May 22, 2012Brian, that is not selection sort. It is just the Quick select algorithm.
Ajax, that is good too.
Your second solutions would require an additional array of O(N) for finding the 'kth' smallest element of the array. I assume you are talking about 'Quick Select' algorithm.
But nice one though,
Time Complexity O(N)
Space Complexity O(N).
Hi, could someone please explain me what this question is about?..I mean why were 2 arrays given in the first place?
Thanks,
Pavan.
@Anonymous1, you can build a heap in two different ways.
1. Top-Down which takes O(nlogn)
2. Bottom-up which takes O(n);
So, generally when people say heap, they construct it using the second approach.
Hope that helps you,
Pavan :).
String pattern= new String("AAABBGFF";
int count = 1;
char prev = pattern.charAt(0);
for(int t=1;i<pattern.length;i++)
{
char current = pattern.charAt(i);
if( current!=prev)
{
System.out.print(count+"{"+prev+"}");
count = 1;
}
else
{
count++;
}
prev=current;
}
How about this approach:
1. First find the highest element; If there are elements i,j such that a[i]>a[j], obviously 'i' marked the end of the first list. O(n);
2. Do a binary search on these elements. If it is found, return it. [O(logn)].
3. If it is not there, then search in the decreasing part; For this multiply the numbers 'i+1' till last element with -1 and also the key with -1; O(n)
4. Search using binary search for the key; O(log n);
5. If found, return else terminate with a message saying that the key is not found.
So, overall complexity is O(n) + O(log n ) + O(n) + O(log n ) ;
6. Final complexity, is O( n );
If you feel that I need to include anything here, do let me know.
thanks,
Pavan
Could someone tell me, what it means by 'rotating a LL'.
- Pavan Dittakavi May 13, 2012Algorithm:
1.Get the linked list lenghth. If it is less than 'K' print the error message. O(N)
2.Traverse to the 'K' the element from the beginning. O(N)
3.Traverse to the N-Kth element from the beginning. O(N)
4. Swap them.O(1)
5.End of Algorithm
Complexity:
O(N).
Algorithm:
1.Get the linked list lenghth. If it is less than 'K' print the error message. O(N)
2.Traverse to the 'K' the element from the beginning. O(N)
3.Traverse to the N-Kth element from the beginning. O(N)
4. Swap them.O(1)
5.End of Algorithm
Complexity:
O(N).
Very inventive thinking Rishi. Truly refreshing. :)
- Pavan Dittakavi May 08, 2012Again, how about a hashmap.
Add each of the elements to the hashmap on its first occurrence and remove it from the hashmap on its second occurrence. This way at the end only the object of our interest remains in the hashmap and can be found easily.
Time Complexity:O(n)
Space Complexity:O(n)
We mean to say that it would perform some computation task N number of times. In fact it is not strictly correct either, we mean to say that there is some task comparision/swap/etc that gets performed a number of times and this number is proportional to N.
- Pavan Dittakavi October 25, 2014So, if this N increases, then the number of comparisions involved would also increase linearly.
Take linear search for example. Worst case is not finding an element. So, if there are 100 elements, in the worst case, we would end up making 100 comparisions [ a[0],a[1]...a[99] ].
Similarly, if we are looking at an array of size 1000, we would consequently make 1000 comparisons. Note the linear nature here.
Similarly, there are algorithms[ many sorting algorithms ] that perform O(n2) [n square] in the worst case.