How to prepare for Interviews

Design Patterns

Cloud Design patterns https://msdn.microsoft.com/en-us/library/dn600223.aspx

• Visitor Pattern 
• Helps to traverse a structured data without actually modifying the structure
• Example traversing a directory structure with one visitor could be FileVisitor and other could be DirectoryVisitor. Base Class is Visitor and FileVisitor and DirectoryVisitor derives from it. FileSystem could have a function which will set Visitor.
• Link http://en.wikipedia.org/wiki/Visitor_pattern
• Template Pattern
• Defines the steps a process should take
• Any Two player Game could be defined as init, makeMove, announceWinner, shutdown etc. Chess could derive from Game.
•  Link http://en.wikipedia.org/wiki/Template_method_pattern
• Strategy Pattern
• Allow the algorithm to be changed in runtime.
• A client wanting to sort an array could set mergeSort or radixSort depending upon his needs. Base class only defines Sort with a method SortArray.
• Link http://en.wikipedia.org/wiki/Strategy_pattern
•  State Pattern
• Algorithm changes based on the state of the system
• Say in game of chess algorithms used at the start of the game is different from one in the end. So when the state changes to end the algorithm also changes.
• Link http://en.wikipedia.org/wiki/State_pattern
• Observer Pattern
• Some classes are interested in the changes in the subject.
• Say compiler when it parses the code could find many things in it. One could be say a compile time error, other could be say a comment. Various components would like to observe these notifications.
• link http://en.wikipedia.org/wiki/Observer_pattern
• Memento Pattern
• Restore the state of an object to a previous state
• Undo could use this pattern. Cookies etc may use this pattern.
• Link http://en.wikipedia.org/wiki/Memento_pattern
• Iterator Pattern
• Iterates over an object one by one
• Iterating over a list of objects encapsulated inside LinkedList.
• Link http://en.wikipedia.org/wiki/Iterator_pattern
• Chain of Responsibility
• In object-oriented design, the chain-of-responsibility pattern is a design pattern consisting of a source of command objects and a series of processing objects.
• A system has a logging facility, depending upon the failure urgency various handlers could actually use it or pass it to the next higher handler. A low urgency message could just be printed, but a higher one could send an email/pager to the owner of the system.
• Link http://en.wikipedia.org/wiki/Chain-of-responsibility_pattern
• Command Pattern
• In object-oriented programming, the command pattern is a behavioral design pattern in which an object is used to represent and encapsulate all the information needed to call a method at a later time.
• Key presses and Mouse events could be placed inside an object and later sent.
• Link http://en.wikipedia.org/wiki/Command_pattern
• Interpreter Pattern
• In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language.
• Link http://en.wikipedia.org/wiki/Interpreter_pattern
• Proxy Pattern
• A proxy, in its most general form, is a class functioning as an interface to something else. The proxy could interface to anything: a network connection, a large object in memory, a file, or some other resource that is expensive or impossible to duplicate.
• http://en.wikipedia.org/wiki/Proxy_pattern
• Bridge Pattern
• The bridge pattern is a design pattern used in software engineering which is meant to "decouple an abstraction from its implementation so that the two can vary independently"
• Draw circle could be an abstraction and  various drawing algorithms could be implementors.
• Link http://en.wikipedia.org/wiki/Bridge_pattern
• Mediator Pattern
• Define an object that encapsulates how a set of objects interact. Mediator promotes loose coupling by keeping objects from referring to each other explicitly, and it lets you vary their interaction independently.
• Link http://en.wikipedia.org/wiki/Mediator_pattern
• Adapter Pattern
• often referred to as the wrapper pattern or simply a wrapper
• A api returning asynchrounouly and we want to make it sychronous to the class users. We can write a wrapper over the existing asynch impl and give a synch api.
• Link http://en.wikipedia.org/wiki/Adapter_pattern
• Object pool Pattern
• The object pool pattern is a software creational design pattern that uses a set of initialized objects kept ready to use, rather than allocating and destroying them on demand
• Link http://en.wikipedia.org/wiki/Object_pool_pattern
• Singleton Pattern
• Specifies an object can have only one instance.
• Logger could be one such class.
• Link http://en.wikipedia.org/wiki/Singleton_pattern
• Prototype Pattern
• It is used when the type of objects to create is determined by a prototypical instance, which is cloned to produce new objects
• Link http://en.wikipedia.org/wiki/Prototype_pattern
• Factory Pattern
• The factory method pattern is an object-oriented creational design pattern to implement the concept of factories and deals with the problem of creating objects (products) without specifying the exact class of object that will be created.
• Link http://en.wikipedia.org/wiki/Factory_method_pattern
• Abstract Factory
• It provides a way to encapsulate a group of individual factories that have a common theme without specifying their concrete classes.
• Link http://en.wikipedia.org/wiki/Abstract_factory_pattern
• Composite Pattern
• The intent of a composite is to "compose" objects into tree structures to represent part-whole hierarchies.
• Directory, file is an example of composite pattern. Directory can contain a file or a directory.
• Link http://en.wikipedia.org/wiki/Composite_pattern
• Facade Pattern
• A facade is an object that provides a simplified interface to a larger body of code, such as a class library
• Link http://en.wikipedia.org/wiki/Facade_pattern

Sorting Algorithms

Bubble Sort

Sort by comparing two adjacent items and swapping them if first is greater than second. Do this for each element till the end.

Selection Sort

The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list

Insertion Sort

It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list.

Merge Sort

Sort by dividing the array into two equal halves and then merging the sorted array.

Heap Sort

Sorts an array by putting elements on a heap and then popping them back to get the sorted list.

Quick Sort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it.

Counting Sort

Counting sort is applicable when each input is known to belong to a particular set, S, of possibilities. The algorithm runs in O(|S| + n) time and O(|S|) memory where n is the length of the input. It works by creating an integer array of size |S| and using the ith bin to count the occurrences of the ith member of S in the input.

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm

Radix Sort

Radix sort is an algorithm that sorts numbers by processing individual digits. n numbers consisting of k digits each are sorted in O(n · k) time

Topological Sort

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

String searching algorithm

Naive Searching Algorithm

Match each character of pattern with text from start index 0, if match fails start from the next position in the text. 

 O(m*n)
Let m be the length of the pattern and let n be the length of the searchable text.

Rabin Karp Algoritm

 Compare hashes instead of text. If hash of pattern and substring of text matches then compare the individual characters. Can be used to match multiple patterns. In case of multiple patterns we can precompute the hashes of the patterns and compare it with the actual text.

average Θ(n+m),
worst Θ((n−m+1) m)

Finite state machine based searching--TODO

Create a FSM using the pattern and run the input on it. When we reach the acceptance state we can assume that we have got a match.

FSM can be created using

Boyer–Moore string search algorithm --TODO

3 main ideas
–right to left scan
–bad character rule
–good suffix rule

Definition
For each character x in the alphabet, let R(x) denote the position of the right-most occurrence of character x in P. 
R(x) is defined to be 0 if x is not in P
Usage
Suppose characters in P[i+1..n] match T[k+1..k+n-i] and P[i] mismatches T[k].
Shift P to the right by max(1, i - R(T[k])) places
Hopefully more than 1
 

http://stackoverflow.com/questions/6207819/boyer-moore-algorithm-understanding-and-example

 http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides03.pdf

KMP Algorithm

String matching using longest suffix which is prefix of the pattern.

KMP-MATCHER(T, P)
 1 n ← length[T]
 2 m ← length[P]
 3 π ← COMPUTE-PREFIX-FUNCTION(P)
 4 q ← 0                          ▹Number of characters matched.
 5 for i ← 1 to n                 ▹Scan the text from left to right.
 6      do while q > 0 and P[q + 1] ≠ T[i]
 7             do q ← π[q]    ▹Next character does not match.
 8         if P[q + 1] = T[i]
 9            then q ← q + 1      ▹Next character matches.
10         if q = m                    ▹Is all of P matched?
11            then print "Pattern occurs with shift" i - m
12                 q ← π[q]    ▹Look for the next match.

COMPUTE-PREFIX-FUNCTION(P)
 1 m ← length[P]
 2 π[1] ← 0
 3 k ← 0
 4 for q ← 2 to m
 5      do while k > 0 and P[k + 1] ≠ P[q]
 6             do k ← π[k]
 7         if P[k + 1] = P[q]
 8            then k ← k + 1
 9         π[q] ← k
10 return π

 http://www.cs.ubc.ca/labs/beta/Courses/CPSC445-08/Handouts/kmp.pdf 

Bit Hacks

Set union

A | B

Set intersection

A & B

Set subtraction

A & ~B

Set negation

ALL_BITS ^ A

Set bit

A |= 1 << bit

Clear bit

A &= ~(1 << bit)

Test bit

(A & 1 << bit) != 0

Compute modulus division by a power-of-2-number

/* This function will return n % d.

   d must be one of: 1, 2, 4, 8, 16, 32, … */

unsigned int getModulo(unsigned int n, unsigned int d)

{

  return ( n & (d-1) );

}   


Compute the sign of an integer:

sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));  // if v < 0 then -1, else +1

Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2 

bool f; // the result goes here 

f = (v & (v - 1)) == 0;

Detect if two integers have opposite signs

bool f = ((x ^ y) < 0); // true iff x and y have opposite signs

Compute the integer absolute value (abs) without branching

int v; // we want to find the absolute value of v 

unsigned int r; // the result goes here 

int const mask = v >> sizeof(int) * CHAR_BIT - 1; 

r = (v + mask) ^ mask;

Counting bits set, Brian Kernighan's way

unsigned int v; // count the number of bits set in v 

unsigned int c; // c accumulates the total bits set in v 

for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set }

 Check if the integer is even or odd.

 if ((x & 1) == 0) { x is even } else { x is odd } 

Toggle the n-th bit.

y = x ^ (1< 

Isolate the rightmost 1-bit.

y = x & (-x)

Right propagate the rightmost 1-bit.

y = x | (x-1)

Isolate the rightmost 0-bit.

y = ~x & (x+1)

Source: 

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

http://www-graphics.stanford.edu/~seander/bithacks.html#OperationCounting 

http://video.mit.edu/watch/lecture-2-bit-hacks-1839/

Divisibility Rules

Divisibility by 7 can be checked by a recursive method. A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7. In other words, subtract twice the last digit from the number formed by the remaining digits. Continue to do this until a small number.

Divisibility by 3: if sum of digits is divisible by 3
Divisibility by 9: if sum of digits is divisible by 9
Divisibility by 2,4,8: Last 1,2,3 digits are divisible by 2,4,8.
Divisibility by 11: alternate digits sum difference is 0.

Divisibility by 13

Remainder Test 13 (1, −3, −4, −1, 3, 4, cycle goes on.) If you are not comfortable with negative numbers, then use this sequence. (1, 10, 9, 12, 3, 4)
Multiply the right most digit of the number with the left most number in the sequence shown above and the second right most digit to the second left most digit of the number in the sequence. The cycle goes on.
Example: What is the remainder when 321 is divided by 13?
Using the first sequence,
Ans: 1 × 1 + 2 × −3 + 3 × −4 = 9

C++

The "diamond problem" (sometimes referred to as the "deadly diamond of death"^[3]) is an ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If D calls a method defined in A (and does not override the method), and B and C have overridden that method differently, then from which class does it inherit: B, or C?. Virtual inheritance is used in c++ to solve this problem.

Vtable for virtual functions. Each base class has a virtual function pointer. Each class has a function table. When an object is constructed virtual function pointer is set to the classes function table. Whenever a virtual function is called the table is looked up to find the correct function pointer. Function table is filled by checking the lowest override.

Other Topics

Distributed Locking

Link

Token-based approach:
◮ A unique token is shared among the sites.
◮ A site is allowed to enter its CS(Critical Section) if it possesses the token.
◮ Mutual exclusion is ensured because the token is unique.

Non-token based approach:
◮ Two or more successive rounds of messages are exchanged among the sites to
determine which site will enter the CS next.

Quorum based approach:
◮ Each site requests permission to execute the CS from a subset of sites (called
a quorum).
◮ Any two quorums contain a common site.
◮ This common site is responsible to make sure that only one request executes
the CS at any time.
https://en.wikipedia.org/wiki/Raymond's_algorithm
https://en.wikipedia.org/wiki/Ricart%E2%80%93Agrawala_algorithm

NP 

NP -> Verifiable in polynomial Time, no polynomial time algorithm exists

P-> Solvable in polynomial time
NP-complete-if it is in NP and is as "hard" as any problem in NP

http://en.wikipedia.org/wiki/NP-hard

Things to do:

1. http://www.parashift.com/c++-faq/index.html

2. http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi

3.http://en.wikipedia.org/wiki/Levenshtein_distance

Topics to cover

1. puzzles??

   1.1 wu puzzles easy

2. algorithms

   2,1 wu puzzles cs/microsoft

   2.2 dsalgo

   2.3 cormen

   2.4 spoj/hackerearth/codechef

3. past projects

4. C++

   4.1 templates

   4.2 standard c++ questions

   4.3 c++ faq

   4.4 Bit manipulation

5. Threads/OS/

   5.1 threaded programming

   5.2 solve thread problems

   5.3 go through basic os concepts.

6. Resume refresh

   6.1 update resume

   6.2 add details about new projects

   6.3 fair-ometer, mockint, chess puzzles app. add to resume

7. apply to jobs

8. Misc

     8.1 Think about why do u want to change company

     8.2 why not u tried internal jobs

     8.3 why do u want to join our company etc etc.

     8.4 Design patterns

     8.5 Python

• Scalability
• Architecture Design
• Capacity Planning
• Platform Selection
• Strategy and Vision
• Development Methodologies
• Internationalization
• Advanced Security concepts (CSRF, XSRF, DDOS mitigation and more)
• OS Concepts
• Agile Processes / CI / Automated Testing
• Algorithms
• OOPs
• Design Patterns
• Networking and TCP/IP
• HTTP
• Sockets programming
• MVC frameworks
• ORM frameworks
• HTML, CSS
• Javascript / Ajax / RIA
• RDBMs (Simple and Advanced)
• Multi-threading
• Agile development / Development methodologies
• Unit Testing / Mocking
• Usability
• Web Services / SOA / REST / SOAP / Remoting
• Security