Compare Hash table vs. STL map

Compare Hash table vs. STL map
How is hash table implemented?
For a hashtable, if the number of inputs are small, what can be used instead of a hashtable?
1) map: no need to have a hash function, don't need to handle collision, O (log N) insert and lookup, insert key/data in sorted order. If you need to find a max/min element, use map instead of hash table.
hash table: transforms a key into position within a table. O(1) lookup and insert in most cases, doesn't insert hashed key/data in sorted order
2) You need a good hash function (i.e. % prime #) to ensure the hash values are uniformly distributed. If collision occurs, you use separate chaining method (Good for full table), which is a linked list that chains element in the same slot, or use the probing method, which increases the position by some amount until an empty position is found (good for sparse table)
When the # of elements to table size ratio is greater than a threshold, then the hash table needs to be resized. You need to transfer the entries from old table to new table by recomputing their positions using the new hash function
3) Use a map, which also stores key/data pair, but doesn't need to statically allocate a huge hash table with many empty slots

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0. e.g. array[n]={1, 3, -4, 8, -1}

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0.
e.g. array[n]={1, 3, -4, 8, -1} k=10
because 3+8-1=10, then return 1;
What is the best time complexity??

Create the prefix sum array b[j]=b[j-1]+a[j] where j is from 0 O(n)
For each value in array b just try to find another value val where val-b[i]=k use hash table O(n)
For this condition, subarray (contiguous) like minimum subarray or specific subarray, we can take advantage prefix sum array
If you get the idx for Prefix sum array is from i to j
The subarray is from i+1 to j

design a parking lot, how to implement valet parking use hash table and two linked list, one is parking list, the other is empty list. For each node i

design a parking lot, how to implement valet parking

use hash table to mapping ticket no. and car parking position

Two strings str1 and str2, find longest common substring

Two strings str1 and str2, find longest common substring
A new method:
Build the hash table based on all substring from str1. O(n^2)
For each substring from str2, lookup the hash table and keep the max length of substring. O(n^2)

How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to

How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time?

Use a hash table the key is idx, the value is the current node’s value and next node’s hashed key, so we can random access the individual element also run through the list from item to item.

Given a constant number of priorities implement a priority queue with O(1) enqueue and dequeue implementations.

Given a constant number of priorities implement a priority queue with O(1) enqueue and dequeue implementations.

Use a hashtable, the key is priority level and the associated value is the linked list which maintains the objects with the same priority level. Also maintain a priority queue to record the priority levels, if a new level join, we update this priority queue, and if we want to dequeue, first get the max priority level from the priority queue and look up the key in the hash table. Enqueue is O(1), dequeue is O(1), while the priority levels are constant

Given an n-ary tree represented as a list of items, containing a node and its parent, construct the n-nary tree from it

Given an n-ary tree represented as a list of items, containing a node and its parent, construct the n-nary tree from it

for(node* it=list->head;it!=NULL;it=it->next)
{
 if(it->parent!=NULL)
  it->parent->addToChildrenList(it);
}

or
Hash the nodes based on their parent pointer values. Then iterate through the list and for each node, get the hash value of its own pointer. All the nodes that are in the list present in that hash slot are its children

Given an integer array A,

Given an integer array A,
find the max item A[i].
A[i]=A[x]+A[y].
1) hash table way O(n^2)
each time, select an element A[i], and check the hash table if ht[A[i]-A[y]] exist, we find the A[x] which is A[A[i]-A[y]].
int foo(int A[], int len)
{
int max=min_int;
for(int i=0;i < len;i++)
{
if(A[i] < max) continus;
hashtable ht;
for(int j=0;j {
if(ht[A[i]-A[j]]==1)
{
if(A[i]>max)
max=A[i];
}
ht[A[j]]==1;
}
}
return max;
}

2)sort the array and use two pointers, each of which point to max element and min element, do the linear search sort array use two pointers.

given an array of integer size N.

given an array of integer size N.
a) find all pairs whose sum is some given value X. array is not sorted & values are distinct. in o(log n)
b) array is sorted. & values can repeat. in o(n) & space compl o(1)
a) hash table O(n) time, better idea???
b) two pointers, p1 points to start, p2 points to end, if equal to sum, p1++;p2--; else if bigger than sum, p2--; else p1++

given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

use pre-order to traverse the tree, for each node, record the start time and finish time, building a hash table for these recodes. if the time interval of one node includes the time interval of the second node, they have parent child relationship.