List / Vector / Array
Abstractions
C++
std::vector: similar to C arrays, but dynamically-resizable;std::list/std::forward_list: a linked list of values; andstd::deque: similar to avectorin that it allows random access, but also supports constant time insertion and removal from both ends of the array.
Vectors are the same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted
If the backing array of s is too small to fit all the given values a bigger array will be allocated. The returned slice will point to the newly allocated array.
Rust
std::vec::Vecorstd::collections::VecDequestd::collections::LinkedList
Go
Slice vs array:
- an array has a fixed size. A slice is a dynamically-sized, flexible view into the elements of an array.
[n]Tis an array ofnvalues of typeT;[]Tis a slice with elements of typeT.- A slice does not store any data, it just describes a section of an underlying array. Changing the elements of a slice modifies the corresponding elements of its underlying array. Other slices that share the same underlying array will see those changes.
s[low : high], low is included, high is excluded. Index start from 0. low and high can be ommitted (e.g. a[:10], a[0:], a[:]).
// primes is an array
primes := [6]int{2, 3, 5, 7, 11, 13}
// s is a slice: [3 5 7]
var s []int = primes[1:4]
// slice literals
[]bool{true, true, false}
// get length
len(s)
// get capacity (num of elements in the underlying array,
// counting from the first element in the slice)
cap(s)
// if len < cap, the slice can be extended
s = s[:4]
// Creating a slice with make
b := make([]int, 0, 5) // len(b)=0, cap(b)=5
If the backing array of s is too small to fit all the given values a bigger array will be allocated. (So it is more like a Java's ArrayList.)
Java
ArrayList is like C++'s Vector
Create
C++
#include <vector>
std::vector<int> v {1, 2, 3, 4};
// or
std::vector<int> v = {1, 2, 3, 4};
Go
An array's length is part of its type, so arrays cannot be resized.
// array length must be a constant
var a [10]int
fmt.Printf("%T\n", a) // =>[10]int
primes := [6]int{2, 3, 5, 7, 11, 13}
Slices can be created using variables:
n := 5
a := make([]int, n)
fmt.Printf("%T\n", a) // => []int
2D array/slice:
// array
c := [5][5]uint8{}
// slice
a := make([][]uint8, dy)
for i := range a {
a[i] = make([]uint8, dx)
}
Java
Create empty:
List<Integer> v = new ArrayList<>();
// Array
String[] arr = new String[]{"A", "B", "C"};
// List
List<Integer> v =
new ArrayList<>(Arrays.asList(5, 4, 3, 2, 1));
Init Stream
Stream<Integer> intStream = Stream.of(1,2,3,4);
Copy from existing:
List<Integer> copy = new ArrayList<>(origin)
Rust
let mut l = LinkedList::new();
let v = vec![5, 4, 3, 2, 1];
Hack
Hack Array:
$v = vec[]
Hack Collection:
$v = Vector{}
$v = vec[1, 2, 3];
$v = vec($container);
PHP
array()
Python
>>> [[0] * 4] * 4
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Repeated Values In List/Tuple
List
>>> [0] * 10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Tuple.
>>> (0,) * 10
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Notice the comma in (0,), otherwise it is scalar calculation
>>> (1) * 10
10
Init 2D array
>>> a = [[0] * 3 for _ in range(4)]
>>> a
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
2D 8-Directions
>>> [(x, y) for x in d for y in d if x != 0 or y != 0]
[(1, 1), (1, 0), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, 0), (-1, -1)]
Ruby
>> numbers = ['zero', 'one', 'two']
=> ["zero", "one", "two"]
JavaScript
const clone = originArray.slice(0);
// first 10 items.
originArray.slice(0, 10);
Get By Index
Ruby
>> numbers[1]
=> "one"
Add Elements
C++
Use push_back or emplace_back:
std::vector<int> v = {1, 2};
v.emplace_back(3);
v.push_back(4);
emplace_back will forward the args to the constructor, while push_back takes the value as the input:
std::vector<std::pair<std::string, int>> v = {std::make_pair("a", 1),
std::make_pair("b", 2)};
v.emplace_back("c", 3);
v.push_back(std::make_pair("d", 4));
Go
In Go, we append elements to a slice. If the backing array of s is too small to fit all the given values a bigger array will be allocated. The returned slice will point to the newly allocated array.
s = append(s, 1)
// append multiple
x := []int{1,2,3}
y := []int{4,5,6}
x = append(x, y...)
Java
list.add()
Python
list.append()
JavaScript
// insert, front
list.unshift();
// insert, back
list.push();
Hack
$v[] = 4;
Ruby
>> numbers.push('three', 'four')
=> ["zero", "one", "two", "three", "four"]
Remove Element
Go
Remove last element of the slice:
if len(slice) > 0 {
slice = slice[:len(slice)-1]
}
JavaScript
// delete from back
list.pop();
// delete from front
list.shift();
Delete without changing indices of other elements(leaving a hole)
delete array[i];
Delete and shift other elements forward(modifying array in place:
var index = array.indexOf(5);
if (index > -1) {
array.splice(index, 1);
}
Delete by filtering
keys.filter((key) => key != 'foo');
Ruby
>> numbers.drop(2)
=> ["two", "three", "four"]
Last Item
C++
vector::back: returns a referencevector::end: returns an iterator just past the element
Contains
C++
Use std::find
std::vector<int> v { 10, 20, 30, 40 };
int val = 20;
if (std::find(v.begin(), v.end(), val) != v.end()) {
...
}
Hack
Hack Array:
C\contains_key($v, 1)
or
C\contains($v, 3)
Python
Use in:
>>> a = [1, 2, 3]
>>> 1 in a
True
>>> 4 in a
False
JavaScript
Use includes:
arr.includes(element);
Map
JavaScript
[1, 2, 3].map((x) => x * 2);
Python
map(lambda x: x * 2, [1, 2, 3])
Array Length
JavaScript
[1, 2, 3].length;
Python
len([1,2,3])
Count Elements
Hack
C\count($v)
Type Signature
Hack
vec<TValue>
Type Test
Hack
is_vec($v)
Join As String
Python
join is a method of string instead of a list, since any iterable can be joined.
>>> "|".join(["a", "b", "c"])
'a|b|c'
Scala
Use mkString
scala> List("a","b","c").mkString("|")
res1: String = a|b|c
Java 8+
String joined = String.join(",", Arrays.asList("a", "b", "c"));
or
String joined = Arrays.asList("a", "b", "c").stream().collect(Collectors.joining(","));
Manipulate before joining, e.g. to Uppercase
String joined = Arrays.asList("a", "b", "c")
.stream()
.map(String::toUpperCase)
.collect(Collectors.joining(","));
Another example:
List<BigDecimal> buffer = ...
String s = buffer.stream()
.map(x -> x.toString())
.collect(Collectors.joining(",")));
PHP
implode
Join Two Arrays
Javascript
[1].concat([2])[(1, 2)];
IndexOf
Javascript
var array = [2, 5, 9];
var index = array.indexOf(5);
Subarray / Slice
Scala
arr.drop(2)
Python
arr_slice = arr[start:end]
arr[2:]
JavaScript
const arrSlice = arr.slice(start, end);
Convert To Other Type
Java
Array to Stream
Arrays.stream(array);
String to IntStream
IntStream is = "abc".chars();
Array to Immutable List
private static final Thing[] PRIVATE_VALUES = { ... };
public static final List<Thing> VALUES =
Collections.unmodifiableList(Arrays.asList(PRIVATE_VALUES));
Arrays.asList does not return ArrayList, so does not support addAll() or add(), will throw UnsupportedOperationException
Convert to string array
String[] y = x.toArray(new String[0]);
Primitive Array To List
Use boxed()
int[] nums = new int[]{1,2,3};
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
Array To List
Integer[] nums = new Integer[]{1,2,3};
List<Integer> list = Arrays.stream(nums).collect(Collectors.toList());
Create ArrayList From Array
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
Deconstruct
JavaScript
const [a, b, c] = str.split('-');
Python
>>> a, *b, c = [1, 2, 3, 4, 5, 6]
>>> a
1
>>> b
[2, 3, 4, 5]
>>> c
6
PHP
list($a, $b, $c) = Str\split(",", $str);
Max / Min
Java
Java 8+
int[] a = new int[]{1,2,3};
int min = Arrays.stream(a).min().getAsInt();
JavaScript
Math.max and Math.min do not work on arrays, for example Math.max(1,2,3,4). To get the max/min of an array, use apply
Math.max.apply(Math, [1, 2, 3, 4]);
Math.min.apply(Math, [1, 2, 3, 4]);
Flatten
Python
There's no flatten builtin, but can use list comprehension:
flat_list = [item for sublist in nestedlist for item in sublist]
which means:
for sublist in nestedlist:
for item in sublist:
flat_list.append(item)
zip
Python
Zip
>>> x = (1, 2, 3)
>>> y = ('a', 'b', 'c')
>>> z = list(zip(x, y))
>>> z
[(1, 'a'), (2, 'b'), (3, 'c')]
Unzip. Use * to unpack z
>>> x, y = list(zip(*z))
>>> x
(1, 2, 3)
>>> y
('a', 'b', 'c')
JavaScript
const a = [1, 2, 3]
const b = ['A', 'B', 'C']
a.map((v, i) => [v, b[i]]
// [[1, 'A'], [2, 'B'], [3, 'C']]
Comprehensions
Python
names = [c.name for c in customers if c.admin]
MaxDiff
Given an array, find the max diff between one integer and the integers to its right. e.g. [1, 5, 3, 65, 7, 43], the max is 65 - 7 = 58.
int maxdiff(int *a, int len)
{
int m = a[0];
int mdiff = 0x80000000;
int i;
for (i = 1; i < len; i++) {
if (m - a[i] > mdiff) {
mdiff = m - a[i];
}
if (a[i] > m) {
m = a[i];
}
}
return mdiff;
}
Binary Search
public class BinarySearch {
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,6};
System.out.println(rank(5,a));
}
}
Shuffle
public static void shuffle(int[] a) {
for (int i = 0; i < a.length; i++){
int k = (int) (Math.random() * (a.length - i)) + i;
int tmp = a[k];
a[k] = a[i];
a[i] = tmp;
}
}
Find Peak In 2D Array
Find any peak in a 2D integer array.
1 3 6 4 2 4
5 9 3 5 1 3
2 6 3 7 9 3
3 4 7 2 7 2
Solution 1: Naive Search
Search every position until a peak is found. O(n^2).
Solution 2: Binary Search Rows
Take the middle 3 rows, find the maximum of each row (3 * O(n)), drop the lower side half. Since the maximum of one row is larger than the other, it is guaranteed to be larger than any number in the other row. O(n log n).
Solution 3: Binary Search Alternating Rows and Columns
Similar to solution 2, but alternating between rows and columns, so first half of the rows are dropped, then half of the columns, then half of the rows.
O(N) + O(N/2) + O(N/4) + ... = O(N)