Iterative Traversal of Binary Tree

Preorder Iterative

1) Create an empty stack nodeStack and push root node to stack. 2) Do following while nodeStack is not empty.
….a) Pop an item from stack and print it.
….b) Push right child of popped item to stack
….c) Push left child of popped item to stack

Inorder Iterative

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = popped_item->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Post Order Iterative 

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack
   2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack

Qn: Given a list of integers, find the highest value that can be obtained by concatenating these integers together?

Ans:
The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers. Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

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

Sort Array

Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).

Solution:
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)

Maximum Sub Sequence of 1s and 0s

You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space algorithm to find the maximum sub sequence which has equal number of 1s and 0s.

Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself

2)1101000
The longest sub sequence that satisfies the problem is 110100

Solution:
1. Worst case algorithm is to list all possible sub sequences and then find the one which is maximum.

2. Take another array which contains the sum of numbers of the orig array
new[i] = orig[0]+...orig[i];
Now we have to find out the sum of each subarray. If the sum of the subarray is half the number of element in the subarray, then check if this subarray can replace the previous maximum. If it can we will replace the current max with this subarray.

Each subarray sum can be found using the following formula
Sum of all elements from j till i = sum[i, j] = new[i] - new[j-1]

Unlucky Numbers

There are few numbers considered to be unlucky(It contains only 4 and 7. ). Our goal is to find count of such numbers in the range of positive integers a and b.
For Example:
Input:: a = 10 b = 20
Output:: 0

Input:: a = 30 b = 50
Output:: 2 (44, 47)

Source: Topcoder

Solution:
Idea is to find the number of digits in a, let that be n. now
1. Start with a number which has n 4s, so if n is 2 start with 44, if n i 5 start with 44444.
2. increment the count.
3. If the curr number greater than b break and print the count.
4. Now start with the curr digit(last digit) of curr number, if the curr is 4 change it to 7 and
go to step2. if it is 7 set the curr digit to 4 and go to next digit to the left. do this step 4 again
until u reach a number greater than b, or reach a place where all digits are 7s and then u add 4
to it and go to step2.


Example:
a = 10 b = 500
actual numbers are 44, 47, 74, 77, 444, 447, 474, 477

Ideal string

An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the "BAOOOA" is an ideal string (quotes for clarity only). The letter 'B' appears 1 time, and its index is 1. The letter 'A' occurs 2 times and its first index is 2. The letter 'O' occurs 3 times and its first index is 3.

Given an int length, return the lexicographically smallest ideal string of that length containing only uppercase letters ('A'-'Z'). If there are no such ideal strings of that length, return an empty String instead.

Source: TopCoder

Solution:
To solve this problem we need to come up with a formula which tells us whether it is possible to have such a string at all or not. As we can see that element at index 1 must appear once, index 2 must appear twice and index n must appear n times.

So total length of string = length = 1 + 2 + .... n
hence n*(n+1)/2 = length
We should be able to represent the length as above, if we cannot then empty string can be returned.
If we can represent we should do the following:
1. Find n from the above equation.
2. Fill "A" in the 1st index and fill the remainder(0) of "A" in the n+1 th index.
3. Fill "B" in the 2nd index and fill the remainder(1) of "B" in the index after the previous fill.
3. Fill "C" in the 3rd index and fill the remainder(2) of "C" in the index after the previous fill.
........
n. Fill "n" in the nth index and fill the remainder (n-1) of "n" in the index after previous fill

After the above operation is done, print the array.

Next Palindrome Problem

Find the next palindrome. Input is an integer and output should be the palindrome integer which is higher than the input.

Example:
Input: 12345
Output:12421
Input:111
Output: 121

Solution:
Let the Input be "ABCDEFGH". Now divide it into two equal parts "ABCD" and "EFGH". let us call the higher part as "ABCD" and lower part as "EFGH". Now reverse the higher part to get "DCBA". Check if "DCBA" greater than "EFGH" or not.
Case 1: DCBA is greater than EFGH
return "ABCDDCBA" as the output.
Case 2: DCBA is lower than or equal to EFGH
Add 10000 to "ABCDEFGH" to "HIJKEFGH" and apply the above logic to return "HIJKKJIH"
10000 is added to ensure that the middle digit is changed. Added index is generally 10^(numOfDigits/2).

Example 1:
112100
higher = 112
lower = 110
reverse higher = 211
So output 112211

Example 2:
1121
higher = 11
lower = 21
reverse higher = 11
So add 100 to change the lowest of the higher part. to get 1221. So output 1221 as the next palindrome.

Example 3:
45621
higher = 45
lower = 21
reverse higher = 54
so return 45654


Example 4:
45678
higher = 45
lower = 78
reverse higher = 54
so add 100 to get 45778 . so return 45754.