# Facebook Cracking the Coding Interview

September 14, 2016

what to expect:

• welcome: hello, small talk
• you will write on walls (if you can only write in the IDE, then you might not know the code as well)

How to crack the interview: Part #1:

1. Listen (are there clues?)
2. Don’t panic!
3. Ask clarification questions (do you understand the problem, what is the expected output)
4. Draw a picture and a sample input (pictures and diagrams can help visualize the problem)
5. Define the scope (are there memory concerns, can I assume ASCII, is input well formed)
6. Can I calculate a couple of expected results

Selecting a Strategy #2:

1. Can you see an optimal solution (if you see it before, be honest)
2. Can you see any solution? (your aim is to get something working, you can optimize it later)
3. If you really can’t see a solution (what tools can you apply from your bag of tricks, apply all computer science tools) -> hash table, linked list, tree, attack with recursion
• pseudo/flowchart

Writing Code: Part #3:

1. Tell me what you are going to do (tell the language you are going to code it in)
2. Start to write code
tip 1: start near the top of the walls
tip 2: use sensible variable names
tip 3: it’s okay to use helper functions
tip 4: it’s hard to copy-paste on a white board
tip 5: if you start off neat, you will probably stay neat, if it starts messy, it will probably be messy
3. Test it, test it, test it!
• walk through a quick sanity check
• just fix mistakes

Now REALLY test it #3:

1. Run through your hand calculated example/diagram still on the board
2. Think like a tester/hacker, and test again (select nasty test cases, Null/Empty, negative, stuck/looped forever)
3. Tell me when you think you’re done (if I say “Are you sure that’s right?”, it’s probably not)
4. Be prepared to answer questions on the code
5. Know about time complexity, and space complexity (Is it O(n^2), O(nlogn), O(n))

Optimization #4:

1. Can your current solution be optimized(“Are you sure that is optimal”, it probably isn’t)
2. Is there a totally different algorithm that might work better (possible ways to solve the problem in a different way, talk through pros/cons, I may ask you to implement a more optimal strategy)

Questions to consider:

• can we modify the data in place
• does order need to be preserved
• Is it case sensitive? ASCII?
• is input well formed?
• if there are multiple solutions, are we looking for one solution, all solutions? If one, the largest? Smallest?

Are there any clues in the question?

• keywords

“Array of numbers”
“Array of integers”
“Array of unsigned 8-bit integers”
“Array of sorted integers”
“Array of sorted, positive, integers”
“Array of unsorted array of integer, some positive, some negative”
“Array of distinct integers”
“Array of sorted,distinct integers”

## Examples

### Example #1 Magic array

M[i] == i

Given an array of sorted distinct integers, find out if there is a magic number

Naiive solution: brute force,

better == binary search

### Example #3 Sum of Digits

Naiive solution: helper function

### Write a function to return the large of two numbers

bail based on sigfigs what should you return if both are equal

add two long string numbers together

### Example #4 Max Product Triplet

Naiive Solution: brute force O(n^3)

Better:

• sort first
• return the last three elements, or first two and last element

Best idea:

• only pass through array once
• find thrid best

### Example #5 Two Sum Problem

Naiive solution - O(n^2)

Better:

• sort into ascending order
• O(nLogn)

### Example #6 Hash Version

• (6,6) is not a pair (they are the same)
• overflow in massive negative numbers

### Example #7 Count number of negative elements

Naiive soltion: O(n * m)

better:

• know numbers to the left are negative, once you reach one, go downwards

practice, practice, practice cracking the coding interview

what we’re looking for:

• you can understand the problem
• suggest a good algorithm and solve it
• convert into clean, efficient, bug-free, code
• understand the time/space complexity of the solution
• describe/communicate the algorithm
• know limitations of the solution

# Command Line Git and Github

September 17, 2016

## UWPHacks 1 Session on Git, Github, and Command Line:

common commands: (left side is mac/linux, right side is Windows) man/help - HELP, lost pwd/cd - present working directory ls/dir - list files in pwd mkdir - make directory cd - change directory

Git is a technology Github is a service

## Configure Git

• open the terminal
• Type ‘git’ if you see something good
• git config –global user.name “Jane Doe”
• git config –global email.name “j26tsang@uwaterloo.ca”
• go to directory you want the repository
• git init
• make a new repository on Github

## Connecting Wires

• git remote -v
• git remote add origin “url from github”
• Now “git remote -v” should show (for some fetch and push links)
origin	https://github.com/jonathantsang/testisthebest.git (fetch)
origin	https://github.com/jonathantsang/testisthebest.git (push)


• touch “filename”
• git status (Files that have changed)
• git diff (Lines that you added in new files)
• git commit -m”Filename” (commits the code to github)
• git log (log of commits made)
• git push origin master (name and email from beginning steps should be the login info from Github)

$git push origin master Username for ‘https://github.com’: jonathantsang Password for ‘https://jonathantsang@github.com’: Counting objects: 3, done. Writing objects: 100% (3/3), 204 bytes | 0 bytes/s, done. Total 3 (delta 0), reused 0 (delta 0) To https://github.com/jonathantsang/testisthebest.git * [new branch] master -> master # Node.js September 17, 2016 ## UWPHacks 1 Session on Node.js: Javascript Node.js • “easily building fast, scabable modular applications” modern web apps in JS both in client and server side • build “anything you want” • single-threaded event driven Javascript, on the server command+option+i for developer console on mac A click is an event event driven javascript $(function(){

\$('a').on('click', function(){
console.log('hi');
});

});


‘a’ part is for “ tag”, on click, it console.log “hi”

example 3: Overused web server example

var onConnection = function (req, res)


createServer is a function that needs a function to run when someone connects to it.

.pipe is the callback for what the request is