brightlightkim

A tree is actually a type of graph, but not all graphs are trees. Simply put, a tree is a connected graph without cycles. A graph is simply a collection of nodes with edges between (some of) them. Graphs can be either directed (like the following graph) or undirected. While directed edges are like a one way street, undirected edges are like a two way street The graph might consist of multiple is..

A trie is a funny data structure. It comes up a lot in interview questions, but algorithm textbooks don't spend much time on this data structure. 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. The * nodes(null nodes) are often used to indicate complete words. For example, the fact that there is a * node under MANY i..

Min Heap: A complete binary tree (that is filled other than the rightmost elements on the last level) where each node is smaller than its children. The root, therefore, is the minimum element in the tree. We have two key operations on a min-heap: insert and extract_min Insert When we insert into a min-heap, we always start by inserting the element at the bottom. We insert it at the rightmost spo..

In Order: visit the left branch, then the current node, and finally visit the right branch. When performed on a binary search tree, it visits the nodes in ascending order (hence the name "in-order") void inOrderTraversal(Node node) { if (node != null){ inOrderTraversal(node.left); visit(node); inOrderTraversal(node.right); } } Pre Order: visits the current node before its child nodes (hence the ..

A Tree is a recursive explanation. A tree is a data structure composed of nodes. Each tree has a root node. (Actually, this isn't strictly necessary in graph theory, but it's usually how we use trees in programming, and especially programming interviews) The root node has zero or more child nodes Each child node has zero or more child nodes, and so on. The tree cannot contain cycles. The nodes m..

Question: Three in One: Describe how you could use a single array to implement three stacks. My Thought Process: The first one is from the beginning. The middle one The last one is from the end. Problem: Stack will not have an equal size. Answer: Stack 1: [0, n/3] Stack 2: [n/3, 2n/3] Stack 3: [2n/3, n] Implementation: public class ThreeStackInOne { private int numberOfStacks = 3; private int st..

Stack (Last-In-First-Out) pop(): remove the top item from the stack push(item): add an item to the top of the stack peek(): return the top of the stack isEmpty(): Return true if and only if the stack is empty Stack Features: It does not offer constant-time access to the ith item. However, it does allow constant-time adds and removes, as it doesn't require shifting elements around. public class M..

2.2 Implement an algorithm to find the kth to last element of a singly linked list. public Node returnKthToLast(Node node, int k){ Node n = node; int i = 0; while (n.next != null){ if (i == k-1){ break; } i++; n = n.next; } return n; } This was so simple, but I found out that this algorithm is not what the potential interviewer is looking for. It's more like.. int printKthToLast(Node head, int k..

2.1 Write code to remove duplicates from an unsorted linked list. The first algorithm that came to my mind was storing data to Set and see if it shows an error when inserting a value to see if it exists. If it already exists then remove the node. Just checked the last Index. public Node deleteDuplicatedNodes(Node head){ Node n = head; Set set = new HashSet(); set.add(n.data); while(n.next != nul..

A Linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node in the linked list. A doubly linked list gives each node pointers to both the next node and the previous one. Unlike an array, a linked list does not provide constant-time access to a particular "index' within the list. This means that if you'd like to find the K'th e..