Algorithm - Interview Questions and Answers for 'Algorithm' - 63 question(s) found - Order By Newest Advanced level question frequently asked in US based companies. Recently asked in EMC and Intuit. Q1. Can you provide some implementation of a Dictionary having large number of words ? Solution Admin info@buggybread.com
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 Q2. What is the difference between Graph's Breadth first and Depth First algorithm ? Algorithm 2017-07-23 10:12:58
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 Q3. In a Linked list with sorted numbers, insert a new numbers while maintaining the sort order. Algorithm 2017-07-25 14:59:01
Ans.
public class LinkedList {
Node start = null;
Node head = null;
class Node{
Integer body;
Node nextNode;
Node(Integer value){
body = value;
}
}
private void insertInMiddle(Integer value){
head = start;
if(start == null) {
start = new Node(value);
head = start;
head.nextNode = null;
return;
}
while(head.body < value){
if(head.nextNode == null || head.nextNode.body >= value){
Node newNode = new Node(value);
newNode.nextNode = head.nextNode;
head.nextNode = newNode;
break;
}
head = head.nextNode;
}
}
private void traverse(){
head = start;
while(head != null){
System.out.println(head.body);
head = head.nextNode;
}
}
public static void main(String[] args){
LinkedList ll = new LinkedList();
ll.insertInMiddle(5);
ll.insertInMiddle(10);
ll.insertInMiddle(15);
ll.insertInMiddle(7);
ll.traverse();
}
} Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  LinkedList  Data structures  Algorithm Q4. What are the pre-requisite for the collection to perform Binary Search ? Admin info@buggybread.com
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 Q5. Write an algorithm / Java Program to show duplicates in an array of n elements? Algorithm 2017-01-19 15:37:26
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 Q6. What is a binary tree ? Algorithm 2017-01-19 15:38:04
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 Q7. Write a program for LinkedList, with method to append node and traversing the list ? Algorithm 2017-07-25 14:31:33
Ans. public class LinkedList {
Node start = null;
Node head = null;
class Node {
Integer body;
Node nextNode;
Node(Integer value) {
body = value;
}
}
private void addNodeToEnd(Integer value) {
if (start == null) {
start = new Node(value);
head = start;
head.nextNode = null;
return;
}
while (head.nextNode != null) {
head = head.nextNode;
}
head.nextNode = new Node(value);
}
private void traverse() {
head = start;
while (head != null) {
System.out.println(head.body);
head = head.nextNode;
}
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.addNodeToEnd(5);
ll.addNodeToEnd(10);
ll.addNodeToEnd(15);
ll.traverse();
}
} Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  LinkedList  Data structures  Algorithm Q8. Write a Program for Graph Depth First Traversal using Apache Commons MultiMap Algorithm 2017-07-23 10:01:14
Ans. import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;
public class Graph {
private static Multimap<Integer,Integer> adjacentDirectedNodesMap = ArrayListMultimap.create();
private static Set<Integer> alreadyVisited = new HashSet();
static{
adjacentDirectedNodesMap.put(1, 2);
adjacentDirectedNodesMap.put(1, 3);
adjacentDirectedNodesMap.put(1, 5);
adjacentDirectedNodesMap.put(2, 4);
adjacentDirectedNodesMap.put(4, 5);
}
public static void main(String[] args){
ArrayList visited = new ArrayList();
Integer startNode = 1;
displayAdjacentNodes(startNode);
}
private static void displayAdjacentNodes(Integer integer){
if(alreadyVisited.contains(integer)){
return;
}
alreadyVisited.add(integer);
System.out.println(integer);
for(Integer adjacentNodes: adjacentDirectedNodesMap.get(integer)){
displayAdjacentNodes(adjacentNodes);
}
}
} Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  graph traversal  depth first algorithm Q9. Which sorting algorithm is used by Collections.sort() in Java ? Core Java Admin info@buggybread.com
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 Q10. How to determine if the linked list has a cycle in it ? admin info@buggybread.com
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 Q11. Find the repeating number using O(n) time and constant space. Algorithm
Ans. http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/ Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  algorithm   program   code   coding  makemytrip.com Q12. Explain Travelling SalesMan Problem ? Algorithm 2016-11-21 15:21:21
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 Q13. Write an Algorithm for Graph Traversal ? The Graph has a loop. Algorithm 2016-11-30 15:42:32
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 Q14. Flatten a Binary Tree to Linked List Algorithm 2016-12-13 14:49:54
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 Q15. Explain various Searching and Sorting Algorithms ? Algorithm 2017-01-11 16:05:54
Ans. a Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve   Asked in 2 Companies Q16. Write an algorithm / java program for Heap Sort ? Algorithm 2017-01-19 15:36:18
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 Q17. Write any sorting algorithm. Algorithm 2017-01-25 13:41:50
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 Q18. How to create list that will sort it's elements dynamically? Algorithm 2017-02-21 12:47:22
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 Q19. Write program to create a linked list and perform different operations on it. Algorithm 2017-02-24 14:18:01
This question was recently asked at 'Kony Labs,Compro Technologies'.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  Linkedlist  data structures  algorithm Asked in 2 Companies basic Q20. Explain bubble sort. Algorithm 2017-03-03 14:28:51
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 Q21. Write code to check if a Binary tree is symmetrical Algorithm 2017-03-03 14:29:12
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 Q22. Write a function that returns the depth of a tree. Algorithm 2017-03-03 14:38:46
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 Q23. Write code to find the node where two linked lists intersect. Algorithm 2017-03-03 14:39:39
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 Q24. Check if tic tac toe has a winner Algorithm 2017-03-03 14:40:05
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 Q25. Write program to balance a binary tree Algorithm 2017-03-03 14:40:54
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   Q26. Given a graph, find if it represents a tree Algorithm 2017-03-03 14:41:06
This question was recently asked at 'Google'.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 Q27. Explain different sorting algorithms and Big O of each Algorithm 2017-03-03 14:41:45
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 Q28. Write a program to find loop in a linked list Algorithm 2017-03-03 14:42:17
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 Q29. How to convert a bst to doubly linked list Algorithm 2017-03-03 14:42:30
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 Q30. How do we implement a weight round robin algorithm in load balancing ? Algorithm 2017-03-19 19:31:41
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 Q31. Given the list of adjacent nodes, What will be the Breadth First path
1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5
Algorithm 2017-07-23 10:30:20
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 Q32. Given the list of adjacent nodes, What will be the Depth First path
1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5 Algorithm 2017-07-23 10:30:48
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 Q33. What will happen in a graph traversal if we don't have a check for cycle Algorithm 2017-07-23 10:32:30
Ans. It will result in never ending loop Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  graph traversal Q34. Describe how you could use a single array to implement three stacks Algorithm 2018-05-24 08:28:08
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  Data Structure Q35. How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time Algorithm 2018-05-24 08:30:09
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  Data Stricture   Big O Notation  time complexity Q36. Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty Algorithm 2018-05-24 08:33:37
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  Data Structures Q37. How different is the Search algorithm when we query Cassandra Tables and When we query Oracle Tables ? Cassandra 2017-08-18 09:40:40
Ans. Relational Database uses linear search if we don't query using indices. Performance for linear search is O(n). If indices have been used , relational database uses binary search. Performance for binary search is O(Log n).
Casandra uses hash search. Performance for Hash Search is O(1). Help us improve. Please let us know the company, where you were asked this question : Like Discuss Correct / Improve  cassandra vs oracle  nosql vs relational  search algorithm Q38. Find Max from Stack in O(1) complexity Algorithm 2018-01-21 17:13:23
This question was recently asked at 'EPAM'.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  complexity  stack  data structure Asked in 1 Companies Q39. Explain Binary Search Algorithm 2018-02-02 08:37:31
This question was recently asked at 'Nagarvision'.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  binary search Asked in 1 Companies basic   frequent Q40. Find all paths of length L in an acyclic graph Algorithm 2018-02-10 12:04:08
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