Interview Questions and Answers for 'Algor' | Search Interview Question

Interview Questions and Answers - Order By Rating

Q31. Given the list of adjacent nodes, What will be the Depth First path

1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5

Algorithm

Ans. 1 -> 2 -> 4 -> 3 -> 5 -> 6

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve depth first traversal graph traversal}

Q32. Given the list of adjacent nodes, What will be the Breadth First path

1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5

Algorithm

Ans. 1 -> 2 -> 3 -> 6 -> 4 - > 5

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve breadth first traversal graph traversal}

Q33. What is the difference between Graph's Breadth first and Depth First algorithm ?

Algorithm

Ans. In Breadth first algorithm, all the adjacent nodes of the starting node is visited first and then the same rule is followed while moving inwards whereas

In Depth first algorithm, all the nodes of a single traversal path are visited first till a cycle or an end is found.

For example , given the following entries of adjacent nodes

1,2
1,3
1,6
2,4
2,5
3,6

The Breadth first path would be

1,2,3,6,4,5

and Depth first path would be

1,2,4,5,3,6

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal breadth first vs depth first frequent}

Q34. How do we implement a weight round robin algorithm in load balancing ?

Algorithm

^{This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve load balancing load balancer}

Q35. How to convert a bst to doubly linked list

Algorithm

^{This question was recently asked at 'Amazon'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q36. Write a program to find loop in a linked list

Algorithm

^{This question was recently asked at 'Microsoft'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q37. Explain different sorting algorithms and Big O of each

Algorithm

^{This question was recently asked at 'Microsoft,ServiceNow'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 2 Companies}

Q38. Given a graph, find if it represents a tree

Algorithm

Ans. We can simply find it by checking the criteria of a tree. A tree will not contain a cycle, so if there is any cycle in the graph, it is not a tree. We can check it using another approach, if the graph is connected and it has V-1 edges, it could be a tree. Here V is the number of vertices in the graph

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q39. Write program to balance a binary tree

Algorithm

^{This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve}

Q40. Check if tic tac toe has a winner

Algorithm

^{This question was recently asked at 'Microsoft'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q41. Write code to find the node where two linked lists intersect.

Algorithm

^{This question was recently asked at 'Amazon'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q42. Write a function that returns the depth of a tree.

Algorithm

^{This question was recently asked at 'Amazon'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q43. Write code to check if a Binary tree is symmetrical

Algorithm

^{This question was recently asked at 'Amazon'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve binary tree Asked in 1 Companies}

Q44. Explain bubble sort.

Algorithm

Ans. array is traversed from first element to last element. Here current element is compared with next element. If current element is greater than next element it is swapped.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve sorting bubble sort Asked in 1 Companies}

Q45. Write program to create a linked list and perform different operations on it.

Algorithm

Ans. import java.util.*;
class LinkedListSolution{
protected LinkedList list;
public LinkedListSolution(){
list = new LinkedList();
}
public Object pop() throws NoSuchElementException{
if(list.isEmpty())
throw new NoSuchElementException();
else
return list.removeFirst();
}
public void push(Object obj){
list.addFirst(obj);
}
public Object peek() throws NoSuchElementException{
if(list.isEmpty())
throw new NoSuchElementException();
else
return list.getFirst();
}
public boolean isEmpty(){
return list.isEmpty();
}
public String toString(){
return list.toString();
}
}
class TestStack{
public static void main(String args[]){
LinkedListSolution s = new LinkedListSolution();
s.push("First");
s.push("Second");
s.push("Third");
System.out.println("Top: " s.peek());
s.push("Fourth");
while(!(s.isEmpty()))
System.out.println(s.pop());
}
}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Linkedlist data structures algorithm Asked in 2 Companies basic}

Q46. How to create list that will sort it's elements dynamically?

Algorithm

Ans. Override the behavior of collection class to sort the list upon each element addition. Though it's not recommended as list are sorting heavy data structures.

List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
super.add(mt);
Collections.sort(list, comparator);
return true;
}
};

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies intermediate}

Q47. Write any sorting algorithm.

Algorithm

Ans. https://javasearch.buggybread.com/InterviewQuestions/questionSearch.php?searchOption=label'

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Algorithm Sorting Algorithm Asked in 4 Companies basic frequent}

Q48. What is a binary tree ?

Algorithm

Ans. Binary tree is a tree in which each node has up to two children.Tree is a data structure composed of nodes.Each tree has a root node(not necessary in graph theory). The root node has zero or more child nodes.Each child node has zero or more child nodes, and so on.The tree cannot contain cycles.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve binary tree Asked in 1 Companies}

Q49. Write an algorithm / Java Program to show duplicates in an array of n elements?

Algorithm

Ans. int duplicateArray[] = { 1, 2, 2, 3, 4, 5, 6, 8, 9}
Set unique = new HashSet();
for (int i = 0; i < duplicateArray.length; i) {
if (unique.contains(duplicateArray[i])) {
System.out.println(duplicateArray[i]);
} else {
unique.add(duplicateArray[i]);
}
}

Complexity O(n) = nHashSet contains and add has O(n) = 1

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve coding code Asked in 2 Companies}

Q50. Write an algorithm / java program for Heap Sort ?

Algorithm

Ans. https://www.geeksforgeeks.org/heap-sort/

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve sorting heap sort Asked in 1 Companies frequent}

Q51. Explain various Searching and Sorting Algorithms ?

Algorithm

^{This question was recently asked at 'HeadStrong,ServiceNow'.This question is still unanswered. Can you please provide an answer.}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Search Algorithm Sorting Algorithm Asked in 2 Companies basic frequent}

Q52. Flatten a Binary Tree to Linked List

Algorithm

Ans. https://www.geeksforgeeks.org/flatten-a-binary-tree-into-linked-list/

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Q53. Write an Algorithm for Graph Traversal ? The Graph has a loop.

Algorithm

Ans. Please not that all such questions can be easily answered through recursion.

Simple recursive implementation could be

traverse(root);

void traverse(Element element){
if(element.hasNext()){
traverse(element.next());
} else {
System.out.println(element);
}
}

but this algo / code lead to endless loop if there is a loop in graph traversal.

So you can keep a collection to keep track of which elements have laready been traversed

static List<Elements> listOfAlreadyTraversedElements = new ArrayList<Elements>();

main(){
traverse(root);
}

void traverse(Element element){
if(element.hasNext()){
traverse(element.next());
} else {
listOfAlreadyTraversedElements.add(element);
System.out.println(element);
}
}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal algorithm graph traversal algorithm using recursion Asked in 1 Companies intermediate}

Q54. Explain Travelling SalesMan Problem ?

Algorithm

Ans. https://en.wikipedia.org/wiki/Travelling_salesman_problem

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve Asked in 1 Companies}

Basic and Very Frequently asked.

Q55. What is Polymorphism in Java ?

Core Java

Ans. Polymorphism means the condition of occurring in several different forms.

Polymorphism in Java is achieved in two manners

1. Static polymorphism is the polymorphic resolution identified at compile time and is achieved through function overloading whereas

2. Dynamic polymorphism is the polymorphic resolution identified at runtime and is achieved through method overriding.

Sample Code for overloading

Sample Code for overriding

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve polymorphism object oriented programming (oops) oops concepts oops concepts Asked in 108 Companies Basic frequent}

Try 2 Question(s) Test

Q56. When do you get ClassCastException?

or

What is ClassCastException ?

Ans. As we only downcast class in the hierarchy, The ClassCastException is thrown to indicate that code has attempted to cast an object to a subclass of which it is not an instance.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve java oops class casting classcastexception exception error Asked in 4 Companies intermediate frequent}

Try 2 Question(s) Test

Q57. What are the pre-requisite for the collection to perform Binary Search ?

Ans. 1. Collection should have an index for random access.
2. Collection should have ordered elements.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve java collections search algorithm search binary search at&t intermediate}

Advanced level question frequently asked in US based companies. Recently asked in EMC and Intuit.

Q58. Can you provide some implementation of a Dictionary having large number of words ?

Solution

Ans. Simplest implementation we can have is a List wherein we can place ordered words and hence can perform Binary Search.

Other implementation with better search performance is to use HashMap with key as first character of the word and value as a LinkedList.

Further level up, we can have linked Hashmaps like ,

hashmap {
a ( key ) -> hashmap (key-aa , value (hashmap(key-aaa,value)
b ( key ) -> hashmap (key-ba , value (hashmap(key-baa,value)
....................................................................................
z( key ) -> hashmap (key-za , value (hashmap(key-zaa,value)
}

upto n levels ( where n is the average size of the word in dictionary.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve java collections hashmap binary search search algorithm advanced architecture data structure Asked in 6 Companies frequent}

Try 1 Question(s) Test

Q59. Which sorting algorithm is used by Collections.sort() in Java ?

Core Java

Ans. The sorting algorithm is a modified mergesort. This algorithm offers guaranteed n log(n) performance.

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve java algorithm collections collections.sort sorting algorithm expert}

Try 1 Question(s) Test

Q60. How to determine if the linked list has a cycle in it ?

Ans. http://stackoverflow.com/questions/494830/how-to-determine-if-a-linked-list-has-a-cycle-using-only-two-memory-locations

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve linked list data structure algorithm java ebay}

Search Interview Questions

Help us and Others Improve. Please let us know the questions asked in any of your previous interview.