A. (based on 'Cracking the Coding Interview' book)
int fibonacci (int i)
{
if ( (i == 0) || (i == 1) ) return i;
return fibonacci (i-1) + fibonacci (i-2);
}
complexity: O(2^n).
Top-Down Dynamic Programming (or Memoization).
We can tweak this function to run in O(n) time. We simply cache the results of fibonacci(i) between calls.
int fibonacci (int n)
{
return fibonacci (n, new int [n+1]);
}
int fibonacci (int n, int[] memo)
{
if ( (i == 0) || (i == 1) ) return i;
if (memo[i] == 0)
memo [i] = fibonacci (i-1, memo) + fibonacci (i-2, memo);
return memo[i];
}
Q. How can you make C behave in an object-oriented way?
A.
Q. What is a deadlock?
Q. What can you do to ensure you do not get to a deadlock situation?
A.
(based on ‘Operating Systems’ by Deitel, Deitel and Choffnes)
Coffman, Elphick and Shoshani proved that the following four conditions are necessary for deadlock to exist:
- A resource may be acquired exclusively by only one process at a time (mutual exclusion condition).
- A process that has acquired an exclusive resource may hold that resource while the process waits to obtain other resources (wait-for condition, also called the hold-and-wait condition).
- Once a process has obtained a resource, the system cannot remove it from the process’s control until the process has finished using the resource (no-preemption condition).
- Two or more processes are locked in a “circular chain” in which each process is waiting for one or more resources that the next process in the chain is holding (circular-wait condition).
All four conditions are necessary and sufficient for deadlock to exist.
Havender, observing that a deadlock cannot occur if a system denies any of the four necessary conditions, suggested the following deadlock prevention strategies:
- Each process must request all its required resources at once and cannot proceed until all have been granted.
- If a process holding certain resources is denied a further request, it must release its original resources and, if necessary, request them again together with additional resources.
- A linear ordering of resources must be imposed on all processes; i.e. if a process has been allocated certain resources, it may subsequently request only those resources later in the ordering.
Note that Havender presents three strategies, not four. The first necessary condition, namely that processes claim exclusive use of the resources they require, is not one that we want to break, because we specifically want to allow dedicated (i.e. serially reusable) resources.
Q. What is encapsulation? What is abstraction?
A. (based on ‘Large-Scale C++ Software Design’ by John Lakos)
An abstraction is an abstract specification of a collection of objects and related behaviors that fulfills a common purpose.
(based on 'How to Program C++ ' by Deitel & Deitel)
Classes normally hide their implementation details from the clients of the classes. This is called information hiding. The programmer may create a stack class and hide from its clients the implementation of the stack. Stacks can easily be implemented with arrays or linked lists. A client of a stack class need not know how the stack is implemented. The client simply requires that when data items are placed in the stack, the data items will be recalled in LIFO order. Describing the functionality of a class independent of its implementation is called data abstraction and C++ classes define so-called abstract data types (ADTs).
(based on 'C++ FAQs' by Cline, Lomow & Girou)
Encapsulation protects abstractions.
Encapsulation provides the explicit boundary between an object's abstract interface (its abstraction) and its internal implementation details. Encapsulation puts the implementation details "in a capsule". Encapsulation tells users which features are stable, permanent services of the object and which features are implementation details that are subject to change without notice.
Encapsulation helps the developers of an abstraction: it provides the freedom to implement the abstraction in any way consistent with the interface. (Encapsulation tells developers exactly what users can and cannot access.) Encapsulation also helps the users of an abstraction: it provides protection by preventing dependence on volatile implementation details.
Abstraction provides business value; encapsulation "protects" these abstractions. If a developer provides a good abstraction, users won't be tempted to peek at the object's internal mechanisms. Encapsulation is simply a safety feature that reminds users not to stray over the line inadvertently.
Q. In SQL, what is BCP?
A.
You use the bcp (bulk copy program) tool to address the bulk movement of data. This utility is bidirectional, allowing for the movement of data into and out of a SQL Server database.
Q. What is the difference between encryption and hashing?
Cryptographic systems tend to involve both an algorithm and a secret value. The secret value is known as the key.
A hash (also known as a message digest) is a one-way function. It is considered a function because it takes an input message and produces an output. It is considered one-way because it’s not practical to figure out what input corresponds to a given output. For a message digest function to be considered cryptographically secure, it must be computationally infeasible to find a message that has a given prespecified message digest, and it similarly should be impossible to find two messages that have the same message digest. Also, given a message it should be impossible to find a different message with the same message digest.
Q. How do you ensure that a class has no objects instantiated?
Q. How do you ensure that a class has only 1 object instantiated?
A. (based on 'Design Patterns')
To ensure a class only has one instance, and provide a global point of access to it. (Solution is to) make the class itself responsible for keeping track of its sole instance. The class can ensure that no other instance can be created (by intercepting requests to create new objects), and it can provide a way to access the instance. This is the Singleton pattern.
class Singleton {
public:
static Singleton* Instance():
protected:
Singleton();
private:
static Singleton* _instance;
}
Singleton* Singleton::_instance = 0;
Singleton* Singleton::Instance() {
if (_instance == 0) {
_instance = new Singleton;
}
return _instance;
}
Q. Do you need a lock to implement a single producer - single consumer process?
A. (based on 'Operating System Concepts' by Silberschatz, Galvin, Gagne, Ch. 4 - Processes)
The unbounded-buffer producer-consumer problem places no practical limit on the size of the buffer. The consumer may have to wait for new items, but the producer can always produce new items. The bounded-buffer producer-consumer problem assumes a fixed buffer size. In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.
The buffer may either be provided by the operating system through the use of an IPC facility, or explicitly coded by the application programmer with the use of shared memory. Let us illustrate a shared-memory solution to the bounded buffer problem. The producer and consumer processes share the following variables:
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in=0;
int out=0;
The shared buffer is implemented as a circular array with two logical pointers: in and out. The buffer is empty when in==out; the buffer is full when ((in+1) % BUFFER_SIZE) == out.
The producer process has a local variable nextProduced in which the new item to be produced is stored:
while (1) {
/* produce an item in nextProduced */
while (((in+1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
The consumer process has a local variable nextConsumed in which the item to be consumed is stored:
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item in nextConsumed */
}
The scheme allows at most BUFFER_SIZE - 1 items in the buffer at the same time.
Q. What are the methods to allocate memory in C? How are they different?
A. malloc, calloc, realloc.
malloc returns a pointer to (n bytes of) uninitialized storage. With calloc, the storage is initialized to zero.
(based on 'Expert C Programming', Ch 7)
The function calloc is like malloc, but clears the memory to zero before giving you the pointer. The function realloc() changes the size of a block of memory pointed to, either growing or shrinking it, often by copying the contents somewhere else and giving you back a pointer to the new location. This is useful when growing the size of tables dynamically.
Q. What is encapsulation? What is abstraction?
A. (based on ‘Large-Scale C++ Software Design’ by John Lakos)
Encapsulation is a term used to describe the concept of hiding implementation details behind a procedural interface. Comparable terms include information hiding or data hiding. Directly accessing a data member of a class violates encapsulation.
An abstraction is an abstract specification of a collection of objects and related behaviors that fulfills a common purpose.
(based on 'How to Program C++ ' by Deitel & Deitel)
Classes normally hide their implementation details from the clients of the classes. This is called information hiding. The programmer may create a stack class and hide from its clients the implementation of the stack. Stacks can easily be implemented with arrays or linked lists. A client of a stack class need not know how the stack is implemented. The client simply requires that when data items are placed in the stack, the data items will be recalled in LIFO order. Describing the functionality of a class independent of its implementation is called data abstraction and C++ classes define so-called abstract data types (ADTs).
(based on 'C++ FAQs' by Cline, Lomow & Girou)
Encapsulation protects abstractions.
Encapsulation provides the explicit boundary between an object's abstract interface (its abstraction) and its internal implementation details. Encapsulation puts the implementation details "in a capsule". Encapsulation tells users which features are stable, permanent services of the object and which features are implementation details that are subject to change without notice.
Encapsulation helps the developers of an abstraction: it provides the freedom to implement the abstraction in any way consistent with the interface. (Encapsulation tells developers exactly what users can and cannot access.) Encapsulation also helps the users of an abstraction: it provides protection by preventing dependence on volatile implementation details.
Abstraction provides business value; encapsulation "protects" these abstractions. If a developer provides a good abstraction, users won't be tempted to peek at the object's internal mechanisms. Encapsulation is simply a safety feature that reminds users not to stray over the line inadvertently.
Q. In SQL, what is BCP?
A.
You use the bcp (bulk copy program) tool to address the bulk movement of data. This utility is bidirectional, allowing for the movement of data into and out of a SQL Server database.
Q. What is the difference between encryption and hashing?
A. (based on ‘Network Security’, by Kaufman, Perlman and Speciner)
A message in its original form is known as plaintext or cleartext. The mangled information is known as ciphertext. The process for producing ciphertext from plaintext is known as encryption. The reverse of encryption is called decryption.Cryptographic systems tend to involve both an algorithm and a secret value. The secret value is known as the key.
A hash (also known as a message digest) is a one-way function. It is considered a function because it takes an input message and produces an output. It is considered one-way because it’s not practical to figure out what input corresponds to a given output. For a message digest function to be considered cryptographically secure, it must be computationally infeasible to find a message that has a given prespecified message digest, and it similarly should be impossible to find two messages that have the same message digest. Also, given a message it should be impossible to find a different message with the same message digest.
Q. How do you ensure that a class has no objects instantiated?
Q. How do you ensure that a class has only 1 object instantiated?
A. (based on 'Design Patterns')
To ensure a class only has one instance, and provide a global point of access to it. (Solution is to) make the class itself responsible for keeping track of its sole instance. The class can ensure that no other instance can be created (by intercepting requests to create new objects), and it can provide a way to access the instance. This is the Singleton pattern.
class Singleton {
public:
static Singleton* Instance():
protected:
Singleton();
private:
static Singleton* _instance;
}
Singleton* Singleton::_instance = 0;
Singleton* Singleton::Instance() {
if (_instance == 0) {
_instance = new Singleton;
}
return _instance;
}
Q. Do you need a lock to implement a single producer - single consumer process?
A. (based on 'Operating System Concepts' by Silberschatz, Galvin, Gagne, Ch. 4 - Processes)
The unbounded-buffer producer-consumer problem places no practical limit on the size of the buffer. The consumer may have to wait for new items, but the producer can always produce new items. The bounded-buffer producer-consumer problem assumes a fixed buffer size. In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.
The buffer may either be provided by the operating system through the use of an IPC facility, or explicitly coded by the application programmer with the use of shared memory. Let us illustrate a shared-memory solution to the bounded buffer problem. The producer and consumer processes share the following variables:
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in=0;
int out=0;
The shared buffer is implemented as a circular array with two logical pointers: in and out. The buffer is empty when in==out; the buffer is full when ((in+1) % BUFFER_SIZE) == out.
The producer process has a local variable nextProduced in which the new item to be produced is stored:
while (1) {
/* produce an item in nextProduced */
while (((in+1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
The consumer process has a local variable nextConsumed in which the item to be consumed is stored:
while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item in nextConsumed */
}
The scheme allows at most BUFFER_SIZE - 1 items in the buffer at the same time.
Q. What are the methods to allocate memory in C? How are they different?
A. malloc, calloc, realloc.
malloc returns a pointer to (n bytes of) uninitialized storage. With calloc, the storage is initialized to zero.
(based on 'Expert C Programming', Ch 7)
The function calloc is like malloc, but clears the memory to zero before giving you the pointer. The function realloc() changes the size of a block of memory pointed to, either growing or shrinking it, often by copying the contents somewhere else and giving you back a pointer to the new location. This is useful when growing the size of tables dynamically.
