Asked in Google Internship Interview 3rd round

Ugly Numbers :
http://www.geeksforgeeks.org/archives/753

Largest Sum Contiguous Subarray

Kadane's algorithm : 
Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

 

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   int i;

   for(i = 0; i < size; i++)

   {

     max_ending_here = max_ending_here + a[i];

     if(max_ending_here < 0)

        max_ending_here = 0;

     if(max_so_far < max_ending_here)

        max_so_far = max_ending_here;

    }

    return max_so_far;

}

Matrix Chain Multiplication

Matrix-Chain(array p[1..n]) {
array s[1..n-1,2..n]
for i = 1 to n do m[i,i] = 0; // initialize
for L = 2 to n do { // L = length of subchain
for i = 1 to n-L+1 do {
j = i + L - 1;
m[i,j] = INFINITY;
for k = i to j-1 do { // check all splits
q = m[i, k] + m[k+1, j] + p[i-1]*p[k]*p[j]
if (q < m[i, j]) {
m[i,j] = q;
s[i,j] = k;
}
}
}
}
return m[1,n] (final cost) and s (splitting markers);
}

References :
1) http://www.cs.sunysb.edu/~jgao/CSE548-fall07/David-mount-DP.pdf
2) http://www.geeksforgeeks.org/archives/15553

Adobe Interview Questions - Java

Interview I :
1) Binary search in a shifted array
2) N teams are playing. Finding a sequence on length N so that the left team has lost to the right team.

Interview 2:
1) I am flipping cards from a deck of 26 cards. Design a game stratregy so that you can guess which card is red. Proof of your strategy by induction.
2) Find two numbers whose sum is k in a bst
3) A number as sum of 1s and 2s. Permutations and Combinations
4)

Interview 3:
1) Implement a LRU cache
2) Implement threadpool in Java
3) Implement a blocking queue in Java
Added question : How to implement connection pool in java.

Interview 4:
1) XML questions on Xpath and search
2) Producer Consumer problem

10 Google Interview Questions

1. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.
2. Given a circularly sorted array, describe the fastest way to locate the largest element.
3. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.
4. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.
5. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
6. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.
7. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.
8. You are making an AI to play Tic-Tac-To. Make a function that takes a board position as an input and returns a good position to play. Describe how you'd represent the board, and how you'd determine where to play next.
9. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible?
10. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?.

Source : http://mathnews.uwaterloo.ca/Issues/mn10704/googlequestions.php

Reverse a linked list recursively

void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
// after: rest = {3, 2}
first->next->next = first; // put the first elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer
}

Reverse a linked list iteratively

static void Reverse(struct node** headRef) {
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
*headRef = result;
}

Get Nth element from a linked list

int GetNth(struct node* head, int index) {

struct node* current = head;

int count = 0;

while (current != NULL) {

if (count == index) return(current->data);

count++;

current = current->next;

}

assert(0); // if we get to this line, the caller was asking

// for a non-existent element so we assert fail.

}

Adobe Interview Experience (Jan - 2008)

First Interview

1. 4 persons with different speeds attempt to cross a bridge in the night. There is only one torch and only two people can cross the bridge together and the joint speed is that of the slower of the two. Find the minimum time required to get everyone across.


Time taken by person 1 : 1 minute
Time taken by person 2 : 2 minutes
Time taken by person 3 : 5 minutes
Time taken by person 4 : 10 minutes

2. There are 2 cans - can 'A' contains a red liquid and can 'B' contains blue liquid. We take one unit of liquid from A and mix it with B. Then we take one unit from B and mix it with A. What's the proportion of red:blue in A and blue:red in B now? 

3. Write a non recursive function to reverse a linked list

4. There are a lot of events emanating from user input (mouse movement, keyboard key punches, mouse clicks etc). In the event processing code - there is a single giant switch case that handles these. How do we organize the switch statement to minimize the number of case checks. 


Second Interview 

1. Array A has size M+N and contains M integers in sorted order. Array B has size N and contains N integers in sorted order. How can we merge A and B without using a third array?

2. Find one pair of elements in a sorted array whose sum equals a given value. If the array is unsorted but contains only positive integers, how would you still solve it in O(n) ? 

3. Given 2 sorted arrays, how will you find the median of numbers contained in both of them in logarithmic time?

4. You have a program a.c that is compiled into a.exe and another b.c that is compiled into b.exe . b.exe appends a file 1.dat to a.exe and creates the file out.exe. Now assuming that out.exe is a valid executable, how would you write code in a.c so that data is read from the data file that is appended to the executable? 

5. What are the differences between new and malloc? You said you could overload new operator - what else must be done so that I can write my own memory management library? Do you know what name hiding is? Do you know what name mangling is - why is it required? 


Third Interview

1. Given n integers from the range 50...100 such that no integer repeats. The integers are stored on the disk - Now you're required to sort them in linear time. You are given only 7 bytes of storage apart from the few variables you will invariably need for writing the code. How will you sort if I gave you even less memory? (The code involved creating a bitmap using the 7 element array and setting the bit corresponding to the integers that was found and later printing out the map - I'd to write the code in all its glory and run it on a few cases) 

2. There are 3W and 2B hats in a basket. Persons labelled 1, 2, 3 are made to stand in a row such that 2 can see the hat 1 is wearing and 3 can see the color of the hats 1 and 2 are wearing. Now 3 remarks, "I've no idea about the color of my hat". Then 2 remarks, "I've no idea about the color of my hat either!". Then 1 correctly deduces the color of his hat - what reasoning did A use and what is the color of his hat? 


Fourth Interview

1. A pre order traversal of a complete binary tree is given in an array - then you need to print all the elements at a specified level.
2. You're given the following program:

-------------------------------- 
int main()
{
printf("TWO\n");
return 0;
}
---------------------------------

Add any code above or below the lines so that the output is 

ONE
TWO
THREE

Give me 10 different ways to do this and which of them are specific to C++? 

3. There's a gold bar 100 units in length. You need to pay a worker 2 units everyday for his work. What's the minimum number of cuts that you need to make and where will you make them?
4. What's the difference between an abstract class and a virtual class? ... from the standpoint of multiple inheritance? 
5.There are 50 famillies in a village each consisting of a husband and a wife. Each woman knows all the men who are thieves except her husband. Now the king announces that there is at least one thief in the village. What happens then?

Static members vs instance members

An instance member is a field or an instance method. These members belong to the instance of a class rather than to the class as a whole. Members which are not explicitly declared static in a class declaration are instance members.

Objects and Reference Variables

Shape rectangle, circle;
rectangle = new Shape();
Shape circle = new Shape();

Shape is class. How many objects and reference variable is created by the above code ?

Solution : Two objects and three reference variables are created. When a reference variable is created, it means a variable is created whether a reference value is assigned or not.

Rules to keep in mind when dealing with Java:

1. Variables are not objects. Variables contain objects (or null) -- a particular object can be stored in zero or more variables simultaneously. This does not create new objects, see #3.
2. Mutating an object mutates that object.
3. Assigning (or passing) an object does not make a copy/clone/duplicate.

References :

1. http://stackoverflow.com/questions/6499636/java-objects-reference-variables-and-the-garbage-collection-heap

How does HashMap work in Java ?

What makes good hash keys ?
Classes which are immutable and implement hashCode() and equals() sensibly, make good hash keys.


Important Points 

•  if two objects are equal according to the equals() method, they must have the same hashCode()value (although the reverse is not generally true).
• Under this default implementation, two references are equal only if they refer to the exact same object.

Why does our root object class need hashCode(), when its discriminating ability is entirely subsumed by that of equals()?

The hashCode() method exists purely for efficiency. The Java platform architects anticipated the importance of hash-based collection classes -- such as Hashtable, HashMap, and HashSet -- in typical Java applications, and comparing against many objects with equals() can be computationally expensive. Having every Java object support hashCode() allows for efficient storage and retrieval using hash-based collections.

The hashmap has a number of "buckets" which it uses to store key-value pairs in. Each bucket has a unique number - that's what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).

When you lookup a value in the hashmap, by giving it a key, it will first look at the hash code of the key that you gave. The hashmap will then look into the corresponding bucket, and then it will compare the key that you gave with the keys of all pairs in the bucket, by comparing them with equals().

Now you can see how this is very efficient for looking up key-value pairs in a map: by the hash code of the key the hashmap immediately knows in which bucket to look, so that it only has to test against what's in that bucket.

Looking at the above mechanism, you can also see what requirements are necessary on thehashCode() and equals() methods of keys:

• If two keys are the same (equals() returns true when you compare them), their hashCode()method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket).
• If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket, but the hashmap will use equals() to tell them apart.

Reference :

• http://www.ibm.com/developerworks/java/library/j-jtp05273/index.html
• http://stackoverflow.com/questions/6493605/how-does-java-hashmap-work
• http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

What is the difference between creating a String using the new operator and String intern ?

String s1 = "abcde";

Creating a String in this way is called interning a String.  string interning is a method of storing only one copy of each distinct string value, which must be immutable. Interning strings makes some string processing tasks more time- or space-efficient at the cost of requiring more time when the string is created or interned. The distinct values are stored in a string intern pool.

String s2 = new String("abcde");
String s3 = "abcde";

A String object is an individual instance of the java.lang.String class. s2 will be a new String object.


Hence, 

(s1 == s2) is false
(s1 == s3) is true
(s1.equals(s2)) is true

Why is the String class immutable ? 
String allocation, like all object allocation, proves costly in both time and memory. The JVM performs some trickery while instantiating string literals to increase performance and decrease memory overhead. To cut down the number of String objects created in the JVM, the String class keeps a pool of strings. Each time your code create a string literal, the JVM checks the string literal pool first. If the string already exists in the pool, a reference to the pooled instance returns. If the string does not exist in the pool, a new String object instantiates, then is placed in the pool. Java can make this optimization since strings are immutable and can be shared without fear of data corruption.


References :

• http://stackoverflow.com/questions/3297867/difference-between-string-object-and-string-literal
• http://en.wikipedia.org/wiki/String_interning

public class StringConstruction {
static String str1 = "You cannot change me!"; // Interned
public static void main(String[] args) {
String emptyStr = new String(); // ""
System.out.println("emptyStr: \"" + emptyStr + "\"");
String str2 = "You cannot change me!"; // Interned
String str3 = "You cannot" + " change me!"; // Interned
String str4 = new String("You cannot change me!"); // New String object
String words = " change me!";
String str5 = "You cannot" + words; // New String object
System.out.println("str1 == str2: " + (str1 == str2)); // (1) true
System.out.println("str1.equals(str2): " + str1.equals(str2)); // (2) true
System.out.println("str1 == str3: " + (str1 == str3)); // (3) true
System.out.println("str1.equals(str3): " + str1.equals(str3)); // (4) true
System.out.println("str1 == str4: " + (str1 == str4)); // (5) false
System.out.println("str1.equals(str4): " + str1.equals(str4)); // (6) true
System.out.println("str1 == str5: " + (str1 == str5)); // (7) false
System.out.println("str1.equals(str5): " + str1.equals(str5)); // (8) true
System.out.println("str1 == Auxiliary.str1: " +
(str1 == Auxiliary.str1)); // (9) true
System.out.println("str1.equals(Auxiliary.str1): " +
str1.equals(Auxiliary.str1)); // (10) true
System.out.println("\"You cannot change me!\".length(): " +
"You cannot change me!".length());// (11) 21
}

Immutable vs Mutable Objects in Java - the question answer approach

1. What is an immutable object ? 

An object is considered immutable if its state cannot change after it is constructed. 


     2.  What is happenning to immutable object myString in the example below ? 

String myString = new String( "old String" ); String myCache = myString; System.out.println( "equal: " + myString.equals( myCache ) ); System.out.println( "same: " + ( myString == myCache ) ); myString = "not " + myString; System.out.println( "equal: " + myString.equals( myCache ) ); System.out.println( "same: " + ( myString == myCache ) );

Result : 

        equal: true
	same:  true
	equal: false
	same:  false

The contents of myString is not changing here. We are discarding the instance and changed our reference to a new one with new contents. 

     3.  How can you change the values of a variable ? 

• You can always change the value of a variable by getting your variable to reference a new object. 
• Sometimes you can change the value of a variable by keeping a reference to the same instance, but change the contents of the instance.

    4.  What are the uses of immutable objects ?

• They can promote thread safety in your code 
• You can share them around without being afraid that they will change without your knowledge 
• They are great for caching and constants

    5.  How can we create a mutable class ? 

• Make all fields private
• Don't provide mutators
• Ensure that methods can't be overridden by either making the class final (Strong Immutability) or making your methods final (Weak Immutability)
• If a field isn't primitive or immutable, make a deep clone on the way in and the way out.

References : 

• http://www.javaranch.com/journal/2003/04/immutable.htm
• http://www.ibm.com/developerworks/java/library/j-jtp02183/index.html
• http://stackoverflow.com/questions/214714/mutable-vs-immutable-objects