卖萌的弱渣

I am stupid, I am hungry.

Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Note

This problem have two method which is Greedy and Dynamic Programming.

The time complexity of Greedy method is O(n).

The time complexity of Dynamic Programming method is O(n2).

We manually set the small data set to allow you pass the test in both ways. This is just to let you learn how to use this problem in dynamic programming ways. If you finish it in dynamic programming ways, you can try greedy method to make it accept again.

Next Permutation

Next Permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note

The list may contains duplicate integers.

Single Number

Single Number

Given 2 * n + 1 numbers, every numbers occurs twice except one, find it.

Example

Given [1,2,2,1,3,4,3], return 4

Challenge

One-pass, constant extra space.

Play Virtio on QEMU

  • QEMU: 2.4
  • Host: Linux3.10
  • Guest: Opensuse 12.x with Linux3.10

Original QEMU commands

1
2
3
4
5
6

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 -net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-hda /data/images/qemu-image/opensuse-50G.img -name 23 -cpu core2duo \
-monitor stdio -smp sockets=1,cores=2,threads=1 -vnc :23

virtio-gpu

Just standard VGA right now. Will suport 3D in the future.

1
2
3
4
5
6

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 -net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-hda /data/images/qemu-image/opensuse-50G.img -name 23 -cpu core2duo \
-monitor stdio -smp sockets=1,cores=2,threads=1 -vnc :23 -vga virtio

virtio-net

1
2
3
4
5

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.img \
-name 23 -cpu core2duo -monitor stdio -smp sockets=1,cores=2,threads=1

virtio-net + virtio-serial port

1
2
3
4
5
6
7

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 -device virtio-serial-pci \
-chardev socket,id=foo,host=localhost,port=1224,server,nowait \
-device virtserialport,chardev=foo,name=virtio.port.0

Test virtio serial port

  • On Host
1

nc localhost 1224 > test.txt
  • On Guest
1

echo "hello" > /dev/virtio-ports/virtio.port.0
  • Resut

Cat test.txt on host, you will see “hello”

virtio-blk

1
2
3
4
5
6

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 \
-net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-drive file=/data/images/qemu-image/opensuse.img,if=virtio,boot=on \
-name 23 -cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23

virtio-scsi

1
2
3
4
5
6
7

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 -net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-drive if=none,id=hd,file=/data/images/qemu-image/opensuse-50G.raw \
-device virtio-scsi-pci,id=scsi -device scsi-hd,drive=hd -name 23 \
-cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23

virtio-scsi cdrom

1
2
3
4
5
6
7
8

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 -net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-drive if=none,id=hd,file=/data/images/qemu-image/opensuse-50G.raw \
-device virtio-scsi-pci,id=scsi -device scsi-hd,drive=hd -name 23 \
-cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23\
-drive if=none,file=/path/xxx.iso,id=cd -device scsi-cd,drive=cd

virtio-input-pci

  • Require:
    1. Guest Linux Kernel >= 4.1
    2. QEMU >=2.4
  • keyboard: add -device virtio-keyboard-pci
  • mouse: add -device virtio-mouse-pci
  • tablet: add -device virtio-tablet-pci

Perf Evaluate KVM Performance

Platform

  • Guest: Opensuse with Linux3.10
  • Host: Linux3.10
  • virtio enabled?: Yes

Boot VM

Boot A VM with virtio block

1
2
3
4
5
6

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 \
-net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 \
-net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh \
-drive file=/data/images/qemu-image/opensuse-50G.raw,if=virtio,boot=on \
-name 23 -cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23

Count VMExit for block R/W

Create an empty file (1GB) and count how many VMExits happens.

On host Machine

1

perf kvm stat record -a ssh root@GuestIP "dd if=/dev/zero of=tempfile bs=1MB count=1024"
  • -a: capture all VCPUs

Read report

1

perf kvm stat report --event=vmexit
  • You will get statistics about VMEXIT
  • There are three event you can capture vmexit,mmio,ioport

Detailed report

  • Boot the VM first
  • On Host Machine
1

perf kvm record -a ssh root@GuestIP "dd if=/dev/zero of=tempfile bs=1MB count=1024"
  • After that, You will get a file named perf.data.guest
  • Run report command to look at it
1

perf kvm report

collect performance data from the host

Add --host between kvm and record

1

perf kvm --host record -a ssh root@GuestIP "dd if=/dev/zero of=tempfile bs=1MB count=1024"

You will get a file namedd perf.data.kvm

1

perf kvm report --input perf.data.kvm

Trailing Zeros

Trailing Zeros

Write an algorithm which computes the number of trailing zeros in n factorial.

Example

11! = 39916800, so the out should be 2

hallenge

O(log N) time

Binary Representation

Binary Representation

Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.

Example

For n = “3.72”, return “ERROR”.

For n = “3.5”, return “11.1”.

Linux Disk Benchmark

For a complete benchmark suit in Linux, I would recommend lmbench. You will have the benchmark result for CPU, memory, network, disk etc.

Simple Linux Disk Benchmark

Actually, you can rely on dd for simple disk performance evaluation

Test Write speed

1

dd if=/dev/zero of=tempfile bs=1M count=1024

Test Read speed from buffer

1

dd if=tempfile of=/dev/null bs=1M count=1024

Teest Real Read speed

Just clear the linux cache, then run dd

1
2

sysctl -w vm/drop_caches=3
dd if=tempfile of=/dev/null bs=1M count=1024

Test on external hard drive

External HD includes external HDD, USB flash drive, removable device etc.

Replace tempfile in the above command by your mount point

1

dd if=/dev/zero of=/media/user/MyUSB/tempfile bs=1M count=1024

Linux Cgroup Assign Dedicated CPUs for a VM

Platform

  • Host: Linux-3.10
  • Guest: Linux-3.10
  • Host CPU#: 8
  • Assigned CPUs: CPU #6

Configure Cgroup

1
2
3
4
5
6
7
8
9

# Create another cgroup folder
mkdir /sys/fs/cgroup/cpuset/test

# You will get a bunch of files in test folder  after create the folder
# Assign the CPU 6 or you can replace 6 by "6-7" if you want more cpus assigned to the VM
echo 6 > /sys/fs/cgroup/cpuset/test/cpuset.cpus

# Assign the memory boundary
echo 0 > /sys/fs/cgroup/cpuset/test/cpuset.mems

Modify your VM boot script

Add qemu process# into cgroup.procs

1
2
3
4
5

# Add the following line at the beginning
echo $$ > /sys/fs/cgroup/cpuset/test/cgroup.procs

# Add "exec" before qemu-system-x86_64 binary
exec 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 -net nic,macaddr=00:20:18:11:01:23,model=rtl8139,vlan=0 -net tap,vlan=0,script=/data/images/qemu-image/qemu-ifup0.sh -drive file=/data/images/qemu-image/opensuse-50G.raw,if=virtio,boot=on -name 23 -cpu core2duo -monitor stdio -smp sockets=1,cores=1,threads=1 -vnc :23

After that, run the boot script, you will see the qemu process number in /sys/fs/cgroup/cpuset/test/cgroup.procs and all threads in /sys/fs/cgroup/cpuset/test/tasks

Unique Binary Search Trees

Unique Binary Search Trees

Given n, how many structurally unique BSTs (binary search trees) that store values 1…n?

Example

Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5

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