Java autoboxing and equals(). Consider two 𝚍𝚘𝚞𝚋𝚕𝚎 values 𝚊 and 𝚋 and their corresponding <tt>Double</tt> values 𝚡 and 𝚢.
- Find values such that (𝚊==𝚋) is 𝚝𝚛𝚞𝚎 but 𝚡.𝚎𝚚𝚞𝚊𝚕𝚜(𝚢) is 𝚏𝚊𝚕𝚜𝚎.
- Find values such that (𝚊==𝚋) is 𝚏𝚊𝚕𝚜𝚎 but 𝚡.𝚎𝚚𝚞𝚊𝚕𝚜(𝚢) is 𝚝𝚛𝚞𝚎.
Hint: IEEE floating point arithmetic has some peculiar rules for 𝟶.𝟶, −𝟶.𝟶, and 𝙽𝚊𝙽. Java requires that 𝚎𝚚𝚞𝚊𝚕𝚜() implements an equivalence relation.
0.0 == -0.0 Double.valueOf(0.0).equals(Double.valueOf(-0.0))
Double.NaN == Double.NaN Double.valueOf(Double.NaN).equals(Double.valueOf(Double.NaN))
Check if a binary tree is a BST. Given a binary tree where each 𝙽𝚘𝚍𝚎 contains a key, determine whether it is a binary search tree. Use extra space proportional to the height of the tree.
Hint: design a recursive function 𝚒𝚜𝙱𝚂𝚃(𝙽𝚘𝚍𝚎𝚡,𝙺𝚎𝚢𝚖𝚒𝚗,𝙺𝚎𝚢𝚖𝚊𝚡) that determines whether 𝚡 is the root of a binary search tree with all keys between 𝚖𝚒𝚗 and 𝚖𝚊𝚡.
if (Nodex == null) return true;
if ( Nodex.value < Keymin || Nodex.value > KeyMax) return false;
return isBST(Nodex.left, Keymin, Nodex.value) && isBST(Nodex.right, Nodex.value , Keymax)
Inorder traversal with constant extra space. Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.
Hint: you may modify the BST during the traversal provided you restore it upon completion.
Web tracking. Suppose that you are tracking n web sites and m users and you want to support the following API:
- User visits a website.
- How many times has a given user visited a given site?
What data structure or data structures would you use?
Hint: maintain a symbol table of symbol tables.