Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Examples

• this binary tree [1,2,2,3,4,4,3] is symmetric:

  1 2 3 4 5

  1 / \ 2 2 / \ / \ 3 4 4 3

• the following [1,2,2,null,3,null,3] is not:

  1 2 3 4 5

  1 / \ 2 2 \ \ 3 3

Trie

Problem

Implement a trie with insert, search, and startsWith methods.

Example

1
2
3
4
5
6
7
8

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

1
2

Input: [3,2,1,5,6,4] and k = 2
Output: 5

1
2

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Problem

Invert a binary tree.

Example

Input:

1
2
3
4
5

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

1
2
3
4
5

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Problem

Given a singly linked list, determine if it is a palindrome.

Examples

1
2

Input: 1->2
Output: false

1
2

Input: 1->2->2->1
Output: true

Data Munging

• Good data scientists spend most of their time cleaning and formatting data.
• The rest spend most of their time complainging there is no data available.
• Data munging or data wrangling is the art of acquiring data and preparing it for analysis.

Relations/Predicates

• Predicates are building-blocks in predicate calculus: p(a_1, a_2, …, a_k)

  • parent(X, Y): X is a parent of Y.

    parent(pam, bob).

    parent(bob, ann).

    parent(tom, bob).

    parent(bob, pat).

    parent(tom, liz).

    parent(pat, jim).

    parent(pam, bob).

    parent(tom, bob).

    parent(tom, liz).

    …

  • male(X): X is a male.

    male(tom).

    male(bob).

    male(jim).

    …

  • female(X): X is a female.

    female(pam).

    female(pat).

    female(ann).

    female(liz).

    We attach meaning to them, but within the logical system they are simply structural building blocks, with no meaning beyond that provided by explicitly-stated interrelationships

Problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note

Do not modify the linked list.

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

Note

A leaf is a node with no children.

Problem

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Examples

1
2

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

1
2

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]