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();
}
}
}