Table of Contents
- Facebook Cracking the Coding Interview
- Command Line Git and Github
- Node.js
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:
- Listen (are there clues?)
- Don’t panic!
- Ask clarification questions (do you understand the problem, what is the expected output)
- Draw a picture and a sample input (pictures and diagrams can help visualize the problem)
- Define the scope (are there memory concerns, can I assume ASCII, is input well formed)
- Can I calculate a couple of expected results
Selecting a Strategy #2:
- Can you see an optimal solution (if you see it before, be honest)
- Can you see any solution? (your aim is to get something working, you can optimize it later)
- 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
Writing Code: Part #3:
- Tell me what you are going to do (tell the language you are going to code it in)
- 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
- Test it, test it, test it!
- walk through a quick sanity check
- just fix mistakes
Now REALLY test it #3:
- Run through your hand calculated example/diagram still on the board
- Think like a tester/hacker, and test again (select nasty test cases, Null/Empty, negative, stuck/looped forever)
- Tell me when you think you’re done (if I say “Are you sure that’s right?”, it’s probably not)
- Be prepared to answer questions on the code
- Know about time complexity, and space complexity (Is it O(n^2), O(nlogn), O(n))
Optimization #4:
- Can your current solution be optimized(“Are you sure that is optimal”, it probably isn’t)
- 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?
“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
Possible Follow up Questions
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
- optimize your current solution
- 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
- 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)
Let’s Add!
- touch “filename”
- git add “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