Pages

Monday 31 December 2012

Design Interview Questions

  1. How would you design the snake and ladder game ?
  2. Some solutions :
    http://www.cvc.uab.es/shared/teach/a21291/materials/Object%20oriented%20design%20principles/laddersAndSnakes.pdf
  3. http://scg.unibe.ch/download/lectures/p2/P2-02-OODesign.pdf - This is the snale and ladder game solution and I got it mostly correct here. This is a very nice solution and shows a nice approach. You have to question your own design at every stage, like is it extensible, what happens when things change, what might be the use cases, can we extend it at runtime, just like head first keeps asking you, does it match the open closed principle.
  4. How would you design a virtual zoo ? - This is like the Duck problem in Head First Design patterns.
  5. Algorithm for top 10 trending words in twitter ?
  6. Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.
  7. How would you design a market place like ebay or an online book selling portal ? Explain the MVC architecture. How you would use an order composer at different places and make the orders, serve it in your database and how you would design the database.
  8. Amazon has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff.
    Make an efficient data structure for storing 3 days of information of all those customers who have visited site exactly two different days and searched more than 3 unique pages of the site in those 2 days. So whoever visited site exactly two days out of these three days and visited more then 3 unique pages should be in the contact list.
  9.  Design a Chess Board : http://tianrunhe.wordpress.com/2012/03/19/design-a-chess-game-using-oo-principles/
  10. Design an IVR system for a Restaurant in which customers can book their tables for lunch and/or dinner. Advance booking for 2 or 7 days/as you wish. After the request from user, respond to him that you will confirm the request within 5 minutes. Check availability and send SMS confirming the same. If the SMS is delivered then assume that the customer is genuine. If the SMS is not delivered properly, discard the user request, as it is not genuine.
    i)       How can you take names and email Ids of the customers during the process?
    ii)     What can you do for repeat customers? How will you identify the repeat customers?
    iii)   If there is request for a team size greater than the table size, what will you do? E.g. request for 10 persons when table sizes are 6, 4 and 2.
  11. http://www.johnpanzer.com/ucscx-oop-java-winter01/BookstoreExample.html



  1. sd

Sunday 30 December 2012

Dynamic Programming

  1. There are two types of problems, increasing and common type where we assume half the array is solved and how can we add another element to the solution and maintain all the constraints. There is another type like common subsequence or coin change, where we find out the total combinations in the solution possible. There we formulate the problem such that we either take the nth element or we don't take the nth element.
  2. Longest Continuous Subarray : maxsoFar = max(maxsoFar + A[I], 0)
        1.                      maxEndingHere = max(maxEndingHere, maxSoFar)
  3. Longest Increasing Subsequence : I need to figure out how to output the longest increasing subsequence as well. I need to study efficient algorithms for longest increasing subsequence as well which work in O(nlogn) time. /* Initialize LIS values for all indexes */
       for ( i = 0; i < n; i++ )
          lis[i] = 1;
        
       /* Compute optimized LIS values in bottom up manner */
       for ( i = 1; i < n; i++ )
          for ( j = 0; j < i; j++ )
             if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;
        
       /* Pick maximum of all LIS values */
       for ( i = 0; i < n; i++ )
          if ( max < lis[i] )
             max = lis[i];
     
  4. Longest Common Subsequence : I need to study other variants of LCS. I need to study some problems of the kind, given the LCS, how can you solve this problem, using this algorithm. This is a nice variant. If last characters of both sequences match (or X[m-1] == Y[n-1]) then
    L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
    If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
    L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
  5. Edit Distance Code
  6. http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/ - I solved this in somewhat worse than O(n) and somewhat better than O(n2). Could have implemented the hash map solution which will solve it in O(n).
  7. Patience Sorting and LIS in O(n log n) time.
  8. Coin Change Problem 1) Solutions that do not contain mth coin (or Sm).
    2) Solutions that contain at least one Sm.
    Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).
  9. Subset Sum isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||
                               isSubsetSum(arr, n-1, sum-set[n-1])
  10. http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
  11. sd
  12. sd
 

Saturday 29 December 2012

Graph Algorithms

  1. Adjacency List Graph construction
  2. Adjacency Matrix Graph Construction
  3. Awesome code to find all the connected components in a graph - really neat http://algs4.cs.princeton.edu/41undirected/CC.java.html
  4. There are three cases that need to be checked for cycles in an undirected graph :
    1. Check for self loops
    2. Check for parallel edges
    3. If a node is not marked in a dfs, go into the dfs
    4. If the node is marked, keep tracking the parent node backward, till you reach that node
  5. Bipartite graphs
    1. Adjacent vertices must have opposite colors. That is the only check that you need and the only condition that a bipartite graph must satisfy. This will imply odd length cycle in the graph does not exit. The dfs function ensures bipartite. In the check function, first we check whether the graph is bipartite or not. If it is not, we then print an odd length cycle in the graph.
  6. Study HeapSort from notes and insertion takes place in O(log n) in heaps
  7. Heap data structure is the basic of the implementation of priority queues. No need to write code separately. HeapSort code will do.
  8. http://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html
  9. http://algs4.cs.princeton.edu/43mst/UF.java.html - study the union find data structure here - only code
  10. Before UF code, read the concept - very nicely explained in Wiki http://en.wikipedia.org/wiki/Disjoint-set_data_structure
  11. http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html
  12. In a disjoint-set forest, the representative of each set is the root of that set's tree. Find follows parent nodes until it reaches the root. Union combines two trees into one by attaching the root of one to the root of the other. One way of implementing these might be:
     function MakeSet(x)
         x.parent := x
    
     function Find(x)
         if x.parent == x
            return x
         else
            return Find(x.parent)
    
     function Union(x, y)
         xRoot := Find(x)
         yRoot := Find(y)
         xRoot.parent := yRoot
    
  13. Djkstra, bellman ford and Floyd warshall from cormen
Todo :
  1. Planarity
  2. Biconnected
  3. Bridges

Wednesday 26 December 2012

Difference between Comparable and Comparator

Comparable
A comparable object is capable of comparing itself with another object. The class itself must implements the java.lang.Comparable interface in order to be able to compare its instances.

Comparator
A comparator object is capable of comparing two different objects. The class is not comparing its instances, but some other class’s instances. This comparator class must implement the java.util.Comparator interface.

If an Employee class is present and its objects are added in an arrayList. Now I want the list to be sorted on the basis of the employeeID of Employee class. What are the steps?
Ans) 1) Implement Comparable interface for the Employee class and override the compareTo(Object obj) method in which compare the employeeID
2) Now call Collections.sort() method and pass list as an argument.
Now consider that Employee class is a jar file.
1) Since Comparable interface cannot be implemented, create Comparator and override the compare(Object obj, Object obj1) method .
2) Call Collections.sort() on the list and pass comparator as an argument.

Tuesday 25 December 2012

Exception Handling Java

  1. http://stackoverflow.com/questions/2699580/difference-between-unchecked-exception-or-runtime-exception
  2. http://java-questions.com/Exceptions_interview_questions.html
  3. http://stackoverflow.com/questions/1457863/what-is-the-difference-between-noclassdeffounderror-and-classnotfoundexception
  4. ClassNotFoundException : this is an exception when a class is trying to load some other class using the forname method and findsystem class in the class loader. This is an error of reflection NoClassDefException : The class was there at compile time but is not there at runtime. This is an error and was not expected.
  5. Difference between throws and throw keyword
  6. http://javarevisited.blogspot.com/2012/02/difference-between-throw-and-throws-in.html
  7. http://stackoverflow.com/questions/7049623/how-to-create-checked-unchecked-custom-exceptions-in-java
  8. throws will be used in the function declaration with no error handling inside the function

Java Multithreading

  1. Study from SCJP
  2. Check question answer from http://java-questions.com/Threads_interview1_questions.html

Java Serialization

  1. http://javarevisited.blogspot.com/2011/04/top-10-java-serialization-interview.html
  2. http://www.javaworld.com/javaworld/jw-07-2000/jw-0714-flatten.html
  3. http://www.javaworld.com/community/node/2915
Serialization is Java's method of writing an object to a file and then reading it back. It is used for object persistence. You can implement the serialization interface and implement the write and the read classes. Static members belong to the class and not to the object and cannot be serialized. Hence, you use separate methods for them. If you have some members that you don't want to save during serialization, you should keep it as transient. Besides, if there are some transient properties in your object, then you should not write it directly. You should only write the non-transient and non-static properties separately.

  1. Object serializationallows an object to be transformed into a sequence of bytes that
    can later be re-created (deserialized) into the original object. After deserialization,
    the object has the same state as it had when it was serialized, barring any data
    members that were not serializable. This mechanism is generally known as persist-ence. Java provides this facility through the ObjectInputand ObjectOutputinterfaces,
    which allow the reading and writing of objects from and to streams. These two
    interfaces extend the DataInputand DataOutputinterfaces
  2. The ObjectOutputStreamclass and the ObjectInputStreamclass implement the
    ObjectOutputinterface and the ObjectInputinterface, respectively, providing meth-ods to write and read binary representation of objects as well as Java primitive val-ues.
  3. For example, in order to store objects in a file and thus provide persistent storage
    for objects, an ObjectOutputStreamcan be chained to a FileOutputStream:
    FileOutputStream outputFile = new FileOutputStream("obj-storage.dat");
    ObjectOutputStream outputStream = new ObjectOutputStream(outputFile);
    Objects can be written to the stream using the writeObject()method of the
    ObjectOutputStreamclass:
    ThewriteObject()method can be used to write anyobject to a stream, including
    strings and arrays, as long as the object implements the java.io.Serializableinter-face, which is a marker interface with no methods. The Stringclass, the primitive
    wrapper classes and all array types implement the Serializableinterface. A serial-izable object can be any compound object containing references to other objects,
    and all constituent objects that are serializable are serialized recursively when the
    compound object is written out. This is true even if there are cyclic references
    between the objects. Each object is written out only once during serialization. The
    following information is included when an object is serialized:
    • the class information needed to reconstruct the object.
  4. the values of all serializable non-transient and non-static members, including
    those that are inherited.
  5. Besides, an object is serializable if its constituent objects are all serializable.

What is the difference between .equals and ==

== checks for identity. That is whether the two objects are the same object and point to the same address in memory.

.equals() by default does the same thing, but can be overridden to perform different equality comparisons. (i.e. strings are considered equal if they have the same characters in the same order)

instanceof checks if an instance is an instance of a given class e.g.if ("hello" instanceof String)

To read Java Blogs

  1. http://www.javabeat.net/ - It has a lot of SCJP questions
  2. http://java-questions.com/ - It has a lot of Java interview questions with nice explanations

What is the difference between deep copying and shallow copying in Java ?

Java Notes : Objects

  1. Thejava.langpackage is indispensable when programming in Java. It is automat-ically imported into every source file at compile time. The package contains the
    Objectclass that is the superclass of all classes,
  2.  A class declaration, without the extendsclause, implicitly extends the Objectclass
  3. int hashCode()
    When storing objects in hash tables, this method can be used to get a hash
    value for an object. This value is guaranteed to be consistent during the execu-tion of the program. This method returns the memory address of the object as
    the default hash value of the object
  4. boolean equals(Object obj)
    Object reference and value equality are discussed together with the ==and !=
    operators (see Section 5.11, p. 191). The equals()method in the Objectclass
    returns trueonly if the two references compared denote the same object. The
    equals()method is usually overridden to provide the semantics of object value
    equality, as is the case for the wrapper classes and the Stringclass. For a
    detailed discussion of the equals()method
  5. final Class<?> getClass()
    Returns the runtime classof the object, which is represented by an object of the
    classjava.lang.Classat runtime
  6. protected Object clone() throws CloneNotSupportedException
    New objects that are exactly the same (i.e., have identical states) as the current
    object can be created by using the clone()method, i.e., primitive values and
    reference values are copied. This is called shallow copying. A class can override
    this method to provide its own notion of cloning. For example, cloning a com-posite object by recursively cloning the constituent objects is called deep copying.
    When overridden, the method in the subclass is usually declared publicto
    allow any client to clone objects of the class. If the overriding clone()method
    in the subclass relies on the clone()method in the Objectclass (i.e., a shallow
    copy), the subclass must implement the Cloneablemarker interface to indicate
    that its objects can be safely cloned. Otherwise, the clone()method in the
    Objectclass will throw a checked CloneNotSupportedException.
  7. String toString()
    If a subclass does not override this method, it returns a textual representation
    of the object, which has the following format:
    "<name of the class>@<hash code value of object>"
    Since the default hash value of an object is its memory address, this value is
    printed as a hexadecimal number, e.g., 3e25a5. This method is usually overrid-den and used for debugging purposes. The method call  Sys-tem.out.println(objRef)will implicitly convert its argument to a textual
    representation by calling the toString()method on the argument

Tuesday 4 December 2012

Equality in Java

Equality. What does it mean for two objects to be equal? If we test equality with (a == b) where a and b are reference variables of the same type, we are testing whether they have the same identity: whether the references are equal. Typical clients would rather be able to test whether the data-type values (object state) are the same. Every Java type inherits the method equals() from Object. Java provides natural implementations both for standard types such as Integer, Double, and String and for more complicated types such as java.io.File and java.net.URL. When we define our own data types we need to override equals(). Java's convention is that equals() must be an equivalence relation:
  • Reflexive: x.equals(x) is true.
  • Symmetric: x.equals(y) is true if and only if y.equals(x) is true.
  • Transitive: if x.equals(y) and y.equals(z) are true, then so is x.equals(z).
In addition, it must take an Object as argument and satisfy the following properties.
  • Consistent: multiple invocations of x.equals(y) consistently return the same value, provided neither object is modified.
  • Not null: x.equals(null) returns false.
Adhering to these Java conventions can be tricky, as illustrated for Date.java and Transaction.java.

Shamelessly copied from : http://algs4.cs.princeton.edu/12oop/. This is just being used as notes for revision purposes.

Monday 3 December 2012

Search and Sorting in Java

Stacks and Queues in Java

A comprehensive list of Linked List interview questions

  1. Remove duplicate elements from an unsorted linked list
  2. http://www.geeksforgeeks.org/sort-a-linked-list-of-0s-1s-or-2s/ - Here you are counting and doing it. However, you might have to do it in O(n). In that case, keep three pointers and keep assigning the nodes to the pointers. Keep track of edge cases 000, 111, 222,0,1,2,00111,0022.
  3. http://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/ : In order to solve this problem, first solve reverse a linked list recursively. Then, you can use that recursive solution here. Solved it well during practice. However, remember the code to reverse a linked list should be learnt by heart.
  4. http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/
  5. http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/ - reverse a doubly linked list by heart.

A comprehensive list of all problems on Binary Search Trees

  1. Tree Traversals InOrder - non decreasing order, PreOrder - used to create a copy, PostOrder - delete the tree
  2. Iterative Pre-Order Traversal : This is a nice question. When you cannot use recursion for such a problem, you need a stack to simulate the recursion.
  3. Level Order Traversal : Before this you should be prepared with the stacks and queue api's first. Besides, study all CTCI questions on Binary Search Trees.
  4. http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/
  5. Find the most weighted node in a BST.
  6. Diameter of a BST
  7. Connect nodes at same level
  8. Children Sum Property
  9. Convert a Binary tree so that it follows the children sum property : look at the soln in the copy, it is more elegant as it doesn't use the increment function. It takes care of both the cases while returning. Nice thinking.
  10. Construct Binary tree from the inorder traversal and following a special property : First, I couldn't understand why this problem is special. Thinking about binary trees after a long time. Is an inorder traversal enough to get a binary tree back ? No right. There might be many combinations that are possible from the inorder traversal. Your work is to print the binary tree which follows the special property that every node has a value which is greater than both the nodes in the left and the right children. One thing, that I get right away is the max element in the inorder traversal is the root. Recursively thinking, the array to the left of it is the left subtree and the array to the right of it is the right subtree. Done.
  11. http://discuss-prog.blogspot.com/2012/08/interesting-problems-on-trees-3.html
  12. http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/
  13. Program to check whether a binary tree is a BST or not ?  The first approach that I thought was that check if the left subtree is a bst, right subtree is a bst and the root is lesser than the right subtree and greater than the left subtree. But it is inefficient. The best way is to do an inorder traversal and check whether it is sorted or not.
  14. The most awesomest code for LCA of a binary tree from leetcode
  15. Do an inorder traversal of the tree and the result should be in sorted order.
  16. Convert a BST to a doubly linked list - look at the leetcode solution which converts it to a circular linked list. Then write the solution for a normal linkedlist
  17. Construct BST from pre-order traversal : here the tree can be constructed from pre-order traversal because we know that it is a BST. This extra criterion helps us.
  18. However, in these lines of questions whether a tree can be constructed from the given traversals, it can only be done if one of the traversals are inorder. It cannot be done even if preorder, postorder and levelorder traversals are given and we only know that the tree is a Binary Tree and not a BST.
  19. Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root. In this question, only one traversal is given and the tree is a binary tree, hence, this question will have to follow a property that the each node is greater than both its children.
  20. http://www.geeksforgeeks.org/construct-a-special-tree-from-given-preorder-traversal/
  21. http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
  22. http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
  23. http://www.geeksforgeeks.org/construct-a-special-tree-from-given-preorder-traversal/ - use static int if you don't feel like pointer to an integer in a function
  24. http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/ - it is not possible to construct a binary tree from preorder and postorder traversal
  25. http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/ - I have not seen this code yet and will be good practice in fresh mind to solve this problem. Even if you are woken up in the middle of the night, you should be able to solve this problem. Here also we can see, that post order and pre-order traversals are given. So this BT will have ambiguity. However, we have the extra condition that it is a full Binary Tree. A full binary tree has the property that it has 2 elements at all the levels. So we know that in preorder the first element is the root and the second element is the left subtree. So we can use this information to find the left subtree and the right subtree from post order traversals.
  26. http://www.geeksforgeeks.org/print-nodes-at-k-distance-from-root/
  27. http://www.geeksforgeeks.org/write-a-c-program-to-get-count-of-leaf-nodes-in-a-binary-tree/
  28. http://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/ - also print the path. Since, root to the leaf node has to be seen, this is going to be preorder traversal. If you have to store the path, then you have to use a stack and keep inputting the roots into the stack. Every time you come out of a left subtree and from a right subtree, you need to pop out the stack except the root, because that is what is required for the next path on may be the right subtree from a parent of the root.
  29. http://codercareer.blogspot.com/2011/09/no-06-post-order-traversal-sequences-of.html - Here also the tree can be constructed from the post order traversal because we know that it is a BST. If it were a binary tree then we would need the inorder traversal to construct the tree.
  30. http://coding-interviewq.blogspot.com/2013/02/trim-given-bst-based-on-min-and-max.html - its all about formulating it recursively
  31. http://coding-interviewq.blogspot.com/2013/02/how-to-get-prev-element-in-inorder.html - Key concept - its all about traversal
  32. Its all about search - http://coding-interviewq.blogspot.com/2013/02/bst-problems-where-underlying-thing.html
  33. http://www.geeksforgeeks.org/iterative-preorder-traversal/ - Iterative traversal can be done using a stack or a queue. A recursion is a function call and architecturally a function call is implemented using a stack. So, put one element in the stack, pop it and check for its children. In the next iteration in the loop pop one of the children and repeat the process.
  34. http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
  35. df
WIP. Please add your  questions on the comments and I will update the list.

Reverse Print Singly Linked List

void reversePrint(Node *head)
{
      if(head!=null)
      {
            reversePrint(head->next);
            printf("%d",head->data);
      }
}

Sunday 23 September 2012

Getting the job offer

This is the most important and the primary part of the process. Some of the companies that have given direct offers for their US locations this year are :

  1. Google
  2. Facebook
  3. Epic Systems
  4. Pocket Gems
  5. Rocket Fuel
One of the ways of getting a call from these companies is to participate in the interviewstreet code sprints. 

These companies generally start hiring from December. Apply early as there are chances that you will have quite a few rounds of interview and the process might take some time. You should target to finish the process and get the complete offer before April of the year you plan to join. The reason for this is that H1B applications generally start from April and the faster you apply, the better it is for you. 

Getting a H1B sponsored job in the US

Last year around this time, I met a lot of people who had worked in the US for some period of time. Speaking to them and knowing their experiences, I also wanted to work there. Now, the advantages/disadvantages of working in the US as a software developer is a different topic of discussion altogether. What seemed overwhelming to me in the beginning is the amount of information and uncertainty that came along my way during the visa process.

In the beginning it seems quite a daunting task as a newbie, when you hear that you can only work in the US if your visa is sponsored by a company. Besides, you need to file a H1B petition in time, otherwise the slots are filled up. There are only 65000 slots every year for H1B employees. So, lot of information, lot of planning required. It drives you crazy. You dont know where to start, what to do and how the whole process will go about.


Things got a little more complex as I was already working. So, in such cases there might come a point when you dont yet have your visa and probably you need to resign with your current firm so that you can join your US company on time, once you get the visa. There were lots of such open ended questions. I think I got lucky at times. I never knew about the 65,000 cap when I applied. I came to know about it when the cap was filled. I have friends who worked equally hard to crack the interviews and couldn't make it because of the visa cap. So having seen all this and having been through the process, I feel that this process can be planned much better, albeit with more information.

This series of posts is going to be directed in that direction. I will document all the steps that I feel should be taken to get a job in the US (right from the interviews) and to successfully convert the visa interviews.

Tuesday 31 July 2012

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

Saturday 28 July 2012

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

Wednesday 11 July 2012

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?.

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?

Monday 9 July 2012

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

Wednesday 4 July 2012

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 HashtableHashMap, 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 :

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";



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 :


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
}


Tuesday 3 July 2012

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 : 

Wednesday 25 April 2012

Redirections and Pipes

1) http://mywiki.wooledge.org/BashFAQ/055
2) http://mywiki.wooledge.org/BashGuide/InputAndOutput#Redirection
3) http://stackoverflow.com/questions/818255/in-the-bash-shell-what-is-21

Friday 20 April 2012

Fail fast and Fail safe in Java

http://www.certpal.com/blogs/2009/09/iterators-fail-fast-vs-fail-safe/
http://javarevisited.blogspot.co.uk/2012/02/fail-safe-vs-fail-fast-iterator-in-java.html

Thursday 19 April 2012

Internal and External Commands to the Unix Shell

Some commands that you type are internal , built into the shell. For example, the cd command is built-in. That is, the shell interprets that command and changes your current directory ( 1.21 ) for you. The ls command, on the other hand, is an external program stored in the file /bin/ls .

The shell doesn't start a separate process to run internal commands. External commands require the shell to fork and exec ( 1.11 ) a new subprocess ( 38.3 ) ; this takes some time, especially on a busy system. (Article 7.4 shows an example where extra speed can be important.)

Reference : http://docstore.mik.ua/orelly/unix/upt/ch01_10.htm

Tuesday 17 April 2012

Autoboxing and Unboxing in Java

Excerpts from the reference :

Definition : You can’t put an int (or other primitive value) into a collection. Collections can only hold object references, so you have to box primitive values into the appropriate wrapper class (which is Integer in the case of int). When you take the object out of the collection, you get the Integer that you put in; if you need an int, you must unbox the Integer using the intValue method. All of this boxing and unboxing is a pain, and clutters up your code. The autoboxing and unboxing feature automates the process, eliminating the pain and the clutter.

Advantages : The result of all this magic is that you can largely ignore the distinction between int and Integer, with a few caveats.Use them only when you have to put code in collections.

Disadvantages :
1)  An Integer expression can have a null value.
2) If your program tries to autounbox null, it will throw a NullPointerException.
3) The == operator performs reference identity comparisons on Integer expressions and value equality comparisons on int expressions.
4) There are performance costs associated with boxing and unboxing, even if it is done automatically.

Example :
You can write Integer i = 5; instead of Integer i = Integer.valueOf(5); or Integer i = new Integer(5);  

Reference :
1) http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

Tip : This feature was introduced in JDK 5.

 Java supplies built-in reference types known as wrapper types, one for each of the primitive types:
Java automatically converts from primitive types to wrapper types (autoboxing) and back (auto-unboxing) when warranted

Monday 16 April 2012

Java Generics


Previous Code :  
// Removes 4-letter words from c. Elements must be strings
static void expurgate(Collection c) {
    for (Iterator i = c.iterator(); i.hasNext(); )
      if (((String) i.next()).length() == 4)
        i.remove();

Disadvantage of this approach : 
When we declare c to be of type Collection<String>, this tells us
something about the variable c that holds true wherever and whenever
it is used, and the compiler guarantees it (assuming the program compiles
without warnings).
 
New Code :
// Removes the 4-letter words from c
static void expurgate(Collection<String> c) {
    for (Iterator<String> i = c.iterator(); i.hasNext(); )
      if (i.next().length() == 4)
        i.remove();
}
 
Advantages of this approach :  
A cast, on the other hand, tells us something the programmer thinks is true at a single point in the code, and the VM checks
whether the programmer is right only at run time.
 
Defining Simple Generics : 
public interface List<E> { void add(E x);
Iterator<E> iterator();
}public interface Iterator<E> { E next();
boolean hasNext();
}

You might imagine that List<Integer> stands for a version of List where E has
been uniformly replaced by Integer:
public interface IntegerList { void add(Integer x)
Iterator<Integer> iterator();
}
 
This might be misleading. 

Type parameters are analogous to the ordinary parameters used in methods or constructors.
Much like a method has formal value parameters that describe the kinds of
values it operates on, a generic declaration has formal type parameters. When a method
is invoked, actual arguments are substituted for the formal parameters, and the method
body is evaluated. When a generic declaration is invoked, the actual type arguments
are substituted for the formal type parameters.

Generic Subtyping : 
If Foo is a subtype (subclass or subinterface) of Bar, and G is some
generic type declaration, it is not the case that G<Foo> is a subtype of G<Bar>.




Best Resources :
1) http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.pdf
2) http://www.ibm.com/developerworks/java/library/j-jtp01255/index.html
3) http://docs.oracle.com/javase/1.5.0/docs/guide/language/generics.html

Tip :
Generics was introduced in Java 1.5.