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.
9. 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.
10.  Design a Chess Board : http://tianrunhe.wordpress.com/2012/03/19/design-a-chess-game-using-oo-principles/
11. 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.
13. http://www.johnpanzer.com/ucscx-oop-java-winter01/BookstoreExample.html

1. sd

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/
12. sd
13. sd

 

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

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.

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

http://java-questions.com/Cloning_interview_questions.html

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

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.

Search and Sorting in Java

1. Binary Search
2. Find the smallest or largest k elements in an array
3. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

Stacks and Queues in Java

1. Queue
2. Stack

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