Programming Interview Study Guide (iOS, Android, Design Patterns, Algorithms)

This is the study guide I built myself over the course of interviewing for iOS and Android development roles over the years. Being a software developer, I figured “If I have to do this more than once, why not just write the guide once and never bother having to track this junk down ever again?” So I did. If you are actively interviewing, I recommend you create your own guide like this (using your own metaphors and wordings)…it will save you a lot of time over the years. Make sure to have sections on common trivia + sections on your domain + common whiteboard problems to practice.

A huge amount of disparate information about software development interviews is spread across multiple books and websites and that it’s purest form is a simple bulleted list which compresses all the most important information into 1/100th of the space. This is my attempt at arriving at that. When I was in full “interview mode,”  I had 100% of this in my head. Getting to that state takes weeks of preparation.

Studying is the act of compressing disparate information to make it more efficient to consume.

I especially like the code samples for tree traversals which I got from a YouTube video linked at the top. These are the most understandable algorithms and pretty easy to remember. A simple rearrangement of the internal methods switch from per-order to pre-order to post-order.

The most important thing you will ever do is to reword these (and other difficult) concepts in your own language using your own metaphors in your own voice. These are written in mine! No other technique has helped me memorize these concepts quite as effectively.

Videos

  • Binary trees: http://www.youtube.com/watch?v=M6lYob8STMI

Design Patterns

  • Adapter Pattern: Converts the interface from one class to another so they can interact without direct knowledge
  • Strategy Pattern: A class can decide it’s algorithmic behavior at run time based on the situation e.g. vary its algorithm to a situation
  • Builder Pattern: Separate construction of an object from it’s instance allowing the “Building” of more complex objects
  • Abstract factory Pattern:Not often used in reality, provides an interface for creating families of related objects
  • Decorator Pattern: Dynamically apply capabilities to an object at Run Time, sort of like Objective-C methods for providing @dynamic methods
  • Facade Pattern: Provide a unified interface to a set of interfaces (hidden)
  • Flyweight Pattern: Used when working with large numbers of objects to provide a lighter weight version of the object for transactional and processing purposes
  • Proxy Pattern: Provide a placeholder for another object to control access to it
  • Iterator Pattern: Provides a proxy to access an underlying aggregate object
  • Command Pattern: Encapsulates a request allowing undo, queuing
  • Mediator Pattern: Provides a loose coupling between objects by preventing them from referring to one another directly, brokers interactions between objects
  • Visitor Pattern: Sort of like a dependency injector, externalizes data delivery and manipulation into a class which visits other classes and performs operations on them. Its an external class which modifies many other classes.

Tree Traversals & Trivia


public function addNode(Node node){

if(rootNode == null){

rootNode = node;

} else {

Node focusNode = rootNode;

while(true){

if(focusNode.value > node.value){

focusNode = node.rightNode;

if(focusNode == null){

node.rightNode = nodel

}

} else{

focusNode = node.leftNode;

 

if(focusNode == null){

node.leftNode = nodel

}

}

}

}

}

 

  • Breadth First Search
    • Treats each “level” of nodes like a flat array, reads them left to right, then drops to the next level and reads those left to right
  • Depth First Search
    • Walks down the left arm until it hits the bottom, then moves back up until it can go “right” and then walks down the left arm again
    • Reapeat from left to right
  • InOrder Search
    • Visit far left node, visit it
    • Visit it’s parent
    • Effectively similar to working through the tree from the bottom left upwards to the right
    • IN order: Print statement occurs IN between the recursors

function inOrder(Node aNode){

if(aNode != null){

inOrder(aNode.left);

printf(aNode.value);

inOrder(aNode.right);

}

}

 

  • Post Order Search
    • Only show the node once all it’s left and right children have been visited
    • Start from left and work upwards to the right
    • Printing recurs POST the recursors

function postOrder(Node aNode){

if(aNode != null){

postOrder(aNode.left);

postOrder(aNode.right);

printf(aNode.value);

}

}

 

  • Pre-order Search
    • VLR
      • Exhaust left sub-tree (left, left, left etc)
      • Then move up and go right
      • Then exhaust left sub-tree
      • Pre-order tranversal. Print occurs PRE the recursors
      • Show every node as you encounter it

function preOrder(Node aNode){

if(aNode != null){

printf(aNode.value);

preOrder(aNode.left);

preOrder(aNode.right);

}

}

Data Structures

  • deque
    • Double sided queue which can be loaded from both ends
  • Binary Search Tree
    • Reading: https://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack
  • Splay Tree
    • Self balancing
    • O(Logn) lookups
    • For many sequences of non-random operations, splay trees perform better than other search trees
    • Worst case O(n) height
  • Red-Black Tree
  • AVL Tree
    • Self balancing binary search tree
    • O(log n) average and worst case lookup times
    • Similar to a red / black tree due to self balancing and look up times
    • Rebalances via 4 common “rotations”:
  • B-Tree
    • Use with database storage
    • Binary tree with many possible nodes
    • Used to reduce read head movements
  • Directed vs Undirected Graphs
  • Balanced vs Unbalanced trees
    • Balanced: Guaranteed lookup time as nodes dont exceed a certain depth difference (O(n))
    • Unbalanced: Nodes may be drastically different (O(log n))
  • Binary tree vs Binary sort tree
    • binary search tree: left side items always “less” than right side items
  • Heap, Stack, Queue
    • Heap: Tree where all items are smaller than their parent node e.g. “heap” property is fulfilled
  • Trie
    • (similar to Radix tree)
    • Useful for autocompletions
    • Each node consists of itself plus the previous node
    • i -> it -> ite -> item
    • Can have any number of children

Algorithms

  • Stable vs Unstable sorts
    • Stable:Duplicate values will always appear in same order
    • Unstable: Duplicates will not always appear in the same order
  • QuickSort
    • Pick a rotation point in the center, move everything larger to the left, everything smaller to the right
    • Subdivide, perform this operation on both sides again
    • O(logn) look up
    • O(n^2) worst case
    • Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time
  • MergeSort
    • O(nLogn)
    • Recursively break apart an array until you have 2 part sections, then swap then largest to smaller
    • Next, merge the sections back with the previous sections
    • “split merge” the right and left half
    • “top merge” them back together
  • Insertion Sort
    • Reading: http://courses.cs.vt.edu/~csonline/Algorithms/Lessons/InsertionSort/index.html
    • Efficient with small data sets
    • Has a front and back pointer starting at 1. Computer advances front marker and compares result to back marker. If greater, does a swap.
    • Next, continues again, when it finds a number smaller
    • Swap the minimum element with the first element (sorted portion) to the left until it is in the correct position
  • Bubble Sort
    • Terrible performance
    • Move from left to right and swap each pair of items based on their size
    • Continue over and over again until the list is sorted
  • Traveling Salesman problem
  • HeapSort
    • Worst case 0(nlogn) sort times
    • Builds a heap out of data points
    • Squashes the heap to produce the resulting array
  • SelectionSort
    • Overage case O(n^2)
    • Uses a double runner
    • Picks a minimum, scans to find a new minimum
    • Once the list is scanned, move the minimum to the left
  • RadixSort
  • Dykstra’s Algorithm
  • Sieve of Erasthenes
    • http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    • Cross off one
    • Pick 2, corss it off, select all multiples of 2 in the grid and cross them off
    • Pick 3, cross off all multiples of 3
    • Skip to 5, skip count by 5’s and cross out all fives
    • Continue until

Advanced Objective-C (Low Level)

  • Multiple ways to create Objective-C Singletons
    • static dispatch_once_t pred; dispatch_once(&pred, ^{} (recommended by Apple)
    • @synchronized([MyObject class]) MUTEX lock method to ensure single access. Not Apple’s preferred method as not backward compatibile(?)
  • Shallow vs. Deep copy: Shallow is by reference, Deep is “completely new object copy”
  • “Copy” always created an immutable copy, use Mutable copy to get changeable copy
  • CoreFoundation vs Foundation
    • CF is pure C general purpose foundation
    • Foundation is general purpose Objective-C and contains NSString and other basics
  • KVB = KVC + KVO
    • Objects that can be KVO must use NSCoding protocol
    • KVC = using NSCoding protocol to trigger updates
    • KVB ties them together
  • Key charactersistics of Objective-C
    • Dynamic typing—determining the class of an object at runtime
      • Looks up the class in a table using the “id”
    • Dynamic binding—determining the method to invoke at runtime
      • Classes are templates which provide guidance of where to find their associated functions located elsewhere
    • Dynamic loading—adding new modules to a program at runtime
      • ?
  • ClassClusters:
  • Formal vs Informal protocols
    • Informal: Standard protocol in an NSOBject .h file generally “a category declared on NSObject.” Are declared @category
    • Formal protocols are declared @protocol
  • Toll Free Bridging and Cor Foundation
    • Reading: http://www.idryman.org/blog/2012/11/22/arc-best-practices-and-pitfalls/
    • ARC has big problems when mixing CF and Objective-C memory management
    • There is no autorelease in core foundation (it is a mouldering code crypt from 100 years ago)
    • Changing object ownership is dangerous between ARC and CF
    • When recieving a CF object: __bridge_retained, or CFBridgingRetain
    • If the object was created via copy / create, use __bridge_transfer or CFBridgingRelease
    • Objects obtained from CF via “get” do not belong to you and you cant retain or own them
  • (CGColorRef)foo {
    UIColor* color = [UIColor redColor];
    return [color CGColor];
    }

Is dangerous because CF produces a color reference and we store i in a pointer. It can crash anytime, we don’t actually own the CGColor though we are storing it in a pointer.

  • (CGColorRef)getFooColor {
    UIColor* __autoreleasing color = [UIColor redColor];
    return [color CGColor];
    }
  • Do you assign or retain a delegate Id in ARC?
  • ARC:
    • Reading: http://stackoverflow.com/questions/8927727/objective-c-arc-strong-vs-retain-and-weak-vs-assign
    • More Reading: http://clang.llvm.org/docs/AutomaticReferenceCounting.html
    • Strong = “This is mine leave it alone, only I can get rid of it”
    • Weak = “I am borrowing this. If whoever owns it gets rid of it, I will never get rid of it myself” Use for IBOutlet. Is essentially “Assign and unretained property” Gets set to “nil” automatically when the object is dead, unsafe_unretained is similar except doesnt get set to nil
    • “assign” = default. Simple variable assignment with no ownership conditions. Use only for C primitives.
    • Use “Weak” with delegates always
    • _autoreleasing (is a strong pointer. “I am giving you this *ham sandwhich, you can use it but give it back to me before I destroy it, don’t destroy it yourself because I own it strongly)
      • NSError* __autoreleasing error = someError;
      • Automatically becomes:
      • NSError* error = [[someError retain] autorelease];
      • Often used with errors that are passed by reference **
      • Helps ARC code interoperate with non-ARC code
      • You may share an error but you do not allow the outside class to “own” the error and need to denote it is autoreleasable
    • _unsafe_unretained:
      • Remember: _unsafe_unretained is just like “weak”
      • Except: unsafe_unretained is DANGEROUSLY unsafe because unlike weak, the pointer is not set to nil when the value is destroyed on the other end
    • Copy implies strong ownership
    • Assign implies unsafe_unretained
  • Low level Objective C
    • What is a V-table?
      • Objective-C uses this to separate functions from class implementations
      • Classes define which functions they use via pointers to functions in a function table
      • Functions are stored in an object’s “Dispatch Table”
    • What is a “message”
      • Consists of a “selector” and an ID and other information. Effectively is a request to match the selector to it’s implementation in a vtable, call the function and get the result
      • Messages are a byproduct of Object-C’s dynamic nature
    • What is swizzling?
      • Run time remapping of a function via a category
    • What are associated objects?
      • Run-time association of one object with another which can allow you to retrieve the object
    • What is the difference between +load and +initialize? Why use either?
      • +load is a static initializer used by categories on setup. Called automatically on runtime…use for initializing static variables
      • +initialize sends a one time message to classes before they are sent their first message
    • What are __weak, __block __strong and when do you use them?
      • Use __weak when referencing “Self” inside a block or properties and ivars of “self”
      • Use __block to copy a stackvar to the heap “means that the variable is like global, that survives the current frame stack, and accessible by the block that you will declare in the scope.”
    • What does block copy do?
      • Copies the block to the heap so it outlasts the stack lifecycle
    • What is a trampoline?
      • Bounces a message from one object to another, similar to a proxy pattern

Advanced Java (Low Level)

Reading : https://www.udemy.com/blog/java-interview-questions/

  • Interface vs Abstract Class
    • Abstract class can have methods that do stuff, interface cant
  • Final vs Const vs Blank Final
    • Blank final is uninitialized final that can be set once
  • Vector vs ArrayList
    • Vector is synchronized
  • Map vs HashMap
    • Map is an interface, HashMap is an implementation
  • Default modifier: Modifer with no access protection e.g. String myString vs private String msString. Default is it is visible to everyone in the package
  • static means 1 per class
  • final class may not be extended, final method cant be overriden, final variable may be set once and never again
  • JVM
    • Javacompiler outputs bytecode
    • Bytecode is highly optimized instructions
    • JVMs from every platform may run byte code
  • JDK vs JRE
    • JDK is the development kit, JRE is the runtime which runs bytecode
  • Supported data types: Byte (8 bit signed 2’s compliment -128 – 128 range)
    • Short 16 but signed 32,768 – 32,767
    • Int 32 bit signed
    • Long 64 bit signed
    • Float
    • Double
  • Autoboxing
    • Java automatically converts primitve types to their wrapper types. int becomes Integer and soon.
    • Unboxing is the opposite. Complex types to primitive types happens automatically
  • String is immutable, StringBuffer / StringBuilder objects are not.
  • Overloadin vs Overriding. Overloading = adding parameters
  • Throw vs Throws in Java
    • Throws is added to a method signature to indicate a block of code will produce an exception that must be handled
    • Throw actually throws the exection
  • ByteStream vs Character Stream:
    • Byte: reading and writing binary stream, a loop that runs througha string of bytes and does stuff
    • Buffered i/O has overhead reduction e.g. reading large files
    • Character streams do this with characters
    • Stream = loop iterating over items. Buffered stream: Does it in the background async or managed
  • ArrayList vs LinkedList
    • ArrayLists support random access, LinkList only sequential access. The search must touch every link to find what you are looking for. Array list lets you just pick something out.
    • Only objects can be added to ArrayList, LinkedList contains link nodes plus a value
  • Iterator vs Enumerators
    • Both are used for looping through object lists and are created by the array or list
    • Iterators allow you to remove and add items to the array that produces them (important!)
    • Enumerators dont let you do that

Android Interview Questions

  • Stick Intent: The intent sticks around after broadcast so it can be recieved on registrerReciever
  • ativityCreator: First launching step in lifecycle of android application
  • adb: Android Debug Bridge. Utility which allows running shell commands on an android device
  • ANR: Application not responding dialog / state
  • Activity lifetime loops:
    • Entire lifetime (onCreate, onDestroy)
    • Visible lifetime (onStart, onStop) (app level pause and resume)
    • Foreground lifetime, onResume,onPause (activity level pause and resume)
  • AAPT: android asset packaging tool allows users to make use of ZIP files
  • How can ANR be prevented: Use background threads on long running processes that may stall the UI
  • AIDL. What is it and what does it dow and how do you use it
    • reading: http://developer.android.com/guide/components/aidl.html
    • Android Interface Definition Language
    • Create an .aidl file which describes an object which may be shared between processes
    • AIDLs are exposed via a process
    • Service must implement IBinder, service uses AIDL to expose assets to remote services
  • What is IPC
    • Interprocess communication
    • AIDL is the interface for doing this
  • What is IBinder?
    • reading: http://developer.android.com/reference/android/os/IBinder.html
    • part of Android’s system for IPC in lightweight fashion
    • Uses “transact()” to send and recieve “Parcels”
    • Parcels are generic data bundles for IPC data communication
    • The Binder system maintains a list of threads and brokers their communication
  • What is ProGuard?
    • Reading: http://developer.android.com/tools/help/proguard.html
    • Obfuscates and optimizes for security and performance
    • External utility tool
    • on Build, outputs the following files:
      • Mapping.txt (lists mappings between obfuscations and classes and field names)
      • Dump.txt (describes internal structures of classes in APK)
      • seeds.txt: Lists classes and members not obfuscated
      • usage.txt: lists code that was stripped from apk
    • Obfuscated code generates obfuscated state traces
  • What is an APK
    • Reading: http://en.wikipedia.org/wiki/APK_(file_format)
    • Mostly an archive containing the same contents as an android project
    • Contents are located in a META-INF
    • Includes a cert
    • lib: compiled code
    • classes .dex – classes compiled into a dex format read by dalvik
    • resources.arsc: compressed resources
  • What is Dalvik?
    • Custom VM for Android
    • Executes .dex files e.g. Dalvik Executeables and odex “optimized dalvik executeables”
    • Unlive Java VM’s which are “Stack Machines” dalvik uses a “register based architexture”
    • What is a “register machine”
  • What is ART virtual machine?
    • Android 4.4 introduced an “Ahead of time” process
    • Compiled to byte code pre compiled at the time of installation

CoreData:

Objective-C / Concurrency

  • Reading: https://developer.apple.com/library/ios/documentation/general/conceptual/concurrencyprogrammingguide/Introduction/Introduction.html
  • @synchronized used to enforce sequential access via a lock
    • Takes in a “lock” which is used to broker access e.g. a MUTEX
    • @synchornized(your_mutex_lock)
    • “Critical Section” Area of code which may be accessed or modified by many threads at once
  • Old and busted: using many threads to utilize many cored OS.
    • Problem: Does not scale well when many new cores are added as with mobile devices
    • Is not future proof solution to future concurrency needs
  • Dispatch queues instead:
    • Simple, holistic, automatic thread pool management
    • Do not trap the kernel under load
    • Async dispatching tasks cant deadlock the queue
    • Scale gracefully
    • More memory efficient
  • NSOperation
  • NSThread & Thread Pool
  • Operation Queues vs. Dispatch Queues
    • NSOperation requires more code and is more bulky, is a higher abstraction on top of GCD
    • Operations suited to non time critical purposes like downloading
    • NSOperation sits on top of GCD
    • Operation queues use NSOperation, NSBlockOperation, NSInvocationOperation
    • Operations:
      • NSInvocation: Fires a given selector on a supplied object. Command pattern implementation.
      • NSBlockOperation: Fires provided block
      • Can be called manually or added to a queue
    • Operation Lifecycles:
      • Operations have multiple KVO events they dispatch during their lifecycle
      • cancelled, concurrent, executing, finished, ready, priority
  • NSThread:
    • Reading: https://developer.apple.com/library/ios/documentation/cocoa/conceptual/Multithreading/CreatingThreads/CreatingThreads.html
    • High cost to the kernel to spawn threads
    • Expensive to kernel memory space. Thread creation costs:
      • 1kb kernal data structures
      • 512kb stack space, minimum 16kb for secondary thread
      • create time: 90 microseconds
    • Spawn by calling detach thread or create a new thread instance
    • POSIX thread API is supported with pthread_create
    • “perform selector in background” may be used to dynamically spawn a thread and perform a specific operation in that background thread and close it when done
    • Detached threads are preferable due to speed, you must directly communicate with detached threads to get data out of them
    • A process can block a thread from joining and delay getting results back out
    • Only POSIX threads are joinable (by default) and you can also set them to being detached
    • Each thread needs it’s own autorelease pool to catch objects nad manage their lifecycle
    • Run Loops:
      • Input sources (thread gets async messages from other processes_
      • Timers are a possible source
      • Threads receive messages via a port
  • Run loops can have many modes
  • Run loop observers can detect certain events triggered by the run loop itself and react accordingly
  • CFRunLoopObserver
  • Input sources are sort of like messengers in Android in that they can pick the thread and send messages in and out
  • NSMachPort: Ability to use threads to talk directly to the thread between process, interface
    • Add ports to the thread to use it to communicate
    • Local thread can send a port back to the originating thread
    • NSPortMessage is used to send messages
  • Thread Synchronization
    • ATomic operations: Dont block threads
      • Work on simple data types
    • Memory Barriers and Volatile variables
      • “A memory barrier is a type of nonblocking synchronization tool used to ensure that memory operations occur in the correct order. A memory barrier acts like a fence, forcing the processor to complete any load and store operations positioned in front of the barrier before it is allowed to perform load and store operations positioned after the barrier. Memory barriers are typically used to ensure that memory operations by one thread (but visible to another) always occur in an expected order”