Ekim Ouye - Coding Interview Ninja: 50 coding questions with Java solutions to practice for your coding interview.

Below is a list of the most important topics, in my opinion, that you need to look into. This list is by no means a complete one. Programming Language You must know really well a programming language of your choice. Being fluent in the language of your choice will give you more time to think about the actual problem rather than thinking how to implement the solution that you have in your mind. The most popular languages among the tech companies are Java, C/C++ and Python. Running time complexity Most of the times, the interviewer will ask you the running time of your program meaning the big O complexity, that is the worst-case analysis of the running time.

In some cases, such as when dealing with popular algorithms that have a bad big O analysis (eg. quicksort), it is useful to know the average running time as well. Data structures Linked Lists Each node in a linked list has a data element and a pointer to the next node. A sample definition of a linked list node is: class LLNode { int data ; LLNode next ; LLNode( int data) { this . data = data; } } A linked list may be double linked, which means that each node has a pointer to the previous node as well. data = data; } } You can insert a new node in a linked list in O(1) time. data = data; } } You can insert a new node in a linked list in O(1) time.

To look up for an element in a linked list you need O(n) time. Trees Each node in a tree has a data element and a list of pointers to its children. The most popular form of trees are the binary trees which have only two children. A sample definition, that is used throughout all the practice questions that follow, is: class TNode { int data ; TNode left , right ; TNode( int data) { this . data = data; } } In some cases the tree nodes could have a pointer to their father-node. A popular specialization of a binary tree is the Binary Search Tree (BST) where each nodes element must be greater than every element in its left subtree and less than every element in its right subtree.

The process of visiting each node in a tree is called tree traversal. There are three basic ways to explore a tree in a depth-first order. The following sample code prints a tree with the three basic traversals: public static void preOrder(TNode root) { if (root == null ) { return ; }; System.out.println(root.data); preOrder(root.left); preOrder(root.right); } public static void inOrder(TNode root) { if (root == null ) { return ; }; inOrder(root. left ); System. out .println(root. right ); } public static void postOrder(TNode root) { if (root == null ) { return ; }; postOrder(root. left ); postOrder(root. right ); System. out .println(root. data ); } Hash Tables A hash map is used to associate a key with a value. data ); } Hash Tables A hash map is used to associate a key with a value.

The advantage of this data structure is that theoretically each operation (insertion, removal, look-up) requires on average O(1) time. To insert a new element into the hash map, you compute the hash code of the key. If the hash code that was computed already exist in the structure, then a collision resolution technique is used. The two most popular resolution techniques are: Separate Chaining: Each bucket is independent and some sort of dynamic list is used for every hash code index. Open Addressing: The buckets are examined until an unoccupied bucket is found. To create a new hash map data structure with String key and values in Java: HashMap hm = new HashMap(); This is maybe the most popular data structure among interviewers! Stacks A Last-In-First-Out data structure.

It would be useful to know how to implement a stack from scratch using arrays since an interviewer could ask to create a modified stack data structure with special functionality. For all the other cases that you might need to use a stack, you can use the built-in implementation of your language. To use a stack of Strings in Java: Stack stack = new Stack(); Queues A First-In-First-Out data structure. It would be useful to know how to implement a queue from scratch using arrays since an interviewer could ask to create a modified queue data structure. To use a queue of Strings in Java: Queue queue = new LinkedList(); Graphs A set of nodes that are connected by links. Can be represented using an adjacency matrix or an adjacency list.

The graph theory can be asked by interviewers since it is used extensively in many popular algorithms. Tries A tree data structure that usually holds characters and has many applications in string manipulation algorithms. Usually, 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 popular application of this data structure is the look up in a dictionary of words (such as a simple auto-complete functionality in a text box). Algorithms Its really rare for an interviewer to ask you to implement a specific complicated and long algorithm (such as Dijkstra, A*, etc). However, you should have an idea how these work, what they are used for and to be able to conduct a basic conversation when the subject is involving a well-known algorithm.

Also, it is recommended to know what and how Dynamic Programming works and to be able to recognize it. The following are popular simpler algorithms that is suggested to know how to implement in case the interviewer asks you to implement a modification of the algorithm: Breadth-first search (DFS) Depth-first search (BFS) Mergesort Quicksort Binary Search OTHER These are techniques or concepts that an interviewer might ask you, even only theoretically. Recursion A powerful technique that is used to solve computer science problems and asked frequently in interviews. Some times makes the solution of a problem simpler and produces compact code. Remember that this technique requires more memory than an iterative solution. Also, when writing a recursive solution dont forget the terminating condition of the recursion.

Object Oriented Design Interviewers might ask you to describe the basic objects for a given system. Therefore, knowing the fundamentals of object oriented principles is crucial. Testing Interviewers might ask you to test your own solution. You need to know how to create test cases that cover even the edge cases (that is having input something unexpected). Also, knowing the basic principles of Unit Testing and mentioning it would be really recommended. System Programming Concepts such as threading, locks and mutex might be asked, especially if the company has a theoretical part in their interview.