Monday 25 June 2012
Bubble Sort
Algorithm:
1: start from the beginning of an array
2: compare current and the next element; if current is bigger than the next one, swap them
3: move one place to the right
4: repeat step 2 till you get to the last element (or, more efficiently till you get to the last highest set in its final location; )
5: goto 1
Complexity: O(N^2)
Bubble sort - Wikipedia
1: start from the beginning of an array
2: compare current and the next element; if current is bigger than the next one, swap them
3: move one place to the right
4: repeat step 2 till you get to the last element (or, more efficiently till you get to the last highest set in its final location; )
5: goto 1
Complexity: O(N^2)
Bubble sort - Wikipedia
Singly Linked List
- Unordered array has fast insertion and slow search and deletion; ordered array has fast search and slow insertion and deletion; arrays have constant size;
Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;
Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.
- Complexity: O(1)
- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;
- Complexity: O(1)
- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;
- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)
Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;
Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.
Unordered (unsorted) Singly Linked List
Operations:
Insertion to the front (push_front):
- Algorithm: item is added at the front of the list- Complexity: O(1)
Insertion to the back (push_back):
- Algorithm: item is added at the back of the list- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;
Removal from the front (pop_front):
- Algorithm: remove the item from the front of the list- Complexity: O(1)
Removal from the end (pop_back):
- Algorithm: remove the item from the back of the list- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;
Search for the item with specific value (key):
- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)
Ordered (sorted) Singly Linked List
Operations:
// TBD
Sunday 24 June 2012
Priority Queue
- has front and rear and items are inserted in the rear and removed from the front
- items are ordered by key value, so that the item with the lowest key (or the highest key) is always at the front; items are inserted in the proper position to maintain the order
- items are ordered by key value, so that the item with the lowest key (or the highest key) is always at the front; items are inserted in the proper position to maintain the order
Deque
Deque is Double Ended Queue: items can be added/removed from the either end of the queue.
- Complexity: O(1)
- Complexity: O(1)
- Complexity: O(1)
- Complexity: O(1)
- Complexity: O(1)
- Complexity: O(1)
Operations:
Insertion to the front (push_front):
- Algorithm: item is added at the front of the queue- Complexity: O(1)
Insertion to the back (push_back):
- Algorithm: item is added at the back of the queue- Complexity: O(1)
Peek at the front:
- Algorithm: return a value of the item from the front of the queue- Complexity: O(1)
Peek at the back:
- Algorithm: return a value of the item from the back of the queue- Complexity: O(1)
Removal from the front (pop_front):
- Algorithm: remove the item from the front of the queue- Complexity: O(1)
Removal from the end (pop_back):
- Algorithm: remove the item from the back of the queue- Complexity: O(1)
Queue
- FIFO concept - First In First Out
- opposite to arrays, only one item can be read or removed at a given time - the oldest item inserted
- its size is predefined: only limited number of items can be added (pushed)
- underlying data structure can be array, vector, linked list
Usage:
- e.g. when performing tasks is slower than the rate tasks are received we want to save tasks in the same order they are received and we want first to execute the oldest tasks: we will put them in the queue
Operations:
Insertion (enqueue):
- Algorithm: item is added at the end (rear) of the queue- Complexity: O(1)
Peek:
- Algorithm: return a value of the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)
Removal (dequeue):
- Algorithm: remove the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)
Stack
- LIFO concept - Last In First Out
- opposite to arrays, only one item can be read or removed at a given time - the last item inserted
- its size is predefined: only limited number of items can be added (pushed)
- stack overflow occurs when a new item is being added but underlying buffer is full
- underlying data structure can be array, vector, linked list
Usage:
- to check whether parentheses ({ }), braces ([ ]) and brackets (( )) are balanced
- to parse arithmetic expressions
- in algorithms applied for other data structures (e.g. traversing binary trees)
- Complexity: O(1)
- Algorithm: return a value of the item from the top of the stack (item that has been added last)
- Complexity: O(1)
- Algorithm: remove the item from the top of the stack (item that has been added last)
- Complexity: O(1)
- opposite to arrays, only one item can be read or removed at a given time - the last item inserted
- its size is predefined: only limited number of items can be added (pushed)
- stack overflow occurs when a new item is being added but underlying buffer is full
- underlying data structure can be array, vector, linked list
Usage:
- to check whether parentheses ({ }), braces ([ ]) and brackets (( )) are balanced
- to parse arithmetic expressions
- in algorithms applied for other data structures (e.g. traversing binary trees)
Operations:
Insertion (push):
- Algorithm: item is added on the top of the stack- Complexity: O(1)
Peek:
- Algorithm: return a value of the item from the top of the stack (item that has been added last)
- Complexity: O(1)
Removal:
- Algorithm: remove the item from the top of the stack (item that has been added last)
- Complexity: O(1)
Ordered (sorted) array
- data is ordered (sorted) in ascending (or descending) key order which enables fast search algorithm - binary search (this is the main reason why we want to keep data sorted)
- can be searched with linear search as well
The range will eventually drop to only one member and if its value matches the searched one - item is found.
As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.
- can be searched with linear search as well
Binary Search Algorithm
Take the idem from the middle of the range (array of sorted elements). If its value is smaller than the searched value then take right sub-array as a new range and repeat this step.The range will eventually drop to only one member and if its value matches the searched one - item is found.
As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.
Operations
Insertion:
- Algorithm: linear search is needed to find the first element smaller than the one to be inserted; item is inserted after it and all bigger items are shifted one place towards the end
- Complexity: O(N) (linear search) + O(N) (shifting) = 2 * O(N) ~ O(N)
Search:
- Algorithm: binary search
- Complexity: O(logN)
Deletion:
- Algorithm: binary search to find the element; once it's found it is removed and all subsequent elements are shifted towards the array beginning
- Complexity: O(logN)(binary search) + O(N) (shifting) ~ O(N)
Unordered (unsorted) array
Array:
- is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values
Array is created with predefined size =>
- if there are less elements than the array size is => memory waste
- if there are more elements that the array size is => program fails
Implementations:
- C-style array
- std::vector
- Complexity: O(N) (because of the search)
- Complexity: O(N)
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)
- Complexity: O(1)
- Complexity: O(N)
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)
- is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values
Array is created with predefined size =>
- if there are less elements than the array size is => memory waste
- if there are more elements that the array size is => program fails
Implementations:
- C-style array
- std::vector
Unordered arrays with no duplicates
Operations:
Insertion
- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed- Complexity: O(N) (because of the search)
Search for a given item (lookup)
- Algorithm: linear search - starts at the beginning and goes through all items till item is found- Complexity: O(N)
Deletion of a given item
- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)
Unordered arrays with duplicates
Operations:
Insertion
- Algorithm: always at the end (at the first vacant position)- Complexity: O(1)
Search for a given item (lookup)
- Algorithm: linear search - starts at the beginning and goes through all items till item is found- Complexity: O(N)
Deletion of a given item
- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)
Write a function which reverses words in a sentence
Algorithm: reverse all characters in the entire sentence and then reverse characters in each word.
Write a function which reverses a string
Algorithm: maintain two pointers - one that goes from the beginning towards the end of the string and another which is going the other way round; each time they move, swap characters at their positions; stop when pointers try to swap their sides;
We can use helper pointer:
Alternatively, we can use just index:
main.cpp:
Output:
We can use helper pointer:
Alternatively, we can use just index:
main.cpp:
Output:
Before reversing: ""
After reversing: ""
Before reversing: "a"
After reversing: "a"
Before reversing: "ab"
After reversing: "ba"
Before reversing: "abc"
After reversing: "cba"
Before reversing: "abcdefg"
After reversing: "gfedcba"
After reversing: ""
Before reversing: "a"
After reversing: "a"
Before reversing: "ab"
After reversing: "ba"
Before reversing: "abc"
After reversing: "cba"
Before reversing: "abcdefg"
After reversing: "gfedcba"
Reversing a string can be achieved by using a helper data structure - stack. Algorithm pushes all characters to the stack and then pops them into the new string which has all characters from an original string reversed.
Write a function which returns a length of a given string
Algorithm: find the last character and return the distance between it and the first one.
We can use helper pointer:
Alternatively, we can use just index:
main.cpp:
Output:
String: ""
Length: 0
String: "a"
Length: 1
String: "ab"
Length: 2
String: "abc"
Length: 3
String: "abcdefg"
Length: 7
Length: 0
String: "a"
Length: 1
String: "ab"
Length: 2
String: "abc"
Length: 3
String: "abcdefg"
Length: 7
Write a code that allocates and then frees an array of seven pointers to functions that return integers.
int (**p) () = new (int (*[7]) ());
delete *p;
http://msdn.microsoft.com/en-us/library/kewsb8ba.aspx
Explain class templates
- Non-type parameters for templates: templates can also have regular typed parameters, similar to those found in functions
- it is possible to set default values or types for class template parameters
- we can create algorithms which evaluate at compile time (factoriel)
Template (C++) (Wikipedia)
- it is possible to set default values or types for class template parameters
- we can create algorithms which evaluate at compile time (factoriel)
Template (C++) (Wikipedia)
Explain concept of Virtual Private Networks
VPN (Wikipedia)
Protocols:
PPTP (Point-to-Point Tunneling Protocol): PPTP uses a control channel over TCP and a GRE tunnel operating to encapsulate PPP packets.
L2TP (Layer 2 Tunneling Protocol): The entire L2TP packet, including payload and L2TP header, is sent within a UDP datagram.
OpenVPN (Wikipedia)
http://openmaniak.com/openvpn.php
With a VPN home computer IP is not seen, VPN server's IP is.
Client side:
- VPN appears to the IP level network code as a normal network device
Saturday 23 June 2012
What accessor is actual in child class if child class changes accessor for virtual function from public (in base class) to private (in inherited class)?
Accessor will be like one in base class (public).
Whenever you declare your function as "virtual", you instruct the compiler to generate a virtual call, instead of the direct call to this function. Whenever you override the virtual function in the descendant class, you specify the behavior of this function (you do not change the access mode for those clients, who rely on the "parent's" interface).
Whenever you declare your function as "virtual", you instruct the compiler to generate a virtual call, instead of the direct call to this function. Whenever you override the virtual function in the descendant class, you specify the behavior of this function (you do not change the access mode for those clients, who rely on the "parent's" interface).
Explain the IS-A and HAS-A class relationships. How would you implement each in a class design?
http://en.wikipedia.org/wiki/Is-a
http://en.wikipedia.org/wiki/Has-a
http://en.wikipedia.org/wiki/Has-a
When does destructor have to be declared as virtual? Why?
http://stackoverflow.com/questions/270917/why-should-i-declare-a-virtual-destructor-for-an-abstract-class-in-c
Does compiler guarantee that initializers will be executed in the same order as they appear on the initialization list?
No. C++ compiler will always initialize your members in the same order as they fall in the declaration.
What is the difference between a copy constructor and an overloaded assignment operator?
class C
{
public:
C();
C(const C& c);
C& operator=(const C& c)
};
C c1; // default c-tor
C c2 = c1; // copy c-tor
C c3(c2); // copy c-tor
C c4; // default c-tor
c4 = c3; // assignment operator
A copy constructor constructs a new object by using the content of the argument object. An overloaded assignment operator assigns the contents of an existing object to another existing object of the same class.
{
public:
C();
C(const C& c);
C& operator=(const C& c)
};
C c1; // default c-tor
C c2 = c1; // copy c-tor
C c3(c2); // copy c-tor
C c4; // default c-tor
c4 = c3; // assignment operator
A copy constructor constructs a new object by using the content of the argument object. An overloaded assignment operator assigns the contents of an existing object to another existing object of the same class.
When are copy constructors called?
A copy constructor is called whenever a new variable is created from an object. This happens in the following cases (but not in assignment).
1) when a function returns an object of that class by value (An object is returned by a function)
2) when the object of that class is passed by value as an argument to a function; A value parameter is initialized from its corresponding argument.
f(p); // copy constructor initializes formal value parameter.
3) when you construct an object based on another object of the same class (Circle c1=c2;)
A variable is declared and initialized from another object, eg:
Person q("Mickey"); // constructor is used to build q.
Person r(p); // copy constructor is used to build r.
Person p = q; // copy constructor is used to initialize in declaration.
p = q; // Assignment operator, no constructor or copy constructor
4) When an object is thrown
5) When an object is caught
6) When an object is placed in a brace-enclosed initializer list
7) When compiler generates a temporary object
1) when a function returns an object of that class by value (An object is returned by a function)
2) when the object of that class is passed by value as an argument to a function; A value parameter is initialized from its corresponding argument.
f(p); // copy constructor initializes formal value parameter.
3) when you construct an object based on another object of the same class (Circle c1=c2;)
A variable is declared and initialized from another object, eg:
Person q("Mickey"); // constructor is used to build q.
Person r(p); // copy constructor is used to build r.
Person p = q; // copy constructor is used to initialize in declaration.
p = q; // Assignment operator, no constructor or copy constructor
4) When an object is thrown
5) When an object is caught
6) When an object is placed in a brace-enclosed initializer list
7) When compiler generates a temporary object
What is a conversion constructor?
A constructor that can be called with a single argument and is used for conversions from the type of the argument to the class type.
What is a default constructor?
Constructor that can be called without passing any arguments. Such constructor either does not have any arguments or default values are define for all its arguments.
Why should you prefer throw/catch mechanism to setjmp/longjmp?
longjmp() does not destroy local objects properly
Class B is derived from class A. Function f is A's friend. Is f B's friend as well?
No. Friendship cannot be inherited.
What is the difference between const char *myPointer and char *const myPointer?
http://www.parashift.com/c++-faq-lite/const-correctness.html
Name four cases where you MUST use initialization list as opposed to assignment in constructors.
1) non-static const data members
2) reference data members
3) if member does not have default c-tor
4) if parent class does not have default c-tor
2) reference data members
3) if member does not have default c-tor
4) if parent class does not have default c-tor
What functions does C++ silently write and call?
- constructors
- destructors
- copy constructors
- assignment operators
- destructors
- copy constructors
- assignment operators
How are prefix and postfix versions of operator++ differentiated?
Postfix has an (unused) int argument in the signature.
How to differentiate (when overloading) between prefix and postfix forms of operator++? (C++)
Why do C++ compilers need name mangling?
Name mangling is the rule according to which C++ changes function's name into function signature before passing that function to a linker. This is how the linker differentiates between different functions with the same name (overloaded functions).
What is function's signature?
Function's signature is its name plus the number and types of the parameters it accepts.
Function signatures do not include return type, because that does not participate in overload resolution.
Function signatures do not include return type, because that does not participate in overload resolution.
Why it's not possible to overload function by the return type?
Because functions can be called without assigning their return value to some variable. If we have
int foo();
and
double foo();
and call it just like
foo();
compiler won't know which overload to call.
int foo();
and
double foo();
and call it just like
foo();
compiler won't know which overload to call.
What is “function overloading”?
Having a functions with the same name but different type and/or number of arguments.
Depending on the types provided, compiler can deduce which overload to call.
Depending on the types provided, compiler can deduce which overload to call.
“mutable” keyword
If we want to allow const member function to change some data member, we have to declare such data member as mutable.
What feature of C++ would you use if you wanted to design a member function that guarantees to leave "this" object unchanged?
Member function that is declared as const.
Const objects can call only const methods.
Non-const objects can call both const and non-const methods.
Const objects can call only const methods.
Non-const objects can call both const and non-const methods.
What is a static member of a class?
Class members can be either data members or methods.
Static data member:
- shared among all instances of the class
- is created even if no instances of the class exist. There is always only a single instance of the static data member!
- its declaration (in the class scope) is NOT a definition at the same time! Therefore in has to be defined in a file scope.
- has external linkage
- requires scope operator in order to be accessed
Static method:
- can be called if there are no instances of the class
- can access only static data members
- requires scope operator in order to be called
Static Data Members (MSDN)
Static data member:
- shared among all instances of the class
- is created even if no instances of the class exist. There is always only a single instance of the static data member!
- its declaration (in the class scope) is NOT a definition at the same time! Therefore in has to be defined in a file scope.
- has external linkage
- requires scope operator in order to be accessed
Static method:
- can be called if there are no instances of the class
- can access only static data members
- requires scope operator in order to be called
Static Data Members (MSDN)
Why were the templates introduced?
When is a template a better solution than a base class?
Inheritance provides specialization in the run-time.
Templates provide specialization in the compile-time.
Containers and algorithms often operate over the various types in the same way and templates allow separating their generic code from the type-dependent code.
Templates allow writing generic (type-independent) code for containers and algorithms. Their specializations (for a given types - template parameters) are created during compile-time.
Virtual function achieves dynamic polymorphism at runtime while template achieves static polymorphism at compile time.
Templates => compile time polymorphism
Abstract classes => run-time polymorphism
Templates provide specialization in the compile-time.
Containers and algorithms often operate over the various types in the same way and templates allow separating their generic code from the type-dependent code.
Templates allow writing generic (type-independent) code for containers and algorithms. Their specializations (for a given types - template parameters) are created during compile-time.
Virtual function achieves dynamic polymorphism at runtime while template achieves static polymorphism at compile time.
Templates => compile time polymorphism
Abstract classes => run-time polymorphism
How do you know that your class needs a virtual destructor?
Base class should have virtual destructor if up-casting takes place and we try to delete child object through base class pointer. In this situation, base class does not need to have any other virtual methods apart from destructor!
If ~A() wasn’t virtual, delete pA would have invoked only ~A() which would cause memory leak.
If ~A() wasn’t virtual, delete pA would have invoked only ~A() which would cause memory leak.
What is the difference between C c; and C c();?
C c; // declares an instance of class C
C c(); // declares a parameterless function c that returns object of type C
C c(); // declares a parameterless function c that returns object of type C
Explain virtual table (v-table) mechanism (dynamic binding/late binding)
As soon as you declare some method in your class as virtual compiler creates a virtual table for that class and adds a pointer to it (vptr) to it. Virtual table is an array whose elements are pointers to virtual functions. Compiler assigns virtual table for each class that implements or declares virtual functions. Virtual method pointer points to the function implementation in the most derived class. Derived classes inherit vptr which is updated and points to virtual table of that particular class.
In the run-time, when we call virtual function through base class pointer which points to derived class object, virtual table of derived class is accessed (via vptr) and examined for function pointer.
In the run-time, when we call virtual function through base class pointer which points to derived class object, virtual table of derived class is accessed (via vptr) and examined for function pointer.
Multimap
Structure:
- multimap generalizes an associative array by allowing multiple values to be associated with a single key.
Implementation:
- often as a map with lists or sets as the map values
Multimap
multimap (sgi)
multimap
Map (associative array, dictionary)
Structure:
- a collection of (key, value) pairs such that each possible key appears at most once in the collection
Operations:
- add (insert): addition of pairs to the collection
- remove (delete): removal of pairs from the collection
- reassign: modification of the values of existing pairs; binding an old key to a new value
- lookup of the value associated with a particular key
Implementations:
- Association list (linked list in which each list element (or node) comprises a key and a value)
- direct addressing into an array (efficient only when the keys are restricted to a narrow range of integers)
- Hash table
- binary search tree
C++:
std::map: Internally, the elements in the map are sorted from lower to higher (or vice versa) key value following a specific strict weak ordering criterion set on construction.
Associative array
- a collection of (key, value) pairs such that each possible key appears at most once in the collection
Operations:
- add (insert): addition of pairs to the collection
- remove (delete): removal of pairs from the collection
- reassign: modification of the values of existing pairs; binding an old key to a new value
- lookup of the value associated with a particular key
Implementations:
- Association list (linked list in which each list element (or node) comprises a key and a value)
- direct addressing into an array (efficient only when the keys are restricted to a narrow range of integers)
- Hash table
- binary search tree
C++:
std::map: Internally, the elements in the map are sorted from lower to higher (or vice versa) key value following a specific strict weak ordering criterion set on construction.
Associative array
What happens if 'delete this' is called in destructor?
delete this recursively calls destructor itself, we get indefinite loop and stack overflow:
Visual Studio catches exception:
Unhandled exception at 0x00880a09 in MiscTests.exe: 0xC00000FD: Stack overflow.
Visual Studio catches exception:
Unhandled exception at 0x00880a09 in MiscTests.exe: 0xC00000FD: Stack overflow.
Friday 22 June 2012
What is the difference between external and internal linkage?
What is external linkage and internal linkage in C++? (SO)
Internal linkage: symbol is visible only within compilation unit where it is defined
External linkage: symbols is visible across multiple compilation units
C specific:
- non-static variables and functions have external linkage by default
- static variables and functions have external linkage
C++ specific:
- global variable, function, class, enumeration, namespace have external linkage by default
Internal linkage: symbol is visible only within compilation unit where it is defined
External linkage: symbols is visible across multiple compilation units
C specific:
- non-static variables and functions have external linkage by default
- static variables and functions have external linkage
C++ specific:
- global variable, function, class, enumeration, namespace have external linkage by default
List and describe OSI model layers
OSI Model
OSI stack:
7. Application Layer:
- HTTP, FTP, DHCP, DNS, RADIUS, SMTP
6. Presentation Layer:
- encryption
- SSL
5. Session Layer:
- establishes, manages and terminates the connections between the local and remote application
- L2TP
4. Transport Layer:
- provides reliable data transport to the upper layers through:
- data flow control
- segmentation/desegmentation
- error control (detection and recovery)
- retransmission on timeout
- protocols can be state- and connection-oriented
- TCP, UDP
3. Network Layer:
- connects hosts from various networks
- routers work at this layer
- IP, ARP
2. Data Link Layer:
- connects hosts within the same network
- physical addressing (MAC address)
- error detection and correction
- PPP, L2TP
1. Physical Layer:
- Ethernet, WLAN, USB, Bluetooth, RS-232
OSI stack:
7. Application Layer:
- HTTP, FTP, DHCP, DNS, RADIUS, SMTP
6. Presentation Layer:
- encryption
- SSL
5. Session Layer:
- establishes, manages and terminates the connections between the local and remote application
- L2TP
4. Transport Layer:
- provides reliable data transport to the upper layers through:
- data flow control
- segmentation/desegmentation
- error control (detection and recovery)
- retransmission on timeout
- protocols can be state- and connection-oriented
- TCP, UDP
3. Network Layer:
- connects hosts from various networks
- routers work at this layer
- IP, ARP
2. Data Link Layer:
- connects hosts within the same network
- physical addressing (MAC address)
- error detection and correction
- PPP, L2TP
1. Physical Layer:
- Ethernet, WLAN, USB, Bluetooth, RS-232
Describe types of packet delivery semantics
Packet forwarding
1) Unicast
- sending of messages to a single network destination identified by a unique address
- a host sends datagrams to another single host identified by a unique IP address
- involves a packet being relayed from link to link along a chain leading from the packet's source to its destination
2) Multicast
- sends data only to interested destinations by using special address assignments
- limits the pool of receivers to those that join a specific multicast receiver group
- a packet is selectively duplicated and copies delivered to each of a set of recipients
3) Broadcast
- transmitting the same data to all possible destinations
- a method of transferring a message to all recipients simultaneously
- transmitting a packet that will be received by every device on the network
- requires a packet to be duplicated and copies sent on multiple links with the goal of delivering a copy to every device on the network
- Ethernet is natural broadcast media — all the nodes are attached to a single long cable and a packet transmitted by one device is seen by every other device attached to the cable. Ethernet nodes implement unicast by ignoring packets not directly addressed to them.
- IPv4
- Broadcast address: A message sent to a broadcast address is typically received by all network-attached hosts, rather than by a specific host.
4) Anycast
5) Geocast
1) Unicast
- sending of messages to a single network destination identified by a unique address
- a host sends datagrams to another single host identified by a unique IP address
- involves a packet being relayed from link to link along a chain leading from the packet's source to its destination
2) Multicast
- sends data only to interested destinations by using special address assignments
- limits the pool of receivers to those that join a specific multicast receiver group
- a packet is selectively duplicated and copies delivered to each of a set of recipients
3) Broadcast
- transmitting the same data to all possible destinations
- a method of transferring a message to all recipients simultaneously
- transmitting a packet that will be received by every device on the network
- requires a packet to be duplicated and copies sent on multiple links with the goal of delivering a copy to every device on the network
- Ethernet is natural broadcast media — all the nodes are attached to a single long cable and a packet transmitted by one device is seen by every other device attached to the cable. Ethernet nodes implement unicast by ignoring packets not directly addressed to them.
- IPv4
- Broadcast address: A message sent to a broadcast address is typically received by all network-attached hosts, rather than by a specific host.
4) Anycast
5) Geocast
What does extern "C" int func(int *, Foo) accomplish?
Assuming this is a declaration of function written in C++ code:
It will turn off "name mangling" for this function so that one can link to code compiled by C compiler. (this C++ function can be used in C code)
Assuming func is a function written in C, this is how it should be declared (prototyped) in C++ code so C++ code can invoke this C function.
It will turn off "name mangling" for this function so that one can link to code compiled by C compiler. (this C++ function can be used in C code)
Assuming func is a function written in C, this is how it should be declared (prototyped) in C++ code so C++ code can invoke this C function.
Related to standard input (cin), how would you implement overloaded operator of extraction (>>) for some custom class?
Input:
3 4
Output:
(1, 2)
(3, 4)
(3, 4)
Extraction/insertion operators can be friends of the our custom class in which case they can access its private members directly:
Thursday 21 June 2012
What are four major concepts of OOP?
1) Abstraction
2) Encapsulation
3) Inheritance
4) Polymorphism
Abstraction:
- the process of separating the how from the what - how an operation is performed inside a class, as opposed to what's visible to the class user
- by abstracting class functionality we make it easier to design a program because we don't need to think about implementation details at too early stage in the design process (1)
References:
Main concepts in OOP (SO)
(1) Data Structures And Algorithms, Robert Lafore
2) Encapsulation
3) Inheritance
4) Polymorphism
Abstraction:
- the process of separating the how from the what - how an operation is performed inside a class, as opposed to what's visible to the class user
- by abstracting class functionality we make it easier to design a program because we don't need to think about implementation details at too early stage in the design process (1)
References:
Main concepts in OOP (SO)
(1) Data Structures And Algorithms, Robert Lafore
Monday 13 February 2012
Strip specified character from a string
Q: Write a function that removes all instances of a specified character from a provided string.
A: Function can do that in-place - it needs to maintain two pointers in the string - one (i) that advances and looks for character and zero termination character and another one (j) which follows the first one and points to the place in the string where the next allowed character will be copied. On the return, input string has the same or smaller size than original string.
Thursday 26 January 2012
How does class members accessibility depend on their access specifiers and class inheritance type?
inheritance type
base class access specifier → derived class access specifier
[ accessible in derived class method? | accessible through derived class object? ]
public:
public → public [yes, yes]
protected → protected [yes, no]
private → private [yes, no]
protected:
public → protected [yes, no]
protected → protected [yes, no]
private → private [no, no]
private:
public → private [yes, no]
protected → private [yes, no]
private → private [no, no]
base class access specifier → derived class access specifier
[ accessible in derived class method? | accessible through derived class object? ]
public:
public → public [yes, yes]
protected → protected [yes, no]
private → private [yes, no]
protected:
public → protected [yes, no]
protected → protected [yes, no]
private → private [no, no]
private:
public → private [yes, no]
protected → private [yes, no]
private → private [no, no]
Sunday 22 January 2012
Subscribe to:
Posts (Atom)