Google

### There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output will be multiplication of A to A[N-1] and Output will be multiplication of A and from A to A[N-1].

Solve it without division operator and in O(n).

```#define N 5

int main(void)
{
unsigned int data[N] = { 1, 2, 3, 4, 5 },
result[N], product, i;

result = 1;
for (i = 0, product = 1; i < N - 1; i++)
{
product *= data[i];
result[i + 1] = product;
}
for (i = N - 1, product = 1; i > 0; i--)
{
product *= data[i];
result[i - 1] *= product;
}

for (i = 0; i < 5; i++)
printf("%d ", result[i]);

return 0;
}
```

#### two binary trees, write a compare function to check if they are equal or not. equal means they have the same value and same structure.

```/*
Given two trees, return true if they are
structurally identical.
*/
int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);

// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}
```

#### There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

Solution:Traverse the list, generating a new random number for each entry. Keep a ‘top k’ chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.

This random number generated for each element can be defined as a function f=absolute(irand()-rand()),which is random enough.

#### Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M » N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm

Solution:This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:

base = n/8; (base is the char whose certain bit needs to be set)

offset = 1 « (n mod 8); (offset is the bit to be set)

b_array[base] |= offset; (I set the particular bit)

Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.

base = m/8; (base is the char whose certain bit needs to be set)

offset = 1 « (m mod 8); (offset is the bit to be set)

if (b_array[base] & offset)
// found the number
else
//number could not be found

#### How do you put a Binary Search Tree in an array in a efficient manner.

Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.

Solution:The method of construction given in Hint though looks good at a mere glance,it has too many shortcomings.Exponential memory is required at the worst case.

The solution is maintain inorder and one of the other 2 traversals of the tree.These 2 are sufficient to construct back the tree.So the space requirement now is 2N i.e O(N)

how to do so?????

#### How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.

Solution:

```int num=0;
void max(tree*t)
{
if(t==NULL)
return;
max(t->right);
num++;
if(num==5)
printf("%d\n",t->no);
max(t->left);
}
```

another solution:

#### Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

Solution:This solution has been framed on the assumption that all the occurances of a string in the large string of length N are to be reported.
So one can just sort the M strings in O(l*Mlog(M)).An additional l figures because comparison function of strings of length l is of complexity O(l).
Once these M strings are sorted,we can simply do a binary search on them for each of the N-l+1 continuous substrings of big string.The complexity of this search for each such substring is O(l*logM).
So the complexity of this procedure is O(l*MlogM)+O((N-l+1)*(l*logM)).
For N»l this reduces to O(l*MlogM)+O(N*l*log(M).
This can be reduced to O((M+N)*l*log(M)).

this is similar to suffix array issue

#### Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree

Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code.
Solution:If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.

```bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}
```
```bool isBST(Node * node)
{
return isBST2(node,INt_MIN,INT_MAX);
}

bool isBST2(Node * node, int min, int max)
{
if(node==NULL) return true;
if(node->value < min || node->value > max) return false;

return isBST2(node->left,min,node->value) &&  isBST2(node->right,node->value+1,max);
}
```

Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.

#### Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.

Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).

#### Write a function to find the middle node of a single link list.

Solution:

```typedef struct linklist
{
int no;
struct linklist*next;
}list;

void midvalue(list*start)
{
list*ptr1,*ptr2;
ptr1=ptr2=start;
while(1)
{
if(ptr2->next==NULL)
{
if(ptr1->next==NULL)
{
printf("Only one node in the list which is %d\n",head->no);
}
else
{
printf("Middle node is %d\n",ptr1->next->no);  //odd number of nodes
}
break;
}

if(ptr2->next->next==NULL)  //even number of nodes
{
printf("Middle nodes are %d and %d\n",ptr1->no,ptr1->next->no);
}

ptr2=ptr2->next->next;
ptr1=ptr1->next;

}
return;

}
```

This algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).

#### Implement put/get methods of a fixed size cache with LRU replacement algorithm.

Solution:Each cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.
Getting some data is just a search for the data thereby incrementing it age and resorting the cache units.

```get(id)
{
z=search(id);
data=cache[z].data;
cache[z].age++;
sort(cache);
return(x);
}

put(id,x)
{
if(top==cachesize)  //if cache is full
top--
cache[top].id=id;
cache[top].data=x;
cache[top].age=0;
top++;
}
```

You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity

Solution:
Point to the first elements of the three arrays, namely a,b,c. Find the smallest and second smallest of the three.
Let us say that a is the smallest and b is the second smallest. Increment the pointer of a until you find a[i]>b. Calculate the difference between a[i-1] and c and store it as current min.

Now,again find the smallest and second smallest between a[i], b, and c and repeat the above process. If the new difference is smaller than current min,update the value of current min.

Repeat the above process until one of the arrays are finished.

#### Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?

Solution:Different solutions exist for this problem,depending on how once perceives the question.
If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2.
We go on merging like this until we have a single union of all the companies.
Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2)*……..*(2c2)=(N!*(N-1)!)/2^(N-1) .

#### Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Solution:Let d be the number of drops required.
Now we need to find an optimal solution no matter at which floor the egg breaks.
So we find d such that it doesn't depend on the floor number.

Let us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.
If the egg doesn't break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.
We proceed in this fashion,till we reach the 100th floor.

Thus we break at d,2*d-1,3*d-2,….

thus d+(d-1)+(d-2)+…. 1 <=100
=>d=14
Thus we need atmax of 14 attempts for any case.

```++++ Write an XML document that contains the following:

- Encoding is ISO-8859-1
- A Document Type Definition (DTD) that defines this is a document of type
note
- note element has four elements: to, from, subject, body
- Declare that the child element to must occur one or more times inside the
note element
- Declare that the elements to, from, and subject are of the type "#PCDATA"
- Declare that the element body is of the type "#CDATA"
- The element subject has an attribute called date with the value "03/14/1592"

Use the following as the data:

to -> John
from -> Jane
subject -> Reminder
body -> Don't forget that 35 < 50!

<?xml version="1.0" encoding="ISO-8859-1"?>
<!DOCTYPE note [
<!ELEMENT note (to,from,subject,body)*>
<!ELEMENT to (#PCDATA)>
<!ELEMENT from (#PCDATA)>
<!ELEMENT subject (#PCDATA)>
<!ELEMENT body (#PCDATA)>

<!ATTLIST subject date CDATA #FIXED "03/14/1592">
]>
<note>
<to>John</to>
<from>Jane</from>
<subject>Reminder</subject>
<body>Don't forget that 35 < 50!</body>
</note>
```

#### Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.

Solution:a)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.

b)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.
The following is a function which returns the length of the longest increasing subsequence in a.

```int lis(int*a,int n)
{
int length[n],path[n],i,j,max=0;

for(i=0;i < N;i++)
length[i]=1,path[i]=i; //path contains the longest subsequence.

for(i=1;i < N;i++)
for(j=0;j < i;j++)
if(a[i] > a[j] && length[i] < length[j]+1)
length[i]=length[j]+1,path[i]=j;

for(i=0;i < N;i++)
if(max < length[i])
max=length[i];

return max;
}
```

#### There are three differences between an interface and an abstract class:

* you can implement multiple interfaces at the same time, but only extend one class,
* an abstract class is allowed to contain implementation (non-abstract methods, constructors, instance initializers and instance variables) and non-public members, and
* abstract classes may be a tiny bit faster (or they may not.)

Actually the first point is the reason for the existence of interfaces in Java: to provide a form of multiple inheritance. In languages with multiple implementation inheritance, an interface would be equivalent to a fully abstract class (a class with only public abstract members).

The above differentiation suggests when to use an abstract class and when to use an interface:

* use an abstract class, if you want to provide common implementation to subclasses,
* use an abstract class, if you want to declare non-public members,
* use an abstract class, if you want to be free to add new public methods in the future,
* use an interface if you're sure the API is stable for the long run
* use an interface if you want to provide the implementing classes the opportunity to inherit from other sources at the same time.

In general, prefer interfaces if you don't need to use an abstract class, because they provide more design flexibility.

http://maordavid.blogspot.com/2007/05/interface-vs-abstract-class.html
List of similarities and differences between an interface and an abstract class:

* In practice,an interface is a good way to encapsulate a common idea for use by a number of possibly unrelated classes, while an abstract class is a good way to encapsulate a common idea for use by a number of related classes.
* When you need to provide common, implemented functionality among all implementations of your component, use an abstract class. Abstract classes allow you to partially implement your class, whereas interfaces contain no implementation for any members.
* An Interface can only inherit from another Interface, when an abstract class can inherit from a class and one or more interfaces
* An Interface cannot contain constructors or destructors, when abstract class can contain constructors or destructors.
* An Interface can be inherited from by structures,when abstract class cannot be inherited from by structures.
* An Interface can support multiple inheritance,when abstract class cannot support multiple inheritance.
* Interfaces are used to define the peripheral abilities of a class;An abstract class defines the core identity of a class and there it is used for objects of the same type.
* If we add a new method to an Interface then we have to track down all the implementations of the interface and define implementation for the new method; If we add a new method to an abstract class then we have the option of providing default implementation and therefore all the existing code might work properly.
*

#### k sort

1)Write an algorithm for Soduku puzzle

2)What method would you use to look up a name in a dictionary?

3)How would you find out if a machine's stack grows up or down in memory?

4)Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

5) Describe the algorithm for a depth-first graph traversal.

6)Design a class library for writing card games.

7)You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

a XOR b XOR a = b : could you please XOR ABCDEF with my phone number and return the answer back to me?
ABCDEF = My Phone Number XOR XYZ ;
if bob's answer is XYZ, it is correct.

8)You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

9)Given a number, describe an algorithm to find the next number which is prime.

10)what is the best and worst performance time for a hash tree and binary search tree

binary search tree: insert/delete/find average: O(logn), best : O(logn) worst: O(n) space : O(n)

hash tree: find : best: O(1), worst: O(n); average : O(1 + a),
For j = 0, 1, … ,m − 1, denote the length of list T[j] by nj. Then the sum of the length of all lists is:
n = n0 + n1 +· · · +nm-1
Average value of nj is E[ nj ] = a = n/m

insert/delete: best: O(1); worst: O(1); average : O(1)

Q: Why are manhole covers round?

Q: A man pushed his car to a hotel and lost his fortune. What happened?

Q: Explain the significance of "dead beef".

Q: Write a C program which measures the the speed of a context switch on a UNIX/Linux system.

Q: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Q: Describe the algorithm for a depth-first graph traversal.

Q: Design a class library for writing card games.

Q: You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Q: How are cookies passed in the HTTP protocol?

Q: What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {
char a;
char* b;
};

Q: Design the SQL database tables for a car rental database.

Q: Write a regular expression which matches a email address.

Q: Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

Q: You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

Q: Explain how congestion control works in the TCP protocol.

Q: how many people needed in a room to have same birthday with probility 50%.

In the best case, two people will suffice; at worst, the maximum possible number of M + 1 = 366 people is needed; but on average, only 25 people are required.
http://en.wikipedia.org/wiki/Birthday_paradox

http://crack-myoogle.blogspot.com/2007/07/googlemicrosoft-interview-questions.html

#### suffix array

```++++ suffix array

char  c[MAXN] ="........a long string...."

maxlen = -1;
for(int i=0; i<n; i++)
{
for(int j=i+1; i<n; j++)
{
if(thislen=comlen(&c[i],&c[j])) > maxlen
{
maxlen = thislen;
maxi=i;
maxj = j;
}
}
}

int comlen=(char *p, char *q)
{
int i=0;
while(*p &&(*p++ == *q++))  i++;
return i;
}

============================================
suffix array

char *a[MAXN];
for(int i=0; i< MAXN; i++)
a[i] = c+i;

qsort(a,n, sizeof(char *),pstrcmp);

for(int i=0; i<n; i++)
{
if(thislen=comlen(a[i],a[i+1]) > maxlen)
{
maxlen = thislen;
maxi=i;
}
}

printf("%d %s\n",maxlen, a[maxi]);
```

#### randowm selection of link list

There is a link list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1)
2. It should be done in O(n).

http://tristan-tech.blogspot.com/2007/09/random-selection-in-lists-with-unknown.html

http://www.joeganley.com/blog.html

Online random selection
Consider the problem of choosing a random element from a linked list whose length you do not know. Obviously, you could count the length of the list, then pick a random number between 1 and length, and then walk to that element, but there is a clever way to do this in one pass.

The algorithm is as follows:

Element choice;
int count = 0;
for (Element e = head; e != NULL; e = e->next) {
if (rand01() <= (1.0 / ++count)) {
choice = e;
}
}

You can easily show that when this finishes, choice is equal to any given element with probability 1/n, where n is the number of elements: The probability of setting the ith element to be the new choice is 1/i. The probability of not selecting any of the subsequent elements to be the new choice is the product as j goes from i+1 to n of (1 - 1/j), which if you work out the math ends up as i/n. Multiply the two probabilities together and you get 1/n.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License