Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Examples

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

1
2
3
4
5
6
7

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

1
2
3

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

1
2
3
4

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself 
             according to the LCA definition.

What is a Heatmap?

A heat map (or heatmap) is a graphical representation of data where the individual values contained in a matrix are represented as colors.

Heap maps originated in 2D displays of the values in a data matrix.

• Larger values were represented by small dark gray or black squares
• Smaller values were represented by small lighter squares

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Examples

1
2

Input: nums = [1,2,3,1], k = 3
Output: true

1
2

Input: nums = [1,0,1,1], k = 1
Output: true

1
2

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Predicate Calculus or The Logic of Quantified Statements

• Propositional calculus:

  Analysis of ordinary compound statements

• Predicate calculus or the Logic of Quantified Statements:

  Symbolic analysis of predicates and quantified statements (forall and exist)

  • P is a predicate symbol

    P stands for ‘is a student at SBU’

    P(x) stands for ‘x is a student at SBU’

  • x is a predicate variable

• A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables.

• The domain of a predicate variable is the set of all values that may be substituted in place of the variable.

  • Example:

    

Logical Equivalence

The properties of the logical connectives can also be exploited to simplify the notations.

• If two formulas evaluate to the same truth value in all situations, so that their truth tables are the same, they are said to be logically equivalent
• We write $p \equiv q$ to indicate that two formulas p and q are logically equivalent
• If two formulas are logically equivalent, their syntax may be different, but their semantics is the same.
• The logical equivalence of two formulas can be established by inspecting the associated truth tables.
• Substituting logically inequivalent formulas is the source of most real-world reasoning errors

Problem

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example

1
2
3
4
5
6
7

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

1
2
3
4
5
6
7
8
9

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Problem

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example

1
2
3
4
5
6
7

Input: 19
Output: true
Explanation: 
1**2 + 9**2 = 82
8**2 + 2**2 = 68
6**2 + 8**2 = 100
1**2 + 0**2 + 0**2 = 1

Problem

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example

1
2
3
4
5
6
7
8
9

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Problem

Given a binary tree, flatten it to a linked list in-place.

Example

For example, given the following tree:

1
2
3
4
5

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6