Data structures and algorithm questions are important part of any programming job interview, be it a Java interview, C++ interview or any other programming language. Since data structures is core programming concept, its mandatory for all programmers, to know basic data structures like stack, linked list, queue, array, tree and graph. Though tree and graph are on tough side, I still see programmers to get familiar will all these. Any list of programming job interview questions is incomplete without questions from data structures and algorithms. Similarly while going on questions from data structure you may get some programming exercise as well e.g. swapping numbers without temp variable .
Linked list and arrays are favorite topics in any data structure interview, questions like reversing linked list, traversing linked list or deleting nodes from linked list, which involves algorithm and data structures are quite common.
Similarly, finding duplicates in array, finding missing numbers, sorting arrays are very popular.
You can also expect questions from stack, queue, array, linked list, tree, graph and HashMap are most common in any data structure interview.
Ques 01 : How to find middle element of linked list in one pass?
Ques 02 : How to find if linked list has loop ?
Ans 02 : This question has bit of similarity with earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to same node. This will only happen if linked list has loop.
Ques 03 : How to find 3rd element from end in a linked list in one pass?
Ans 03 : This is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has moved upto 3rd element, than when first pointer reaches to the end of linked list, second pointer will be pointing to the 3rd element from last in a linked list.
Ques 04 : In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ?
Ans 04 : This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2) which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.
Ques 05 : What is difference between Stack and Queue data structure ?
Ans 05 : One of the classical datastrucutre interview question. I guess every one know, No? Any way main difference is that Stack is LIFO(Last In First Out) data structure while Queue is a FIFO(First In First Out) data structure.
Ques 06 : How do you find duplicates in array if there is more than one duplicate?
Ans 06 : Sometime this is asked as follow-up question of earlier datastrucutre interview question, related to finding duplicates in Array. One way of solving this problem is using a Hashtable or HashMap data structure. You can traverse through array, and store each number as key and number of occurrence as value. At the end of traversal you can find all duplicate numbers, for which occurrence is more than one. In Java if a number already exists in HashMap then calling get(index) will return number otherwise it return null. this property can be used to insert or update numbers in HashMap.
Ques 07 : What is difference between Singly Linked List and Doubly Linked List data structure?
Ans 07 : This is another classical interview question on data structure, mostly asked on telephonic rounds. Main difference between singly linked list and doubly linked list is ability to traverse. In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.
Ques 08 : Write Java program to check if a number is palindrome or not?
Ans 08 : division operator can be used to get rid of last digit e.g. 1234/10 will give you 123, and modulus operator can give you last digit e.g. 1234%10 will return 4.
Ques 09 : What is binary search tree?
Ans 09 : This is a data structure question from Tree data structures. Binary Search Tree has some special properties e.g. left nodes contains items whose value is less than root , right sub tree contains keys with higher node value than root, and there should not be any duplicates in the tree. Apart from definition, interview can ask you to implement binary search tree in Java and questions on tree traversal e.g. IN order, pre-order, and post order traversals are quite popular data structure question.
Ques 10 : Write a Java program to implement Stack in Java?
Ans 10: You can implement Stack by using array or linked list. This question expect you to implement standard method provided by stack data structure e.g. push() and pop(). Both push() and pop() should be happen at top of stack, which you need to keep track. It’s also good if you can implement utility methods like contains(), isEmpty() etc. By the way JDK has java.util.Stack class and you can check it’s code to get an idea.
Ques 11: Priority Queue ?
Ques 12: Sorting Algorithms ?
Ques 13: Complexity / Algorithms ?
Ques 14: "Transpose A Matrix", "Swap Number", "Reverse Number", "Print Alphabets", "Linear Search", "System Commands", "Prime Number", "Palindrome", "Largest Number", "Floyd Triangle", "Factorial", "Calculator", "Bubble Sort", "Binary Search", "Armstrong Number", "Add Matrix", "GCD (Greatest Common Divisor)", "Fibonacci", Reverse a linked list (recursive & iterative).
Linked list and arrays are favorite topics in any data structure interview, questions like reversing linked list, traversing linked list or deleting nodes from linked list, which involves algorithm and data structures are quite common.
Similarly, finding duplicates in array, finding missing numbers, sorting arrays are very popular.
You can also expect questions from stack, queue, array, linked list, tree, graph and HashMap are most common in any data structure interview.
Ques 01 : How to find middle element of linked list in one pass?
Ques 02 : How to find if linked list has loop ?
Ans 02 : This question has bit of similarity with earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to same node. This will only happen if linked list has loop.
Ques 03 : How to find 3rd element from end in a linked list in one pass?
Ans 03 : This is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has moved upto 3rd element, than when first pointer reaches to the end of linked list, second pointer will be pointing to the 3rd element from last in a linked list.
Ques 04 : In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ?
Ans 04 : This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2) which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.
Ques 05 : What is difference between Stack and Queue data structure ?
Ans 05 : One of the classical datastrucutre interview question. I guess every one know, No? Any way main difference is that Stack is LIFO(Last In First Out) data structure while Queue is a FIFO(First In First Out) data structure.
Ques 06 : How do you find duplicates in array if there is more than one duplicate?
Ans 06 : Sometime this is asked as follow-up question of earlier datastrucutre interview question, related to finding duplicates in Array. One way of solving this problem is using a Hashtable or HashMap data structure. You can traverse through array, and store each number as key and number of occurrence as value. At the end of traversal you can find all duplicate numbers, for which occurrence is more than one. In Java if a number already exists in HashMap then calling get(index) will return number otherwise it return null. this property can be used to insert or update numbers in HashMap.
Ques 07 : What is difference between Singly Linked List and Doubly Linked List data structure?
Ans 07 : This is another classical interview question on data structure, mostly asked on telephonic rounds. Main difference between singly linked list and doubly linked list is ability to traverse. In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.
Ques 08 : Write Java program to check if a number is palindrome or not?
Ans 08 : division operator can be used to get rid of last digit e.g. 1234/10 will give you 123, and modulus operator can give you last digit e.g. 1234%10 will return 4.
Ques 09 : What is binary search tree?
Ans 09 : This is a data structure question from Tree data structures. Binary Search Tree has some special properties e.g. left nodes contains items whose value is less than root , right sub tree contains keys with higher node value than root, and there should not be any duplicates in the tree. Apart from definition, interview can ask you to implement binary search tree in Java and questions on tree traversal e.g. IN order, pre-order, and post order traversals are quite popular data structure question.
Ques 10 : Write a Java program to implement Stack in Java?
Ans 10: You can implement Stack by using array or linked list. This question expect you to implement standard method provided by stack data structure e.g. push() and pop(). Both push() and pop() should be happen at top of stack, which you need to keep track. It’s also good if you can implement utility methods like contains(), isEmpty() etc. By the way JDK has java.util.Stack class and you can check it’s code to get an idea.
Ques 11: Priority Queue ?
Ques 12: Sorting Algorithms ?
Ques 13: Complexity / Algorithms ?
Ques 14: "Transpose A Matrix", "Swap Number", "Reverse Number", "Print Alphabets", "Linear Search", "System Commands", "Prime Number", "Palindrome", "Largest Number", "Floyd Triangle", "Factorial", "Calculator", "Bubble Sort", "Binary Search", "Armstrong Number", "Add Matrix", "GCD (Greatest Common Divisor)", "Fibonacci", Reverse a linked list (recursive & iterative).
No comments:
Post a Comment