Telephonic :
1) How to limit the scope of a variable -> I explained about static
2) what is linked list, implement using array and linked list (which is better single or doubly? ) and space and runtime complexities of push() and pop().

O(1)
3) In a directed graph how can you find a cycle? is it possible to find using BFS, why BFS is preferred over DFS.

DFS

int findkth(vector<int> nums, int start, int end, int k) {
    if (nums.size()== 0) {
        return -1;
    }
    return quickSelect(nums, 0, nums.size()-1, k);
}
int quickSelect(vector<int>& nums. int start, int end, int k) {
    int left = start;
    int right = end;
    if (left == right) {
    return nums[left];
    }
    int pivot = nums[(left+right)/2];
    while (left <= right) {
        while (left <= right && nums[left] > pivot) {
        left++;
        }
        while (left <= right && nums[right] < pivot {
        right++;
        }
        if (left <= right) {
            int temp .= nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
            right--;
        } 
    }
    if (k <= right - start + 1) {
        return quickSelect(nums, start, right, k);
    }
    if (k >= left - start + 1) {
        return quickSelect(nums, left, end, k - (left - start));
    }
    return nums[right+1];
}

Face to Face
Round 1 :
1) Automata basic questions (i din remember automata.. the guy helped me in this one)
make a State diagram for a*b*c expression.
2) convert it into deterministic diagram
3) state diagram for a[POW(n)]b[POW(n)]c (use of counter is required)
4) n jobs are given , their dependency list is given how will you schedule them ? (I explained using modified BFS)
5)If a graph DS is given, how will you dump that into memory and retrieve it again ?

Round 2 :
1) Write code for string reversal.
2) Write code for linked list implementation. push and pop

void push (ListNode** head, int data) {
    ListNode* newNode = new ListNode (data);
    newNode->next = *head;
    *head = newNode;
}

int pop(ListNode** head) {
    ListNode* deleteNode = *head;
    int val = deleteNode->data;
    *head = deleteNode->next;
    delete deleteNode;
    return val;
}

3) Puzzle – 23 coins are given and two player are there. anyone can pick 1 to 4 coins at a time.
One who picks the last coin wins.. Find algo for it.

n%5

Round 3 :
1) In a project, i have an api which takes some parameters and returns a string.
How will you handle the memory allocation done inside this API ? – Ans is you make it static.

2) Puzzle – two ropes are given. each burn in 60 mins. how to count 45 mins from it.

Round 4:
1) General questions about my current work and projects done with the senior manager.

Round 1 – Telephonic

1. Tell me about yourself

2. What is the difference between C and C++

3. Is a C program faster than a C++ compiled program.

4. What is UNION in C?

5. What all type of sorting algorithms do you know?

6. What does the term “object oriented programming mean?”

refers to a programming methodology based on objects, instead of just functions and procedures. These objects are organized into classes, which allow individual objects to be group together.

1. What is the difference between overloading and overriding?

2. About my present work.

I was then called for face to face interviews; I did not delay and fixed it the day after today.

Round 2 – F2F

1. What does your current company’s software do? About the current company?

2. Compilation of a C/C++ code. He gave me a dummy program. He then asked me to use #ifdef #endif in the header files, then asked its uses.

3. Different segments of memory. Where all can a variable be allocated?

4. There is a stack where push and pop operation are happening. At any point of time user will query secondMin(). This API should return second minimum present in the stack.

5. Given a number, tell number of bits set in the number in its binary representation. Ex. N = 5, Ans – 2 (101 has 2 1’s in it)

6. Reversing a string recursively, iteratively. He then asked me to rewind the whole stack or trace the recursive version for examples – “hello” and “ABCD”.

7. Cell padding concept in struct/class.

8. Traversal in a tree. Made me code iterative and recursive version of in-order traversal.

class Solution {
public:
    /*
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    vector<int> inorderTraversal(TreeNode * root) {
        // write your code here
        vector<int> results;
        stack<TreeNode*> stackN;
        TreeNode* cur = root;
        while (cur != NULL || !stackN.empty()) {
            while (cur != NULL) {
                stackN.push(cur);
                cur = cur->left;
            }
                cur = stackN.top();
                stackN.pop();
                results.push_back(cur->val);
                cur = cur->right;

        }
        return results;
    }
};

Round 3 – F2F

1. Difference between static and dynamic bindings.

2. Concept of virtual function in C++. How is a vtable maintained? What are its enteries? Example code where virtual function is used.

3. What is auto, volatile variables? Scopes of variables.

4. References in C++.

5. What is a static function in a C++ class? Why is it used? How to call a static function of class from any part of the code.

6. Given an array of numbers (+ve and –ve), tell the subarray with the highest sum.

7. Height of a tree, diameter of a tree.

Round 4 – F2F (Manager/Director round)

1. Allocate a 2-D array using C/C++.

int** ary = new int*[rowCount];
for(int i = 0; i < rowCount; ++i)
    ary[i] = new int[colCount];

1. Why does a program crash? Valgrind issues etc.

2. Puzzle: 100 floor building and 2 eggs given, find the minimum/maximum number of trys required to find the floor where the egg will break. The answer I gave was 19. He asked me to normalize the solution; we then came up with answer 13.

x+x-1+x-2+x-3 = 100

x(x+1) / 2 = 100

1. Puzzle: Jumbled N pens and N caps, all caps separated from their pens, all pens have some thickness properties. How would you cap all the pens?

2. Given a dictionary, how can you represent it in memory? What will be the worst case complexity of a search done on the DS designed?

3. About my current work

what is setup slack and hold slack of a given timing graph

how to detect a cycle in a graph

how to levelize a graph

what is stable/consistent/deterministic sort

what is counting sort

# variables:
#    input -- the array of items to be sorted; 
#    key(x) -- function that returns the key for item x
#    k -- a number such that all keys are in the range 0..k-1
#    count -- an array of numbers, with indexes 0..k-1, initially all zero
#    output -- an array of items, with indexes 0..n-1
#    x -- an individual input item, used within the algorithm
#    total, oldCount, i -- numbers used within the algorithm

# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

write swap function to swap two integers

what is the size of a given C++ class

what is copy constructor

diff of malloc and new

write serialization function to serial a class with a pointer to itself without using any library

In Prim's, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

Algorithm

1) Create a set mstSet that keeps track of vertices already included in MST.

2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.

3) While mstSet doesn’t include all vertices

….a) Pick a vertex u which is not there in mstSet and has minimum key value.

….b) Include u to mstSet.

….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

In Kruskal's, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.

1. Sort all the edges in non-decreasing order of their weight.

2.
Pick the smallest edge. Check if it forms a cycle with the spanning tree 
formed so far. If cycle is not formed, include this edge. Else, discard it.  


3.Repeat step#2 until there are (V-1) edges in the spanning tree.

Shortest Path

Dijkstra’s Algorithm

 1    function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance
14                                                      // will be selected first
15          remove u from Q 
16          
17          for each neighbor v of u:           // where v is still in Q.
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               // A shorter path to v has been found
20                  dist[v] ← alt 
21                  prev[v] ← u 
22
23      return dist[], prev[]

Height of a Tree;

Delete Linked List (Lazy deletion)

Two Sum

Search a 2D matrix

二叉树

Odd Even LinkedList

string to int

Maximum sum

http://www.cnblogs.com/Raising-Sun/p/5847691.html

Path Sum

Course Schedule

Reverse Linked List

Delete Linked List

OOD

template

template <class myType>

myType GetMax (myType a, myType b) {

return (a>b?a:b);

}

Virtual Destructor

Deleting a derived class object using a pointer to a base class that has a non-virtual destructor results in undefined behavior. To correct this situation, the base class should be defined with a virtual destructor. For example, following program results in undefined behavior.

virtual function

A virtual function a member function which is declared within base class and is re-defined (Overriden) by derived class.When you refer to a derived class object using a pointer or a reference to the base class, you can call a virtual function for that object and execute the derived class’s version of the function.

Virtual functions ensure that the correct function is called for an object, regardless of the type of reference (or pointer) used for function call.

They are mainly used to achieve Runtime polymorphism

Functions are declared with a virtual keyword in base class.

The resolving of function call is done at Run-time.

copy constructor

ClassName (const ClassName &old_obj);

Point(const Point &p2) {x = p2.x; y = p2.y; }

class X

{

private:

int i;

int \*pi;

public:

class X
{
private:
    int i;
    int *pi;
public:
    X()
        : pi(new int)
    { }
    X(const X& copy)   // <-- copy ctor
        : i(copy.i), pi(new int(*copy.pi))  // <-- note this line in particular!
    { }
};

how to implement smart pointer

We will create a class called SP which can hold a pointer to the Person class and will delete the pointer when its destructor is called.

Since the smart pointer should behave like a pointer, it should support the same interface as pointers do; i.e., they should support the following operations.

Dereferencing (operator *)

Indirection (operator ->)

template < typename T > class SP

static

C++ introduces two more uses for the static keyword when applied to classes: static member variables, and static member functions.

static member variables are shared by all objects of the class

a static member variable is shared between all objects of the class

static members exist even if no objects of the class have been instantiated! Much like global variables, they are created when the program starts, and destroyed when the program ends.

Variable Definition vs Declaration

Declaration just define function type without body

Definition Need everything.

swap without temp;

Method 1 (Using Arithmetic Operators)
The idea is to get sum in one of the two given numbers. The numbers can then be swapped using the sum and subtraction from sum.

#include <stdio.h>
int main()
{
  int x = 10, y = 5;

  // Code to swap 'x' and 'y'
  x = x + y;  // x now becomes 15
  y = x - y;  // y becomes 10
  x = x - y;  // x becomes 5

  printf("After Swapping: x = %d, y = %d", x, y);

  return 0;
}
Run on IDE
Output:

After Swapping: x = 5, y = 10
Multiplication and division can also be used for swapping.

#include <stdio.h>
int main()
{
  int x = 10, y = 5;

  // Code to swap 'x' and 'y'
  x = x * y;  // x now becomes 50
  y = x / y;  // y becomes 10
  x = x / y;  // x becomes 5

  printf("After Swapping: x = %d, y = %d", x, y);

  return 0;
}
Run on IDE
Output:

After Swapping: x = 5, y = 10
Method 2 (Using Bitwise XOR)
The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which has all the bits as 1 wherever bits of x and y differ. For example XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111 and XOR of 7 (0111) and 5 (0101) is (0010).

#include <stdio.h>
int main()
{
  int x = 10, y = 5;

  // Code to swap 'x' (1010) and 'y' (0101)
  x = x ^ y;  // x now becomes 15 (1111)
  y = x ^ y;  // y becomes 10 (1010)
  x = x ^ y;  // x becomes 5 (0101)

  printf("After Swapping: x = %d, y = %d", x, y);

  return 0;

Balanced tree checking
Tree Rotations
Constructors and Inheritance fundamentals.

1. Height and Balance factor for binary tree.
2. http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

class Solution {
private: 
    long minV = LONG_MIN;
    long maxV = LONG_MAX;
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, minV, maxV);
    }
    bool helper(TreeNode* root, long minVAL, long maxVAL) {
        if (root == NULL) {
            return true;
        }
        if (root->val <= minVAL || root->val >= maxVAL) {
            return false;
        }
        return helper(root->left, minVAL, root->val) && helper(root->right, root->val, maxVAL);
    }
};

1. Size of a binary tree

int size(struct node* node) 
{  
  if (node==NULL) 
    return 0;
  else     
    return(size(node->left) + 1 + size(node->right));  
}

1. Merge two sorted array, recursive approach for the same using LinkedList (http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/)

Method 3 (Using Recursion)
Merge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.

struct Node* SortedMerge(struct Node* a, struct Node* b) 
{
  struct Node* result = NULL;

  /* Base cases */
  if (a == NULL) 
     return(b);
  else if (b==NULL) 
     return(a);

  /* Pick either a or b, and recur */
  if (a->data <= b->data) 
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}

1. http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

2. Pascal triangle based question

class Solution {  
public:  
    vector<vector<int> > generate(int numRows) {  
        vector<vector<int> > result;  
        if(numRows<1)return result;  

        for(int i=0;i<numRows;i++)  
        {  
            vector<int> t;
            for(int j=0;j<=i;j++)  
            {  
                if (j == 0 || i == j) {
                    t.push_back(1);
                } else {
                    t.push_back(result[i-1][j-1]+result[i-1][j]);  
                }
            }  
            result.push_back(t);  
        }  
        return result;  
    }  
};

1. http://www.geeksforgeeks.org/maximum-difference-between-two-elements/

In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far.
2) Minimum number visited so far.

int maxDifference(int arr[], int n)
{
    int min_element=arr[0];
    int diff=arr[1]-arr[0];
    for(i=1;i<n;i++)
    {
        if(arr[i]-min_element>diff)
            diff=arr[i]-min_element;
        if(arr[i]<min_element)
            min_element=arr[i];
    }
    return diff;
}

1. Given a student table with marks, find Nth rank student

2. http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/

void detectAndRemoveLoop(Node *head)
{
    // If list is empty or has only one node
    // without loop
    if (head == NULL || head->next == NULL)
        return;

    Node *slow = head, *fast = head;

    // Move slow and fast 1 and 2 steps
    // ahead respectively.
    slow = slow->next;
    fast = fast->next->next;

    // Search for loop using slow and
    // fast pointers
    while (fast && fast->next)
    {
        if (slow == fast)
            break;
        slow = slow->next;
        fast = fast->next->next;
    }

    /* If loop exists */
    if (slow == fast)
    {
        slow = head;
        while (slow->next != fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }

        /* since fast->next is the looping point */
        fast->next = NULL; /* remove loop */
    }
}

1. String is represented in a linked list, how to effectively check whether the string is a palindrome (http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/)

   a. Write a function to check if a binary tree is a BST or not.  
   b. Write a function to do zig-zag traversal in a tree.  
   d. Given a linked list find if there is a loop in it or not. if loop exists, find the starting position of loop.
   

2. Concepts of reference and pointers.

3. Virtual function concepts.

4. Given a BST find the kth largest element.

class Solution {
int count = 0;
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL) {
            return -1;
        }
        int left = kthSmallest(root->left, k);
        count++;
        if (count == k) {
            return root->val;
        }
        int right = kthSmallest(root->right,k);
        if (left != -1) {
            return left;
        } else {
            return right;
        }
    }
};

1. Given an unsorted array create a BST.

2. Copy a Linked list to a new location.

3. Virtual pointer and virtual function concepts.

4. How it achieves run time polymorphism ?

5. Give examples of compile time polymorphism .

1. LCA of BST and binary tree.
2. Write a code for BFS of a graph.
3. Write it recursively.
4. Derive the time complexity.
5. Given an array in sorted order and a sum. Check whether the sum of any two elements in the array is equal to the given sum.