# Shared Flashcard Set

## Details

Programming
A collection of programming flash cards to help prepare for a job interview
10
Computer Science
10/08/2012

Term
 What are the main differences between Array and LinkedList
Definition
 *It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.*It's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.*Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.*As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.
Term
 Merge Sort - algorithm and efficiency
Definition
 First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.Worst case performance O(n log n)
Term
 Constant time
Definition
 O(1) ex. Determining if an integer (represented in binary) is even or odd
Term
 Logarithmic time
Definition
 O(log n)ex. Binary searchhttp://en.wikipedia.org/wiki/Binary_search
Term
 Linear time
Definition
 O(n)ex. Finding the smallest item in an unsorted array
Term
 Linearithmic time
Definition
 O(n log n)ex. Fastest possible comparison sorthttp://en.wikipedia.org/wiki/Comparison_sort
Term
Definition
 O(n^2)ex. Bubble sort; Insertion sort
Term
 Exponential time
Definition
 2^O(n)ex.Solving the traveling salesman problem using dynamic programming
Term
 Factorial time
Definition
 O(n!)ex. Solving the traveling salesman problem via brute-force search. Or any brute-force algorithm.
Term
 Traveling salesman problem
Definition
 Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city. NP-Hardhttp://en.wikipedia.org/wiki/Traveling_salesman_problem
Supporting users have an ad free experience!