Assuming indexes in the range 1...N,start at (1,N) ,i.e. right hand top and check if the element is negative.If yes,obviously all the elements on its left including itself would be -ve.So set the count_of_negatives to N and increment the row_index.If a(1,N) is >=0,decrement the col_index.

So at any general grid point , if a(row,col)< 0, increment row by 1 and count_of_negatives by col,because all the elements to the left of a(row,col) including itself in the same row would be < 0. On the other hand if a(row,col) >=0, just decrement col. Execute the above in a loop till you transcend the boundaries of the matrix.

Time Complexity is 2n which is O(n),where n is number of rows(cols) in the square matrix

The pseudocode is

numNegatives(a[1..N][1...N]){

if a(1,1) >= 0 return 0;

if a(N,N) < 0 return N*N;

row = 1
col = N
count = 0; //count is the number of negatives in the matrix
while( row <=N && col >= 1 ){
if(a(row,col) < 0){
count += col; //everything on the left of a(row,col)including itself are -ve
row++;
}else{
col--;
}
}

return count;
}

Q. No. :

3

Question :

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

// Store the row and column index with //value 0. Let the dimension be mxn
for (int i = 0; i < m; i++) {
for (int j = 0; j < n;j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
column[j] = 1;
}
}
}

// Set arr[i][j] to 0 if either row i or column j //has a 0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}

Q. No. :

4

Question :

Given an unsigned integer 1345, the program constructs a linked list of 1->3->4->5.
Write the test cases for it.

Test cases
1. what to do when the number is negative...where to store the - sign
2. what if the value is 0. no need to perform the % and / operator. create a single node with data value equal to 0
3.what if the number is out of range
4. what if the number is float (given it is an unsigned int, but does your logic handle for a wrong input??)
5.check for memory allocation of the node, can be a failure sometimes
6.similarly check for a wrong input of characters instead of digits

Q. No. :

5

Question :

Given two sorted arrays where the size of second array is large enough to hold the first array, write code to merge them (in sorted order). Write test cases

While traversing the tree,keep a variable,currLevel for level. When a leaf is encountered,push it inside the stack and store its level as rowLevel.
Next time when a leaf is encountered,three cases are possible.
1 currLevel
2 currLevel=rowLevel:In this case,push the node to stack.
3 currLevel>rowLevel:In this case,empty the stack and push the current leaf into stack and rowLevel=currLevel.

Q. No. :

9

Question :

Write a function that gets an integer and returns its string representation in Roman numbers.

1. where is the elevator used. (size of the building)
2. How many floors it has to serve
3. How many entry and exit door are available
4. what is the style of the doors, (glass doors, iron doors..)
5. What is the maximum capacity of the elevator
6. Does it use a rope-pully system or magnetic style
7. Are the floor numbers button style or touch screen
8. what is the style of the display inside and outside...which language..single or multiple

and then start testing each of them.
safety
stress
load
performance
functional
In how many different languages, the safety instructions are displayed
functional in case of fire
lighting and fan inside the elevator
back up lights

Q. No. :

11

Question :

There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blinded .

Divide the coins in half by quantity (easy to count coins while blindfolded)
Then, flip all the coins in one pile over.

Q. No. :

12

Question :

Given a M*N matrix A in which all the elements in a row and all the elements in a column are strictly increasing. Find a path from the smallest element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum. Time Complexity O(m+n). Use efficient space

Only two paths are possible either first row and last column or first column and last row(Why?? Think Yourself!!) Calculate sum of these two paths ans select one with less sum. And that can be easily done in O(m+n)

Q. No. :

13

Question :

Write a function to check if two strings are anagrams. Write a fuction to find all possible anagrams of a given string. You are given a method isWord() to check if the string is a valid word in a dictionary. Assuming that pre processing can be done what pre processing will u do inorder to speed up the process of finding anagrams.

Many ways possible.
e.g For only alphabet character string
input : string1, string2 (to be checked)

step 1: allocate two integer array c1[26], c2[26]
step 2: initialize elements of array c1, c2 to zero

step 3 : for each character in string1
increment corresponding element in c1 by one (ex : for 'a', c[0]++)

step 4 : for each character in string2
decrement corresponding element in c2 by one (ex : for 'a', c[0]--)
step 5:Check if all c[i] is zero, if zero then It's an anagram.

Q. No. :

14

Question :

Give examples of cases where you would prefer to pass objects/variables by reference instead of value?

When To Pass an Argument by Value:
If the calling code element underlying the argument is a nonmodifiable element, declare the corresponding parameter ByVal. No code can change the value of a nonmodifiable element.

If the underlying element is modifiable, but you do not want the procedure to be able to change its value, declare the parameter ByVal. Only the calling code can change the value of a modifiable element passed by value.

When To Pass an Argument by Reference:
If the procedure has a genuine need to change the underlying element in the calling code, declare the corresponding parameter ByRef.
*

If the correct execution of the code depends on the procedure changing the underlying element in the calling code, declare the parameter ByRef. If you pass it by value, or if the calling code overrides the ByRef passing mechanism by enclosing the argument in parentheses, the procedure call might produce unexpected results.

Q. No. :

15

Question :

Perform Sorted Insert on a link list and write test cases

generate_subsets(set, sizeOfSubsets) # assuming sizeOfSubsets cannot be negative
# use a type that enforces this for god's sake!
if sizeOfSubsets is 0 then return {}
else if sizeOfSubsets is 1 then
result = []
for each element in set do result <- result + {element}
return result
else
result = []
baseSubsets = generate_subsets(set, sizeOfSubsets - 1)
for each subset in baseSubssets
for each element in set
if no element in subset then result <- result + { subset + element }
return result

Q. No. :

18

Question :

Write a program to find the mirror image of a n-ary tree( may or may not binary)

Tnode MirrorTree(TNode tnode)
{
// Don't do anything if the number of children is less than one
if(tnode.Children.Count < 2) return tnode;
// else push the children into a stack and set that as children
List children = tnode.Children;
List stack = new List;
foreach(TNode t in children){
stack.insertAt(0,MirrorTree(t));
}
t.Children = stack;
children = null;
return tnode;
}

Q. No. :

19

Question :

Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.

Using Recursion
#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);
int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};

print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;
// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}
//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}

// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}

// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}

if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}

Q. No. :

20

Question :

Find an Item in a Sorted Array with Shifted Elements

Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n)
// myArray is the input array
// startIndex and endIndex are the indexes in the
// array where the binary search starts and ends
// The method returns the index of the searchVal
// if found in the array, else it returns -1

int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal);

// this method will return the index of the searchVal
// if found, else it return -1
int SearchElement(int[] myArray, int shift, int searchVal)
{
// to take care of scenarios where the shift is more
// than the length of the array
shift = shift % myArray.Length;

// -ve shift can be seen as positive shift equal to
// the length of the array - ( -ve shift)
if (shift < 0)
shift = myArray.Length + shift;

There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.
// A1 and A2 are two sorted arrays.
// A2 is not completely full (has empty slots at the end and are exactly the
// size of A1)
// the goal is to merge the two arrays in a sorted fashion

void Merge(int[] A1, int[] A2)
{
int count = FindCount(A2); // get the count of full slots
int i = A1.Length - 1;
int j = count - 1;
int k = A2.Length - 1;

The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR will do the trick. Its gives you O(n) solution with no extra memory.
int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];

// returns the index of the target element if found, else returns -1
static int Binary_Search(int[] arr, int start, int end, int target)
{
int medianIndex = (end - start) /2 + start;
int medianValue = arr[medianIndex];

Use two pointers. Move one pointer at twice the speed of the second. When the 1st pointer reaches the end of the list, the 2nd pointer will be pointing to the middle node. Note: If the list has even number of nodes, the middle node will be floor of âŒŠ n/2 âŒ‹.
Node * FindMiddle(Node *listHead)
{
Node *ptr1, *ptr2; // we need 2 pointers
ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

int i=0;

while(ptr1->next != NULL) // keep looping until we reach the tail
// (next will be NULL for the last node)
{
if(i == 0)
{
ptr1 = ptr1->next; //increment only the 1st pointer
i=1;
}
else if( i == 1)
{
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
i = 0;
}
}
return ptr2; //now return the ptr2 which points to the middle node
}

Q. No. :

25

Question :

Given a singly linked list find the n-th node from the back.

Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.
//define the list node
typedef struct _node
{
int i;
struct _node *next;
} Node;

Node * FindNthFromBack(Node *listHead, int n)
{
Node *ptr1, *ptr2; // we need 2 pointers
ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
{
if(n > 0)
{
ptr1 = ptr1->next; //increment only the 1st pointer
n--;
}
else
{
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
}
}
return ptr2; //now return the ptr2 which points to the nth node from the tail
}

Q. No. :

26

Question :

How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection,
or path, between two people

When we deal with a service the size of Orkut or Facebook, we cannot possibly keep all of our data on one machine. That means that our simple Person data structure from above doesn’t quite work—our friends may not live on the same machine as us. Instead, we can replace our list of friends with a list of their IDs, and traverse as follows:
1. For each friend ID: int machine_index = lookupMachineForUserID(id);
2. Go to machine machine_index
3. Person friend = lookupFriend(machine_index);

Q. No. :

27

Question :

Write the code for producing/printing permutations of the characters in a string. For example: If "abc" is the input string, output permutations should be "abc", "bac", "bca", "acb", "cab", "cba".

The idea here is to put each character in the string in the 1st position and combine it with the permutation of the characters in the rest of the string. As you can see this is also a recursive definition. Pseudo Code:

For i=0 to N
1. Swap letters 0 and i.
2. Permute letters 1 to N-1, printing or saving the entire string each time.

Imagine you have ten trees to plant. You have to get an orchard
which must consist of five straight rows of trees and each row must
contain four trees. One straight line of ten trees cannot be used.
Thus the question is: what template could be used for the planting?

The solution involves using one of the stacks as inbox stack. Incoming items are pushed onto this stack. The other stack is used as an outbox. When items need to be dequeued from the Queue and the outbox stack is empty, all the items from the inbox stack are popped and pushed on to the outbox stack. From there they can be popped until the outbox stack is empty. If the outbox is not empty then Dequeue operation is just a simple Pop() on the outbox stack.

The Enqueue and Dequeue methods for the Queue are as follows:

void Enqueue(int item)
{
// all incoming items go on to the inboxStack
inboxStack.push(item);
}

int Dequeue()
{
//if the outbox stack has items in it just pop it from there and return
if(outboxStack.Count > 0)
{
return outboxStack.Pop();
}
else
{
// move all items from the inbox stack to the outbox stack
while(inboxStack.Count > 0)
{
outboxStack.Push(inboxStack.Pop());
}
if(outboxStack.Count > 0)
{
return outboxStack.Pop();
}
}
}

Write me a function that receives three integer inputs for the lengths of the sides of a triangle and returns one of four values to determine the triangle type (1=scalene, 2=isosceles, 3=equilateral, 4=error). Generate test cases for the function assuming another developer coded the function

Each number represents the first number found after the decimal point when one number is divided by another. The first number, 5 is for 1/2; 6 is for 2/3, 7 is for 3/4, 8 is for 4/5, & so on.

++a means increment & use. a++ means use & increment. i.e use the same value and then increment. This means a temporary is created to hold & use the same value. While a is incremented. So, ++a is faster & it is always better practice to use ++a

Q. No. :

35

Question :

What it wrong with this function:
F1(...){
x = new();
F2();
delete x;
}

F2() has to assume that x has been newed i.e F1() has been called. This results in dependency of F2() on F1(). The design is flawed. If F1 throws an exception, F2 may not be called & memory for x cannot be reclaimed as long as the program is running.

Q. No. :

36

Question :

Given 2 squares on a 2 dimensional plane, find a line that would cut these two squares in half.

Find the centers of the squares and draw a line joining them. Any Line passing the center of the square cuts it in half.

Q. No. :

37

Question :

Suppose you have a 100 files in a directory and you need to find out if a keyword occurs in these files. How would you do it in Unix? How would you do it in Windows?

on Unix:
grep /*
on windows (using a dos command):
find (keyword) (file location & pattern)

Q. No. :

38

Question :

Given a cube. A ant is placed in a corner and cannot move. A spider starts from the opposite corner, and can move along cube edges in any direction (x,y,z) with probablity 1/3. What is the expected number of steps for this spider to get to the ant?

Let x=number of turns to reach ant from starting point.
Let y=number of turns to reach ant from diagonal corner on same face as ant.
Let z=number of turns to reach ant from an adjacent corner to ant.

After one turn the spider will be on a diagonal corner of a common face as the ant. So the mean number of turns from the x position is one more than the mean number from the y position:

E(x)=1+E(y).

Once at a y position there is a 2/3 chance it will then move to a z position, and a 1/3 chance back to an x position:

E(y)=(2/3)*(1+E(z))+(1/3)*(1+E(x)).

If the spider arrives at a z position there is a 1/3 chance it will move to the ant, and a 2/3 chance it will move back to a y position:

E(z)=(1/3)*1+(2/3)*(1+E(y)).

With these three equations and three unknowns it is not difficult to solve for E(x), E(y), and E(z).

Q. No. :

39

Question :

What is: in-order traversal of tree, quick sort in an array

A duck is in circular pond. The duck wants to swim ashore, because it wants to fly off and this particular duck is not able to start flying from the water. There is also a fox, on the shore. The fox wants to eat the duck, but this particular fox cannot swim, so it can only hope to catch the duck when the duck reaches the shore. The fox can run 4 times faster than the duck can swim. Is there always a way for the duck to escape?

(You don't have to remember much linear algebra to understand this -- just the formula for multiplying two symmetric 2x2 matrices:

[ a b ] [ d e ] [ ad + be bd + ce ]
[ b c ] [ e f ] = [ bd + ce be + cf ]

You can then prove the result above by induction: Let

[ 1 1 ]
A = [ 1 0 ]

assume by induction that the equation above is is true for some n, multiply both sides by another power of A using the formula for matrix multiplication, and verify that the terms you get are the same as the formula defining the Fibonacci numbers.)

int M[2][2] = {{1,0}{0,1}}

int fib(int n)
{
matpow(n-1);
return M[0][0];
}

void matpow(int n)
{
if (n > 1) {
matpow(n/2);
M = M*M;
}
if (n is odd) M = M*{{1,1}{1,0}}
}

Q. No. :

42

Question :

A computer has three registers, A, B and R. It has only three instructions:

A->R : Load R with A

B->R : Load R with B

A-R->A : Subtract R from A and store the result in A

Using these instructions how can you do the follwoing?

SELECT *
FROM customer c JOIN orders o ON c.custId=o.custId
JOIN order_items oi ON oi.OrderId=o.OrderId
JOIN inventory i ON oi.invId=i.invId
WHERE c.LName=:lname;

**NB: Breaking Order_items into a separate table to prevent a many-to-many relationship. For interview, this is probably not necessary

Q. No. :

44

Question :

What is static method? What is a static initializer?

A staic method in a class's role is to use the static data members only.
and staic method can be accessed by a static/non-static class object.
But a static method cannot have non-static access to the data-members.
And static method cnnot be constant, volatile and virtual.

Now, static non-class method: A staic keyword in front of a non-class method is used to limit the method scope to the current compilation unit. It has internal linkage and one can use this principal in C for information hiding, while class's static method/data-member has external-linkage.
e.g.
In abc.cpp/c
static void print_some_data()
{
}
is limited in abc.cpp/c only, no other compilation unit in an application can use it.

Q. No. :

45

Question :

Write a method to calculate the acute angle between a clock hour hand and minute hand.

public class Clock{
public static void main(String args[]){
long hours = 3;
long minutes = 15;
// Angle made by the hour hand in hours and minutes
long angle_hour = 30* hours;
double angle_Min_hour = 0.5*minutes;
long mins = 6 * minutes;
System.out.println(angle_hour+":"+angle_Min_hour+":"+mins);
System.out.println("Diff:"+((angle_hour+angle_Min_hour)-mins));
}
}

Q. No. :

46

Question :

Template vs. Inheritance. Why use one over the other?

Templates are useful when a specific behavior is independent of data type on which it operates.
Whereas inheritance is useful when a)code reuse b)more specifically (as in case of polymorphism) you want to have different specific behavior with a generic name for the behavior.

Q. No. :

47

Question :

Given a IP address, Validate the IP address. The IP address lies between [000.000.000.000]-[255.255.255.255] .
IP address is in String, hence you can fetch the characters in the string and move ahead.

Virtual Functions are implemented usign the vtable, which is a table of function pointers for each of the virtual function present in the class.
The class creates a vtable upon call of its constructor. In case of derived class ,base class creates the initial vtable but constructor of derived class over-rides the entry in the vtable if the virtual function is defined in derived class.

Q. No. :

49

Question :

Whatâ€™s the difference between these two declarations?
struct str1 { â€¦ } ;
typedef struct { â€¦ } str2 ;

The first form declares a structure tag whereas the second declares a typedef. The main difference is that the second declaration is of a slightly more abstract type â€” its users donâ€™t necessarily know that it is a structure, and the keyword struct is not used when declaring instances of it.