CareerCup

We can implement it by using a combination of HashMap and BST. HashMap will contain entry for key-value pair and BST only keys. All keys will be maintained in BST (sorted order).

lookup(Key): Make a simple lookup in to HashMap
rangeLookup() - It will be in two parts -
Keys[] rage(Key1, Key 2) from BST
Entry[] lookups(Keys[]) in HashMap

Why not go for B+ tree: en.wikipedia.org/wiki/B%2B_tree
Lookup is O(log n)
Range lookup is O(log n + (Key2 - Key1))

Since lookup is the major concern here, BSTs are the best. However, there is a form of BST called the Splay Tree, which are efficient for lookups. They have an interesting property which makes them bubble up the requested element to the root.. In this particular question, since we have to do a rangeLookup(k1, k2), the first time we search for k1, it will bubble up to be the root.. because of this, elements close to k1 will also bubble up close to the root. Hence, when we search for elements closer to k1, they will more likely be found closer to the root, and improving performance slightly better.

Also, since you are building a data structure, it will have to support the operations of lookup, and rangeLookup not just once, but multiple times.. i.e.

I can come up with a sequence like lookup(1), lookup(5, 10), lookup(7), lookup(2,5).. your data structure has to be efficient over the course of all the above lookups, and not just one. Splay trees provide a slight advantage in such cases over a normal BST.

Use Red-Black/AVL Tree.
For Lookup T(N) = O(Log(N)).
For Range Lookup T(N) = O(Log(N) + Number of keys in between Key1 & Key2).

Can you please explain what is a range lookup?

This could be implemented using a hash table and a RB tree. In C++ STL, it would be a hash_map and map
1. lookup, just lookup the hash_map
2. range lookup: find the key1 in map, iterate the map to key2, and while iterating, output all the values from hash_map. O(n), where n is the # of keys between key 1 and 2.

Why not just use BST + hash?

lookup a key can be done in O(1) with hash table
for lookup(k1, k2) range, what is the expected complexity?

Since I don't remember B+ or Splay trees I would just write the following code to implement the range method. Basically I store the (key, value) in a Node and then store the Nodes in a BST. For lookup, I can either just do a binary search or have a HashMap as well as many have suggested.

static ArrayList<Node> range(Node n, int smaller, int larger) {
  ArrayList<Node> result = new ArrayList<Node>();
  boolean gteSmaller = (n.value >= smaller);
  boolean lteLarger = (n.value <= larger);
  
  if(gteSmaller && lteLarger)
    result.add(n);
  if(n.left != null && gteSmaller)
    result.addAll(range(n.left, smaller, larger));
  if(n.right != null && gteSmaller)
    result.addAll(range(n.right, smaller, larger));
  return result;
}

public ArrayList<BTNode> findNodesWithinRange(BTNode root, int min, int max){
		ArrayList<BTNode> result = new ArrayList<BTNode>();
		if(root!=null){
			if(root.getData()<=max && root.getData()>=min){
				result.add(root);
			}
			if(root.getData()>=min && root.getLeft()!=null)
				result.addAll(findNodesWithinRange(root.getLeft(), min, max));
			if(root.getData()<=max && root.getRight()!=null)
				result.addAll(findNodesWithinRange(root.getRight(), min, max));
		}
		return result;
	}

If the key's are ints or chars then a Hashmap would definitely be the simple enough. Though running time I guess is O(n^2) .. i.e check n items for m items within the range...

Using a BST would probably reduce each lookup time to log(n) from n.
A BST would also allow keys which are not integars .. like real numbers .. things which can't be enumerated...

just my thoughts

I guess a hashmap could also handle non integer values (real numbers like fractions, floats doubles) if we just iterate through all the elements and filter items inside the range.. this would be the dumb n^2 approach I guess. For a hash map with n integars looking for a range of m items would be nm ..

There are also specialized trees which do range lookups:

Range_tree

K-d_tree

given everyone is talking about O(logN), why not just a array sorted by key.......

If range is densely populated, then hash table will be the best option. You can check from a starting element to last element, whether it exists in hash table. But it begins to underperform when you have lot less elements than your range or you need huge has table to avoid collision. Otherwise you can use BST. And red black tree is the best choice here.

bst

void rangeSearch(TreeNode* root, int k1, int k2)
{
if (root != NULL)
{
if (root->val < k1) { rangeSearch(root->right, k1, k2); }
else if (root->val > k2) { rangeSearch(root->left, k1, k2); }
else { rangeSearch(root->left, k1, k2); cout << root->val << endl;
rangeSearch(root->right, k1, k2); }

}
}

Why not use a hashmap, which maps a key to a value pointer and all values are stored as a linked list. Its O(1) for a lookup. For ranged queries, it would be the number of element values between key1 and key2. Please suggest

Skip list would be best solution. No needs to have two separate data structures. O(log N) for lookup and O(logN + K) for range query when K is the size of the range.

I think the best data structure is TreeMap.
Since in TreeMap the keys are sorted so range query can be easily answered i.e. do a inorder traversal.
And lookup can be done in O(1) time too.

wouldn't this be a typical scenario to use interval trees?

tree

DynamoDB :)

cool :)