Wednesday, 12 September 2012
Tuesday, 11 September 2012
Data Structure Basics
1.
What is data structure?
A
data structure is a way of organizing data that considers not only the items
stored, but also their relationship to each other. Advance knowledge about the
relationship between data items allows designing of efficient algorithms for
the manipulation of data.
2.
List out the areas in which data structures are applied extensively?
- Compiler Design,
- Operating System,
- Database Management System,
- Statistical analysis package,
- Numerical Analysis,
- Graphics,
- Artificial Intelligence,
- Simulation
3.
What are the major data structures used in the following areas : RDBMS, Network
data model and Hierarchical data model.
- RDBMS = Array (i.e. Array of structures)
- Network data model = Graph
- Hierarchical data model = Trees
4. If
you are using C language to implement the heterogeneous linked list, what
pointer type will you use?
The
heterogeneous linked list contains different data types in its nodes and we
need a link, pointer to connect them. It is not possible to use ordinary
pointers for this. So we go for void pointer. Void pointer is capable of
storing pointer to any type as it is a generic pointer type.
5.
Minimum number of queues needed to implement the priority queue?
Two.
One queue is used for actual storing of data and another for storing
priorities.
6.
What is the data structures used to perform recursion?
Stack.
Because of its LIFO (Last In First Out) property it remembers its 'caller' so
knows whom to return when the function has to return. Recursion makes use of
system stack for storing the return addresses of the function calls.
Every
recursive function has its equivalent iterative (non-recursive) function. Even
when such equivalent iterative procedures are written, explicit stack is to be
used.
7.
What are the notations used in Evaluation of Arithmetic Expressions using
prefix and postfix forms?
Polish
and Reverse Polish notations.
8. Convert the expression ((A
+ B) * C - (D - E) ^ (F + G)) to equivalent Prefix and Postfix notations.
- Prefix
Notation: - * +ABC ^ - DE + FG
- Postfix
Notation: AB + C * DE - FG + ^ -
9.
Sorting is not possible by using which of the following methods? (Insertion,
Selection, Exchange, Deletion)
Sorting
is not possible in Deletion. Using
insertion we can perform insertion sort, using selection we can perform
selection sort, using exchange we can perform the bubble sort (and other
similar sorting methods). But no sorting method can be done just using
deletion.
10.
What are the methods available in storing sequential files ?
- Straight merging,
- Natural merging,
- Polyphase sort,
- Distribution of Initial runs.
11.
List out few of the Application of tree data-structure?
- The manipulation of Arithmetic
expression,
- Symbol Table construction,
- Syntax analysis.
12.
List out few of the applications that make use of Multilinked Structures?
- Sparse matrix,
- Index generation.
13.
In tree construction which is the suitable efficient data structure? (Array,
Linked list, Stack, Queue)
Linked
list is the suitable efficient data structure.
14.
What is the type of the algorithm used in solving the 8 Queens problem?
Backtracking.
15.
In an AVL tree, at what condition the balancing is to be done?
If
the 'pivotal value' (or the 'Height factor') is greater than 1 or less than -1.
16.
What is the bucket size, when the overlapping and collision occur at same time?
One.
If there is only one entry possible in the bucket, when the collision occurs,
there is no way to accommodate the colliding value. This results in the
overlapping of values.
17.
Classify the Hashing Functions based on the various methods by which the key
value is found.
- Direct method,
- Subtraction method,
- Modulo-Division method,
- Digit-Extraction method,
- Mid-Square method,
- Folding method,
- Pseudo-random method.
18.
What are the types of Collision Resolution Techniques and the methods used in
each of the type?
- Open addressing (closed hashing), The methods
used include: Overflow block.
- Closed addressing (open hashing), The methods used include: Linked list, Binary tree.
- 19. In RDBMS, what is the efficient data structure used in the internal storage representation?
B+
tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes
searching easier. This corresponds to the records that shall be stored in leaf
nodes.
20. What is a spanning Tree?
A
spanning tree is a tree associated with a network. All the nodes of the graph
appear on the tree once. A minimum spanning tree is a spanning tree organized
so that the total edge weight between nodes is minimized.
21. Does the minimum spanning tree of a
graph give the shortest distance between any 2 specified nodes?
No.
The Minimal spanning tree assures that the total weight of the tree is kept at
its minimum. But it doesn't mean that the distance between any two nodes
involved in the minimum-spanning tree is minimum.
22. Which is the simplest file structure?
(Sequential, Indexed, Random)
Sequential
is the simplest file structure.
23. Whether Linked List is linear or
Non-linear data structure?
According
to Access strategies Linked list is a linear one.
According to Storage Linked List is a Non-linear one.
Saturday, 8 September 2012
The Empty Soap Box
One of the most memorable case studies on Japanese management was the case of the empty soap box, which happened in one of Japan's biggest cosmetics companies. The company received a complaint that a consumer had bought a soap box that was empty.
Immediately the authorities isolated the problem to the assembly line, which transported all the packaged boxes of soap to the delivery department. For some reason, one soap box went through the assembly line empty.
Management asked its engineers to solve the problem. Post-haste, the engineers worked hard to devise an X-ray machine with high- resolution monitors manned by two people to watch all the soap boxes that passed through the line to make sure they were not empty.
No doubt, they worked hard and they worked fast but they spent whoopee amount to do so. But when a workman was posed with the same problem, did not get into complications of X-rays, etc but instead came out with another solution.
He bought a strong industrial electric fan and pointed it at the assembly line. He switched the fan on, and as each soap box passed the fan, it simply blew the empty boxes out of the line.
Moral of the story: Always look for simple solutions. Devise the simplest possible solution that solves the problem. So, learn to focus on solutions not on problems. "If you look at what you do not have in life, you don't have anything; if you look at what you have in life, you have everything.
Dos and Don’ts of participating in Group Discussion
As you have to participate in a Group Discussion. several questions spring across your mind. You want to know what actions and gestures can get you positive points and what can cost you the selection. Here’s a list of Dos and Don’ts of participating in the GD.
Dos of participating in a GD:
- Listen to the subject carefully
- Put down your thoughts on a paper
- Initiate the discussion if you know the subject well
- Listen to others if you don’t know the subject
- Support you point with some facts and figures
- Make short contribution of 25-30 seconds 3-4 times
- Give others a chance to speak
- Speak politely and pleasantly. Respect contribution from other members.
- Disagree politely and agree with what is right.
- Summarize the discussion if the group has not reached a conclusion.
Don’ts of participating in a Group Discussion
- Initiate the discussion if you do not have sufficient knowledge about the given topic.
- Over speak, intervene and snatch other’s chance to speak.
- Argue and shout during the GD
- Look at the evaluators or a particular group member
- Talk irrelevant things and distract the discussion
- Pose negative body gestures like touching the nose, leaning back on the chair, knocking the table with a pen etc.
- Mention erratic statistics.
- Display low self confidence with shaky voice and trembling hands.
- Try to dominate the discussion
- Put others in an embarrassing situation by asking them to speak if they don’t want.
How to Clear a Technical Interview ??
Technical Interview is part of the recruitment process for almost all the companies and this is the second biggest elimination round after the written test.
Well, I will assume here as you are a fresher trying to get into a software company (since most does irrespective of their branch).
Any software firm small or big wants their employees to know the basics of the subjects like,
1. Programming
2. software engineering
3. operating systems
4. Databases
5. Computer Networks.
Having said that they won’t expect you to know every part and parcel of the subjects, rather they would look for someone who at least knows what they are for.
Now if you are asked to write a C-Program which does check whether a given integer/string is a palindrome or not (which is part of lab programs for almost all the universities in the country in the 1st year), he would expect that you will write it easily and if you fail to do so, please don’t expect him to select you.
So what would we suggest is that, you should have basic knowledge on the aforementioned subjects and we will also tell you the areas you should concentrate in each subject.
1. Programming
In any technical interview, it is obvious that you would be asked to write some programs and mostly in C,C++ & Java .
To be confident at this area, you should know the basic syntax of all these subjects as the semantic or logic remains the same.
Start with C, learn variables, operators, control structures, functions & pointers (the most important stuff), structures and files. Then go for C++ and java, try to understand the differences between all the three precisely.
OOPS is the most important & probable topic, where you might get questions from.
Below is the list of the most frequently asked programs that you must learn to clear this round.
a) Write a C program to swap two numbers without using a third variable.
b) Write a C program to check whether the given number or a string is palindrome or not.
c) Write a C program to create a Pascal triangle.
d) Write a C program to perform matrix multiplication and addition.
e) Write a C program which performs bit manipulation (&,|,etc) of a given number.
f) Also, learn programs which does basic file manipulations (creation, writing data and reading)
We would post some more programs which are important, with the complete code ? in a separate section.
2. Software Engineering
This is the most important & also a boring subject, since it is mostly theoretical.
Not many interviewers ask questions on this subject in the technical interview, but it is always better to know the basics and be on the safer side.
Questions in this subject would be basically on the following topics,
a. Phases of Software Development Life Cycle
b. Process Models like Waterfall model, agile model etc.
c. Cyclomatic complexity of a software
d. Basics of software testing(white box, black box testing)
If you can learn all these, then you could possibly answer all the questions in the interview.
3. Operating Systems
Define operating system?
Could be the first possible question in some technical interview’s and this subject is one of the core subjects of computer science. Students from CS and IT back ground can’t take any excuses for not answering questions in this subject and others may get excuse if you don’t answer.
Now in this subject, you have to know the following things:
a. The definition of an Operating System, components of an OS(like process management, memory management , etc)
b. Learn the functionality of all the cpu scheduling algorithms like FCFS,SJF, Round-Robbin , etc.
c. Learn how process synchronization works, this concept involves semaphore, monitor to achieve process s synchronization.
d. Learn basic memory management techniques like paging, segmentation etc.
This should do for answering any question in Operating System.
4. Databases
No application works without a database and so it is must for us to know the basics of the data base management system.
Do learn the following things,
a. Whenever we say DBMS we refer to RDBMS and everything is relational here in this DB. Go through the basics like entities, attributes and relations,ER-models,keys and constraints.
b. Now learn to implement them with the structured query language shortly called as SQL, learn the basic operations CRUD(create, insert ,update & delete).
These all should do,but also go through transactions which is also an important concept and might be asked in the interview.
5 .Computer Networks
Stand alone systems don’t do any wonders and that is why the systems are connected through a network.
In computer networks all you need to concentrate is on the OSI reference model which covers everything, do try to know what each layer does and know about TCP,IP in particular.
This should do for computer networks
Subscribe to:
Comments (Atom)