You must know a programming language of your choice really well. Being fluent in the language of your choice will give you more time to think about the actual problem rather than thinking about 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 time, the interviewer will ask you for the run time of your program, meaning the big O complexity, which 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 linked list may be double linked, which means that each node has a pointer to the previous node as well.
You can insert a new node in a linked list in O(1) time. To look up 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.
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 node’s 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 - pre-order, in-order, and post-order.
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.
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 you 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<String> stack = new Stack<String>();
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 you to create a modified queue data structure. To use a queue of Strings in Java:
Queue<String> queue = new LinkedList<String>();
Graphs
A set of nodes that are connected by links. Can be represented using an adjacency matrix or an adjacency list. 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
It's 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 don’t 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.
Bitwise
Binary operations using bitwise operators might be asked from time to time especially in companies specializing in lower level software.
Program memory
The difference between the stack and the heap memory areas and when each one is used.
FINALLY
A lot of practice with interview-like questions.
A good way to prepare (Training set):
Cracking the Coding Interview: 150 Programming Questions and Solutions
A good way to test your preparation (Test set):
Coding Interview Ninja: 50 coding questions with Java solutions to practice for your coding interview
Now coming for the main question
The topics
1.trees
2.dynamic programming
3.operating systems
4.mathmatical algorithm
And the sources for the same
1. GeeksforGeeks - A computer science portal for geeks
2. CrazyForCode | A Guide to nail the technical interview
3. Programming Interview Questions | CareerCup
Comments
Post a Comment