on 31-Oct-2018 (Wed)

Question

In Linux, when email is received for you (from another user on the same machine or from a user from another machine) it is appended to the file: [...] /<username>

Answer

/var/spool/mail
^^ note that spool means a cylindrical device on which film/magnetic tape/other flexible materials can be wound

Question

In algorithms, a queue can be more effieciently implemented as two stacks (when enqueue vs dequeue is evenly distributed) compared to a single linked list, by having an [...] stack and a [...] stack (note: each occlusion is a different word)

Answer

insert stack AND remove/delete stack

Question

In algorithms, what is the characteristic that makes a binary tree, a Binary Search Tree (BST)?

Answer

In a BST, for a given node with a value, all the nodes in the left sub-tree are less than or equal to the value of that node, and all the nodes in the right sub-tree of this node are greater than the value of that node.

Question

In algorithms, for a Binary Search Tree how do you find the node with smallest value?

Answer

You find the left most node by starting from the root node as being current node and keep making the left child the new current node, until there is no more left child, that last node is then the node with lowest value.

Question

In algorithms, for a Binary Search Tree how do you find the node with largest value?

Answer

You find the right most node by starting from the root node as being current node and keep making the right child the new current node, until there is no more right child, that last node is then the node with largest value.

Question

In algorithms, the time complexity to find the minimum or maximum value in a Binary Search Tree is [...]

Answer

O(h), where h is height of tree.

Question

In algorithms, when you are implementing Binary Tree functionality, you create a BinaryTree class, and an underlying [...] class, which is used in (and its inner workings abstracted away in) the BinaryTree class.

Answer

Node

Question

In algorithms/python, when implementing Binary Tree functionality, you do so via the below Tree class, as well as the underlying Node class. Defince the Node class.

class Tree:
    def __init__(self):
        self.root = None
...
...

Answer

class Node:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None

Question

In algorithms/python, when implementing Binary Tree functionality, you do so via the BinaryTree class, as well as the underlying Node class. Defince the BinaryTree class (class signature and constructor only) given the underlying Node class below:

class Node:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None

Answer

class BinaryTree:
    def __init__(self):
        self.root = None

[default - edit me]

Question

In algorithms/python, for Binary Search Trees, given the below class definitions for Node and Tree class, complete the find_min function to return the node which has the minimum value in the BST:

class Node:        
    def __init__(self, data):            
        self.data = data
        self.right_child = None
        self.left_child = None


class Tree:        
    def __init__(self):            
        self.root = None

    # returns pointer to node with min value  
    def find_min(self):
    ####  IMPLEMENT THIS FUNCTION BODY #####
 

Answer

    def find_min(self):
        current = self.root
        while current and current.left_child:
            current = current.left_child
        return current

^^^ the algorithm for above function is basically based on fact that in BST, by design, the smallest value is the left most node (just like the largest is right most node)
^^^ note that the "while current" part of "while current and current.left_child) is there to take care of case that self.root is None