w*****8
发帖数: 38 | 1 How would you estimate time complexity of an operation of adding a string
into the intern pool of unique strings? N is the size of the pool
我说是O(N), interviewer 说不对。 但不说为什么。 |
d**e
发帖数: 6098 | 2 pool是什么data structure?
【在 w*****8 的大作中提到】
: How would you estimate time complexity of an operation of adding a string
: into the intern pool of unique strings? N is the size of the pool
: 我说是O(N), interviewer 说不对。 但不说为什么。
|
c***2
发帖数: 838 | 3 http://en.wikipedia.org/wiki/String_interning
intern pool is just a hash table or count table
depending on how the table is stored:
0) hash table: O(1)
1) linear array: O(n)
2) heap/BST: O(logn) |
w*****8
发帖数: 38 | 4
Actually before insert the string into the pool, it needs to search if
this string is existing or not; if not, the string will be added into the
pool, so I think it is O(N)
【在 c***2 的大作中提到】
: http://en.wikipedia.org/wiki/String_interning
: intern pool is just a hash table or count table
: depending on how the table is stored:
: 0) hash table: O(1)
: 1) linear array: O(n)
: 2) heap/BST: O(logn)
|
d**e
发帖数: 6098 | 5 depends on what data structure is pool is.
if it is hash table, O(1) search.
if sorted list, BST search takes O(lg n).
if unsorted list, it's O(n).
【在 w*****8 的大作中提到】
:
: Actually before insert the string into the pool, it needs to search if
: this string is existing or not; if not, the string will be added into the
: pool, so I think it is O(N)
|
h**6
发帖数: 4160 | 6 O(len(str)) If it's a trie. |
c***2
发帖数: 838 | 7 That what it takes (to locate the position), insertion itself always takes O
(1)
【在 w*****8 的大作中提到】
:
: Actually before insert the string into the pool, it needs to search if
: this string is existing or not; if not, the string will be added into the
: pool, so I think it is O(N)
|
