What is the difference between declaration and definition of a variable/function
Ans: Declaration of a variable/function simply declares
that the variable/function exists somewhere in the program but the
memory is not allocated for them. . Coming to the definition, when we define a
variable/function, apart from the role of declaration, it also
allocates memory for that variable/function. Therefore, we can think of
definition as a super set of declaration. (or declaration as a subset of
definition). From this explanation, it should be obvious that a
variable/function can be declared any number of times but it can be
defined only once. (Remember the basic principle that you can’t have two
locations of the same variable/function).
// This is only declaration. y is not allocated memory by this statement
extern int y;
// This is both declaration and definition, memory to x is allocated by this statement.
int x;
What are different storage class specifiers in C?
Ans: auto, register, static, extern
What is scope of a variable? How are variables scoped in C?
Ans: Scope of a variable is the part of the program
where the variable may directly be accessible. In C, all identifiers are
lexically (or statically) scoped. See
this for more details.
How will you print “Hello World” without semicolon?
Ans:
int main(void)
{
if (printf(“Hello World”)) ;
}
When should we use pointers in a C program?
1. To get address of a variable
2. For achieving pass by reference in C: Pointers allow different functions to share and modify their local variables.
3. To pass large structures so that complete copy of the structure can be avoided.
C
4. To implement “linked” data structures like linked lists and binary trees.
What is NULL pointer?
Ans: NULL is used to indicate that the pointer doesn’t
point to a valid location. Ideally, we should initialize pointers as
NULL if we don’t know their value at the time of declaration. Also, we
should make a pointer NULL when memory pointed by it is deallocated in
the middle of a program.
What is Dangling pointer?
Ans: Dangling Pointer is a pointer that doesn’t point
to a valid memory location. Dangling pointers arise when an object is
deleted or deallocated, without modifying the value of the pointer, so
that the pointer still points to the memory location of the deallocated
memory. Following are examples.
int *ptr = (int *)malloc(sizeof(int));
.............
.............
free(ptr);
*ptr = 10;
|
int *ptr = NULL
{
int x = 10;
ptr = &x;
}
|
What is memory leak? Why it should be avoided
Ans: Memory leak occurs when programmers create a
memory in heap and forget to delete it. Memory leaks are particularly
serious issues for programs like daemons and servers which by definition
never terminate.
#include
void f()
{
int *ptr = (int *) malloc(sizeof(int));
return;
}
|
What are local static variables? What is their use?
Ans:A local static variable is a variable whose
lifetime doesn’t end with a function call where it is declared. It
extends for the lifetime of complete program. All calls to the function
share the same copy of local static variables. Static variables can be
used to count the number of times a function is called. Also, static
variables get the default value as 0. For example, the following
program prints “0 1″
#include
void fun()
{
static int x;
printf("%d ", x);
x = x + 1;
}
int main()
{
fun();
fun();
return 0;
}
|
What are static functions? What is their use?
Ans:In C, functions are global by default. The “static”
keyword before a function name makes it static. Unlike global functions
in C, access to static functions is restricted to the file where they
are declared. Therefore, when we want to restrict access to functions,
we make them static. Another reason for making functions static can be
reuse of the same function name in other files. See
this for examples and more details.
What are main characteristics of C language?
C is a procedural language. The main features of C language include
low-level access to memory, simple set of keywords, and clean style.
These features make it suitable for system programming like operating
system or compiler development.
What is difference between i++ and ++i?
1) The expression ‘i++’ returns the old value and then increments i. The
expression ++i increments the value and returns new value.
2) Precedence of postfix ++ is higher than that of prefix ++.
3) Associativity of postfix ++ is left to right and associativity of prefix ++ is right to left.
4) In C++, ++i can be used as l-value, but i++ cannot be. In C, they both cannot be used as l-value.
See
Difference between ++*p, *p++ and *++p for more details.
What is l-value?
l-value or location value refers to an expression that can be used on
left side of assignment operator. For example in expression “a = 3″, a
is l-value and 3 is r-value.
l-values are of two types:
“nonmodifiable l-value” represent a l-value that can not be modified. const variables are “nonmodifiable l-value”.
“modifiable l-value” represent a l-value that can be modified.
What is the difference between array and pointer?
See
Array vs Pointer
How to write your own sizeof operator?
#define my_sizeof(type) (char *)(&type+1)-(char*)(&type)
|
See
Implement your own sizeof for more details.
How will you print numbers from 1 to 100 without using loop?
We can use recursion for this purpose.
void printNos(unsigned int n)
{
if(n > 0)
{
printNos(n-1);
printf("%d ", n);
}
}
|
What is volatile keyword?
The volatile keyword is intended to prevent the compiler from applying
any optimizations on objects that can change in ways that cannot be
determined by the compiler.
Objects declared as volatile are omitted from optimization because their
values can be changed by code outside the scope of current code at any
time. See
Understanding “volatile” qualifier in C for more details.
Can a variable be both const and volatile?
yes, the const means that the variable cannot be assigned a new value.
The value can be changed by other code or pointer. For example the
following program works fine.
int main(void)
{
const volatile int local = 10;
int *ptr = (int*) &local;
printf("Initial value of local : %d \n", local);
*ptr = 100;
printf("Modified value of local: %d \n", local);
return 0;
}
What is Object Oriented Programming?
Object
Oriented
Programming
(OOP) is a programming paradigm where the complete software operates as
a bunch of objects talking to each other. An object is a collection of
data and methods that operate on its data.
Why OOP?
The main advantage of OOP is better manageable code that covers following.
1) The overall understanding of the software is increased as the
distance between the language spoken by developers and that spoken by
users.
2) Object orientation eases maintenance by the use of
encapsulation. One can easily change the underlying representation by
keeping the methods same.
OOP paradigm is mainly useful for relatively big software. See
this for a complete example that shows advantages of OOP over procedural programing.
What are main features of OOP?
Encapsulation
Polymorphism
Inheritance
What is encapsulation?
Encapsulation is referred to one of the following two notions.
1) Data hiding: A language feature to restrict access to members of an
object. For example, private and protected members in C++.
2) Bundling of data and methods together: Data and methods that operate on that data are bundled together.
What is Polymorphism? How is it supported by C++?
Polymorphism means that some code or operations or objects behave
differently in different contexts. In C++, following features support
polymorphism.
Compile Time Polymorphism: Compile time polymorphism means
compiler knows which function should be called when a polymorphic call
is made. C++ supports compiler time polymorphism by supporting features
like templates, function overloading and default arguments.
Run Time Polymorphism: Run time polymorphism is supported by virtual functions
. The idea is,
virtual functions
are called according to the type of object pointed or referred, not
according to the type of pointer or reference. In other words, virtual
functions are resolved late, at runtime.
What is Inheritance? What is the purpose?
The idea of inheritance is simple, a class is based on another class and uses data and implementation of the other class.
The purpose of inheritance is Code Reuse.
What is Abstraction?
The first thing with which one is confronted when writing programs is
the problem. Typically we are confronted with “real-life” problems and
we want to make life easier by providing a program for the problem.
However, real-life problems are nebulous and the first thing we have to
do is to try to understand the problem to separate necessary from
unnecessary details: We try to obtain our own abstract view, or model,
of the problem. This process of modeling is called abstraction (Source
http://gd.tuwien.ac.at/languages/c/c++oop-pmueller/node4.html#SECTION00410000000000000000)
See
the source for a complete example and more details of abstraction.
What are advantages of DBMS over traditional file based systems?
Ans: Database management systems were developed to
handle the following difficulties of typical file-processing systems
supported by conventional operating systems.
1. Data redundancy and inconsistency
2. Difficulty in accessing data
3. Data isolation – multiple files and formats
4. Integrity problems
5. Atomicity of updates
6. Concurrent access by multiple users
7. Security problems
Source:
http://cs.nyu.edu/courses/spring01/G22.2433-001/mod1.2.pdf
What are super, primary, candidate and foreign keys?
Ans: A
superkey is
a set of attributes of a relation schema upon which all attributes of
the schema are functionally dependent. No two rows can have the same
value of super key attributes.
A
Candidate key is minimal superkey, i.e., no proper subset of Candidate key attributes can be a superkey.
A
Primary Key
is one of the candidate keys. One of the candidate keys is selected as
most important and becomes the primary key. There cannot be more that
one primary keys in a table.
Foreign key is a field (or collection of fields) in one table that uniquely identifies a row of another table. See
this for an example.
What is the difference between primary key and unique constraints?
Ans: Primary key cannot have NULL value, the unique
constraints can have NULL values. There is only one primary key in a
table, but there can be multiple unique constrains.
What is database normalization?
Ans: It is a process of analyzing the given relation
schemas based on their functional dependencies and primary keys to
achieve the following desirable properties:
1) Minimizing Redundancy
2) Minimizing the Insertion, Deletion, And Update Anomalies
Relation schemas that do not meet the properties are decomposed into
smaller relation schemas that could meet desirable properties.
Source:
http://cs.tsu.edu/ghemri/CS346/ClassNotes/Normalization.pdf
What is SQL?
SQL is Structured Query Language designed for inserting and modifying in a
relational database system.
What are the differences between DDL, DML and DCL in SQL?
Ans: Following are some details of three.
DDL stands for Data Definition Language. SQL queries like CREATE, ALTER, DROP and RENAME come under this.
DML stands for Data Manipulation Language. SQL queries like SELECT, INSERT and UPDATE come under this.
DCL stands for Data Control Language. SQL queries like GRANT and REVOKE come under this.
What is the difference between having and where clause?
Ans: HAVING is used to specify a condition for a group
or an aggregate function used in select statement. The WHERE clause
selects before grouping. The HAVING clause selects rows after grouping.
Unlike HAVING clause, the WHERE clause cannot contain aggregate
functions. (See
this for examples)
What is Join?
Ans: An SQL Join is used to combine data from two or
more tables, based on a common field between them. For example, consider
the following two tables.
Student Table
| EnrollNo |
StudentName |
Address |
| 1000 |
geek1 |
geeksquiz1 |
| 1001 |
geek2 |
geeksquiz2 |
| 1002 |
geek3 |
geeksquiz3 |
StudentCourse Table
| CourseID |
EnrollNo |
| 1 |
1000 |
| 2 |
1000 |
| 3 |
1000 |
| 1 |
1002 |
| 2 |
1003 |
Following is join query that shows names of students enrolled in different courseIDs.
SELECT StudentCourse.CourseID, Student.StudentName
FROM StudentCourse
INNER JOIN Customers
ON StudentCourse.EnrollNo = Student.EnrollNo
ORDER BY StudentCourse.CourseID;
The above query would produce following result.
| CourseID |
StudentName |
| 1 |
geek1 |
| 1 |
geek2 |
| 2 |
geek1 |
| 2 |
geek3 |
| 3 |
geek1 |
What is Identity?
Ans: Identity (or AutoNumber) is a column that
automatically generates numeric values. A start and increment value can
be set, but most DBA leave these at 1. A GUID column also generates
numbers; the value of this cannot be controlled. Identity/GUID columns
do not need to be indexed.
What is a view in SQL? How to create one
Ans: A
view is a virtual table based on the result-set of an SQL statement. We can create using create view syntax.
CREATE VIEW view_name AS
SELECT column_name(s)
FROM table_name
WHERE condition
What are the uses of view?
1. Views can represent a subset of the data contained
in a table; consequently, a view can limit the degree of exposure of the
underlying tables to the outer world: a given user may have permission
to query the view, while denied access to the rest of the base table.
2. Views can join and simplify multiple tables into a single virtual table
3. Views can act as aggregated tables, where the
database engine aggregates data (sum, average etc.) and presents the
calculated results as part of the data
4. Views can hide the complexity of data; for example a
view could appear as Sales2000 or Sales2001, transparently partitioning
the actual underlying table
5. Views take very little space to store; the database
contains only the definition of a view, not a copy of all the data which
it presentsv.
6. Depending on the SQL engine used, views can provide extra security
Source:
Wiki Page
What is a Trigger?
Ans: A
Trigger
is a code that associated with insert, update or delete operations. The
code is executed automatically whenever the associated query is
executed on a table. Triggers can be useful to maintain integrity in
database.
What is a stored procedure?
Ans: A
stored procedure
is like a function that contains a set of operations compiled together.
It contains a set of operations that are commonly used in an
application to do some common database tasks.
What is the difference between Trigger and Stored Procedure?
Ans: Unlike Stored Procedures, Triggers cannot be called directly. They can only be associated with queries.
What is a transaction? What are ACID properties?
Ans: A
Database Transaction is a set of database operations that must be treated as whole, means either all operations are executed or none of them.
An example can be bank transaction from one account to another account.
Either both debit and credit operations must be executed or none of
them.
ACID (Atomicity,
Consistency, Isolation, Durability) is a set of properties that
guarantee that database transactions are processed reliably.
What are indexes?
Ans: A
database index
is a data structure that improves the speed of data retrieval
operations on a database table at the cost of additional writes and the
use of more storage space to maintain the extra copy of data.
Data can be stored only in one order on disk. To support faster access
according to different values, faster search like binary search for
different values is desired, For this purpose, indexes are created on
tables. These indexes need extra space on disk, but they allow faster
search according to different frequently searched values.
What are clustered and non-clustered Indexes?
Ans: Clustered indexes is the index according to which
data is physically stored on disk. Therefore, only one clustered index
can be created on a given database table.
Non-clustered indexes don’t define physical ordering of data, but
logical ordering. Typically, a tree is created whose leaf point to disk
records.
B-Tree or
B+ tree are used for this purpose.
We will soon be covering more DBMS questions. Please write comments
if you find anything incorrect, or you want to share more information
about the topic discussed above.
What is a process and process table? What are different states of process
A
process is an instance of program in execution.
For example a Web Browser is a process, a shell (or command prompt) is a process.
The operating system is responsible for managing all the processes that
are running on a computer and allocated each process a certain amount of
time to use the processor. In addition, the operating system also
allocates various other resources that processes will need such as
computer memory or disks. To keep track of the state of all the
processes, the operating system maintains a table known as the
process table.
Inside this table, every process is listed along with the resources the
processes is using and the current state of the process.
Processes can be in one of three states: running, ready, or waiting.
The running state means that the process has all the resources it need
for execution and it has been given permission by the operating system
to use the processor. Only one process can be in the running state at
any given time. The remaining processes are either in a waiting state
(i.e., waiting for some external event to occur such as user input or a
disk access) or a ready state (i.e., waiting for permission to use the
processor). In a real operating system, the waiting and ready states are
implemented as queues which hold the processes in these states. The
animation below shows a simple representation of the life cycle of a
process (Source:
http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html)
What is a Thread? What are the differences between process and thread?
A thread is a single sequence stream within in a process. Because
threads have some of the properties of processes, they are sometimes
called
lightweight processes. Threads are popular way to improve
application through parallelism. For example, in a browser, multiple
tabs can be different threads. MS word uses multiple threads, one thread
to format the text, other thread to process inputs, etc.
A thread has its own program counter (PC), a register set, and a stack
space. Threads are not independent of one other like processes as a
result threads shares with other threads their code section, data
section and OS resources like open files and signals. See
http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/threads.htm for more details.
What is deadlock?
Deadlock is a situation when two or more processes wait for each other
to finish and none of them ever finish. Consider an example when two
trains are coming toward each other on same track and there is only one
track, none of the trains can move once they are in front of each other.
Similar situation occurs in operating systems when there are two or
more processes hold some resources and wait for resources held by
other(s).
What are the necessary conditions for deadlock?
Mutual Exclusion: There is s resource that cannot be shared.
Hold and Wait: A process is holding at least one resource and waiting for another resource which is with some other process.
No Preemption: The operating system is not allowed to take a resource back from a process until process gives it back.
Circular Wait: A set of processes are waiting for each other in circular form.
What is Virtual Memory? How is it implemented?
Virtual memory creates an illusion that each user has one or more
contiguous address spaces, each beginning at address zero. The sizes of
such virtual address spaces is generally very high.
The idea of virtual memory is to use disk space to extend the RAM.
Running processes don’t need to care whether the memory is from RAM or
disk. The illusion of such a large amount of memory is created by
subdividing the virtual memory into smaller pieces, which can be loaded
into physical memory whenever they are needed by a process.
What is Thrashing?
Thrashing is a situation when the performance of a computer degrades or
collapses. Thrashing occurs when a system spends more time processing
page faults than executing transactions. While processing page faults is
necessary to in order to appreciate the benefits of virtual memory,
thrashing has a negative affect on the system. As the page fault rate
increases, more transactions need processing from the paging device. The
queue at the paging device increases, resulting in increased service
time for a page fault (Source: h
ttp://cs.gmu.edu/cne/modules/vm/blue/thrash.html)
What is Belady’s Anomaly?
Bélády’s anomaly is an anomaly with some page replacement policies where
increasing the number of page frames results in an increase in the
number of page faults. It occurs with First in First Out page
replacement is used. See
the wiki page for an example and more details.
Differences between mutex and semphore?
See
http://www.geeksforgeeks.org/mutex-vs-semaphore/
We will soon be covering more Operating System questions. Please
write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
What is a Data Structure?
A data structure is a way of organizing the data so that the data can be
used efficiently. Different kinds of data structures are suited to
different kinds of applications, and some are highly specialized to
specific tasks. For example, B-trees are particularly well-suited for
implementation of databases, while compiler implementations usually use
hash tables to look up identifiers. (Source:
Wiki Page)
Which data structures are used for BFS and DFS of a graph?
Queue is used for BFS and Stack is used for DFS.
DFS can also be implemented using recursion (Note that recursion also uses function call stack).
What is an algorithm?
Informally, an algorithm is any well-defined computational procedure
that takes some value, or set of values, as input and produces some
value, or set of values, as output. An algorithm is thus a sequence of
computational steps that transform the input into the output. (Source:
Introduction to Algorithms 3rd Edition by CLRS)
What is time complexity of Binary Search?
Time complexity of binary search is O(Logn). See
Binary Search for more details.
Can Binary Search be used for linked lists?
Since random access is not allowed in linked list, we cannot reach the
middle element in O(1) time. Therefore Binary Search is not possible for
linked lists. There are other ways though, refer
Skip List for example.
How to find if two given rectangles overlap?
Two rectangles do not overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.
See
Find if two rectangles overlap for more details.
How to find angle between hour and minute hands at a given time?
The idea is to take a reference point as 12. Find the angle moved by
hour and minute hands, subtract the two angles to find the angle between
them. See
angle between hour hand and minute hand for more details
When does the worst case of QuickSort occur?
In
quickSort,
we select a pivot element, then partition the given array around the
pivot element by placing pivot element at its correct position in sorted
array.
The worst case of quickSort occurs when one part after partition
contains all elements and other part is empty. For example, if the input
array is sorted and if last or first element is chosen as a pivot, then
the worst occurs. See
http://geeksquiz.com/quick-sort/ for more details.
A sorted array is rotated at some unknown point, how to efficiently search an element in it.
A simple approach is linear search, but we can search in O(Logn) time using
Binary Search. See
Search an element in a sorted and pivoted array for more details.
Other variations of this problem like
find the minimum element or maximum element in a sorted and rotated array.
Given a big string of characters, how to efficiently find the first unique character in it?
The efficient solution is to use character as an index in a count array.
Traverse the given string and store index of first occurrence of every
character, also store count of occurrences. Then traverse the count
array and find the smallest index with count as 1. See
find the first unique character for more details.
How to count inversions in a sorted array?
Two elements arr[i] and arr[j] in an array arr[] form an inversion if
a[i] > a[j] and i < j. How to count all inversions in an unsorted
array. See
Count Inversions in an array for all approaches.
Given a big array, how to efficiently find k’th largest element in it?
There can be many solutions for this. The best solution is to use min
heap. We Build a Min Heap MH of the first k elements. For each element,
after the kth element (arr[k] to arr[n-1]), compare it with root of MH,
if the element is greater than the root then make it root and call
heapify for MH, Else ignore it. Finally, MH has k largest elements and
root of the MH is the kth largest element. See
k largest(or smallest) elements for more details.
Given an array of size n with range of numbers from 1 to
n+1. The array doesn’t contain any duplicate, one number is missing,
find the missing number.
There can be many ways to solve it. The best among is to use XOR. See
Find the missing number for details. There are many variations of this problem like
find the two repeating numbers,
find a missing and a repeating number, etc.
How to write an efficient method to calculate x raise to the power n?
The idea is to use
divide an conquer here to do it in O(Logn) time. See
Write a C program to calculate pow(x,n) for more details.
Given an input string and a dictionary of words, find out
if the input string can be segmented into a space-separated sequence of
dictionary words.
The idea is to use Dynamic Programming. See
Word Break Problem for more details.
Given a row of n coins of values v1 . . . vn, where n is
even. We play a game against an opponent by alternating turns. In each
turn, a player selects either the first or last coin from the row,
removes it from the row permanently, and receives the value of the coin.
Determine the maximum possible amount of money we can definitely win if
we move first.
This is also a Dynamic Programming Question. See
Optimal Strategy for a Game for more details.
You are given an array of sorted words in an arbitrary
language, you need to find order (or precedence of characters) in the
language. For example if the given arrays is {“baa”,
“abcd”, “abca”, “cab”, “cad”}, then order of characters is ‘b’, ‘d’,
‘a’, ‘c’. Note that words are sorted and in the given language “baa”
comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly we
can find other orders.
This can be solved using two steps: First create a graph by processing given set of words, then do
topological sorting of the created graph, See
this for more details.
