# Interview Questions

Please find the complete list of programming, theoretical and behavior interview questions faced while looking for an internship in few of the big companies.

Few Points:

1. Setup a meeting room or quiet place so that you can concentrate on your interview and obviously place where you have good cell phone reception
2. Think aloud when giving phone interviews
3. Make sure you do everything on the scratch pad, online editor or whatever tool you are using for online coding
4. If you know better/worse or any approaches to the problem, make sure you let your interviewer know about it
5. Time and Space Complexities of Algorithm: You should be able to answer time/space complexities of very common sorting/searching algorithm and should also be able to answer for your algorithm.

Programming Interview Questions:

Difficulty Level: Easy

1. Linked List Reversal: Reverse a linked list iteratively and NOT by recursion. Linked List Reversal is one of the toughest simple question that you might face in almost every other interview. You should always practice it in both the ways recursively and iteratively considering every “boundary conditions”.
2. Insert Node in Binary Search Tree (BST): Make sure you explain the properties of BST to the interviewer before you start coding on the scratch pad. Interviewer can ask you to do it both the ways, recursively and iteratively.
3. Remove duplicates from an unsorted array: This seems to be a very easy question where you would simply sort the array and then use the sorted array property to remove the duplicates but only thing to keep in mind is what interviewer is looking for – for e.g time complexity or space complexity. This question may further lead to sort related questions.
4. Remove duplicates from a sorted array: Make sure you use the sorted array properties and don’t end up using hash maps and increasing space complexity.
5. How to remove all instances of a character in a big string: Given a long text string T = ASLHFLFHASHSDAHSDASDHLK and a character ch = ‘A’ the result should be a string without character A i.e. Result = SLHFLFHSHSDHSDSDHLK.
6. Counting numbers in an array: Given an array A[] = {1,2,2,3,4,4,5,2,5} the output should be (1,1), (2,3), (3,1), (4,2), (5,2). You can make use of hash maps or other approaches as long as they are in best interest of interviewers and gives you the correct answer.

Difficulty Level: Medium

1. Trim Binary Search Tree: Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree.
2. Counting Array Numbers and Arranging in descending order of count – Given an array A[] = {1,2,1,7,4,5,4,3,1,4,4,2} the output should be {(4,4), (1, 3), (2,2), (7,1), (5,1), (3,1)}. The catch here is to write counts in descending order and if the count is 1 then you should maintain the order of the array. In the above example since 7 comes before 5 in the array the count of 7 is written before 5 in the output set.
3. How well do you know 32-bit to 64-bit encoding: This is a tricky question because it might involve bit manipulation and can mess up things in the interview if not done correctly. Make sure you understand everything about big endian and little endian and how the data storage is done in 32-bit and 64-bit architectures. You should also try writing code for 64-bit to 32-bit architecture. Practicing Bit operators would be a good idea as they often confuse you in the interview by asking questions.
4. Finding frequency of element in a sorted string: This is a good question which will test your binary search skills and how you can effectively mold it to make an algorithm of time complexity: O(logn) and O(1) space.

Difficulty Level: Hard

1. Fun with Strings: Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example: S = `"ADOBECODEBANC" and T = "ABC" Minimum window is "BANC".`
2. Unix Process Creation: Implement data structure that can works as Unix processes where one process can spawn multiple child process where each child process can create more child processes. Implement method to add process, delete a process, print siblings information and print grand parents information.
3. Longest Palindromic Substring: This is a good dynamic programming question and interviewers look for candidates thinking capability rather than a perfect solution.

Computer Science Theoretical Questions:

• Difference between C and C++? Advantages/Disadvantages of C over C++ and some more follow ups on C.
• What are SET data structures, where can we use them? Any programming example?
• What is difference between Threads and Processes? Follow up: Producer Consumer Problem, Synchronization Primitives, locking, semaphores and deadlocks
• How can you prevent deadlock and given an example where you can induce deadlock situation? Minimum number of locks required to induce deadlock in three threads?
• Can you implement your own synchronization primitives (Think of TestandSet Locks, etc. CS537 Intro to OS concepts)
• How COW (Copy On Write) File Systems work? How are they different from Journaling? Follow up: Write Buffering?

Good Source of Information on Interview Questions:

1. geeksforgeeks – they have plethora of questions and just don’t go by their solutions. Solutions in comment make a lot of sense sometime.
2. I really liked this website: http://www.ardendertat.com/2012/01/09/programming-interview-questions/. It has good collection of questions along with their solutions.
3. Cracking the Coding Interview Book is a very good book and everyone should at least do it once.
4. Leetcode Algorithms – Very good collection of algorithms with an online editor/compiler and gives you a good experience of online coding challenges and discussion section is just awesome as it provides more insight to the problem.