CtCI

17 Jan 2014

####Google

Pay attention to Bit Manipulation

####General

Scalability

####Build a strong network

Meetup.com or alumni network
Be open
LinkedIn
Be helpful

####Compile a preparation grid

See Page.40

####Power of 2 table

See Page.47

####5 Steps to a technical question

Resolve ambiguity
Design an algorithm
Write pseudocode first(tell about it)
Write code at moderate pace
Test and fix

####5 Algorithm approaches

Examplify
Pattern matching
Simplify and generalize
Base case and build
Data structure brainstorm

##Interview Questions

###Data Structures

###1. Arrays and Strings

#####Hash Tables Implementing a hash table…

#####ArrayList(Dynamically Resizing Array)

#####StringBuffer Implement your own version of StringBuffer

#####1.1

Forgot the fact that if the string contains unique chars, then the length should be $<=$ length of alphabet
Need to familiaze with bit manipulation

#####1.3

For string equal, use String.equals(anotherStr), == only determines if it is identical
If possible, try to cut out some temporary variables
If one is permutation of another, they must have the same length
Always think of some property to minimize the computation
The pattern to sort an string: toCharArray then sort
Forget about case sensitive and whitespace

#####1.4

Watch out about i++ etc
I really don’t know that I’ll have the true length of the string(But it says it in the question)Read!!
Starting backwards is really a excellent idea.

#####1.5

Forget about the last sentence: the addition case
As long as there is loop, watch out for array out of index!
An alternative to StringBuffer would be declare the char array with enough space upfront
Review the countCompression when possible

#####1.6

It is not neccessary to use recursion
It’s easy to fall into the thinking pattern that every index, position starts with 0
It’s actually matrix transformation

#####1.7

The thinking is easy
But think further to reduce the space
We only care about if one row or column has an zero, we don’t care about the exact location

#####1.8

Abstract the problem!
Again, length of strings

###2. Linked Lists

#####Creating a Linked List

First find the tail, then append the node at the end.

#####Deleting a Node

Watch out if it’s a singly linked list or doubly linked list
In C, C++ you’ll also have to care about memory management

#####The “Runner” Technique

Introduce a second pointer, different pointers have different pace of movement.

#####Recursive Problems

Using recursion is a way out, but that means O(n) space.

#####2.1 Remove duplicates

LinkedListNode
HashTable is an important thing(constant to add, find)
Watchout if head is null
The loop condition: (n != null)
The code is very subtle

#####2.2 kth to last element

Edge case!! Care about every parameter
You never know if n.next is a null pointer or not, So check everytime you access next field

#####2.3 delete node with only access to that node

Think harder
Think outside the box, you may not need to actually eliminate the node in the memory, just make the linked list right after “delete”
If n is the last node, you cannot delete it. Because you cannot make it null. Consider marking the node as dummy.

#####2.4 partition linked list around value x

Watch out when you return something, it should not be some value instead of null
Think about the special case where the linked list is un-balanced around x
Be careful about pointer operations

#####2.5 linked list addition

The recursive way is very sutle, pay attention
Think about all the possible state of the function call
To put code in separate method is a very clean way
Must do it again!

#####2.6 beginning of the loop

Find collision point is easy: runner
But find the beginning is another story
Need to do the math and use the property of loop

#####2.7 palindrome detect

Only need to detect if the front half is the reverse of the second half
Reverse order: the help of stack!

###3. Stacks and Queues

#####3.1 three stacks in one array

Read the question carefully, seriously
Maybe use a linked list to store all index of the stacks, take O(n) to initialize but doesn’t waste space

#####3.2 stack returns minimum in constant time

The min changes when you push and pop
Pay attention to memory optimization

#####3.3 set of stacks

Need to revisit the FOLLOW-UP

#####3.4 Hanoi using stack

Base Case and Build approach:

$n = 1$
Pretty easy
$n = 2$
Tower 2 as a buffer
$n = 3$ etc

Don’t be afraid of recursion!

#####3.5 MyQueue with two stacks

don’t settle for naive solution, try to optimize it!

Week 1

15 Jan 2014

###Challenges of DS

Configuration
Consensus
Consistency
Fault Tolerance

###Characteristics of DS

Computational nodes
Interconnections
Shared state

Client and server are just relatively speaking. Server can also be a client requesting different service.

###Reading: CDK Chapter.1

Reiterates a lot about concepts. Shares a lot in common with the lecturer.

Some truth

06 Jan 2014

###About hacking 1. Premature optimization is the root of all evil- Donald Knuth 2. Beware of bugs in the above code; I have only proved it correct, not tried it.- Donald Knuth 3. If you’ve done something twice, you’re likely to do it again. 4. The difference between theory and practice is shorter in theory than in practice. 5. Elegance is not optional.- Richard O’Keefe 6. Perfect is the enemy of good.- Voltairo 7. Syntactic sugar causes cancer of the semicolon.- Alan Perlis 8. Planning is just a way of avoiding figuring out what to do next.- Rodney Allen Brooks

###About sleeping 1. The quality of sleep at night is only as good as the quality of your day. - One sleep expert

UNIX Programming Environment

03 Jan 2014

##Chapter.1 Beginners

###1.1 Getting started

RETURN key:

CTRL-m

no more input:

CTRL-d

rings the bell:

CTRL-g

backspace:

CTRL-h

tab:

CTRL-i

break:

CTRL-c

which terminal:

who am i

erase one word:

CTRL-w

erase the entire line:

CTRL-u

Stop output:

CTRL-s

resume

CTRL-q

###1.2 Files and common commands

ls

-t  #time order
-l  #long listing
-u  #when is used
-r  #reverse the order

word count

wc

compare

cmp
diff

###1.4 Shell

####Filename shorthand any string of characters:

range of letters or digits

[1-46-9]
[a-z]

any single character

turn off the special meaning

ls '?'
ls \?

####Input-output redirection

output to file

command >filename   #overwritting
command >>filename  #appending

take input from a file

command <filename

####Processes

no hangup:

nohup command &

lower priority

nice command &

start command at some time

at <time>   #2130 930pm
command1
command2
...
CTRL-d

##Chapter.2 The File System

###2.1 Basics of files octal dump

od -c   #character
od -b   #octal numbers
od -x   #hex numbers

###2.2 What’s in a file ###2.3 Directories and filenames

disc space used(listing all the files in current directory, pipe it to grep to find a specific file)

du
du -a   #all files in a directory

###2.4 Permissions 3 kinds of permissions:

read, write, execute

different people:

you, group, others

permission string:

-   indicates it's an ordinary file
d   indicates it's a directory
rws s: when the command is run, it is to be given the permissions corresponding to the file owner

directory permission:

r   "read" e.g. ls
w   "write" create and delete files in this dir
    even if you don't have write permission to that file, you can delete it
x   "search"

chmod

octal:  4 for read, 2 for write and 1 for execute
+:      turns a permission on
-:      turns a permission off

changing permissions on the directory doesn’t change its modification date

###2.5 Inodes
three times:

modified(written) time, used(read or executed) time, (permission) changed time

Chapter.4 Filters

###4.1 The grep family

grep -n #print line numbers
grep -v #invert the sense of the test
grep -y #smart case matching

always a good idea to enclose grep patterns in single quotes

regular expressions:

[^0-9]  #any non-digit
.       #match any one character
*       #closure operator- any number(including 0) of successive matches
.*      #anything up to a new line
.*x     #anything end with x

####grep family: fgrep, egrep

###4.2 Other filters

####sort

sort -f #case insensitive
sort -d #letters, digits and blanks only
sort -n #by numeric value
sort -r #reverse
sort -u #unique

####uniq

uniq -d #only print duplicated
uniq -u #only print unique
uniq -c #number of occurrences

####comm- compare

print 3 columns of output: lines occur only in f1, occur only in f2, occur in both

comm f1 f2

####tr- translate characters

####an idiom

sort | uniq -c | sort -n

###4.3 The stream editor sed

ind- stick a bat at the beginning of each line:

sed 's/^/	/' $*       #Every line
sed '/./s/^/	/' $*   #Non-empty line
sed '/^$/!s/^/	/'  $*  #Non-empty line

###4.4 The awk pattern scanning and processing language

###4.5 Good files and good filters

##Chapter.5 Shell Programming

###5.1 Customizing the cal command

Shell Built-in Variables(P136)

Shell Pattern Matching Rules(P137)

###5.2 Which command is which?

A smart use of

and &&

test -f filename || echo 'file 'filename' does not exist'
# is equivalent to
if test ! -f filename
then
    echo 'file 'filename' does not exist'
fi

###5.3 while and until loops: watching for things

”:” is a shell built-in command that does nothing but evaluate its arguments and return “true”.

####Evaluating variables Examine if the variable is defined or not, if not, print message:

${var?message}

Return value if not defined:

${var-value}

Return value and set var to value if not defined:

${var=value}

Return thing if var is defined or nothing:

${var+thing}

###5.4 Traps: catching interrupts

###5.5 Replacing a file: overwrite

sort file -o file
# sorting the file and output to the same file

###5.6 zap: killing processes by name

###5.7 The pick command: blanks vs. arguments

About $* and $@:(P173)

###5.8 The news command: community service messages

5.9 get and put: tracking file changes

5.10 A look back

Vim write down

28 Dec 2013

##Modes Table of contents of the reference manual

:help usr_toc

Index of manual

:help index

###Insert mode

:help inserting
:help replacing

###Switching modes

:help mode-switching

##Moving around

###Jump within window

‘H’igh- first line of the window

Middle of the window

‘L’ow- last line of the window

###help-motions

:help word-motions
:help cursor-motions

###Sentence wise

next sentence

previous sentence

###Paragraph wise next paragraph

previous paragraph

###Mark

create a mark

m(a-zA-Z)

jump to the mark

'(a-zA-Z)

###Jump around jump back to previous location

CTRL-o

jump forward to next location

CTRL-i

###Parts of the text

visual select a paragraph

vap

a word

aw

a quoted string

a"

a block

ab

flip the case

####Some help :help object-motions :help text-objects :help various-motions :help motion

###Help

List of contents of the entire user manual

:help user-manual

###:helpgrep

:helpgrep {Beginning of a world}

Navigate

:cnext 
:cprev

Whole list

:clist

###keywordprg

Don’t quite know it

:let &keywordprg=':help'

##Editing Basics

###Swap

:help swap-file

###Directory

Change Vim directory

:cd

Print Vim working directory

:pwd

###Swap tricks

Swap 2 characters

xp

Swap 2 words

dwwP

###Time machine

Travel between time

:earlier 4m
:later 45s
:undo 5
:undolist

manual for it :help :undolist :help undo-redo :help usr_32.txt

###Search

search for exact word

/\<word\>

search for number

/\d   #1 digit
/\d\+ #1 or more digits
/\d\* #0 or more digits

manual

:help pattern

##Multiplicity

###Fold

:set foldmethod=indent
:nnoremap <space> za
:help folding

###Buffer

open file

:e filename #open file
:b num      #switch to buffer 1

buffer list

:buffers
:ls

delete buffer

:bd num

help

:help buffer-list

###Window

switch between windows

CTRL-w <motion key>   #w means 'w'indows

cycle between windows

CTRL-w CTRL-w

same file, different parts

:sp     #'sp'lit window
CTRL-w s

vertical split

:vsp
CTRL-w v

‘r’otate the windows

CTRL-w r

move current window to the topmost position

CTRL-w K

resize to num lines long

:resize num

make current window as big as possible

CTRL-w _

make all windows ‘equal’ in height again

CTRL-w =

help manual

:help windows

###Tabs

open a new tab

:tabnew

switch between tabs

gt    #'g'o to the next 't'ab
gT    #opposite direction

close a tab

:tabc
:q

open text in a new tab instead

:help tabpage
=>:tab help tabpage

tab reorder

:tabmove <num>

help manual

:help tabpage

##Scripting

###Macros

q(a-zA-Z)   #record a macro
@(a-zA-Z)   #replay a macro

###Scripts

List of available functions

:help function-list

List of features

:help feature-list

Help manuals

:help eval
:help python-commands
:help perl-using
:help ruby-commands

##Plugins

###Syntax scheme

manuals when writing syntax scheme

:help syntax
:help usr_44.txt
:help group-name
:help pattern-overview
:help mysyntaxfile
:help new-filetype

redraw the screen

CTRL-L

###Compiler plugin

help

:help write-compiler-plugin
:help quickfix

###Disabling plugin

vim -u NONE
vim -u your-minimal-initialization.vim

help

:help -u
:help starting

##Programmes Editor

###Syntax highlighting

pipe Unix shell output to Vim

cmd | vim -R -
# end dash tells Vim to read from standard input

###Bounce jump to corresponding curly bracket, or between the start and end of a block

###Shell

access a full-fledged shell

:sh

run external filters for current text

:%!sort
# sort current content

###Jumping around

open the file(position your cursor on a file name)

gf

go to the local definition of the variable(cursor on variable name)

gd

go to the global declaration

gD

next { in the first column

]]

display all lines that contain the keyword under the cursor

[I

help

:help object-motions
:help 29.3
:help 29.4
:help 29.5

###Browsing code

####File system

:Vex
:Sex

####ctags

open taglist window

:TlistToggle

jump to definition of

:tag foo

jump to definition of symbol under the cursor

CTRL-]

return to previous code you were reading

CTRL-t

jump to definition in a split window

CTRL-w ]

move between matching tags

:tnext
:tprev
:tfirst
:tlast

help

:help taglist-intro

##More

###Modeline

enforce pure tabs within certain file

# vim: noexpandtab
(put within the first 2 lines or last 2 lines)

###Dr.Chip’s plugins

Need to apply it

###Community

mailing list

tips

##What next

Best of Vim Tips

:help user-manual
:help new-7

###Some tricks

Cancel search highlight

:noh

###Vim/Cscope

search: CTRL-<space> s

command line search: :scscope find symbol foo or :scs f s foo

go back: CTRL-t

####types of search

sfind all uses of symbol
gglobal definition
call calls to a function
fopens the filename under the cursor

####auto reindent

gg=G

Luqi Pan

CtCI

Week 1

Some truth

UNIX Programming Environment

Chapter.4 Filters

5.9 get and put: tracking file changes

5.10 A look back

Vim write down