About PCI-e

A tutorial of PCIe.

http://zone.ni.com/devzone/cda/tut/p/id/3767

• Similar to network protocols, the architecture of PCIe consists of layers: physical layer, data-link layer, transaction layer, software layer.
  
• Lane - a basic physical layer channel, a device can request more than one lanes and combine those lanes for higher bandwidth
• Data-link layer: enable reliable data transmission between pairs. Use sequence number, CRC, and retransmissions to ensure reliable communication.
  
• Transaction Layer: creates request packets and serve corresponding response packets from the data-link layer. Provide address spaces.

Northbridge
Southbridge


IO Virtualization
Part 1: http://www.embedded.com/design/networking/217701325

• What is IO virtualization? why is it needed?

System Questions

1) x86 & ARM platform

2) qualcomm snapdragon vs samsung ARM
both ARM-based?
ASIC: application specific IC
SoC: system-on-chip
integrated processors for embedded systems
bus, I/O chipsets, memory controllers (RAM,ROM,...), graphics accelerator

3) NAND vs NOR
NAND can be denser (most usb flash memory)
NOR is more reliable? (used for BIOS ROM)

4) HDMI mirror?

5) embedded controller (EC)

6) bluez

7) at command set (for serial terminal?)

8) SSD, DRAM, SRAM, flash memory
SRAM: static RAM, faster, expensive, less power in idle state
DRAM: dynamic RAM
SDRAM: synchronous DRAM
EEPROM: early flash, byte-wide erasable, flash is usually page-wide erasable

Interview Questions

1. Simulate a seven-sided die using only five-sided

2. Giving Two Strings, Find out whether they are Anagrams or not?

3. find the longest palindrome in a string?

4. find longest common substring in 2 strings using suffix tree

Some terms:

• suffix tree of a string S: a tree whose edges are labeled with strings, such that each suffix of S corresponds to exactly one path from the tree's root to a leaf.
• trie: each edge is labelled with a single character
• radix tree, Patricia tree/trie: edges are labelled with a string instead of single character
  

suffix tree: a special type of radix tree

• How to construct suffix tree?
• How to find longest common substring using suffix tree?

DP algorithm runs in O(mn).

Reference:
Fast String Searching With Suffix Trees

Algorithm Reviews

Foundation of Algorithms Using C++ Pseudocode, 3rd Edition.
By Richard Neapolitan and Kumarss Naimipour

Chapter 5 Backtracking
Backtracking is the technique to prune non-promising nodes in the state space tree.

CLRS
Ch 11 Hash Tables

11.3 Hash Functions

11.4 Open Addressing
Uniform hashing: idealized hashing function selects a permutation with equal prob.
Linear Probing: h(k,i) = ( h'(k) + i ) mod m
Quadratic Probing:
Double Hashing

Wireless Crackers

I came across this website today:
http://forums.remote-exploit.org/

Indeed many people are constantly trying to crack other's wireless password. How scary is that?

Interview Questions

From careercup.com:

• Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?

Answer: Use two pointers, one is the left of the range, one is the right of the range. For each word w_i we also keep a left and right pointer. Both initialize to the head of occurrence list (0).
Initially left is at the leftest word occurrence.
(Loop)
(AdvanceRight) Advance right by advancing the leftest of the right pointers in the occurrence list.
if reached the right end, break the main loop

Keep an array of counters for each word to count how many times w_i occurs in the range.
Advance right until all words are included.
Record range(left,right)
(AdvanceLeft)
Advance the left pointer and decrement the corresponding counter whenever left pointer moves pass word w_i
Repeat until at least one word doesn't occur in the range

Record range( left-1, right) if it's the current optimal

Go back to Loop

• Find the median of 2 sorted arrays

Which phone to buy

My contract with AT&T was over like 2.5 years ago but I haven't renew the contract. It's about time to get a new phone. Here are some choices I found on Amazon:

• Sony W760a
• Nokia 6650
• Samsung A867 ($50)
  

W760a looks good but I already have a Sony Ericsson. Nokia a little boxy but seems like a good phone and the battery is good. A867 seems like a good i-phone alternative, but I don't really need all the smartphone features. So which one to buy? still deciding...