Arrays are a data structure that hold an ordered collection of items. Each spot in the array has an index which (generally) starts at 0. In some languages, such as C or Java, you must declare how long the array will be when you create it. If you need to increase the size of the array you'd need to declare a new one and move over the old items. In other languages, such as Python, the data structure will automatically resize itself - these are called resizing ararys. Arrays are handy because they have constant time lookup and insertion on average. This is because the contents of the array are stored contiguously in memory, so during lookup the computer just need to do a bit of math to find the index you're looking for.
For example, if your array started at memory location 100 and you were looking up index 3, your computer would just have to add the index to the memory location to find the correct location in memory.
Memory | Index | Data --- | --- | ___ 100 | 0 | 'H' 101 | 1 | 'e' 102 | 2 | 'l' 103 | 3 | 'l' 104 | 4 | 'o' 105 | 5 | ' '
So looking up array[3] would yeild 'l'.
In fact, strings are typically stored as an array in memory. So, for example, when you create a string:
my_string = "Hello world!"
this string is stored as an array in your computer, with the name of the array pointing to the location in memory, and each character mapped to an index. 'H' maps to 0, 'e' to 1, 'l' to 2 and so on.
Write a function that takes in a string and returns the reversed version of the string. Examples: reverse_string("abcde") -> "edcba" reverse_string("1") -> "1"
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
You are given a square 2D image matrix (List of Lists) where each integer represents a pixel. Write a method transpose_matrix to transform the matrix into its Transpose - in place. The transpose of a matrix is a matrix which is formed by turning all the rows of the source matrix into columns and vice-versa. Example: Input image: 1 0 1 0 Output: 1 1 0 0
Given a list of sorted integer ranges, merge all overlapping ranges. Note: You can assume these ranges are "mini-arrays" with two items in them - index 0 contains the start of the range, and index 1 contains the end of the range. Example: Input: [[1, 10], [5, 8], [8, 15]] Output: [[1, 15]]
Write a function that searches a list of ints for a given integer. If the input integer is found in the list, return True. Otherwise resturn False. Example: Input: 5, [8, 9, 4] Output: False
Followup: Can you decrease the runtime if the array was sorted?
Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited ot just dictionary words. Example: Input: "Tact Coa" Output: True (permutations: "taco cat", "atco cta", etc.)
The idea behind the classic Mergesort algorithm is to divide the array in half, sort each half, and merge the two halves into a single sorted list. Examples: merge_sort([2,7,5,9,8,9]) -> [2,5,7,8,9,9] merge_sort([7,1,8,2]) -> [1,2,7,8]
Given a sorted list of integers, find all the unique triplets which sum up to the given target. Note: Each triplet must be in order having elements (input[i], input[j], input[k]) such that i < j < k. The ordering of unique triplets within the output list does not matter. Example: Input: [1, 2, 3, 4, 5, 6, 7] Target: 15 Output: [(2, 6, 7), (3, 5, 7), (4, 5, 6)]
Gist content by Mary Troiani for presentation she gave at the Algorithms and Technical Interview Study Group - Jan 24, 2018 meetup
This is a part of a series of presentations for Learn Teach Code - Algorithm Study Group