Data structures and algorithm questions are an important part of any programming job interview, be it a Java interview, a C++ interview, or any other programming language. Since data structures are core programming concepts, it's mandatory for all programmers, to know basic data structures like the stack, linked list, queue, array, tree, and graph. Though trees and graphs are on the tougher side, I still see programmers 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.
The linked list and array are favorite topics in any data structure interview, questions like reversing a linked list, traversing a linked list, or deleting nodes from the linked list, which involves algorithm and data structures that are quite common.
Similarly, finding duplicates in an array, finding missing numbers, sorting arrays are very popular. You can also expect questions from the stack, queue, array, linked list, tree, graph, and hash table are most common in any data structure interview.
In this tutorial, we will see a couple of data structure questions answers from these topics. Let us know if you have any interesting questions from data structures and algorithms, which you faced during any Java interviews.
By the way, you also need some understanding of the basic data structure before solving these questions. There is no point in attempting these questions if you don't know how to access elements from an array or linked list or can't even code them using the programming language of your choice.
In such cases, it's better to revise fundamentals by joining a comprehensive online course like Data Structures and Algorithms: Deep Dive Using Java. This way you can get the best of both worlds, you will learn data structure and algorithms and also prepare for the interview.
Question 1: How to find the middle element of the linked list in one pass?
Question 2: How to find if a linked list has a loop?
Question 3: How to find the third element from the end in a linked list in one pass?
Question 4: In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?
Question 5: How to reverse String in Java?
Question 6: Write a Java program to sort an array using the Bubble Sort algorithm?
Question 7: What is the difference between Stack and Queue data structure?
Question 8: How do you find duplicates in an array if there is more than one duplicate? (solution)
Question 9: What is the difference between the Singly Linked List and Doubly Linked List data structure?
Question 10: Write a Java program to print the Fibonacci series?
Question 11: Write a Java program to check if a number is a palindrome or not? (solution)
Question 12: What is a binary search tree? (solution)
Question 13: How to reverse a linked list using recursion and iteration? (solution)
Question 14: Write a Java program to implement Stack in Java? (solution)
I also suggest looking at data structure and algorithm questions on Cracking the Coding Interview book, as this book contains some good questions with proper explanations. That will certainly help you to do better in programming job interviews.
One more suggestion I have to make is whenever you get some time, just read the Introduction to Algorithm by Thomas Cormen, if you have not read it already. This book is the bible of algorithms and IMHO every programmer should read this book.
The linked list and array are favorite topics in any data structure interview, questions like reversing a linked list, traversing a linked list, or deleting nodes from the linked list, which involves algorithm and data structures that are quite common.
Similarly, finding duplicates in an array, finding missing numbers, sorting arrays are very popular. You can also expect questions from the stack, queue, array, linked list, tree, graph, and hash table are most common in any data structure interview.
In this tutorial, we will see a couple of data structure questions answers from these topics. Let us know if you have any interesting questions from data structures and algorithms, which you faced during any Java interviews.
By the way, you also need some understanding of the basic data structure before solving these questions. There is no point in attempting these questions if you don't know how to access elements from an array or linked list or can't even code them using the programming language of your choice.
In such cases, it's better to revise fundamentals by joining a comprehensive online course like Data Structures and Algorithms: Deep Dive Using Java. This way you can get the best of both worlds, you will learn data structure and algorithms and also prepare for the interview.
15 Data Structures and Algorithm Interview Questions for Java Programmers
This is a combined list of questions from the various data structures e.g. array, linked list, stack, or queue. It includes some coding questions as well, which gel with data structures.
One of the most popular questions from data structures and algorithms is mostly asked in a telephonic interview. Since many programmers know that, in order to find the length of a linked list we need to first traverse through the linked list till we find the last node, which is pointing to null, and then in the second pass we can find a middle element by traversing only half of length.
They get confused when the interviewer asks him to do the same job in one pass i.e. without traversing the linked list again.
In order to find the middle element of the linked list in one pass, you need to maintain two-pointer, one increment at each node while the other increments after two nodes at a time, having this arrangement, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list. See this trick to find the middle element of the linked list in a single pass for more details.
They get confused when the interviewer asks him to do the same job in one pass i.e. without traversing the linked list again.
In order to find the middle element of the linked list in one pass, you need to maintain two-pointer, one increment at each node while the other increments after two nodes at a time, having this arrangement, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list. See this trick to find the middle element of the linked list in a single pass for more details.
This question has a bit of similarity with the 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 the other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node.
This will only happen if a linked list has a loop or cycle. You can check my article linked list with cycles for more details.
If we maintain two pointers, and we increment one pointer after processing two nodes and the other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node.
This will only happen if a linked list has a loop or cycle. You can check my article linked list with cycles for more details.
This is another frequently asked linked list interview question. This question is exactly similar to finding the middle element of a linked list in a single pass.
If we apply the same trick of maintaining two-pointers and increment another pointer, when first has moved up to the 3rd element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the 3rd element from last in a linked list.
Sometimes, interviewers can also generalize this problem and ask him to find the kth element from the tail, end, or last. Just use the same logic, replace 3 with k and you can solve the problem.
If you want to learn more about the linked list, you can also check out Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight.
If we apply the same trick of maintaining two-pointers and increment another pointer, when first has moved up to the 3rd element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the 3rd element from last in a linked list.
Sometimes, interviewers can also generalize this problem and ask him to find the kth element from the tail, end, or last. Just use the same logic, replace 3 with k and you can solve the problem.
If you want to learn more about the linked list, you can also check out Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight.
This is a rather simple data structure question, especially for this kind of. In this case, you can simply add all numbers stored in an array, and the total sum should be equal to n(n+1)/2. Now just subtract the actual sum to the 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 the performance of O(n^2) which is not good.
By the way, this trick will not work if an array has multiple duplicates, or it's not numbered forming an arithmetic progression. Here is an example of one way to find a duplicate number in the array.
Of course, there is a brute force way of checking each number against all other numbers, but that will result in the performance of O(n^2) which is not good.
By the way, this trick will not work if an array has multiple duplicates, or it's not numbered forming an arithmetic progression. Here is an example of one way to find a duplicate number in the array.
This is one of my favorite questions. Since String is one of the most important types of programming, you expect a lot of question-related to String in any data structure interview.
There are many ways to reverse String in Java or any other programming language, and the interviewer will force you to solve this problem by using without API i.e. without using the reverse() method of StringBuffer.
In the follow-up, he may ask to reverse String using recursion as well. See 3 ways to reverse String in Java to learn to reverse String using both loops and recursion in Java.
There are many ways to reverse String in Java or any other programming language, and the interviewer will force you to solve this problem by using without API i.e. without using the reverse() method of StringBuffer.
In the follow-up, he may ask to reverse String using recursion as well. See 3 ways to reverse String in Java to learn to reverse String using both loops and recursion in Java.
Question 6: Write a Java program to sort an array using the Bubble Sort algorithm?
I have always sent a couple of questions from searching and sorting in data structure interviews. Bubble sort is one of the simplest sorting algorithms but if you ask anyone to implement it on the spot it gives you an opportunity to gauge the programming skills of a candidate. See How to sort an array using Bubble Sort in Java for a complete solution to this data structure interview question.
One of the classical data structure interviews questions. I guess everyone knows, No? Anyway, the main difference is that Stack is LIFO (Last In First Out) data structure while Queue is a FIFO (First In First Out) data structure. You can further see my article stack vs queue in Java for more details.
Question 8: How do you find duplicates in an array if there is more than one duplicate? (solution)
Sometimes this is asked a follow-up question of earlier data structure interview questions, related to finding duplicates in Array. One way of solving this problem is by using a Hashtable or HashMap data structure.
You can traverse through the array, and store each number as a key and the number of occurrences as a 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 a number otherwise it returns null. this property can be used to insert or update numbers in HashMap.
You can traverse through the array, and store each number as a key and the number of occurrences as a 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 a number otherwise it returns null. this property can be used to insert or update numbers in HashMap.
This is another classical interview question on the data structure, mostly asked on telephonic rounds. The main difference between the singly linked list and the doubly linked list is the ability to traverse.
In a singly linked list, a node only points towards the next node, and there is no pointer to the previous node, which means you can not traverse back on a singly linked list.
On the other hand, the doubly linked list maintains two pointers, towards the next and previous node, which allows you to navigate in both directions in any linked list.
If you are preparing for interviews then I also suggest you learn some essential coding patterns like two points, fast and slow pointers, sliding window, and merge interval which can help you to solve many frequently asked coding problems.
If you need a course, I highly recommend Grokking the Coding Interview: Patterns for Coding Questions course on Educative. It's an interactive course where you can try out this pattern in the browser itself.
In a singly linked list, a node only points towards the next node, and there is no pointer to the previous node, which means you can not traverse back on a singly linked list.
On the other hand, the doubly linked list maintains two pointers, towards the next and previous node, which allows you to navigate in both directions in any linked list.
If you are preparing for interviews then I also suggest you learn some essential coding patterns like two points, fast and slow pointers, sliding window, and merge interval which can help you to solve many frequently asked coding problems.
If you need a course, I highly recommend Grokking the Coding Interview: Patterns for Coding Questions course on Educative. It's an interactive course where you can try out this pattern in the browser itself.
This is not a data structure question, but a programming one, which many times appear during data structure interview. Fibonacci series is a mathematical series, where each number is the sum of the previous two numbers e.g. 1,1, 2, 3, 5, 8, 13, 21.
An interviewer is often interested in two things, a function that returns an nth number in the Fibonacci series and solving this problem using recursion in Java.
Though it's an easy question, the recursion part often confuses beginners. See this link to find the nth Fibonacci number in Java.
An interviewer is often interested in two things, a function that returns an nth number in the Fibonacci series and solving this problem using recursion in Java.
Though it's an easy question, the recursion part often confuses beginners. See this link to find the nth Fibonacci number in Java.
This is similar to the previous question, not directly related to data structures, but quite popular along with other questions. A number is called palindrome if the reverse of the number is equal to the number itself.
An interviewer asks to solve this problem without taking help from Java API or any open source library. Anyway, it’s a simple question, you can use the division operator (/) and remainder operator (%) to solve this question.
Just remember, the division operator can be used to get rid of the last digit e.g. 1234/10 will give you 123, and the modulus operator can give you the last digit e.g. 1234%10 will return 4. By the way, here is a Java program to check if the number is palindrome or not.
An interviewer asks to solve this problem without taking help from Java API or any open source library. Anyway, it’s a simple question, you can use the division operator (/) and remainder operator (%) to solve this question.
Just remember, the division operator can be used to get rid of the last digit e.g. 1234/10 will give you 123, and the modulus operator can give you the last digit e.g. 1234%10 will return 4. By the way, here is a Java program to check if the number is palindrome or not.
This is a data structure question from Tree data structures. Binary Search Tree has some special properties like left nodes contain items whose value is less than root, right subtree contains keys with higher node value than root, and there should not be any duplicates in the tree.
Apart from the definition, an interview can ask you to implement a binary search tree in Java, and questions on tree traversal e.g. in order, preorder, and postorder traversals are quite popular data structure questions.
Apart from the definition, an interview can ask you to implement a binary search tree in Java, and questions on tree traversal e.g. in order, preorder, and postorder traversals are quite popular data structure questions.
Question 13: How to reverse a linked list using recursion and iteration? (solution)
This is another good question on data structures. There are many algorithms to reverse the linked list and you can search for them using google. I am thinking of writing another blog post to explain the linked list reversal and will share it with you later.
As one of my readers mentioned, I have already written about it and linked it into the solution link, you can check out my solution but I strongly suggest you try it yourself before looking at the solution.
As one of my readers mentioned, I have already written about it and linked it into the solution link, you can check out my solution but I strongly suggest you try it yourself before looking at the solution.
You can implement Stack by using an array or linked list. This question expects you to implement a standard method provided by stack data structure e.g. push() and pop(). Both push() and pop() should be happening at top of the stack, which you need to keep track of. It’s also good if you can implement utility methods like contains(), isEmpty() etc.
By the way, JDK has a java.util.Stack class and you can check its code to get an idea. You can also check the Effective Java book, where Josh Bloch has explains how an incorrect implementation of the stack can cause a memory leak in Java.
By the way, JDK has a java.util.Stack class and you can check its code to get an idea. You can also check the Effective Java book, where Josh Bloch has explains how an incorrect implementation of the stack can cause a memory leak in Java.
I also suggest looking at data structure and algorithm questions on Cracking the Coding Interview book, as this book contains some good questions with proper explanations. That will certainly help you to do better in programming job interviews.
One more suggestion I have to make is whenever you get some time, just read the Introduction to Algorithm by Thomas Cormen, if you have not read it already. This book is the bible of algorithms and IMHO every programmer should read this book.
That's all on this list of data structure interview questions and answers. This is one topic, which is always asked in any programming interview, doesn't matter if you are C, C++, or Java developer, basic knowledge of data structure like an array, linked list, stack, queue, the tree is must to clear any programming interview.
Other Data Structure and Algorithms Articles you may like
- Top 30 Array Coding Interview Questions with Answers (see here)
- How to find a missing number in an array? (answer)
- 10 Algorithms Books Every Programmer Should Read (books)
- How to compare two arrays in Java? (answer)
- 100+ Data Structure Coding Problems from Interviews (questions)
- How to reverse an array in place in Java? (solution)
- Top 15 Data Structure and Algorithm Interview Questions (see here)
- Top 20 String coding interview questions (see here)
- How to find all pairs whose sum is equal to a given number in Java (solution)
- Top 30 linked list coding interview questions (see here)
- Top 50 Java Programs from Coding Interviews (see here)
- 7 Best courses to learn Data Structure and Algorithms (courses)
- 50+ Data Structure and Algorithms Problems from Interviews (questions)
- How to remove duplicate elements from an array in Java? (solution)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)
Thanks a lot for reading this article so far. If you like these Data Structure and Algorithm Interview questions and answers then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.
P. S. - If you think that your data structure and algorithm skill are not par and you want to spend some time sharpening your skill then you can start with these free Algorithm courses.
41 comments :
Great post Javin! Really helpful.
I was recently asked following questions in interviews. I have found answers via Google search, but it would be great to know your comments on these questions.
1. Write your own HashMap/Hashtable implementation in Java
2. How to implement your own LinkedList (without using any Java API)
@Heisenberg, Thanks for sharing those questions, they are real good. You can implement HashMap by using Array, because only provide constant time access, if you know index. Key is to writing hash function to minimize collision. Similarly, you can implement linked list by creating some class e.g. Node, which holds data and keep track of next node. By the way, I will try to blog answers in more details.
Hi Javin, Gr8 artcile once again regarding second question ( How to find if linked list has loop ?), I want to add the following thing...
1) To determine if linked list has a loop or not..
You can detect it by simply running two pointers through the list. Start the first pointer A on the first node and the second pointer B on the second node.
Advance the first pointer by one every time through the loop, advance the second pointer by two. If there is a loop, they will eventually point to the same node. If there's no loop, you'll eventually hit the end with the advance-by-two pointer.
Consider the following loop:
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
^ |
| |
+------------------------+
Starting A at 1 and B at 2, they take on the following values:
A B
= =
1 2
2 4
3 6
4 8
5 4
6 6
Because they're equal, and B should always be beyond A (because it's advancing by two as opposed to the advance-by-one behaviour of A), it means you've discovered a loop.
The pseudo-code will go something like this:
def hasLoop (pointer nodeA):
# nodeA is first element
# Empty lest has no loops.
if nodeA == NULL: return false
# Set nodeB to second element.
nodeB = nodeA.next
# Until end of list with nodeB.
while nodeB != NULL:
# Advance nodeA by one, nodeB by two (with end-list check).
nodeA = nodeA.next
if nodeB.next == NULL: return false
nodeB = nodeB.next.next
# If same, we have a loop.
if nodeA == nodeB: return true
endwhile
# Exited without loop maens no loop.
return false
enddef
2) The second query is to the point at which loop started...
Once you know a node within the loop, finding the first node is easy.
Leave one pointer A on that node and advance the other B by one. Then use a third node C, initially set to the head.
Then you just advance B continuously. If you find it equal to C, then C is the start of your loop. On the other hand, if B ends up wrapping around to A again, then C is before your loop.
In that case, advance C and B by one and keep going. Eventually, C will enter the loop and be met by B, at which point you're done.
(C goes this way).
C ->> A (this is where A and B
| | first met).
v v
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
^ |
| |
+------------------------+
(B runs through this loop, every time
it reaches A, you advance C; when it
reaches C, that's your first loop node).
Javin Regarding Q3 (How to find 3rd element from end in a linked list in one pass)
One approach could be in terms of pseudo ode could also be
The first node in you list I am assuming is called head.
So set a pointer to head, we'll call it current
Node current = head;
Then make another pointer that points three positions ahead
Node threeAhead = head.next.next.next;
Then write a loop that first checks to see if threeAhead.next is null, if it is not:
threeAhead = threeAhead.next;
curr = curr.next;
When threeAhead.next becomes null, you are three positions from the end with current.
so finally if you know what the length of the list is before you start,
node = first;
for (i = 0; i < length - N_FROM_END; i++) {
node = node.next;
}
result = node.value
In java ..java.util.LinkedList: linkedList.get(linkedList.size() - 3)
but if you don't now the length..
nodes = new Node[N_FROM_END];
node = first;
for (i = 0; node != null; i++) {
nodes[i % N_FROM_END] = node;
node = node.next;
}
result = nodes[i % N_FROM_END].value
or something like that. (Check the boundary conditions ... and account for the list length being less than N_FROM_END.)
@Saral Saxena, Great comment and thanks for your pseudo code, I see it helps. I will try to cover question of detecting linked list with loop, may be another post. Once again, thanks for adding value.
Javin
@Javin and Saral, can u guys please have a look if below method is correct for Queation 2 (loop detection in linkedlist)
public static void isListInLoop(LinkedList.Node head, Node tail) {
LinkedList.Node nodeA = head.next();
LinkedList.Node nodeB = head.next().next();
int counter = 0;
while(nodeB.next() != null) {
if( nodeA.equals(nodeB) )
break;
nodeB = nodeB.next();
}
System.out.println("Loop detected...");
}
For Question 3 another solution could be (with java.util.LinkedList),
public static void get3rdElementFromEnd () {
java.util.LinkedList ll = new java.util.LinkedList();
ll.add("A");
ll.add("B");
ll.add("C");
ll.add("D");
ll.add("E");
ll.add("F");
ll.add("G");
int threeAhead=0, threeBack=0;
System.out.println("ll.size = "+ll.size());
if(ll.size() > 3) {
for(String s : ll) {
threeAhead++;
if(threeAhead > 3 )
threeBack++;
}
int i = threeAhead - threeBack;
System.out.println("-- i = "+i);
if( i == 3 ) {
System.out.println("Third Element From End = "+ll.get(threeBack));
}
}
}
Please comment if this solution is not perfect at any point.
Hi guys, recently in an interview I was asked how would you reverse a linked list? I answered that I would have a new list, iterate the original linked list and add elements of this list at head of new list. Interviewer was not convinced with my answer. Anyway I thought of writing a program to prove this...here is complete program.
package example.datastructure;
public class LinkedlistExample {
public static void main(String[] args) {
Node head = new Node();
for (int i =3;i<=10;i++)
{
insertAtTail(head, new Node(""+i, null));
}
for (int i =2;i>0;i--)
{
insertAtHead(head, new Node(""+i, null));
}
traverseList(head);
reverseList(head);
traverseList(head);
deleteNode(head, "10");
traverseList(head);
}
/*
* Add element at tail of list.
* */
static void insertAtTail(Node head, Node node)
{
if (head.next == null)
{
head.next=node;
System.out.println("Linked list is empty insertAtLast");
return;
}
Node lastNode = head.next;
while(lastNode.next!=null)
{ lastNode=lastNode.next;
}
lastNode.next=node;
}
/*
* delete a node matching data.
* */
static void deleteNode(Node head, String data)
{
if (head.next == null)
{
System.out.println("Linked list is empty in deleteNode");
return;
}
Node lastNode = head.next;
Node previousNode = head;
while(lastNode!=null)
{
if(lastNode.data.equals(data))
{
break;
}
previousNode = lastNode;
lastNode=lastNode.next;
}
previousNode.next=lastNode.next;
}
/*
* Add element at head of list
* */
static void insertAtHead(Node head, Node node)
{
if (head.next == null)
{
head.next=node;
System.out.println("Linked list is empty insertAtHead");
return;
}
node.next=head.next;
head.next=node;
}
static void traverseList(Node head)
{
Node lastNode = head.next;
if (head.next == null)
{
System.out.println("Linked list is empty in traverseList");
}
System.out.print("Data: ");
while(lastNode!=null)
{
System.out.print(" " + lastNode.data);
lastNode=lastNode.next;
}
System.out.println();
}
/*
* Reverse a linked list.
* */
static void reverseList(Node head) {
if (head.next == null)
{
System.out.println("Linked list is empty in reverseList");
}
/*
* Create a linked list by adding elements of original list at head of new list.
* */
Node newHead = new Node();
Node lastNode = head.next;
Node tempNode;
while(lastNode!=null)
{
tempNode = lastNode;
lastNode=lastNode.next;
tempNode.next=newHead.next;
newHead.next=tempNode;
}
head.next = newHead.next;
}
}
class Node
{
String data;
Node next;
Node()
{}
Node(String data, Node next)
{
this.data=data;
this.next= next;
}
}
Output:
Linked list is empty insertAtLast
Data: 1 2 3 4 5 6 7 8 9 10
Data: 10 9 8 7 6 5 4 3 2 1
Data: 9 8 7 6 5 4 3 2 1
Please suggest if anything wrong in this code.
Thanks,
Prashant
Some more codes..1) Find middle element 2) find nth element 3) Find and remove loop in list
package example.datastructure;
public class LinkedlistExample {
public static void main(String[] args) {
Node head = new Node();
for (int i =3;i<=10;i++)
{
insertAtTail(head, new Node(""+i, null));
}
for (int i =2;i>0;i--)
{
insertAtHead(head, new Node(""+i, null));
}
findMiddleElement(head);
findNthElementfromlast(head,4);
// Create , detect and remove loop from list
head = new Node();
createListHavingLoop(head);
findAndRemoveLoopNode(head);
traverseList(head);
}
static void removeLoopNode(Node loopNode, Node head)
{
Node node1 = head;
Node node2 = null;
while (true)
{
node2 = loopNode;
while (node2.next != loopNode && node2.next != node1)
{
node2 = node2.next;
}
if (node2.next == node1)
{
break;
}
else
{
node1= node1.next;
}
}
node2.next=null;
}
static void findAndRemoveLoopNode(Node head)
{
if (head.next == null)
{ System.out.println("Linked list is empty findLoopNode");
return;
}
Node currentNode = head.next;
Node startNode=head;
Node lastNode=head.next.next;
while(lastNode!=null)
{
currentNode = currentNode.next;
if (lastNode.next != null)
{
lastNode = lastNode.next.next;
}
if(lastNode == currentNode)
{
startNode = startNode.next;
System.out.println("Loop Node is :" + currentNode.data);
removeLoopNode(currentNode, head);
return;
}
}
System.out.println("Loop node does not exist");
}
static void createListHavingLoop(Node head)
{
Node node1= new Node("1", null);
Node node2= new Node("2", null);
Node node3= new Node("3", null);
Node node4= new Node("4", null);
Node node5= new Node("5", null);
Node node6= new Node("6", null);
Node node7= new Node("7", null);
Node node8= new Node("8", null);
Node node9= new Node("9", null);
Node node10= new Node("10", node4);
insertAtTail(head, node1);
insertAtTail(head, node2);
insertAtTail(head, node3);
insertAtTail(head, node4);
insertAtTail(head, node5);
insertAtTail(head, node6);
insertAtTail(head, node7);
insertAtTail(head, node8);
insertAtTail(head, node9);
insertAtTail(head, node10);
}
static void findNthElementfromlast(Node head, int nthFromLast)
{
if (head.next == null)
{ System.out.println("Linked list is empty findNthElementfromlast");
return;
}
Node currentNode = head.next;
Node tempNode=head;
Node lastNode = null;
for (int i=1; i<=nthFromLast;i++)
{
tempNode = tempNode.next;
}
lastNode=tempNode;
while(lastNode.next!=null)
{
if (lastNode.next != null)
{ lastNode = lastNode.next;}
currentNode = currentNode.next;
}
System.out.println(nthFromLast + " element from last is : " + currentNode.data);
}
static void findMiddleElement(Node head)
{
if (head.next == null)
{ System.out.println("Linked list is empty findMiddleElement");
return;
}
int length = 0;
Node middleNode = head;
Node lastNode= head.next;
while(lastNode!=null)
{
length++;
if(length % 2 == 0)
{
middleNode = middleNode.next;
}
lastNode = lastNode.next;
}
if (length %2 ==1)
{
middleNode = middleNode.next;
}
System.out.println("Middle element is : " + middleNode.data);
}
}
Thanks,
Prashant
We can have one more way to solve the first question :: using queue.
We can maintain a queue and insert the element as we encounter in the linked list. While we are inserting elements, we need to make sure that queue represent the middle element at the beginning. We can do this as follows ::
Inserting 3 elements out of n at first allows us to appreciate that it will be the second element which will be middle element(atleast because we have considered only 3 elements while inserting into queue). Now we will remove the first element (as queue structure)inserting next two elements. Now we have 5 elements and for sure we know we can make out the middle element will be at greater position than previously encountered one. So that's it. We will proceed with this till the end of list. By this we do not have to spend extra overhead maintaining pointers.
For the question on identifying the duplicate in the array containing numbers 1 to 100, the difference in actual and expected sums may not give you the duplicate.
For instance, if I have an array containing three elements in the range 1-3, with 2 being the duplicate, i.e., the array is 1, 2 and 2, then the actual sum is 5 and the expected sum is 6. The difference is 1, which isn't the duplicate element.
You could use a hashmap, with the numbers 1-100 as keys and their count as values. When a key is updated twice, then that is the duplicate element. Thus, the problem of locating a duplicate element can be solved in O(n) time, but may take O(n) space.
In one of interview with Credit Suisse, I was asked to that which data structure will you use to represent and OrderBook in financial market? I wasn't sure, but I replied that Binary tree will be better choice because Orders are always sorted on time, in a particular price bracket for a particular instrument. Can any one please advise on below question, Though I think I tried in hard, still want to know expert opinions.
Can you also suggest Which data structure is suitable for parking lot, imagine you have millions of parking lots?
@Vishnu, I think binary tree is right choice to implement a LIMIT order book, where order can match either to exact price or better price, which is lower than specified for buy orders and higher than specified for sell orders. For that reason, you need to navigate to tree, whose node should be price, but they should also contain Queue of Orders to maintain time priority. In short, your Orderbook should look like:
class OrderBook{
private Map<Instrument, Tree<Node(Price, Queue<Orders>>> book;
}
In one interview i was asked to write a function to print below. input to the function is 3.
*
* * *
* * * *
Which data-structure should I use to detect deadlock between threads? This was asked as write a routine to detect deadlock from a pool of threads to me in a Java interview.
Given a string S, and a list of strings of positive length, F1,R1,F2,R2,...,FN,RN, proceed to find in order the occurrences (left-to-right) of Fi in S and replace them with Ri. All strings are over alphabet { 0, 1 }. Searching should consider only contiguous pieces of S that have not been subject to replacements on prior iterations. An iteration of the algorithm should not write over any previous replacement by the algorithm.
Input sample:
Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will contain a string, then a semicolon and then a list of comma separated strings.eg.
10011011001;0110,1001,1001,0,10,11
Output sample:
For each line of input, print out the string after substitutions have been made.eg.
11100110
For the curious, here are the transitions for the above example: 10011011001 => 10100111001 [replacing 0110 with 1001] => 10100110 [replacing 1001 with 0] => 11100110 [replacing 10 with 11] => 11100110
HI gyuz, I want to check the two strings are matching 70% or not. Can anyone help me out?
can you help me:
Consider the file named cars.txt, each line in the file contains information about a
car (Year, Company, Manufacture, ModelName, Type ).
1) Read the file.
2) Add each car which is represented using one line of the file to a singular link
list. Use an object of the following class.
Class node
{
int year;
stringCompany;
stringManufacture;
stringModelName;
stringType;
Char Owner;
node next;
}
3) After creating your list do the following:
a. Print how many cars owned by the person (B)?
b. Print how many cars are on the file (you need to count the link list
nodes)?
c. Print everything about all the cars that have been manufactured on
2012 on a new file called 2012Cars.
d. Print all companies’ names on a new file called company. Note do
not repeat the company name.
e. Print all the cars that has been Manufactured by Toyota in a new file
called Toyota. Note, we need to print only the ModleName.
f. Delete the first car in the list that manufactured by Honda and print
the file again. Name the file Honda.
g. Delete the last car in the list. Print the result in a new file called
CarLast. h. Print the Manufacture and the modelName of all trucks in the list
Print the result in a new file called Trucks.
ans of q4 is not correct.
ans would be
int[] o = {1,2,3,4,5,6,2,8,9,10};
int[] n = new int[o.length+1];
for(int i= 0; i < o.length; i++){
n[o[i]]++;
}
for(int i= 0; i < o.length; i++){
System.out.println("no of "+ o[i] + " is "+ n[o[i]]);
}
For Question number nine if we just have to find the Duplicate values and not their occurance below code is sufficient:
import java.util.HashSet;
import java.util.Set;
public class DuplicateFinder
{
public Set getDuplicateValues(T[] arr)
{
Set duplictes = new HashSet();
Set hashSet = new HashSet(arr.length);
for(int i=0; i< arr.length; i++) {
if(!hashSet.add(arr[i])) {
duplictes.add(arr[i]);
}
}
return duplictes;
}
/**
* @param args
*/
public static void main(String[] args) {
DuplicateFinder duplicateStringFinder = new DuplicateFinder();
Set duplicateStrings = duplicateStringFinder.getDuplicateValues(new String[]{"a", "b", "c", "d","d","a"});
System.out.println("Duplicate strings are:" + duplicateStrings.toString());
DuplicateFinder duplicateIntFinder = new DuplicateFinder();
Set duplicateIntegers = duplicateIntFinder.getDuplicateValues(new Integer[]{1,2,3,4,1,4,5,5,5});
System.out.println("Duplicate integers are:" + duplicateIntegers.toString());
}
}
Regarding Q-2
we can do it by storing the next pointer values of each node , if any duplicate comes then it's a loop.
or
we can also do with two pointers in O(n). simply say one slow pointer and one fast pointer. slow pointer will increase one time where as fast pointer will increase twice. so if we get fastpointer==slowpointer then there is loop , and if fastpointer==null then no loop that's it.
Write a routine X in Java that takes an integer n and returns sum of 1+2+.. +n and square of number n
If n = 5, sum = 15 and square is 25.
Write routine X in Java
can any one,please give me the soloution
can any one help me
Write code in Java that prints:
For n = 5
*****
****
***
**
*
You are given this routine
private static void printNstars(int n) {
for (int i = 0; i < n; ++i) {
System.out.print("*") ;
}
System.out.println() ;
}
YOU NEED to write the routine below, which prints the above figure.
YOU CANNOT USE ANY LOOP STATEMENTS like while, do, for etc
Whenever looping is blocked, the next resort is recursive and vice versa
void printstararray(int N)
{
if (n == 0) return;
printNstars(N);
printstararray(N-1);
}
Thanks a lot for all the blogs. It helped me get a job at major investment bank.
I was asked this question at Deutsche bank.
If you were given all the prices of a stock for a given day in an array of double, you need to find the best buy and sell price.
You can only buy stock first and then sell it after that (short-selling is not allowed).
The hint is to find the buy and sell prices that give you maximum profit.
I've a solution that is O(n^2) .
public static void bestBuyandSellIndexes(Double[] prices) {
if (prices == null || prices.length < 2)
throw new IllegalArgumentException("No of prices less than 2.");
double profit = 0;
int buyIndex = -1, sellIndex=-1;
for (int i=0; i < prices.length - 1; i++) {
for (int j=i+1; j< prices.length; j++) {
if (prices[j] - prices[i] > profit) {
profit = prices[j] - prices[i];
buyIndex = i;
sellIndex = j;
}
}
}
if (profit > 0) {
System.out.println(String.format("The best profit %f can be obtained by buying at %f(%d)th index and selling at %f(%d)th index.", profit, prices[buyIndex], buyIndex, prices[sellIndex], sellIndex));
}
else {
System.out.println("No scenario found to get non-zero profit.");
}
}
@Taurun
Once again(parser kills my code)
Here is O(n) solution:
http://pastebin.com/Ez7QQRfH
anybody help
visual c++
define structuer employee with name,salary,employmantday then define array of 4 employees then print name of the employee with highst salary and names of all employees who works more than 10 years
Your solution for finding the 3rd node from the end of the list while may work is not a solution that will get a pass in an interview. Using two pointers shows a fundamental lack of understanding of how to properly traverse lists.
There's two ways I would accept as 'correct'. One using a loop and a pointer. Or the even better way of using recursion. Both of them would employ using p.next.next==null; Recursively I'd do it like this.
public ListNode findThird(ListNode n) { (this.next.next==null)?this:findThird(this.next);}
One line solutions make you look like the man in interviews. :)
Some more algorithm interview questions for true coders :
- write code to implement radix sort
- write code for two pivot quicksort algorithm
this code never print its an infinite while loop u made
sorry for it I didn't see break
hi did u dind the answer for this question? Could u pls share it
Thanks
For Java Developers, I would say to prepare well for DS and Algo, you can check some sample Data structure questions here, once you are good at that, just prepare some basic Java questions for telephonic round. Once you are done that you are ready, but if you want more confidence, you should check this Mega list of Java questions, which contains core Java questions including multi-threading, exception handling, collections, GC, design pattern and OOP questions from last 5 years of Java interviews.
sir, if I open the applications on my desktop one after another immediatly,then on which data structure the applications stored?
Can you please provide the code for you own hashtable implementation with you own hashcode function
This cheat sheet is a good resource, backed up by a github repo - https://www.amazon.com/dp/0692907815
Thanks for the article!
Could you add link to question 14 - you've already writem the post with the answer
https://javarevisited.blogspot.com/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html
Thanks MARica, I have added it.
Basing on the following contents, please implement specified functions of Array List.
Given:
------------------------------------------
#include
#define ElementType int
#define MAXSIZE 10
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
int Last;
};
--------------------------------------------------
You need to implement the following key functions of Array List (write down your code here, the necessary code annotations are needed):
List CreateArrayList(); // To create an empty array list
int Find(ElementType X, List PtrL); // Finding out an index of an element
void Insert(ElementType X, int i, List PtrL); // Inserting a new element
void Delete(int i, List PtrL); // Delete a specified element
void Update(ElementType X, int i, List PtrL); // Update a specified element
Post a Comment