Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

1
2
3
4
5
6

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
The binary tree A is a height-balanced binary tree, but B is not.

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. A single node tree is a BST

Example

An example:

1
2
3
4
5

  2
 / \
1   4
   / \
  3   5

The above binary tree is serialized as {2,1,4,#,#,3,5} (in level order).

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

Reverse Linked List

Reverse a linked list

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

Decode the virtio pci config space

• Device: virtio-serial
• QEMU: 2.5
• Helper: PCI peek program (written by myself)
  • open /dev/mem
  • use linux mmap to map the device address to virtual address (address must be page aligned.
  • read the content from the virtual address

Virtio pci config space

Convert Sorted List to Balanced BST

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Example

1
2
3

               2
1->2->3  =>   / \
             1   3

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2->null and x = 3,

return 1->2->2->4->3->5->null.

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Challenge

Could you solve it with O(1) space?

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.