Category: Primer (Arrays)
Very basics of working with arrays. This serves as a refresher :)
Primer – Example – Spiral
Given a m x n
matrix, where m
is the number of rows and n
is the number of columns, return all elements of the matrix in spiral order. Solution is here, password is array-example-spiral
Example
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Return: [1, 2, 3, 6, 9, 8, 7, 4, 5]
You can check your code here.
Here is a YouTube video with the solution approach:
Templates
C
/** Return an integer array after spiral traversing a matrix * * @returns integer array pointer * @param A: 2D integer array * @params m, n: Dimensions of the matrix * @param len: length of the output array (technically an outut) */ int* spiralOrder(const int** A, int m, int n, int *len) { // TODO: Your sollution here }
C++
/** Return an integer array after spiral traversing a matrix * * @returns integer vector * @param A: vector of integer vectors */ vector<int> spiralOrder(const vector<vector<int> > &A) { // TODO: Your code here }
Java
public class spiral { /** Return an integer array after spiral traversing a matrix * * @returns ArrayList<Integer> * @param A: 2D integer array (List<ArrayList<Integer>>) */ public static ArrayList<Integer> spiralOrder(final List<ArrayList<Integer>> A) { // TODO: Your code here } };
Python
def spiralOrder(A): """Return an integer array after spiral traversing a matrix @returns integer vector @param A: vector of integer vectors """ pass
Primer – Predict Array 2
Predict the output of the following codes. There are different versions of the code (C/C++/Java/Python). The codes are also saved here. Answer: [5 10 2 1 5 1 2 10]
C
int* performOps(int *A, int len, int *blen) { int i; *blen = len * 2; int *B = (int *)malloc((*blen) * sizeof(int)); for (i = 0; i < len; i++) { B[i] = A[i]; B[i + len] = A[(len - i) % len]; } return B; } int main() { const int len = 4; /********** Generate A **********/ int A[] = {5, 10, 2, 1}; /********** End of Gen **********/ // A = {5, 10, 2, 1}; int blen; int *B = performOps(A, len, &blen); int i; for (i = 0; i < blen; i++) printf("%d ", B[i]); }
C++
vector<int> performOps(vector<int> A) { vector<int> B(2 * A.size(), 0); for (int i = 0; i < A.size(); i++) { B[i] = A[i]; B[i + A.size()] = A[(A.size() - i) % A.size()]; } return B; } int main() { vector<int> A = {5,10,2,1}; vector<int> B = performOps(A); for (int i = 0; i < B.size(); i++) cout<<B[i]<<" "; }
Java
public class predict_array { public static ArrayList<Integer> performOps(ArrayList<Integer> A) { ArrayList<Integer> B = new ArrayList<Integer>(); for (int i = 0; i < 2 * A.size(); i++) B.add(0); for (int i = 0; i < A.size(); i++) { B.set(i, A.get(i)); B.set(i + A.size(), A.get((A.size() - i) % A.size())); } return B; } public static void main(String[] args) { /********** Generate A **********/ ArrayList<Integer> A = new ArrayList<>(Arrays.asList(5,10,2,1)); /********** End of Gen **********/ // A = {5,10,2,1} ArrayList<Integer> B = performOps(A); for (int i = 0; i < B.size(); i++) System.out.print(B.get(i) + " "); } };
Python
def performOps(A): blen = 2 * len(A) B = [0]*blen for i in xrange(len(A)): B[i] = A[i] B[i + len(A)] = A[(len(A) - i) % len(A)] return B if __name__ == '__main__': A = [5, 10, 2, 1] B = performOps(A) for i in xrange(len(B)): print B[i],
Primer – Buggy Array
The following codes are supposed to rotate an array by specified number of positions. However, they don't do that. Please, find the bug. The codes are also saved here. Answer: ret[i] = A[(i + B) % A.size()]
C
int* rotateArray(int* A, int n1, int B, int *len) { int *ret = (int *)malloc(n1 * sizeof(int)); *len = n1; int i; for (i = 0; i < n1; i++) ret[i] = A[i + B]; return ret; }
C++
vector<int> rotateArray(vector<int> &A, int B) { vector<int> ret; for (int i = 0; i < A.size(); i++) { ret.push_back(A[i + B]); } return ret; }
Java
ArrayList<Integer> rotateArray(ArrayList<Integer> A, int B) { ArrayList<Integer> ret = new ArrayList<Integer>(); for (int i = 0; i < A.size(); i++) { ret.add(A.get(i + B)); } return ret; }
Python
def rotateArray(self, a, b): ret = [] for i in xrange(len(a)): ret.append(a[i + b]) return ret
Primer – Predict Array
Predict the output of the following code without running it. The same code is written in C, C++, Python, and Java. The working codes are stored here.
Answer: [4 3 2 1 8 7 6 5 12 11 10 9]
C
int** performOps(int **A, int m, int n, int *len1, int *len2) { int i, j; *len1 = m; *len2 = n; int **B = (int **)malloc((*len1) * sizeof(int *)); for (i = 0; i < *len1; i++) B[i] = (int *)malloc((*len2) * sizeof(int)); for (i = 0; i < m; i++) for (j = 0; j < n; j++) B[i][n - 1 - j] = A[i][j]; return B; } int main() { const int m = 3, n = 4; /********** Generate A **********/ int **A = (int**)malloc(sizeof(int*)*m); for (int i = 0; i < m; ++i) A[i] = (int*)malloc(sizeof(int) *n); for (int idx = 0; idx < m; ++idx) for (int jdx = 0; jdx < n; ++jdx) A[idx][jdx] = idx * n + jdx+1; /********** End of Gen **********/ // A = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; int len1, len2; int **B = performOps(A, m, n, &len1, &len2); int i, j; for (i = 0; i < len1; i++) for (j = 0; j < len2; j++) printf("%d ", B[i][j]); }
C++
vector<vector<int> > performOps(vector<vector<int> > &A) { vector<vector<int> > B; B.resize(A.size()); for (int i = 0; i < A.size(); i++) { B[i].resize(A[i].size()); for (int j = 0; j < A[i].size(); j++) { B[i][A[i].size() - 1 - j] = A[i][j]; } } return B; } int main() { vector<vector<int> > A = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; vector<vector<int> > B = performOps(A); for (int i = 0; i < B.size(); i++) for (int j = 0; j < B[i].size(); j++) cout << B[i][j] << " "; }
Java
ArrayList<ArrayList<Integer>> performOps(ArrayList<ArrayList<Integer>> A) { ArrayList<ArrayList<Integer>> B = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < A.size(); i++) { B.add(new ArrayList<Integer>()); for (int j = 0; j < A.get(i).size(); j++) { B.get(i).add(0); } for (int j = 0; j < A.get(i).size(); j++) { B.get(i).set(A.get(i).size() - 1 - j, A.get(i).get(j)); } } return B; } void main(String[] args) { /********** Generate A **********/ ArrayList<ArrayList<Integer>> A = new ArrayList<>(Arrays.asList( new ArrayList<>(Arrays.asList(1, 2, 3, 4)), new ArrayList<>(Arrays.asList(5, 6, 7, 8)), new ArrayList<>(Arrays.asList(9, 10, 11, 12)))); /********** End of Gen **********/ // A = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; ArrayList<ArrayList<Integer>> B = performOps(A); for (int i = 0; i < B.size(); i++) for (int j = 0; j < B.get(i).size(); j++) System.out.print(B.get(i).get(j) + " "); }
Python
def performOps(A): m = len(A) n = len(A[0]) B = [] for i in xrange(len(A)): B.append([0] * n) for j in xrange(len(A[i])): B[i][n - 1 - j] = A[i][j] return B if __name__ == '__main__': A = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] B = performOps(A) for i in xrange(len(B)): for j in xrange(len(B[i])): print B[i][j],
Edit: Fixed Python bug