Skip to content

Instantly share code, notes, and snippets.

@codenameyau

codenameyau/Interview Topics.md

Forked from lawloretienne/Interview Topics.md
Created January 30, 2017 20:37
Show Gist options
  • Save codenameyau/581a189917111a9c3a751fe177237f74 to your computer and use it in GitHub Desktop.
Save codenameyau/581a189917111a9c3a751fe177237f74 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Interview Topics.md

Table Of Contents

Data Structures

Linked Lists

  • A linear collection of data elements, called nodes, each pointing to the next node using a pointer.
  • List elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk.
  • Linked lists are a dynamic data structure, which can grow and be pruned, allocating and deallocating memory while the program is running.
  • Stacks and queues can be implemented using a linked list.
  • Items can be added or removed from the middle of list.
  • Nodes are not stored contiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
  • Singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.
  • The entry point into a linked list is called the head of the list.
  • A doubly linked list stores a pointer or reference to the previous node.
  • Linked Lists allow only sequential access to elements.
  • Questions involving Linked Lists can often be solved by using two pointers. FastRunner moves two steps and SlowRunner moves one step at a time. Sometimes these two pointers both move just one step at a time but have different start points.

Trees

  • A tree is a data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
  • A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
  • Root - The top node in a tree.
  • Child - A node directly connected to another node when moving away from the Root.
  • Parent - The converse notion of a child.
  • Siblings - A group of nodes with the same parent.
  • Descendant - A node reachable by repeated proceeding from parent to child.
  • Ancestor - A node reachable by repeated proceeding from child to parent.
  • Leaf/External node - A node with no children.
  • Branch/Internal node - A node with at least one child.
  • Degree - The number of sub trees of a node.
  • Edge - The connection between one node and another.
  • Path - A sequence of nodes and edges connecting a node with a descendant.
  • Level - The level of a node is defined by 1 + (the number of connections between the node and the root).
  • Height of node - The height of a node is the number of edges on the longest path between that node and a leaf.
  • Height of tree - The height of a tree is the height of its root node.
  • Depth - The depth of a node is the number of edges from the node to the tree's root node.
  • Forest - A forest is a set of n ≥ 0 disjoint trees.
  • A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

Binary Trees

  • A tree data structure in which each node has at most two children, the left child and the right child.
  • A binary tree is a special case of an ordered K-ary tree, where k is 2.
  • Binary trees are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting.
  • Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent.
  • A full binary tree is a binary tree in which each node has exactly zero or two children.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Binary Search Tree

  • Binary Search Trees (BST) are sometimes called ordered or sorted binary trees.
  • They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.
  • Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees.

Red-Black Tree

  • A kind of self-balancing binary search tree.
  • Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node.
  • These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
  • Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case.
  • When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
  • Tracking the color of each node requires only 1 bit of information per node because there are only two colors.
  • The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) binary search tree.

AVL Tree

  • A self-balancing binary search tree.
  • In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
  • Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation.
  • Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Tries

  • A prefix tree that is a kind of search tree — an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.
  • Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.
  • All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
  • A trie is a variant of an n-ary tree in which characters are stored at each node.
  • Each path down the tree may represent a word.

Graphs

  • A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph.
  • These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph.
  • The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

Stacks

  • An abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.
  • The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).
  • Additionally, a peek operation may give access to the top without modifying the stack.
  • You can implement a stack as a singly linked list and a pointer to the top element.
  • Questions involving Stacks can often be solved by using an additional Stack as a buffer. Elements can be moved in an out of the buffer throughout the solution.
private class Stack {
    Node top;

    Object pop() {
        if(top != null){
            Object item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }

    void push(Object item) {
        Node t = new Node(item);
        t.next = top;
        top = t;
    }

    Object peek() {
        if(top != null)
            return top.data;
        else
            return null;
    }
}

private class Node {
    Object data;
    Node next;

    Node(Object item){
        data = item;
    }
}

Queues

  • A particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue.
  • This makes the queue a First-In-First-Out (FIFO) data structure.
  • The first element which is inserted into the queue will be the first one to be removed.
class Queue {
	Node first, last;
	
	void enqueue(Object item) {
		if(first == null){
			last = new Node(item);
			first = last;
		} else {
			last.next = new Node(item);
			last = last.next;
		}
	}
	
	Object dequeue() {
		if(first != null){
			Object item = first.data;
			first = first.next;
			return item;
		}
		return null;
	}
}

class Node {
    Object data;
    Node next;

    Node(Object item){
        data = item;
    }
}

Vectors

  • A one-dimensional array.
  • Vector containers are implemented as dynamic arrays.
  • Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.
  • While an array uses a static amount of memory, the memory used by the vector can be increased or decreased as elements are added or removed from the vector.
  • A Vector defaults to doubling the size of its array when resizing occurs.
  • Access to a Vector is synchronized.
  • A vector is very similar to an ArrayList, except that it is synchronized. Its' syntax is almost identical as well.

ArrayLists

  • A random access, variable-size list data structure that allows elements to be added or removed.
  • ArrayList supports dynamic arrays that can grow as needed.
  • An ArrayList increases its array size by 50 percent when resizing occurs.
  • Access to an ArrayList is not synchronized.
  • An ArrayList is a dynamically resizing array, which grows as you insert elements.

Hash Tables

  • A data structure used to implement an associative array, a structure that can map keys to values.
  • A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
  • Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket.
  • Instead, most hash table designs assume that hash collisions (different keys that are assigned by the hash function to the same bucket) will occur and must be accommodated in some way.
  • Hash tables are often implemented as an array of linked lists.
  • When you create your own key object for use in a Hashtable, you must override the Object.equals() and Object.hashCode() methods since Hashtable uses a combination of the key's hashCode() and equals() methods to store and retrieve its entries quickly.
  • It's also a general rule that when you override equals(), you always override hashCode().
  • A Hashtable internally contains buckets in which it stores the key/value pairs.
  • The Hashtable uses the key's hashcode to determine to which bucket the key/value pair should map.
  • A hash table / hash map would be a good choice for a data structure that could track duplicates in another data structure.

Adjacency Matrix

  • A square matrix used to represent a finite graph.
  • The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
  • If the graph is undirected, the adjacency matrix is symmetric.
  • The adjacency matrix allows testing whether two vertices are adjacent to each other in constant time; the adjacency list is slower to support this operation.

Adjacency List

  • A collection of unordered lists used to represent a finite graph.
  • Each list describes the set of neighbors of a vertex in the graph.
  • For a sparse graph (one in which most pairs of vertices are not connected by edges) an adjacency list is significantly more space-efficient than an adjacency matrix (stored as an array).
  • The space usage of the adjacency list is proportional to the number of edges and vertices in the graph, while for an adjacency matrix stored in this way the space is proportional to the square of the number of vertices.
  • In an adjacency list, the neighbors of each vertex may be listed efficiently, in time proportional to the degree of the vertex. In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree.
  • Two vertices are called adjacent if they are connected by an edge.
  • Two edges are called incident, if they share a vertex.

Incidence List

  • A variant of the adjacency list that allows for the description of the edges at the cost of additional edges.
  • Instead of storing adjacent vertices, the list stores all of the edges that contain the referencing vertex.
  • Edges are required to have two vertices.

Algorithms

Breadth First Search

  • An algorithm for traversing or searching tree or graph data structures.
  • It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.
  • Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue.
  • This traversal visits nodes by levels from top to bottom and from left to right.
  • Breadth first search can also be useful to find the shortest path.
void bfs(Node root) {
    Queue queue = new Queue();
    queue.enqueue(root);

    while(!queue.isEmpty()){
        Node node = (Node)queue.dequeue();

        if(node.getLeft() != null){
            queue.enqueue(node.getLeft());
        }

        if(node.getRight() != null){
            queue.enqueue(node.getRight());
        }
    }
}

private class Node {
    private Object data;
    private Node left;
    private Node right;

    Node(Object item, Node left, Node right){
        this.data = item;
        this.left = left;
        this.right = right;
    }

    public Object getData() {
        return data;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }
}

private class Queue {
    Node first, last;

    void enqueue(Object item) {
        if(first == null){
            last = new Node(item);
            first = last;
        } else {
            last.next = new Node(item);
            last = last.next;
        }
    }

    Object dequeue() {
        if(first != null){
            Object item = first.data;
            first = first.next;
            return item;
        }
        return null;
    }

    boolean isEmpty() {
        if(first != null)
            return false;
        else
            return true;
    }
}

Depth First Search

  • An algorithm for traversing or searching tree or graph data structures.
  • One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
  • There are three different types of traversals :
    • PreOrder traversal - visit the parent first and then left and right children
    • InOrder traversal - visit the left child, then the parent and the right child
    • PostOrder traversal - visit left child, then the right child and then the parent
  • Depth First Search may traverse one adjacent node very deeply before ever going onto the immediate neighbors.
  • Depth First Search can be implemented with recursion.
void preOrderDFS(Node root) {
    if(root == null)
        return;

    Stack stack = new Stack();
    stack.push(root);

    while(!stack.isEmpty()){
        Node node = (Node)stack.pop();

        Node left = node.getLeft();
        Node right = node.getRight();

        if(right != null){
            stack.push(right);
        }

        if(left != null){
            stack.push(left);
        }
    }
}

void inOrderDFS(Node root) {
    if(root == null)
        return;

    Stack stack = new Stack();
    Node p = root;

    while(!stack.isEmpty() || p != null){
        if(p != null){ // if it is not null, push to stack and go down the tree to left
            stack.push(p);
            p = p.left;
        } else { // if no left child pop stack, process the node then let p point to the right
            Node temp = (Node)stack.pop();
            p = temp.right;
        }
    }
}

void postOrderDFS(Node root) {
    if(root == null)
        return;

    Stack stack = new Stack();
    stack.push(root);

    while(!stack.isEmpty()){
        Node node = (Node)stack.peek();

        Node left = node.getLeft();
        Node right = node.getRight();

        if(left == null && right == null){ // leaf node
            stack.pop();
        } else {
            if(right != null){
                stack.push(right);
                node.right = null;
            }

            if(left != null){
                stack.push(left);
                node.left = null;
            }
        }
    }
}

private class Stack {
    Node top;

    Object pop() {
        if(top != null){
            Object item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }

    void push(Object item) {
        Node t = new Node(item);
        t.next = top;
        top = t;
    }

    Object peek() {
        if(top != null)
            return top.data;
        else
            return null;
    }

    boolean isEmpty() {
        if(peek()!=null){
            return false;
        } else {
            return true;
        }
    }
}

private class Node {
    private Object data;
    private Node left;
    private Node right;

    Node(Object item, Node left, Node right){
        this.data = item;
        this.left = left;
        this.right = right;
    }

    public Object getData() {
        return data;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }
}

Binary Search

  • A search algorithm that finds the position of a target value within a sorted array
  • It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
  • Binary search runs in at worst logarithmic time.
  • Binary search works on sorted arrays.
int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if(a[mid] < target) {
            low = mid + 1;
        } else if(a[mid] > target){
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1; // Error
}

int binarySearchRecursive(int[] a, int target, int low, int high) {
    if (low > high) return -1; // Error

    int mid = (low + high) / 2;
    if (a[mid] < target) {
        return binarySearchRecursive(a, target, mid + 1, high);
    } else if(a[mid] > target){
        return binarySearchRecursive(a, target, low, mid - 1);
    } else{
        return mid;
    }
}

Merge Sort

  • A sorting technique based on divide and conquer technique and has a worst-case time complexity being Ο(n log n).
  • Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
  • Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single-element arrays. It is the "merge" part that does all the heavy lifting.
  • The merge method operates by copying all the elements from the target array segment into a helper array, keeping track of where the start of the left and right halves should be (helperLeft and helperRight). We then iterate through helper, copying the smaller element from each half into the array. At the end, we copy any remaining elements into the target array.
void mergesort(int[] array) {
	int[] helper = new int[array.length];
    mergesort(array, helper, 0, array.length - 1); 
}

void mergesort(int[] array, int[] helper, int low, int high){
    if (low < high) {
        int middle = (low + high) / 2;
        mergesort(array, helper, low, middle); // Sort left half
        mergesort(array, helper, middle+1, high); // Sort right half 
        merge(array, helper, low, middle, high); // Merge them
    }
}

void merge(int[] array, int[] helper, int low, int middle, int high) {
    /* Copy both halves into a helper array */ 
    for (int i = low; i <= high; i++) {
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1; 
    int current = low;
    
    /* Iterate through helper array. Compare the left and right 
    * half, copying back the smaller element from the two halves 
    * into the original array. */
    while (helperLeft <= middle && helperRight <= high) { 
        if (helper[helperLeft] <= helper[helperRight]) {
            array[current] = helper[helperLeft]; 
            helperLeft++;
        } else { // If right element is smaller than left element 
            array[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }
    /* Copy the rest of the left side of the array into the 
    * target array */
    int remaining = middle - helperLeft; 
    for (int i = 0; i <= remaining; i++) {
        array [current + i] = helper[helperLeft + i];
    }
}

Quick Sort

  • An efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.
  • Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
  • On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare.
void quickSort(int[] array) {
    quickSort(array, 0, array.length-1);
}

void quickSort(int[] array, int left, int right) {
    int index = partition(array, left, right);
    if (left < index - 1){ // Sort left half
        quickSort(array, left, index - 1);
    }
    if (index < right) { // Sort right half
        quickSort(array, index, right);
    }
}

int partition(int[] array, int left, int right) {
    int pivot = array[(left + right) / 2]; // Pick pivot point
    while (left <= right) {
        // Find element on left that should be on right
        while (array[left] < pivot)
            left++;
        // Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        // Swap elements, and move left and right indices
        if (left <= right) {
            swap(array, left, right); // swaps elements
            left++;
            right--;
        }
    }
    return left;
}

void swap(int array[], int left, int right){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

Selection Sort

  • Selection sort finds the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, finds the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.
void selectionSort(int[] array){
    int i, j, first;
    for (i = array.length - 1; i > 0; i--){
        first = 0;   //initialize to subscript of first element
        for(j = 1; j <= i; j++){   //locate smallest element between positions 1 and i.
            if(array[j] > array[first])
                first = j;
        }
        swap(array, first, i); //swap smallest found with element in position i.
    }
}

void swap(int array[], int left, int right){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

Bubble Sort

  • A simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
  • The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
  • The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.
void bubbleSort(int[] array) {
    boolean flag = true; // set flag to true to begin first pass
    while (flag) {
        flag = false; //set flag to false awaiting a possible swap
        for (int j = 0; j<array.length-1; j++) {
            if (array[j] > array[j+1]){
                swap(array, j, j+1);
                flag = true; //shows a swap occurred
            }
        }
    }
}

void swap(int array[], int left, int right){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

Radix Sort

  • Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the Os are grouped together. Then, we sort each of these groupings by the next digit. We repeat this process sorting by each subsequent digit, until finally the whole array issorted.
  • Unlike comparison sorting algorithms, which cannot perform better than 0(n log(n)) in the average case, radix sort has a runtime of 0(kn), where n is the number of elements and k is the number of passes of the sorting algorithm.
void radixSort(int[] a){
    int i, m = a[0], exp = 1, n = a.length;
    int[] b = new int[10];
    
    for (i = 1; i < n; i++)
        if (a[i] > m)
            m = a[i];
    
    while (m / exp > 0){
        int[] bucket = new int[10];

        for (i = 0; i < n; i++)
            bucket[(a[i] / exp) % 10]++;
        for (i = 1; i < 10; i++)
            bucket[i] += bucket[i - 1];
        for (i = n - 1; i >= 0; i--)
            b[--bucket[(a[i] / exp) % 10]] = a[i];
        for (i = 0; i < n; i++)
            a[i] = b[i];
        exp *= 10;
    }
}

Tree Searching

  • Binary Search Tree
  • Trie
  • AVL Tree
  • Red-Black Tree

Tree Insertion

  • Binary Search Tree
  • Trie
  • AVL Tree
  • Red-Black Tree

Tree Deletion

  • Binary Search Tree
  • Trie
  • AVL Tree
  • Red-Black Tree

Traveling Salesman Problem (TSP)

  • Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
  • It is an NP-hard problem in combinatorial optimization.
  • The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapeast (using brute force search).
  • The run time for the brute force approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities.

Knapsack Problem

  • Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
  • It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
  • The decision problem form of the knapsack problem ("Can a value of at least V be achieved without exceeding the weight W?) is NP-Complete, thus it is expected that no algorithm can be both correct and fast (polynomial-time) on all cases.
  • There is a pseudo polynomical time algorithm using dynamic programming.

Dijkstra's Algorithm

  • An algorithm for finding the shortest paths between nodes in a graph.
  • Marks a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
  • For a given source node in the graph, the algorithm finds the shortest path between that node and every other.
  • Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.
    • Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
    • Mark all nodes except the initial node as unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
    • For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
    • When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
    • The next current node will be the node marked with the lowest (tentative) distance in the unvisited set.
    • If the unvisited set is empty, then stop. The algorithm has finished. Otherwise, set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
  • If the vertices of a graph are stored in a linked list or array, run time of this algorithm is O(|E|+|V|^2)=O(|V|^2).
  • Implementation (https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java)

A* Algorithm

  • The process of plotting an efficiently traversable path between multiple points, called nodes.
  • A* achieves better performance than Dijkstra's Algorithm by using heuristics.
  • A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution.
  • It is formulated in terms of weighted graphs: starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.
  • At each iteration of its main loop, A* needs to determine which of its partial paths to expand into one or more longer paths.
  • It does so based on an estimate of the cost (total weight) still to go to the goal node. Specifically, A* selects the path that minimizes f(n)=g(n)+h(n) where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal.
  • The heuristic is problem-specific.
  • For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node.
  • Steps :
  • Add the starting square (or node) to the open list.
  • Repeat the following:
    • Look for the lowest F cost square on the open list. We refer to this as the current square.
    • Switch it to the closed list.
    • For each of the 8 squares adjacent to this current square …
      • If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
      • If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
      • If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
    • Stop when you: Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path.
  • Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

Concepts

Bit Manipulation

  • The act of algorithmically manipulating bits.
  • Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization.
  • For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions.
  • Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.
  • Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed ups, as bit manipulations are processed in parallel, but the code can become more difficult to write and maintain.

  • is the right shift operator.

  • << is the left shift operator.
  • Bit Manipulation Chart - http://imgur.com/a/QUCCH

Singleton Design Pattern

  • A design pattern that restricts the instantiation of a class to one object.
  • This is useful when exactly one object is needed to coordinate actions across the system.
  • An implementation of the singleton pattern must ensure that only one instance of the singleton class ever exists and provide global access to that instance.
  • Typically, this is achieved by declaring all constructors of the class to be private and providing a static method that returns a reference to the instance.
public final class Singleton {
    private static final Singleton instance = new Singleton();
    private Singleton() {}

    public static Singleton getInstance() {
        return instance;
    }
}

Factory Design Pattern

  • In Factory pattern, we create object without exposing the creation logic to the client and refer to newly created object using a common interface.

  • Implementation of the Factory Design Pattern :

    • Create an interface
    • Create concrete classes implementing the same interface.
    • Create a Factory to generate object of concrete class based on given information.
    • Use the Factory to get object of concrete class by passing an information such as type.
    • Verify the output.

Shape.java

public interface Shape {
   void draw();
}

Rectangle.java

public class Rectangle implements Shape {

   @Override
   public void draw() {
      System.out.println("Inside Rectangle::draw() method.");
   }
}

Square.java

public class Square implements Shape {

   @Override
   public void draw() {
      System.out.println("Inside Square::draw() method.");
   }
}

Circle.java

public class Circle implements Shape {

   @Override
   public void draw() {
      System.out.println("Inside Circle::draw() method.");
   }
}

ShapeFactory.java

public class ShapeFactory {
	
   //use getShape method to get object of type shape 
   public Shape getShape(String shapeType){
      if(shapeType == null){
         return null;
      }		
      if(shapeType.equalsIgnoreCase("CIRCLE")){
         return new Circle();
         
      } else if(shapeType.equalsIgnoreCase("RECTANGLE")){
         return new Rectangle();
         
      } else if(shapeType.equalsIgnoreCase("SQUARE")){
         return new Square();
      }
      
      return null;
   }
}

FactoryPatternDemo.java

public class FactoryPatternDemo {

   public static void main(String[] args) {
      ShapeFactory shapeFactory = new ShapeFactory();

      //get an object of Circle and call its draw method.
      Shape shape1 = shapeFactory.getShape("CIRCLE");

      //call draw method of Circle
      shape1.draw();

      //get an object of Rectangle and call its draw method.
      Shape shape2 = shapeFactory.getShape("RECTANGLE");

      //call draw method of Rectangle
      shape2.draw();

      //get an object of Square and call its draw method.
      Shape shape3 = shapeFactory.getShape("SQUARE");

      //call draw method of circle
      shape3.draw();
   }
}
Inside Circle::draw() method.
Inside Rectangle::draw() method.
Inside Square::draw() method.

Memory (Stack vs. Heap)

  • The stack and heap are the two sections of the memory layout of a process.
  • The stack is used to keep track of variables/parameters local to a function in a program.
  • Whenever you call a new function, a new stack frame is pushed to the stack with parameters and variables local to that function. When that function returns, the stack frame is popped out and the context switches back to the previous function (the caller).
  • Java Stack memory is used for execution of a thread.
  • The stack contains method specific values that are short-lived and references to other objects in the heap that are getting referred from the method.
  • Stack memory is always referenced in LIFO (Last-In-First-Out) order.
  • Stack memory size is very less compared to Heap memory.
  • A heap is a kind of a global memory pool.
  • A function can allocate memory on the heap if it wants the data to live longer than the function itself.
  • Objects allocated on the heap are accessible to all the functions, given they have the reference/address of the object to access it.
  • Java Heap space is used by Java runtime to allocate memory to Objects and JRE classes.
  • Whenever we create any object, it’s always created in the Heap space.
  • Garbage Collection runs on the heap memory to free the memory used by objects that don't have any reference.
  • Any object created in the heap space has global access and can be referenced from anywhere in the application.

Garbage Collection

  • Automatic garbage collection is the process of looking at heap memory, identifying which objects are in use and which are not, and deleting the unused objects.
  • An in use object, or a referenced object, means that some part of your program still maintains a pointer to that object.
  • An unused object, or unreferenced object, is no longer referenced by any part of your program. So the memory used by an unreferenced object can be reclaimed.
  • In Java, the process of deallocating memory is handled automatically by the garbage collector.

Memory Leak

  • A memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released.
  • In object-oriented programming, a memory leak may happen when an object is stored in memory but cannot be accessed by the running code.

Recursion

  • A method where the solution to a problem depends on solutions to smaller instances of the same problem.
  • You should make sure that your base cases as well as your null cases are well handled in recursive algorithms.
public int factorial(int n) {
    if (n <= 1) // test for base case
        return 1; // base cases: 0! = 1 and 1! = 1
    else
        // recursion step
        return n * factorial(n - 1);
}

Dynamic Programming

  • A method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure.
  • The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.)
  • The technique of storing solutions to subproblems instead of recomputing them is called "memoization".
  • A Dynamic Programming problem can be approached in the same way as a recursion problem, but the difference is that intermediate results are cached for future calls to avoid unnecessary calculations.
int fibonacci(int n) {
    int[] memoizationArray = new int[n+1];
    Arrays.fill(memoizationArray, -1);
    return fibonacci(n, memoizationArray);
}

int fibonacci(int n, int[] a) {
    if (n <= 2) {
        return 1;
    } else if (a[n] != -1) {
        return a[n]; // Return cached result.
    } else {
        a[n] = fibonacci(n-1, a) + fibonacci(n-2, a); // Cache result
    }
    return a[n];
}

Big-O Time

  • Big O notation is used to classify algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large
  • Big O notation is the language we use for articulating how long an algorithm takes to run.
  • It's how we compare the efficiency of different approaches to a problem.
  • With Big O notation we express the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrarily large.
  • http://bigocheatsheet.com/

NP

  • The set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs.
  • These proofs have to be verifiable by deterministic computations that can be performed in polynomial time.
  • The set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine.

NP-complete

  • A decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to "nondeterministic polynomial time".
  • Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place.
  • The most notable characteristic of NP-complete problems is that no fast solution to them is known.

NP-hard

  • A class of problems that are, informally, "at least as hard as the hardest problems in NP".
  • A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H, that is given a solution for L we can verify it is a solution for H in polynomial time.
  • As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.

Process

  • An instance of a computer program that is being executed.
  • It contains the program code and its current activity.
  • Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.
  • A computer program is a passive collection of instructions, while a process is the actual execution of those instructions.
  • Several processes may be associated with the same program; for example, opening up several instances of the same program often means more than one process is being executed.
  • A process can be thought of as an instance of a program in execution. A process is an independent entity to which system resources (e.g., CPU time and memory) are allocated. Each process is executed in a separate address space, and one process cannot access the variables and data structures of another process. If a process wishes to access another process' resources, inter-process communications have to be used. These include pipes, files, sockets, and other forms.

Thread

  • A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.
  • A thread is a component of a process.
  • Multiple threads can exist within one process, executing concurrently and sharing resources such as memory, while different processes do not share these resources.
  • In particular, the threads of a process share its executable code and the values of its variables at any given time.
  • A thread exists within a process and shares the process' resources (including its heap space). Multiple threads within the same process will share the same heap space. This is very different from processes, which cannot directly access the memory of another process. Each thread still has its own registers and its own stack, but other threads can read and write the heap memory.
  • A thread is a particular execution path of a process. When one thread modifies a process resource, the change is immediately visible to sibling threads.

Monitor (Lock)

  • A synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.
  • Monitors also have a mechanism for signalling other threads that their condition has been met.
  • A monitor consists of a mutex (lock) object and condition variables.
  • A condition variable is basically a container of threads that are waiting for a certain condition.
  • Monitors provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.

Deadlock

  • A deadlock is a situation where a thread is waiting for an object lock that another thread holds, and this second thread is waiting for an object lock that the first thread holds (or an equivalent situation with several threads).
  • Since each thread is waiting for the other thread to relinquish a lock, they both remain waiting forever. The threads are said to be deadlocked.
  • In order for a deadlock to occur, you must have all four of the following conditions met:
    • Mutual Exclusion: Only one process can access a resource at a given time. (Or, more accurately, there is limited access to a resource. A deadlock could also occur if a resource has limited quantity.)
    • Hold and Wait: Processes already holding a resource can request additional resources, without relinquishing their current resources.
    • No Preemption: One process cannot forcibly remove another process' resource.
    • Circular Wait: Two or more processes form a circular chain where each process is waiting on another resource in the chain.
  • Most deadlock prevention algorithms focus on avoiding circular wait.

Semaphore

  • A variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a concurrent system such as a multiprogramming operating system.
  • A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.
  • The variable is then used as a condition to control access to some system resource.
  • A useful way to think of a semaphore as used in the real-world systems is as a record of how many units of a particular resource are available, coupled with operations to adjust that record safely (i.e. to avoid race conditions) as units are required or become free, and, if necessary, wait until a unit of the resource becomes available.
  • Semaphores are a useful tool in the prevention of race conditions; however, their use is by no means a guarantee that a program is free from these problems.
  • Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores.

Context Switch

  • The process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.
  • This enables multiple processes to share a single CPU and is an essential feature of a multitasking operating system.
  • A context switch is the time spent switching between two processes (i.e., bringing a waiting process into execution and sending an executing process into waiting/terminated state). This happens in multitasking. The operating system must bring the state information of waiting processes into memory and save the state information of the currently running process.

Probability

  • Probability of A and B - P(A and B) = P(B given A) P(A)
  • Probability of A or B - P(A or B) = P(A) + P(B) - P(A and B)
  • Independence - P(A and B) = P(A) P(B)
  • Mutual Exclusivity - P(A or B) = P(A) + P(B)
  • As long as two events have non-zero probabilities, they will never be both mutually exclusive and independent.

Java

Inheritance

  • In object-oriented programming, inheritance enables new objects to take on the properties of existing objects.
  • A class that is used as the basis for inheritance is called a superclass or base class.
  • A class that inherits from a superclass is called a subclass or derived class.
  • The terms parent class and child class are also acceptable terms to use respectively.
  • A child inherits visible properties and methods from its parent while adding additional properties and methods of its own.

Encapsulation

  • A language mechanism for restricting direct access to some of the object's components.
  • A language construct that facilitates the bundling of data with the methods (or other functions) operating on that data.
  • Encapsulation can be used to hide data members and members function
  • It is also called "information hiding".
  • An object has to provide its users only with the essential information for manipulation, without the internal details.
  • Encapsulation is wrapping, just hiding properties and methods.
  • Encapsulation means hiding the code and data in a single unit to protect the data from the outside the world.
  • Encapsulation is hiding the implementation details which may or may not be for generic or specialized behavior(s).

Abstraction

  • Abstraction means working with something we know how to use without knowing how it works internally.
  • Abstraction refers to showing only the necessary details to the intended user.
  • Abstraction is providing a generalization (say, over a set of behaviors).
  • Abstraction lets you focus on what the object does instead of how it does it.

Polymorphism

  • Subclasses of a class can define their own unique behaviors and yet share some of the same functionality of the parent class.
  • Polymorphism is the ability to present the same interface for differing underlying data types.
  • Polymorphism is used to make applications more modular and extensible.
  • Treating a derived type as if it were it's base type.
class Shape{
   void draw(){}
}

class Circle extends Shape{
   private int x, y, r;

   Circle(int x, int y, int r){
      this.x = x;
      this.y = y;
      this.r = r;
   }

   // For brevity, I've omitted getX(), getY(), and getRadius() methods.

   @Override
   void draw(){
      System.out.println("Drawing circle (" + x + ", "+ y + ", " + r + ")");
   }
}

class Rectangle extends Shape{
   private int x, y, w, h;

   Rectangle(int x, int y, int w, int h){
      this.x = x;
      this.y = y;
      this.w = w;
      this.h = h;
   }

   // For brevity, I've omitted getX(), getY(), getWidth(), and getHeight()
   // methods.

   @Override
   void draw(){
      System.out.println("Drawing rectangle (" + x + ", "+ y + ", " + w + "," +
                         h + ")");
   }
}

class Shapes{
   public static void main(String[] args){
      Shape[] shapes = { new Circle(10, 20, 30),
                         new Rectangle(20, 30, 40, 50) };
      for (int i = 0; i < shapes.length; i++)
         shapes[i].draw();
   }
}

Interface

  • A Java interface is a bit like a class, except a Java interface can only contain method signatures and fields.
  • A Java interface cannot contain an implementation of the methods, only the signature (name, parameters and exceptions) of the method.
  • You can use interfaces in Java as a way to achieve polymorphism.
  • Interfaces cannot be instantiated—they can only be implemented by classes or extended by other interfaces.
  • An interface in Java is a blueprint of a class.
  • It has static constants and abstract methods only.
  • Interfaces can be used to achieve loose coupling.
  • Interface fields are public, static and final by default, and methods are public and abstract.
  • An interface does not contain any constructors.
  • An interface is not extended by a class; it is implemented by a class.
public interface Predator {
    boolean chasePrey(Prey p);
    void eatPrey(Prey p);
}

public class Lion implements Predator {
    @Override
    public boolean chasePrey(Prey p) {
        // programming to chase prey p (specifically for a lion)
    }
    
    @Override
    public void eatPrey(Prey p) {
        // programming to eat prey p (specifically for a lion)
    }
}

Abstract Class

  • Abstract classes are classes that contain one or more abstract methods.
  • Abstract classes may not be instantiated, and require subclasses to provide implementations for the abstract methods.
  • An abstract method is a method that is declared without an implementation.
  • If a class includes abstract methods, then the class itself must be declared abstract.
  • When an abstract class is subclassed, the subclass usually provides implementations for all of the abstract methods in its parent class. However, if it does not, then the subclass must also be declared abstract.
public abstract class GraphicObject {
   // declare fields
   // declare nonabstract methods
   abstract void draw();
}

Overriding

  • An instance method in a subclass with the same signature (name, plus the number and the type of its parameters) and return type as an instance method in the superclass overrides the superclass's method.
  • The ability of a subclass to override a method allows a class to inherit from a superclass whose behavior is "close enough" and then to modify behavior as needed.
public class Animal {
    public static void testClassMethod() {
        System.out.println("The static method in Animal");
    }
    
    public void testInstanceMethod() {
        System.out.println("The instance method in Animal");
    }
}

public class Cat extends Animal {
    public static void main(String[] args) {
        Cat myCat = new Cat();
        Animal myAnimal = myCat;
        Animal.testClassMethod();
        myAnimal.testInstanceMethod();
    }
    
    public static void testClassMethod() {
        System.out.println("The static method in Cat");
    }
    
    @Override
    public void testInstanceMethod() {
        System.out.println("The instance method in Cat");
    }
}

Output :
The static method in Animal
The instance method in Cat

Overloading

  • Overloading is a term used to describe when two or more methods have the same name but differ in the type or number of arguments.
public class DataArtist {
	public void draw(String s) {}
    public void draw(int i) {}
    public void draw(double f) {}
    public void draw(int i, double f) {}
}

Access modifiers

  • Keywords in object-oriented languages that set the accessibility of classes, methods, and other members.
  • A class may be declared with the modifier public, in which case that class is visible to all classes everywhere.
  • If a class has no modifier (the default, also known as package-private), it is visible only within its own package.
  • At the member level, you can also use the public modifier or no modifier (package-private).
  • The private modifier specifies that the member can only be accessed in its own class.
  • The protected modifier specifies that the member can only be accessed within its own package (as with package-private) and, in addition, by a subclass of its class in another package.

transient

  • The transient keyword in Java is used to indicate that a field should not be serialized.
  • Variables may be marked transient to indicate that they are not part of the persistent state of an object.

volatile

  • The volatile modifier guarantees that any thread that reads a field will see the most recently written value.
  • The volatile keyword is used to indicate that a variable's value will be modified by different threads.
  • The value of this variable will never be cached thread-locally: all reads and writes will go straight to "main memory";
  • Access to the variable acts as though it is enclosed in a synchronized block, synchronized on itself.

final vs. finally vs. finalize

  • final
    • Variable - The value cannot be changed once initialized.
    • Method - The method cannot be overridden by a subclass.
    • Class - The class cannot be subclassed.
  • finally
    • The finally keyword is used in association with a try/catch block and guarantees that a section of code will be executed, even if an exception is thrown. The finally block will be executed after the try and catch blocks, but before control transfers back to its origin.
  • finalize
    • The automatic garbage collector calls the finalize() method just before actually destroying the object.
    • A class can therefore override the finalize() method from the Object class in order to define custom behavior during garbage collection.

static

  • Static tells the compiler that the element (member variable/method) is not associated with any instance members of the class in which it is declared. That is, the element is associated with the class rather than with an instance of the class.
  • Static elements belong to class rather than Object.
  • The static keyword denotes that a member variable, or method, can be accessed without requiring an instantiation of the class to which it belongs.
  • Static variables or methods are global and we can also call them class variable or class methods
  • A non-static nested class (or 'inner class') has full access to the members of the class within which it is nested. A static nested class does not have a reference to a nesting instance, so a static nested class cannot invoke non-static methods or access non-static fields of an instance of the class within which it is nested.
  • Technically, there is no such thing as a static inner class. The correct terminology is a "static nested class". A non-static nested class is indeed an inner class, along with anonymous classes and local classes. Each instance of a nonstatic [nested] class is implicitly associated with an enclosing instance of its containing class... It is possible to invoke methods on the enclosing instance. A static nested class does not have access to the enclosing instance.
  • Nested classes are divided into two categories: static and non-static. Nested classes that are declared static are simply called static nested classes. Non-static nested classes are called inner classes.
  • You would define a static inner class when you know that it does not have any relationship with the instance of the enclosing class/top class. If your inner class doesn't use methods or fields of the outer class, it's just a waste of space, so make it static.
  • The advantage of a static nested class is that it doesn't need an object of the containing class/top class to work. This can help you to reduce the number of objects your application creates at runtime.

Strong Reference

  • A Strong reference is a normal reference that protects the referred object from collection by a garbage collector.

Soft Reference

  • Soft reference objects are cleared at the discretion of the garbage collector in response to memory demand.
  • Soft references are most often used to implement memory-sensitive caches.
  • A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers.
  • An object which is softly reachable will generally stick around for a while.

Weak Reference

  • A Weak reference is a reference that does not protect the referenced object from collection by a garbage collector.
  • A weak reference is a reference that isn't strong enough to force an object to remain in memory.
  • Weak references allow you to leverage the garbage collector's ability to determine reachability for you, so you don't have to do it yourself.
  • An object which is only weakly reachable (the strongest references to it are WeakReferences) will be discarded at the next garbage collection cycle.
WeakReference weakWidget = new WeakReference(widget);

Autoboxing

  • Autoboxing is the automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes.
  • For example, converting an int to an Integer, a double to a Double, and so on. If the conversion goes the other way, this is called unboxing.

Unboxing

  • Converting an object of a wrapper type (Integer) to its corresponding primitive (int) value is called unboxing.
  • The Java compiler applies unboxing when an object of a wrapper class is passed as a parameter to a method that expects a value of the corresponding primitive type or assigned to a variable of the corresponding primitive type.

Enumeration

  • Enumeration only traverses the Collection object. You can’t do any modifications to Collection while traversing the Collection using Enumeration.
  • An object that implements the Enumeration interface generates a series of elements, one at a time.
  • Successive calls to the nextElement method return successive elements of the series.

Iterator

  • An iterator over a collection.
  • The Iterator interface allows us to remove an element while traversing the Collection object.
  • Iterator has remove() method which is not there in the Enumeration interface.
  • Iterator should be preferred over Enumeration, as Iterator takes the place of Enumeration in the Java collections framework.

Android

Activity

  • An activity is a single, focused thing that the user can do.
  • Almost all activities interact with the user, so the Activity class takes care of creating a window for you in which you can place your UI with setContentView(View).
  • While activities are often presented to the user as full-screen windows, they can also be used in other ways: as floating windows (via a theme with windowIsFloating set) or embedded inside of another activity (using ActivityGroup).
  • An activity represents a single screen with a user interface.

Fragment

  • Fragment class helps to better modularize code, build more sophisticated user interfaces for larger screens, and help scale their application between small and large screens.
  • A Fragment is a piece of an application's user interface or behavior that can be placed in an Activity.
  • Though Fragment defines its own lifecycle, that lifecycle is dependent on its activity: if the activity is stopped, no fragments inside of it can be started; when the activity is destroyed, all fragments will be destroyed.

Service

  • An application component representing either an application's desire to perform a longer-running operation while not interacting with the user or to supply functionality for other applications to use.
  • Each service class must have a corresponding <service> declaration in its package's AndroidManifest.xml.
  • Services can be started with Context.startService() and Context.bindService().
  • Services run in the main thread of their hosting process.
  • If your service is going to do any CPU intensive (such as MP3 playback) or blocking (such as networking) operations, it should spawn its own thread in which to do that work.
  • A facility for the application to tell the system about something it wants to be doing in the background (even when the user is not directly interacting with the application).

BroadcastReceiver

  • A broadcast receiver is a component that responds to system-wide broadcast announcements.
  • Many broadcasts originate from the system—for example, a broadcast announcing that the screen has turned off, the battery is low, or a picture was captured.
  • Apps can also initiate broadcasts—for example, to let other apps know that some data has been downloaded to the device and is available for them to use.
  • Although broadcast receivers don't display a user interface, they may create a status bar notification to alert the user when a broadcast event occurs.
  • More commonly, though, a broadcast receiver is just a "gateway" to other components and is intended to do a very minimal amount of work.
  • For instance, it might initiate a service to perform some work based on the event.

ContentProvider

  • A content provider manages a shared set of app data.
  • You can store the data in the file system, an SQLite database, on the web, or any other persistent storage location your app can access.
  • Through the content provider, other apps can query or even modify the data (if the content provider allows it).
  • Content providers are also useful for reading and writing data that is private to your app and not shared.

Activity Lifecycle

  • There are 4 States of an Activity :
  • If an activity is in the foreground of the screen (at the top of the stack), it is active or running.
  • If an activity has lost focus but is still visible (that is, a new non-full-sized or transparent activity has focus on top of your activity), it is paused. A paused activity is completely alive (it maintains all state and member information and remains attached to the window manager), but can be killed by the system in extreme low memory situations.
  • If an activity is completely obscured by another activity, it is stopped. It still retains all state and member information, however, it is no longer visible to the user so its window is hidden and it will often be killed by the system when memory is needed elsewhere.
  • If an activity is paused or stopped, the system can drop the activity from memory by either asking it to finish, or simply killing its process. When it is displayed again to the user, it must be completely restarted and restored to its previous state.

Activity Lifecycle

  • The entire lifetime of an activity happens between the first call to onCreate(Bundle) through to a single final call to onDestroy(). An activity will do all setup of "global" state in onCreate(), and release all remaining resources in onDestroy(). For example, if it has a thread running in the background to download data from the network, it may create that thread in onCreate() and then stop the thread in onDestroy().
  • The visible lifetime of an activity happens between a call to onStart() until a corresponding call to onStop(). During this time the user can see the activity on-screen, though it may not be in the foreground and interacting with the user. Between these two methods you can maintain resources that are needed to show the activity to the user. For example, you can register a BroadcastReceiver in onStart() to monitor for changes that impact your UI, and unregister it in onStop() when the user no longer sees what you are displaying. The onStart() and onStop() methods can be called multiple times, as the activity becomes visible and hidden to the user.
  • The foreground lifetime of an activity happens between a call to onResume() until a corresponding call to onPause(). During this time the activity is in front of all other activities and interacting with the user. An activity can frequently go between the resumed and paused states -- for example when the device goes to sleep, when an activity result is delivered, when a new intent is delivered -- so the code in these methods should be fairly lightweight.
 public class Activity extends ApplicationContext {
    protected void onCreate(Bundle savedInstanceState);
    protected void onStart();
    protected void onRestart();
    protected void onResume();
    protected void onPause();
    protected void onStop();
    protected void onDestroy();
}

Intent

  • An abstract description of an operation to be performed.
  • It can be used with startActivity to launch an Activity, broadcastIntent to send it to any interested BroadcastReceiver components, and startService(Intent) or bindService(Intent, ServiceConnection, int) to communicate with a background Service.
  • An Intent provides a facility for performing late runtime binding between the code in different applications.
  • Intent is a messaging object you can use to request an action from another app component.
  • A passive data structure holding an abstract description of an action to be performed.
  • Explicit intents specify the component to start by name (the fully-qualified class name). You'll typically use an explicit intent to start a component in your own app, because you know the class name of the activity or service you want to start. For example, start a new activity in response to a user action or start a service to download a file in the background.
  • Implicit intents do not name a specific component, but instead declare a general action to perform, which allows a component from another app to handle it. For example, if you want to show the user a location on a map, you can use an implicit intent to request that another capable app show a specified location on a map.
  • An intent has an action and data :
  • action -- The general action to be performed, such as ACTION_VIEW, ACTION_EDIT, ACTION_MAIN, etc.
  • data -- The data to operate on, such as a person record in the contacts database, expressed as a Uri.

Intent Filter

  • An intent filter is an expression in an app's manifest file that specifies the type of intents that the component would like to receive.
  • For instance, by declaring an intent filter for an activity, you make it possible for other apps to directly start your activity with a certain kind of intent.
  • Likewise, if you do not declare any intent filters for an activity, then it can be started only with an explicit intent.
  • When you create an implicit intent, the Android system finds the appropriate component to start by comparing the contents of the intent to the intent filters declared in the manifest file of other apps on the device.
  • If the intent matches an intent filter, the system starts that component and delivers it the Intent object.
  • If multiple intent filters are compatible, the system displays a dialog so the user can pick which app to use.

APK

  • Android application package (APK) is the package file format used by the Android operating system for distribution and installation of mobile apps and middleware.
  • An APK file contains all of that program's code (such as .dex files), resources, assets, certificates, and manifest file.

ADB

  • The Android Debug Bridge (ADB) is a toolkit included in the Android SDK package.
  • It consists of both client and server-side programs that communicate with one another.
  • The ADB is typically accessed through the command-line interface.
  • It can execute remote shell commands to run applications on an emulator.

DDMS

  • Dalvik Debug Monitor Server (DDMS) is a debugging tool which provides port-forwarding services, screen capture on the device, thread and heap information on the device, logcat, process, and radio state information, incoming call and SMS spoofing, location data spoofing, and more.

AAPT

  • The Android Asset Packaging Tool (AAPT) is a tool that is part of the SDK (and build system) and allows you to view, create, and update Zip-compatible archives (zip, jar, apk).
  • It can also compile resources into binary assets.
  • Build scripts and IDE plugins utilize this tool to package the apk file that constitutes an Android application.

JVM

  • A Java virtual machine (JVM) is an abstract computing machine that enables a computer to run a Java program.
  • There are three notions of the JVM specification, implementation and instance.
  • The specification is a document that formally describes what is required of a JVM implementation.
  • Having a single specification ensures all implementations are interoperable.
  • A JVM implementation is a computer program that meets the requirements of the JVM specification.
  • An instance of a JVM is an implementation running in a process that executes a computer program compiled into Java bytecode.

JRE

  • Java Runtime Environment (JRE) is a software package that contains what is required to run a Java program.
  • It includes a Java Virtual Machine implementation together with an implementation of the Java Class Library.

JDK

  • Java Development Kit (JDK) is a superset of a JRE and contains tools for Java programmers, e.g. a javac compiler.

DVM

  • Dalvik is a discontinued process virtual machine (VM) that executes applications written for Android.
  • Dalvik is an integral part of the Android software stack in Android versions 4.4 "KitKat" and earlier.
  • Programs for Android are commonly written in Java and compiled to bytecode for the Java virtual machine, which is then translated to Dalvik bytecode and stored in .dex (Dalvik EXecutable) and .odex (Optimized Dalvik EXecutable) files.
  • The compact Dalvik Executable format is designed for systems that are constrained in terms of memory and processor speed.

ART

  • The successor of Dalvik is Android Runtime (ART), which uses the same bytecode and .dex files (but not .odex files), with the succession aiming at performance improvements transparent to the end users.
  • The new runtime environment was included for the first time in Android 4.4 "KitKat" as a technology preview, and replaced Dalvik entirely in later versions.
  • Android 5.0 "Lollipop" is the first version in which ART is the only included runtime.

AIDL

  • AIDL (Android Interface Definition Language) allows you to define the programming interface that both the client and service agree upon in order to communicate with each other using interprocess communication (IPC).
  • On Android, one process cannot normally access the memory of another process.
  • So to talk, they need to decompose their objects into primitives that the operating system can understand, and marshall the objects across that boundary for you.
  • The code to do that marshalling is tedious to write, so Android handles it for you with AIDL.

NDK

  • The Android NDK is a toolset that lets you implement parts of your app using native-code languages such as C and C++ to boost the performance.

ANR

  • ANR stands for Application Not Responding. It is a dialog box that appears if the application is no longer responding.
  • The system displays an ANR if an application cannot respond to user input.
  • Anything your application is doing in the UI thread that takes a long time to complete can trigger the ANR dialog because your application is not giving itself a chance to handle the input event or intent broadcasts.
  • For example, if an application blocks on some I/O operation (frequently a network access) on the UI thread so the system can't process incoming user input events.
  • Or perhaps the app spends too much time building an elaborate in-memory structure or computing the next move in a game on the UI thread.

Shared Preferences

  • The SharedPreferences class provides a general framework that allows you to save and retrieve persistent key-value pairs of primitive data types.
  • You can use SharedPreferences to save any primitive data: booleans, floats, ints, longs, and strings.
  • This data will persist across user sessions (even if your application is killed).

Nine-Patch

  • A NinePatchDrawable graphic is a stretchable bitmap image, which Android will automatically resize to accommodate the contents of the View in which you have placed it as the background.
  • An example use of a NinePatch is the backgrounds used by standard Android buttons — buttons must stretch to accommodate strings of various lengths.
  • A NinePatch drawable is a standard PNG image that includes an extra 1-pixel-wide border. It must be saved with the extension .9.png, and saved into the res/drawable/ directory of your project.
  • The Nine-patch refers to the way you can resize the image: 4 corners that are unscaled, 4 edges that are scaled in 1 axis, and the middle one that can be scaled into both axes.

Support Library

  • The Android Support Library offers a number of features that are not built into the framework.
  • These libraries offer backward-compatible versions of new features, provide useful UI elements that are not included in the framework, and provide a range of utilities that apps can draw on.
  • Support libraries allow apps running on older versions of the Android platform to support features made available on newer versions of the platform.

Loader

  • Introduced in Android 3.0, loaders make it easy to asynchronously load data in an activity or fragment.
  • Loaders have these characteristics:
    • They are available to every Activity and Fragment.
    • They provide asynchronous loading of data.
    • They monitor the source of their data and deliver new results when the content changes.
    • They automatically reconnect to the last loader's cursor when being recreated after a configuration change. Thus, they don't need to re-query their data.

StrictMode

  • StrictMode is a developer tool which detects things you might be doing by accident and brings them to your attention so you can fix them.
  • StrictMode is most commonly used to catch accidental disk or network access on the application's main thread, where UI operations are received and animations take place.

Gradle

  • Android Studio uses Gradle, an advanced build toolkit, to automate and manage the build process, while allowing you to define flexible custom build configurations.
  • Each build configuration can define its own set of code and resources, while reusing the parts common to all versions of your app.
  • The Android Plugin for Gradle works with the build toolkit to provide processes and configurable settings that are specific to building and testing Android applications.

Android Build Process

  • The build process for a typical Android app module, follows these general steps:
    • The compilers convert your source code into DEX (Dalvik Executable) files, which include the bytecode that runs on Android devices, and everything else into compiled resources.
    • The APK Packager combines the DEX files and compiled resources into a single APK. Before your app can be installed and deployed onto an Android device, however, the APK must be signed.
    • The APK Packager signs your APK using either the debug or release keystore:
      • If you are building a debug version of your app, that is, an app you intend only for testing and profiling, the packager signs your app with the debug keystore. Android Studio automatically configures new projects with a debug keystore.
      • If you are building a release version of your app that you intend to release externally, the packager signs your app with the release keystore. To create a release keystore, read about signing your app in Android Studio.
    • Before generating your final APK, the packager uses the zipalign tool to optimize your app to use less memory when running on a device.
  • At the end of the build process, you have either a debug APK or release APK of your app that you can use to deploy, test, or release to external users. Android Build Process

Proguard

  • Code shrinking is available with ProGuard, which detects and removes unused classes, fields, methods, and attributes from your packaged app, including those from included code libraries (making it a valuable tool for working around the 64k reference limit).
  • ProGuard also optimizes the bytecode, removes unused code instructions, and obfuscates the remaining classes, fields, and methods with short names.
  • The obfuscated code makes your APK difficult to reverse engineer, which is especially valuable when your app uses security-sensitive features, such as licensing verification.

Multidex

  • Android application (APK) files contain executable bytecode files in the form of Dalvik Executable (DEX) files, which contain the compiled code used to run your app.
  • The Dalvik Executable specification limits the total number of methods that can be referenced within a single DEX file to 65,536, including Android framework methods, library methods, and methods in your own code.
  • Getting past this limit requires that you configure your app build process to generate more than one DEX file, known as a multidex configuration.

Questions

Most frequent K words in a document

  • Given a word document as a String, find the K most frequent words in the document?
private List<String> getMostFrequentWords(String document, int numOfWords){
    List<String> mostFrequentWords = new ArrayList<>();

    if(numOfWords<=0 || TextUtils.isEmpty(document)){
        return mostFrequentWords;
    }

    String[] tokens = document.split("\\s*[^a-zA-Z']*?\\s+");

    Map<String, Integer> wordFrequencies = new HashMap<>();
    for(String token : tokens){
        if(wordFrequencies.containsKey(token))
            wordFrequencies.put(token, wordFrequencies.get(token) + 1);
        else
            wordFrequencies.put(token, 1);
    }

    PriorityQueue maxHeap = new PriorityQueue(wordFrequencies.size(), new Comparator<Object>() {
        @Override
        public int compare(Object lhs, Object rhs) {
            int freq1 = ((Word)lhs).getFrequency();
            int freq2 = ((Word)rhs).getFrequency();
            if(freq1 < freq2){
                return 1;
            } else if(freq1 > freq2){
                return -1;
            } else {
                return 0;
            }
        }
    });

    for ( String key : wordFrequencies.keySet() ) {
        Word word = new Word(key, wordFrequencies.get(key));
        maxHeap.add(word);
    }

    for(int i=0; maxHeap.size()>0 && i<numOfWords; i++){
        Word word = (Word) maxHeap.poll();
        mostFrequentWords.add(word.getText());
    }

    return mostFrequentWords;
}

private class Word{

    // region Member Variables
    private String text;
    private int frequency;
    // endregion

    // region Constructors
    public Word(String text, int frequency){
        this.text = text;
        this.frequency = frequency;
    }
    // endregion

    // region Getters
    public int getFrequency() {
        return this.frequency;
    }

    public String getText() {
        return this.text;
    }
    // endregion

    // region Setters
    public void setText(String text) {
        this.text = text;
    }

    public void setFrequency(int frequency) {
        this.frequency = frequency;
    }
    // endregion
}

Longest common subsequence

  • Given two Strings, find the longest common subsequence?
public String lcs(String a, String b){
    if(TextUtils.isEmpty(a) || TextUtils.isEmpty(b))
        return "";
    else if(a.charAt(a.length()-1) == b.charAt(b.length()-1)){
        return lcs(a.substring(0, a.length()-1), b.substring(0, b.length()-1)) + a.substring(a.length()-1);
    } else {
        return maxSequence(lcs(a.substring(0, a.length()-1), b.substring(0, b.length())),
                lcs(a.substring(0, a.length()), b.substring(0, b.length()-1)) );
    }
}

private String maxSequence(String firstSequence, String secondSequence){
    if(firstSequence.length() > secondSequence.length()){
        return firstSequence;
    } else {
        return secondSequence;
    }
}

String compression

  • Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.
public String stringCompression(String uncompressedString){
    String compressedString = "";
    if(TextUtils.isEmpty(uncompressedString))
        return "";

    int repeatedFreqCount = 0;
    for(int i=0; i<uncompressedString.length(); i++){
        if(i == 0){
            repeatedFreqCount++;
        } else {
            if(uncompressedString.charAt(i) == uncompressedString.charAt(i-1)){
                repeatedFreqCount++;
            } else {
                compressedString += uncompressedString.charAt(i-1)+""+repeatedFreqCount;
                repeatedFreqCount = 1;
            }

            if(i == uncompressedString.length()-1){
                compressedString += uncompressedString.charAt(i)+""+repeatedFreqCount;
            }
        }
    }

    if(compressedString.length() < uncompressedString.length()){
        return compressedString;
    } else {
        return uncompressedString;
    }
}

Two Sum

  • You have an unsorted array, and you are given a value S. Print all pairs of elements in the array that add up to value S.
public void twoSum(int[] array, int sum){
    Map<Integer, List<Integer>> map = new HashMap<>();

    for(int i=0; i<array.length; i++){
        if(map.containsKey(array[i])){
            List<Integer> indices = map.get(array[i]);
            indices.add(i);
            map.put(array[i], indices);
        } else {
            List<Integer> indices = new ArrayList<>();
            indices.add(i);
            map.put(array[i], indices);
        }
    }

    for(int i=0; i<array.length; i++){
        int b = sum - array[i];
        if(map.containsKey(b)){
            List<Integer> indices = map.get(b);
            for(Integer index : indices){
                if(i!=index && i < index){
                    System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, index, sum));
                }
            }
        }
    }
}

Sudoku Board Validator

  • Given a sudoku board as a two-dimensional int array, write a method to validate if the board is valid.
public static int BOARD_DIMENSION = 9;

public boolean isSudokuBoardValid(int[][] board){

    // check rows
    for(int i=0; i<BOARD_DIMENSION; i++){
        if(!isRowValid(board, i)){
            return false;
        }
    }

    // check columns
    for(int j=0; j<BOARD_DIMENSION; j++){
        if(!isColumnValid(board, j)){
            return false;
        }
    }

    // check sections
    int i=0;
    int j=0;
    for( ; i<BOARD_DIMENSION; ){
        for( ; j<BOARD_DIMENSION; ){
            if(!isRegionValid(board, i, i + 2, j, j + 2)){
                return false;
            }
            j+=3;
        }
        i+=3;
    }

    return true;
}

private boolean isRowValid(int[][] board, int row){
    Set<Integer> uniqueNumbers = new HashSet<>();

    for(int i=0; i<BOARD_DIMENSION; i++){
        int value = board[row][i];
        if(value<1 || value>9){
            return false;
        }

        if(uniqueNumbers.contains(i)){ // found duplicate
            return false;
        } else {
            uniqueNumbers.add(i);
        }
    }

    return true;
}

private boolean isColumnValid(int[][] board, int column){
    Set<Integer> uniqueNumbers = new HashSet<>();

    for(int i=0; i<BOARD_DIMENSION; i++){
        int value = board[i][column];
        if(value<1 || value>9){
            return false;
        }

        if(uniqueNumbers.contains(value)){ // found duplicate
            return false;
        } else {
            uniqueNumbers.add(value);
        }
    }

    return true;
}

private boolean isRegionValid(int[][] board, int rowStartIndex, int rowEndIndex, int columnStartIndex, int columnEndIndex){
    Set<Integer> uniqueNumbers = new HashSet<>();

    for(int i=rowStartIndex; i <rowEndIndex; i++){
        for(int j=columnStartIndex; j<columnEndIndex; j++){
            int value = board[i][j];
            if(value<1 || value>9){
                return false;
            }

            if(uniqueNumbers.contains(value)){ // found duplicate
                return false;
            } else {
                uniqueNumbers.add(value);
            }
        }
    }

    return true;
}

Multiples of 3

  • Given an int array, write a function that prints out the indices where the value at that index is a mulitple of 3. So for example if the int [] a = { 1, 2, 3, 5, 7, 8, 11, 12, 14, 15, 17} , then the output should be all on one line (no newlines) : 2, 7, 9
private String multiplesOfThree(int[] a){
    String indices = "";
    for(int i=0; i<a.length; i++){
        if(a[i] % 3 == 0){
            if(i == a.length){
                indices += i+"";
            } else {
                indices += i+",";
            }
        }
    }

    return indices.substring(0, indices.length()-1);
}

Fibonacci series

  • The Fibonacci series is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc. Write a recursive function to compute the nth number in the fibonacci series.
int fibonacci(int n) {
    int[] memoizationArray = new int[n+1];
    Arrays.fill(memoizationArray, -1);
    return fibonacci(n, memoizationArray);
}

int fibonacci(int n, int[] a) {
    if (n <= 2) {
        return 1;
    } else if (a[n] != -1) {
        return a[n]; // Return cached result.
    } else {
        a[n] = fibonacci(n-1, a) + fibonacci(n-2, a); // Cache result
    }
    return a[n];
}

BigInt sum

  • Given two very long sequeces of digits, lets call these BigInts, write a function to calculate the sum of two BigInts. These sequences could be 1000 or more digits long. Think of the sequences as strings.
public String sum(String a, String b) {
    int d1, d2, tempSum;
    int carry = 0;

    int sumLength = (a.length()>b.length()) ? a.length() : b.length();
    StringBuilder sb = new StringBuilder(sumLength);

    int i=a.length()-1;
    int j=b.length()-1;

    while(i>=0 || j>=0){
        d1 = 0;
        d2 = 0;

        if(i>=0) {
            d1 = a.charAt(i) - '0';
            i--;
        }

        if(j>=0) {
            d2 = b.charAt(j) - '0';
            j--;
        }

        tempSum = d1+d2+carry;
        if(tempSum>9){
            carry = tempSum / 10;
            tempSum = tempSum % 10;
        } else {
            carry = 0;
        }

        sb.insert(0, tempSum);
    }

    return sb.toString();
}

LRU Cache

  • Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get() and set().
  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
public class LRUCache {

    // region Member Variables
    private int capacity;
    private Map<Integer, Node> data;
    private Node head;
    private Node tail;
    // endregion

    // region Constructors
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.data = new HashMap<>();
    }
    // endregion

    public int get(int key){

        // Existing key
        if(data.containsKey(key)){

            // Move to first
            Node node = data.get(key);
            moveFirst(node);

            return node.value;
        }

        // Not found
        return -1;
    }

    public void set(int key, int value){
        // Existing slot
        if(data.containsKey(key)){
            Node node = data.get(key);
            node.value = value;
            moveFirst(node);
            return;
        }

        // Out of capacity, cleaning the oldest slot
        if(data.size() >= capacity){
            int id = tail.key;
            removeLast();
            data.remove(id);
        }

        // New slot
        Node node = new Node(key, value);
        add(node);
        data.put(key, node);
    }
    
    private void add(Node node){
        // Reset position
        node.prev = null;
        node.next = null;

        // First element
        if(head == null){
            head = node;
            tail = node;
            return;
        }

        // Existing element
        head.prev = node;
        node.next = head;
        head = node;

    }

    private void remove(Node node){
        // Nothing to do
        if(node == null || head == null){
            return;
        }

        // The only one item
        if(head == tail && node == head){
            head = null;
            tail = null;
            return;
        }

        // Remove from head
        if(node == head){
            head.next.prev = null;
            head = head.next;
            return;
        }

        // Remove from end
        if(node == tail){
            tail.prev.next = null;
            tail = tail.prev;
            return;
        }

        // Remove in the middle
        node.prev.next = node.next;
        node.next.prev = node.prev;

    }

    // move a node to the head (for a cache hit)
    private void moveFirst(Node node){
        remove(node);
        add(node);
    }

    // remove the oldest item which is the tail
    private void removeLast(){
        remove(tail);
    }

    public void printContents(){
        if(head == null){
            System.out.println("LRUCache is empty");
            return;
        }

        Node currNode = head;

        String contents = "";
        while(currNode != null){
            contents += String.format("%s ", currNode.value);
            currNode = currNode.next;
        }

        System.out.println(String.format("LRUCache contents : %s", contents));
    }

    // region Inner Classes
    private class Node {
        Node prev;
        Node next;
        int key;
        int value;

        private Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // endregion
}

LinkedList Cycle

  • Detect if a linkedlist has a cycle.
boolean hasCycle(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Reverse Stack

  • Reverse the elements of a stack without using another data structure.
void reverseStack(Stack stack) {
    if (stack.isEmpty()) {
        return;
    } else {
        Object obj = stack.pop();
        reverseStack(stack);
        insert(stack, obj);
    }
}

void insert(Stack stack, Object obj){
    if (stack.isEmpty()) {
        stack.push(obj);
    } else {
        Object element = stack.pop();
        insert(stack, obj);
        stack.push(element);
    }
}

Valid Expression

  • Given a string ((0+4)+(1x3) ) Or ( { } ) { ] [ } Or { ( [ (1*3) +2 ] ) / a+ [12 ] } Or { ( a+b ) Output whether the expression is valid (that is, the brackets “match up”). No need to evaluate results. 1 and 3 are valid, 2 and 4 are not.
String a = "((0+4)+(1x3)  )";
String b = "( { } ) { ] [ }";
String c = "{ ( [ (1*3) +2 ] )  / a+ [12 ] }";
String d = "{ ( a+b )";
    
System.out.println(String.format("Exp a is %b", isValidExpression(a)));
System.out.println(String.format("Exp b is %b", isValidExpression(b)));
System.out.println(String.format("Exp c is %b", isValidExpression(c)));
System.out.println(String.format("Exp d is %b", isValidExpression(d)));

public static boolean isValidExpression(String exp){
    Stack<Character> bracesStack = new Stack<Character>();
    
    for(int i=0; i<exp.length(); i++){
      char c1 = exp.charAt(i);
      
      if(isOpeningChar(c1)){
        bracesStack.push(c1);
      } else if(isClosingChar(c1)) {
        char c2 = bracesStack.peek();
        if(isMatchingBrace(c2, c1))
          bracesStack.pop();
        else
          return false;
      } 
    }
    
    if(bracesStack.isEmpty())
      return true;
    
	return false;
}
  
private static boolean isOpeningChar(char c1){
	if(c1 == '(' || c1 == '[' || c1 == '{')
      return true;
    else
      return false;
}
  
private static boolean isClosingChar(char c1){
	if(c1 == ')' || c1 == ']' || c1 == '}')
      return true;
    else
      return false;
}
  
private static boolean isMatchingBrace(char c1, char c2){
	if(c1 == '(' && c2 == ')'){
		return true;  
    } else if(c1 == '{' && c2 == '}'){
      return true;
    } else if(c1 == '[' && c2 == ']'){
      return true;
    } 
    
	return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment