Interview Questions: Algo

Q1. 100 monkey's questions:

There are 100 monkeys goes to a room, where 100 switchs are there with all in off state. each monkey toggle there number switch [ e.g 5th monkey toggle 5,10,15 and so on... ] then how many and what all the switches will be off and on.

ANS: All the absolute square number's will be on "ON" state.    

echo "sqrt (100)" | bc -l | awk -F"." '{print $1}'   => 10   [ Logic, only sq number's factorial's are odd number's in count ]

Q2. Sand glass timers?

If you have two sand glass timers, one with 7 minutes worth of sand and another with 4 minutes worth of sand, how do you use both to precisely time 9 minutes?

Ans: start the 7 min and 4 min sandbox the same time, and filp the 4 min sandbox when its done, and flip the 4 min sandbox again when the 7 min sandbox is done, so now you have 1 min in the 4 min sandbox, then you can do 2 time flip of 4 min sendbox, that is: 1 + 4 + 4 = 9


Q3. For a given number, find the next greatest number which is just greater than previous one and made up of same digits.

Eg: 5436782  => Ans is 5436827

data structure Questions
1.What is data structure?
2.What are the goals of Data Structure ?
3.What does abstract Data Type Mean?
4.What is the difference between a Stack and an Array?
5.What do you mean by recursive definition?
6.What is sequential search?
7.What actions are performed when a function is called?
8.What actions are performed when a function returns?
9.What is a linked list ?
10.What are the advantages of linked list over array(static data structure) ?
11.Can we apply binary search algorithm to a sorted linked list,why ?
12.What do you mean by free pool ?
13.What do you mean by garbage collection ?
14.What do you mean by overflow and underflow ?
15.What are the disadvantages array implementation of linked list ?
16.What is a queue ?
17. What is a priority queue ?
18.What are the disadvantages of sequential storage?
19.What are the disadvantages of representing a stack or queue by a linked list ?
20.What is dangling pointer and how to avoid it ?
21.What are the disadvantages of linear list ?
22.Define circular list ?
23. What are the disadvantages of circular list ?
24.Define double linked list?
25.Is it necessary to sort a file before searching a particular item ?
26.What are the issues that hampers the efficiency in sorting a file ?
27.Calculate the efficiency of sequential search ?
28. Is any implicit arguments are passed to a function when it is called ?
29.Parenthesis is never required in Postfix or Prefix expressions, Why?
30.List out the areas in which data structures are applied extensively?
31.What are the major data structures used in the following areas : network data model & Hierarchical data model.
32.If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
33.Minimum number of queues needed to implement the priority queue?
34.What is the data structures used to perform recursion?
35.What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
36. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
37. Sorting is not possible by using which of the following methods?
38. List out few of the Application of tree data-structure?
39. List out few of the applications that make use of Multilinked Structures?
40. In tree construction which is the suitable efficient data structure?
41. What is the type of the algorithm used in solving the 8 Queens problem?
42 .In an AVL tree, at what condition the balancing is to be done?
43 .There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have formed a full binary tree?
44.In RDBMS, what is the efficient data structure used in the internal storage representation?
45. Of the following tree structure, which is, efficient considering space and time complexities?
(a) Incomplete Binary Tree.
(b) Complete Binary Tree.
(c) Full Binary Tree.
46.What is a spanning Tree?
47.Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes?
48.Whether Linked List is linear or Non-linear data structure?

########### Few Links #########
http://www.careercup.com/page?pid=data-structures-interview-questions


http://www.careercup.com/



http://www.indiabix.com/technical/data-structures/
http://www.gointerviews.com/top-50-data-structure-interview-questions/
http://careerride.com/Data-Structure-Interview-Questions.aspx
https://sites.google.com/site/interviewquestionsandanswers/data-structure-algorithms-interview-questions-and-answers
http://www.freejobalert.com
########### Further ###########

- NP complete problem
- Nth fibonacci number -- iterative
- Find least common ancestor in a tree with back links to parents
- Speed, distance analytical question



######## Should look for ###########

Understand and dissect complex problems quickly
Understand trade-offs between space / time complexity
Come up with solutions with minimal space / time complexity
Reasonably mathematically savvy
Familiarity with graph theory, graph traversals etc

Basic Knowledge of data structures - Hashmaps, Binary tree, B-Tree, B+Tree, Linked Lists etc
Understanding of trade-offs between various data structures etc
Advanced Knowledge of implementation of data structures - Hashmaps, Binary tree, B-Tree, B+Tree, Linked Lists etc

Basic RDBMS knowledge
Advanced RDBMS knowledge
Query optimization
RDBMS tuning
Replication and Clustering
RDBMS Scalability

Basic knowledge of caching
Advanced caching strategies

Strong knowledge of OOPs
Design patterns and application thereof
Understanding of KISS, YAGNI, DRY, SOC, SRP, Loose Coupling etc

Basic knowledge of DNS
Protocol level understanding of TCP / UDP
Deep understanding of OSI stack
Basic understanding of Routing concepts

Ability to implement a protocol server/client
Ability to write high performance server/client
Understanding of Async I/O
Understanding of various network protocols

Basic Javascript
Protocol level knowledge of HTTP

Basic knowledge of multi-threading
Advanced knowledge of multi-threading / trade-offs

Planning and writing stress tests

Understanding of OS concepts, kernel, interrupts, native libraries etc
Understanding of OS process scheduling concepts

Knowledge of different forms of IPC / RPC

Knowledge of OWASP
Knowledge of Network layer security
Knowledge of secure architectures

Knowledge of Unicode and its implementations
Knowledge of implementation of internationalized interfaces
Understand implications of internationalized data in RDBMS, searches, indexing etc

Knowledge of Agile, XP, Scrum, TDD and pairing
Knowledge of Identifying code smells and Refactoring


Write and plan stress tests to determine scalability
Ability to identify scalability and performance bottlenecks quickly
Ability to determine whether an application is / will be disk bound, memory bound, cpu bound, network bound etc
Understanding of all layers from the hardware to the application to determine bottlenecks
Knowledge of scaling techniques on the application side such as Async IO, caching, multi-threading etc
Knowledge of scaling techniques on the data side such as Identifying optimized data structures, caching strategies, Horizontal / Vertical partitioning, replication / clustering
Knowledge of scaling techniques on the app server side such as clustering and load balancing

Basic Unix commands and shell operation (including grep, awk, sed, regex and shell / perl scripting)
Basic Windows administration

Knowledge of information architecture

Good grammar - written and oral
Ability to understand discussions well