Tag: primer

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