Data Structures & Algorithms Flashcards
How are items in a Stack ordered?
LIFO, last in first out
What are common functions on a Stack?
Push, Peek, Pop
How does a Stack work?
Similar to an array in most languages, new items are added to the end of the list via push and removed from the end via pop
How does a Queue work?
New items are added to the end, and items are removed from the front
How are items in a Queue ordered?
FIFO, first in first out
How does insertion sort work?
Take number from unsorted pile and insert into sorted location
What is the runtime complexity of InsertionSort and why?
O(n^2), quadratic, because theres 2 nested loops. One loop for the input array, a second loop to determine where to insert each element into the output array from the input array
Identify the pattern(s) to use:
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
- brute force: compare every number against every other number, quadratic time complexity, o(n^2), because of nested loops
- sliding window: create a dynamic window of days, o(n), linear bc only takes one pass
- two pointers: both pointers start at 0, very similar to sliding window here, linear, o(n) bc it only takes 1 pass
Identify the pattern(s) to use:
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
- brute force: iterate the word and append to new string, then compare strings. runtime complexity: linear, o(n) bc we only iterate once. However, space complexity is also o(n) bc we made a new array
- two pointers: place pointers at both ends of the word, iterate towards middle, comparing letters. Runtime is linear o(n) bc we iterate once, space complexity is constant, o(1) bc no new space is used
Identify the pattern(s) to use:
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
- brute force: compare every number against every other number, quadratic, o(n^2) bc nested loops
- hash: iterate and store in hash, identify diff. Runtime: o(n), linear, bc theres multiple iterations but not nested. spacetime is o(n) bc requires new space for hash.
