Category: Algorithms

Algorithms and Codes

Math – Reach

You are given a sequence of 2D points in an order that you have to cover them. Every point is represented by 2 digits (x and y coordinate). Compute the distance from the first point to the last point. Movement in all eight directions is allowed (horizontal, vertical, and diagonal). You can test your solution here.

Example

Input X: [0, 1, 1]
Input Y: [0, 1, 2]
Output: 2

The input is [(0,0), (1,1), (1,2)], and the distance from (0,0) to (1,1) is 1, while distance from (1,1) to (1,2) is also 1. The total distance is 2.

Possible Corner Case Inputs

  • Zero length
  • Single point
  • Movement back (negative movement – i.e.: from 1 to 0)
  • Movement only diagonally
  • Any more?

Templates

C

/**
 * Traverse through all points, and return the total distance
 *
 * @return Integer
 *
 * @input X : Integer array corresponding to the X coordinate
 * @input n1 : Integer array's ( X ) length
 * @input Y : Integer array corresponding to the Y coordinate
 * @input n2 : Integer array's ( Y ) length
 */
int coverPoints(int* X, int n1, int* Y, int n2) {
    // TODO: Write your code here
}

C++

/**
 * Traverse through all points, and return the total distance
 *
 * @return int
 *
 * @input X : int vector corresponding to the X coordinate
 * @input Y : int vector corresponding to the Y coordinate
 */
int coverPoints(vector<int> &X, vector<int> &Y) {
    // TODO: Write your code here
}

Java

public class reach {
    /**
     * Traverse through all points, and return the total distance
     *
     * @return int
     *
     * @input X : ArrayList<Integer> corresponding to the X coordinate
     * @input Y : ArrayList<Integer> corresponding to the Y coordinate
     */
    public int coverPoints(ArrayList<Integer> X, ArrayList<Integer> Y) {
        // TODO: Write your code here
    }
}

Python

"""Traverse through all points, and return the total distance

Args:
    X: list corresponding to the X coordinate
    Y: list corresponding to the Y coordinate
Returns:
    integer, representing the total distance
"""
def coverPoints(X, Y):
    # TODO: Write your code here
    return

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

Recursion

  1. What is the worst case time complexity? 
    /* 
 * V is sorted 
 * V.size() = N
 * The function is initially called as searchNumOccurrence(V, k, 0, N-1)
 */
int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
    if (start > end) return 0;
    int mid = (start + end) / 2;
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
}
    1. O(sqrt N)
    2. O(log N)
    3. O(log^2 N )
    4. O(N)
    5. O(N * log N)
    6. O(N * sqrt N)

    Answer: O(N)

  2. What is the worst case time complexity? Assume R=V.size() and C=V[0].size() 
    int findMinPath(vector<vector<int> > V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
}
    1. O(2^(R + C))
    2. O(R*C)
    3. O(R + C)
    4. O(R*R + C*C)
    5. O(R*C*log(R*C))

    Answer: O(2^(R + C))

  3. What is the worst case time complexity, assuming R=V.size(); C=V[0].size() and V has positive elements. 
    int memo[101][101];
int findMinPath(vector<vector<int> > V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  if (memo[r][c] != -1) return memo[r][c];
  memo[r][c] =  V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
  return memo[r][c];
}

    Callsite:

    memset(memo, -1, sizeof(memo));
findMinPath(V, 0, 0);
    1. O(2^(R + C))
    2. O(R*C)
    3. O(R + C)
    4. O(R*R + C*C)
    5. O(R*C*log(R*C))

    Answer: O(R*C)

Function comparison

These are the multiple choice questions. Please, try to understand why the answer is what it is. If you are stuck, ask in the comments.

  1. Which of the following are not O(n2). Answer: n3/sqrt(n)
    1. (1510) * n + 12099
    2. n1.98
    3. n3/sqrt(n)
    4. 220 * n
  2. Sort the functions by increasing order of complexity. Answer: f3, f2, f4, f1
    1. f1(n) = 2n
    2. f2(n) = n3/2
    3. f3(n) = n log n
    4. f4(n) = nlog n
  3. Which of the following loops is the fastest? Assume the same code inside the loops. Also assume n is a positive integer. Answer: for (idx = 1; idx < n; idx *= 2)
    1. for (idx = 0; idx < n; ++idx)
    2. for (idx = 0; idx < n; idx += 2)
    3. for (idx = 1; idx < n; idx *= 2)
    4. for (idx = n; idx > -1; idx /= 2)

Study materials

Try solving the problems without looking in the solutions. If you have questions, ask in the comments.

If you are not sure where to start open some books and read up. Here is a list of books I use:

  • CLRS:Introduction to Algorithms, Third Edition, by {Cormen, Leiserson, Rivest, Stein}
  • GT-C++:Data Structures and Algorithms in C++, Second Edition, by {Goodrich, Tamassia, Mount}
  • GT-Python:Data Structures and Algorithms in Python, First Edition, by {Goodrich, Tamassia, Goldwasser}
  • GT-Java:Data Structures and Algorithms in Java, Sixth Edition, by {Goodrich, Tamassia}

Here is a list of study materials by topic. The format is BOOK{Chapters}

  1. Time complexity: CLRS{3}, GT-C++{4}, GT-Python{3,4.2}, GT-Java{4}
  2. Arrays:GT-C++{3.1,6.1}, GT-Python{5}, GT-Java{3.1}

Edit: Modified the list of books