Sunday, April 5, 2015

Computer Science - Some Interview Questions

Basic Concepts of Important Subjects of Computer Science

Data Structures


What is an algorithm?
The method of solving a problem is known as algorithm.
More precisely, an algorithm is a sequence of instructions that act on some input data to produce some output in a finite number of steps.

An algorithm must have the following properties.

1. Input
2. Output
3. Finiteness
4. Definiteness
5. Effectiveness

What is analysis of algorithms?
An algorithm must not only be able to solve the problem at hand, it must be able to do so in as efficient a manner as possible. Determining which algorithm is efficient than the other involves analysis of algorithms.

Number of operations to be done is to be decided. This is done for significant operations. There are two classes of  operations that are typically chosen for the significant operations - comparison and arithmetic.

In arithmetic operations, additive and muliplicative operations are separately counted as multiplication operation takes more time than the addition operation.

Cases to be considered during analysis -  Best case, Worst case, Average case

Additional Issues of Analysis

Time efficiency
Space efficiency
Simplicity
Generality
Range of input that an algorithm takes

What are important data structures

1. Arrays  2. Strings  3. Linked lists  4. Sparse matrices  5. Stacks  6. Queues 7. Trees  8. Graphs

Searching and Sorting is an important operation on data structures.



Design of Algorithms


Algorithmic Strategies

1. Naive - Brute force - Attempting to solve a problem without thinking of doing it efficiently.
2. Divide and conquer
3. Greedy method - Optimization at every stage.
4. Dynamic programming - Stage-wise optimization. From every point the optimal path to the goal is found starting with one stage ahead of the goal.
5. Backtracking - In backtracking, all possible alternatives to find a solution are not searched. Thus, the algoirthm gives a solution with less number of steps compared to an exhaustive search that finds all possible alternatives. The efficiency is obtained by eliminating certain paths early by determining that they are not feasible paths or efficient paths.
6. Branch and bound
7. Internet Algorithms - String and pattern matching algorithms - Rabin-Karp algorithm - String matching with finite automata - Boyer Moore algorithm - Knuth-Morris-Pratt algoirthm


Database System Concepts


A Database-management system (DBMS) is a collection of interrelated data and a set of programs to access those data.

The primary goal of a DBMS is to provide a way to store and retrieve database information that is both convenient and efficient.

Management of data involves both defining structures for storage of information and providing mechanisms for the manipulation of information.

Database Systems versus File Systems

File systems were used earlier. Data was stored in different individual files and was accessed as required by accessing required files. But the system had drawbacks which were overcome by database systems.

Drawbacks of file-based systems

Data redundancy and inconsistency
Difficulty in accessing data - Multiple files are to be accessed.
Data isolation
Integrity problems
Atomicity problem - Ability to restore all the data up to an instant
Concurrent access anomalies
Security


Instances and Schema

The collection of information stored in the database at a particular moment is called an instance of the database.

The overall design of the database is called the database schema.

Data Models

Underlying the structure of a database is the data model: a collection of conceptual tools for describing data, data relationships, data semantics, and consistency constraints.

Entity Relationship Model

The entity relationship (E-R) model is based on the idea that real world consists of a collection of basic objects, called entities and there are relationships among these objects or entities.

Relational Model

The relational model uses a collection of tables to represent both data and the relationships among those data. Each table has multiple columns, and each column has a unique name.

The relational model is a record based model. Relational database is structured in fixed-format records of several types. Each table contains records of a particular type. Each record type defines a fixed number of fields, or attributes. The columns of the table correspond to the attributes of the recod type,

Object Oriented Data Model

The object oriented model can be seen as extending the E-R model with notions of encapsulation, methods (functions) and object identity.

Database languages

Data definition language (DDL)

Data manipulation language (DML)

Database Access from Application Programs

Application programs of users interact with the database to retrieve data they want. Application programs are usually written in languages such as Cobol, C, C++, or Java.


Database System Structure

A database system is partitioned into modules. The two important modules are storage manager and the query processor module or component.

Storage Manager Components

Authorization and integrity manager
Transaction manager
File manager
Buffer manager

The storage manager implements several data structures as part of the physical system implementation

Data files (tables)
Data dictionary
Indices


The Query Processor Components

DDL Interpreter
DML Compiler
Query evaluation manager.


Application architecture

Two tier - Application at client level - database at server level

Three tier - client front end - application server - database server

Relational Database Design

First Normal Form

A domain is atomic if elements of the domain are considered to be indivisible units. We say that a relation schema R is in first normal form (1NF) if the domains of all attributes of R are atomic.

Boyce-Codd Normal Form (BCNF)

Third Normal Form


Computer Organization and Architecture


Functions of Computer

Data Processing
Data Storage
Data Movement
Control

Structure

There are four main structural components of a computer

1. CPU
2. Main Memory
3. I/O
4. System Interconnection: Some mechanism that provides for communication among CPU, main memory and I/O

Why an IT or Computer Science student has to know computer architecture and organization?

To select the most effective computer for use throughout the organization. The ability to make choice between cache sizes, and clock rates etc. is essential.

Many processor or computer components are part of embedded systems. The IT person must be able to debug them.


Generation
of Computer   -  Period     -        Technology  -  Typical Speed (Operations per second)

First

Second

Third

Fourth

Fifth

Sixth              1991 -                    Ultra large scale integration      - one billion    


Memory Hierarchy


Internal Memory

      Registers
      Cache
      Main internal memory

Outboard Storage

       Magnetic disc
       CD ROM
       Cd-RW
       DVD-RW
       DVD - RAM

Off-line storage

       Magnetic tape
       MO
       WORM

Cache memory has high speed of data transfer like registers, but is less expensive than that of registers and cost is more closer to main memory.

Cache contains a copy of portions of main memory.



Computer Graphics

Raster scan displays

The beam intensity is turned on and off to create a pattern of illuminates spots that give a picture. Each screen point is referred to as pixel or pel (shortened forms of picture elements).

The raster system can have 2 bits for a pixel. But high quality systems have even 24 bits for a pixel.

Refreshing the picture takes place at the rate of 60 to 80 frames for second.

Graphics Functions

A general purpose graphics package provides users with a variety of functions for creating and manipulating pictures.


Output Primitives

Line Drawing Algorithms

DDA Algorithm
Bresenham's Line Algorithm
Parallel Line Algorithm

Circle Generating Algorithms

Midpoint Circle Algorithm


Ellipse Generating Algorithms


Midpoint Ellipse Algorithm


Software Engineering

Based on Book of Roger Pressman, Sixth Edition
Software Engineering Practice



George Polya outlined the essenece of problem solving

1. Understand the problem
2. Plan a solution
3. Carry out the plan
4. Examine the result for accuracy

Core Principles

the dictionary defines the word principle as "an important underlying law or assumption required in a system of thought."

David Hooker has proposed seven core principles that focus on software engineering process as a whole.

1. The reason it all exists.
2. Keep it simple, stupid
3. Maintain the vision
4. What you produce, others will consume
5. Be open to the future
6. Plan ahead for reuse.
7. Think

Communication Principles that apply to customer communication

1. Listen
2. Prepare before you communicate
3. Someone should facilitate the activity
4. face to face communication is best.
5. Take notes and document decisions
6. Strive for collaboration
7. Stay focused, modularize your discussion.
8. If something is unclear, draw a picture
9. Once you agree to something move on; If you can't agree tosomething move on; If a feature or function is unclear and cannot be clarified at the moment, move on.
10. Negotiation is not a contest or a game. It works best when both parties win.

Principles of Planning

1. Understand the scope of the project
2. Involve the customer in the planning activity
3. Recognize that planning is iterative
4. Estimate based on what you know.
5. Consider risk as you define the plan
6. Be realistic
7. Adjust granularity as you define the plan
8. Define how you intend to ensure quality.
9. Describe how you intend to accommodate change
10. Track the plan frequently and make adjustments as required.


Analysis Modeling Principles

1. The information domain of a problem must be represented and understood.
2. The functions that the software performs must be defined.
3. The behavior of the software (as a consequence of external events) must be represented.
4. the models that depict information, function, and behavior must be partitioned in a manner that uncovers detail in a layered(or hierarchical) fashion.
5. The analysis task should move from essential information toward implementation detail.

Software Design Modeling Principles

1 Design should be traceable to the analysis model.
2. Always consider architecture of the system to be built.
3. Design of data is as important as design of processing function
4. Interfaces must be designed with care (both external and internal)
5. User interface design should be designed to the needs of the end user.
6. Component level design should be functionally independent.
7. Components should be loosely coupled  to one another and to the external environment.
8. Design representations (models) should be easily understandable.
9. The design should be developed iternatively. With each iteration the designer should strive for greater simplicity.


Coding Principles and  Concepts

Preparation Principles

1. Understand the problem you're trying to solve.
2. Understand the basic design principles and concepts.
3. Pick a programming language that meets the needs of the software to be built and the environment in which it will operate.
4. Select a programming environment that provides tools that will  make your work easier.
5. Create a set of unit tests that will be applied once the component you code is completed.


Coding Principles

1. Constrain your algorithms by following structured programming (BOH00)
2. Select data structures that will meet the needs of the design.
Understand the software architecture and create interfaces that are consistent with it.
4. Keep conditional logic as simple as possible.
5. create nested loops in a way that makes them easily testable.
6. Select meaningful variable names and follow other local coding standards
7. Write code that is self-documenting.
8. Create visual layout (e.g., indentation and blank lines) that aids understanding.


Validation Principles

1. Conduct a code walkthrough when appropriate.
2. Perform unit tests and correct errors yoou've uncovered.
3. Refactor the code.

Software Testing Principles


Principles developed by Davis
1. All tests should be traceable to customer requirements.
2. tests should be planned long before testing begins.
3. The pareto principle applies to software testing.
4. testing should begin "in the small" and progress toward testing "in the large"
5. Exhaustive testing is not possible


Deployment Principles

1. Customer expectations for the software must be managed.
2. A complete delivery package must be assembled and tested.
3. A support regime must be established before the software is delivered.
4. Appropriate instructional materials must be provided to end users.
5. Buggy software should be fixed first, delivered later.