Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = “aab”, Return

1
2
3
4

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
8
9
10
11
12

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint

Could you do it in-place with O(1) extra space?

QEMU Commands

• virtualized serial port is directed to the host tcp port:1223

1

qemu-system-x86_64 -enable-kvm -rtc base=utc,clock=vm,driftfix=none -bios bios.bin -device piix3-usb-uhci -soundhw ac97,hda -m 1024 -serial tcp::1223,server,nowait -netdev tap,script=/data/images/qemu-image/qemu-ifup0.sh,id=net0 -device virtio-net-pci,netdev=net0 -hda /data/images/qemu-image/opensuse-50G.raw -name 23 -cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23

Configure Guest GRUB

• dmesg | grep ttyS make sure virtualized serial port exists

• Make guest display boot message on serial

  1. /etc/default/grub/

1
2
3

GRUB_CMDLINE_LINUX_DEFAULT="console=tty0 console=ttyS0,9600n8 "
GRUB_TERMINAL=serial
GRUB_SERIAL_COMMAND="serial --speed=9600 -unit=0 --word=8 --parity=no --stop=1"    

2. update grub config

Host connection

• Turn of the VM
• Add -S in the qemu command to suspend the VM and you can telnet the port
• Boot the VM and telnet localhost 1223 after VM is suspended.
• Resume the VM in qemu

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

1
2
3
4
5
6
7

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = “lintcode”, dict = [“lint”, “code”].

Return true because “lintcode” can be break as “lint code”.

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Notice

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Example

Given the following triangle:

1
2
3
4
5
6

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Note

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = “aabcc”, s2 = “dbbca”

When s3 = “aadbbcbcac”, return true.

When s3 = “aadbbbaccc”, return false.

Challenge

O(n2) time or better