Microsoft Interview Questions

1. Design a POKER game - http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/10/deck-of-cards.html
2. http://adrianquark.blogspot.com/2008/09/how-to-shuffle-array-correctly.html
3. Design a vending machine
4. Compare two BSTs
5. 
   

Static nested class in java

http://stackoverflow.com/questions/253492/static-nested-class-in-java-why

BST problems where the underlying thing happenning is search - whatever be the name of the function

1. Print Ancestors of a given node in Binary Tree - very sweet problem. If the element is on the left subtree or the right subtree from this element, then this element is an ancestor. So, basically its like search on the left and right subtree. Formulate it recursively :    http://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/
2. LCA of two nodes in a BST : looks complicated. There are few frameworks for all BST problems, traversal or search. Search basically is also a form of traversal only. Just my way of thinking and categorizing.
3. Node *LCA(Node *root, Node *p, Node *q) {

     if (!root) return NULL;

     if (root == p || root == q) return root;

     Node *L = LCA(root->left, p, q);

     Node *R = LCA(root->right, p, q);

     if (L && R) return root;  // if p and q are on both sides

     return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees

   }
4.  
5. sd
6. sd

 

How to get the prev element in an inorder successor in a BST - comparison of two problems

Here think very naively first. You can simply write the inorder traversal of the BST. Now, that would be a sorted array. If two non-adjacent nodes are swapped, then there would be two inflection points in the array. Write a BST, write its inorder traversal and check. Looking at an example you can easily realize that there will be another case where the two adjacent nodes will be swapped. So in that case there will be two inflection points. Now this solution will take O(n) extra space.

However, you can do it easily using recursion. Think about it. First what do you need to think ? How to traverse the tree. Here, you need to compare the previously seen element with the current element. So, if the previous is in the left subtree, the root can be the current. Its a typical case of inorder traversal and is similar to Convert a BST to a double linked list problem.

 We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent

void correctBSTUtil( struct node* root, struct node** first,

                     struct node** middle, struct node** last,

                     struct node** prev )

{

    if( root )

    {

        // Recur for the left subtree

        correctBSTUtil( root->left, first, middle, last, prev );

 

        // If this node is smaller than the previous node, it's violating

        // the BST rule.

        if (*prev && root->data < (*prev)->data)

        {

            // If this is first violation, mark these two nodes as

            // 'first' and 'middle'

            if ( !*first )

            {

                *first = *prev;

                *middle = root;

            }

 

            // If this is second violation, mark this node as last

            else

                *last = root;

        }

 

        // Mark this node as previous

        *prev = root;

 

        // Recur for the right subtree

        correctBSTUtil( root->right, first, middle, last, prev );

    }

}

 

Look at the way prev is stored here. We just store the root which is the previously seen element. You can get a clear understanding of how this thing can be altered in another problem. Looking at these two problems will improve your clarity of thinking. The problem is Convert a BST to doubly linked list

 

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {

  if (!p) return;

  treeToDoublyList(p->left, prev, head);

  // current node's left points to previous node

  p->left = prev;

  if (prev)

    prev->right = p;  // previous node's right points to current node

  else

    head = p; // current node (smallest element) is head of

              // the list if previous node is not available

              //because prev will come from left subtree in the recursion. There is no left subtree, so it the smallest and head

  // as soon as the recursion ends, the head's left pointer

  // points to the last node, and the last node's right pointer

  // points to the head pointer.

  Node *right = p->right;

  head->left = p;

  p->right = head;

  // updates previous node

  prev = p; // In an inorder traversal before going to the right subtree the previous always gets updated

  treeToDoublyList(right, prev, head);

}

 

 

// In an inorder traversal before going to the right subtree the previous always gets updated

Trim a given BST based on Min and Max values

How do you think about this problem recursively. First think about the traversals. It cannot be pre order because you have to return the root. So you need the computation of the left subtree and the right subtree done when you return the values. Hence, it has to be post order traversal. Now, since you know the kind of traversal, think of a recursive solution. Suppose you apply your trim function to the left subtree and the right subtree. Now you have the solutions of the left subtree and the right subtree and they satisfy the min and the max criterion. You are now only left to check the min and the max criterion with the root. Now, write down the code.

TreeNode trim(TreeNode node, int min, int max) {
        if(node == null) return node;
        node.left = trim(node.left, min, max);
        node.right = trim(node.right, min, max);
        if(node.data < max and node.data > min) return node;
        else if(node.data < min) return node.right;
        else if(node.data > max) return node.left;


}

Wireless Generation Interview Questions

1. How would you design a storage service
2. http://aws.amazon.com/architecture/
3. I was asked to design a system that could be used by many different applications to READ/WRITE/LIST/DELETE/STATUS files. That was all the description so you need to decide on everything else.
4. http://wikibon.org/wiki/v/Developing_a_storage_services_architecture
5. http://chucksblog.emc.com/chucks_blog/2011/09/storage-as-a-service-basic-concepts.html
6. How does a spell checker work ? read bloom filters
7. Move pattern for a chess board game
8. Write a function that takes up a price and returns a minimum set of coins that add up to that price
9. design a system for museums that helps visitors enjoy the exhibits. Had to think about location-awareness, routing algorithms, data structures, file formats.
10. write code that implements a whitespace regex matcher in C++/Java
11. write a method that accepts two character arrays and determine whether the first could be recreated using only the characters in the second.
12. -Write a method that accepts a list of integer pairs. The method should compare the integer pairs and combine/delete pairs that intersect/comprise other pairs on the number line(for instance (1,4) and (2,5) could be reduced to (1,5); (1,4) and (1,3) could be reduced to (1,4); (1,4) and (6,8) couldn't be reduced). The method should return this list of integer pairs.
13. -Design the class structure and explain the general methodology of software that would guide museum-goers on an audio tour. The museum-goers enter a customized list of which exhibits they want to see and the software figures out the best path for them to take. Also design a file format so that the museum can tell the software the layout of the museum (I did a simple XML format that gave each room a name and described which rooms connected to each other).
14. Write a method that accepts a list of integers and returns each number as a percentage of the largest number. This wasn't too difficult, though it did bring to light some questions about efficiency. Again, it was a big help to sort the list first.
15. They seemed like a cool company, but now that I know how they deal with people they aren't interested in anymore, I'm glad I have nothing to do with them.
16. How would you handle acceptance testing of a huge project spread across two geographies and five teams?
17. If different architectural teams had come to different decisions on a technology foundation for part of the system, how would you work to resolve the differences and come to the best decision for the team?
18. How I would break a spell check service into sub modules and direct the work of other developers ?
19. Tight coupling is when a group of classes are highly dependent on one another.
20. This scenario arises when a class assumes too many responsibilities, or when one concern is spread over many classes rather than having its own class.
21. Loose coupling is achieved by means of a design that promotes single-responsibility and separation of concerns.
22. A loosely-coupled class can be consumed and tested independently of other (concrete) classes.
23. Write an algorithm to move a knight on a chessboard from a given position.
24. Write an algorithm to determine if a set of characters, matches a given regex.
25. Write a file format to describe a museum and it's contents, and then design a UI to interface with it. Explain how gps enabled units could navigate a user through the museum only to see the exhibits they want to.
26. If you need to process a million records in 2 seconds, how would you do it? Assume XML records

Multithreading Interview Questions

1. The static class lock is independent of the object lock
2. wait is called from synchronized context only while sleep can be called without synchronized block. see Why wait and notify needs to call from synchronized method for more detail.
   
   2) wait is called on Object while sleep is called on Thread. see Why wait and notify are defined in object class instead of Thread.
   
   3) waiting thread can be awake by calling notify and notifyAll while sleeping thread can not be awaken by calling notify method.
   
   4) wait is normally done on condition, Thread wait until a condition is true while sleep is just to put your thread on sleep.
   
   
   5) wait release lock on object while waiting while sleep doesn’t release lock while waiting
3. Major difference between yield and sleep in Java is that yield() method pauses the currently executing thread temporarily for giving a chance to the remaining waiting threads of the same priority to execute. If there is no waiting thread or all the waiting threads have a lower priority then the same thread will continue its execution. The yielded thread when it will get the chance for execution is decided by the thread scheduler whose behavior is vendor dependent. Yield method doesn’t guarantee  that current thread will pause or stop but it guarantee that CPU will be relinquish by current Thread as a result of call to Thread.yield() method in java.
   
   
   Sleep method in Java has two variants one which takes millisecond as sleeping time while other which takes both mill and nano second for sleeping duration.
   
   
   sleep(long millis)
   or
   sleep(long millis,int nanos)
4. Yield will send the thread from the Running state to the Ready to run state. This is the place where the thread first comes and waits after the call on the start method. Then the scheduler picks up the thread and allows it to run
5. 1) Thread.sleep() method is used to pause the execution, relinquish the CPU and return it to thread scheduler.
   
   
   2) Thread.sleep() method is a static method and always puts current thread on sleep.
   
   
   3) Java has two variants of sleep method in Thread class one with one argument which takes milliseconds as duration for sleep and other method with two arguments one is millisecond and other is nanosecond.
   
   
   4) Unlike wait() method in Java, sleep() method of Thread class doesn't relinquish the lock it has acquired.
   
   
   5) sleep() method throws Interrupted Exception if another thread interrupt a sleeping thread in java.
   
   
   6) With sleep() in Java its not guaranteed that when sleeping thread woke up it will definitely get CPU, instead it will go to Runnable state and fight for CPU with other thread.
   
   
   7) There is a misconception about sleep method in Java that calling t.sleep() will put Thread "t" into sleeping state, that's not true because Thread.sleep method is a static method it always put current thread into Sleeping state and not thread "t".
6. 
   

Basic OOP interview questions

Basic OOP Questions  :

1. http://stackoverflow.com/questions/1031273/what-is-polymorphism

The abiltiy to define more than one function with the same name is called Polymorphism. In java,c++ there are two type of polymorphism: compile time polymorphism (overloading) and runtime polymorphism (overriding).

 

When you override methods, JVM determines the proper methods to call at the program’s run time, not at the compile time. Overriding occurs when a class method has the same name and signature as a method in parent class.

Overloading occurs when several methods have same names with

Overloading is determined at the compile time.

 

Different method signature and different number or type of parameters.

Same method signature but different number of parameters.

Same method signature and same number of parameters but of different type 

 

Shape, rectangle and circle is an example of polymorphism

1. What is encapsulation ? Combining the data and the methods to act on the data and putting them in a class together
2. COMPOSITION
   Imagine a software firm that is composed of different Business Units (or departments) like Storage BU, Networking BU. Automobile BU. The life time of these Business Units is governed by the lifetime of the organization. In other words, these Business Units cannot exist independently without the firm. This is COMPOSITION. (ie the firm is COMPOSED OF business units)
   ASSOCIATION
   The software firm may have external caterers serving food to the employees. These caterers are NOT PART OF the firm. However, they are ASSOCIATED with the firm. The caterers can exist even if our software firm is closed down. They may serve another firm! Thus the lifetime of caterers is not governed by the lifetime of the software firm. This is typical ASSOCIATION
   AGGREGATION
   Consider a Car manufacturing unit. We can think of Car as a whole entity and Car Wheel as part of the Car. (at this point, it may look like composition..hold on) The wheel can be created weeks ahead of time, and it can sit in a warehouse before being placed on a car during assembly. In this example, the Wheel class's instance clearly lives independently of the Car class's instance. Thus, unlike composition, in aggregation, life cycles of the objects involved are not tightly coupled.
3. Tip to remember : Composition RBS, association caterer, aggregation car
4. IS A relationship means you inherit and extend the functionality of the base class.
   HAS A relationship means the class is using another class, so it has it as a member
5. Composition is a specific case of aggregation
6. Does java support pass by value or by reference ? Java supports plain pass by value but the object reference it passes will always be the references. Hence manipulations on the objects will always work.

Java Keywords :

1. What is the volatile keyword in Java ?  When multiple threads using the same variable, each thread will have its own copy of the local cache for that variable. So, when it’s updating the value, it is actually updated in the local cache not in the main variable memory. The other thread which is using the same variable doesn’t know anything about the values changed by the another thread. To avoid this problem, if you declare a variable as volatile, then it will not be stored in the local cache. Whenever thread are updating the values, it is updated to the main memory
2. ThreadLocal variables
   If you want to maintain a single instance of a variable for all instances of a class, you will use static-class member variables to do it. If you want to maintain an instance of a variable on a per-thread basis, you'll use thread-local variables. ThreadLocal variables are different from normal variables in that each thread has its own individually initialized instance of the variable, which it accesses via get() or set() methods.
   Let's say you're developing a multithreaded code tracer whose goal is to uniquely identify each thread's path through your code. The challenge is that you need to coordinate multiple methods in multiple classes across multiple threads. Without ThreadLocal, this would be a complex problem. When a thread started executing, it would need to generate a unique token to identify it in the tracer and then pass that unique token to each method in the trace.
   With ThreadLocal, things are simpler. The thread initializes the thread-local variable at the start of execution and then accesses it from each method in each class, with assurance that the variable will only host trace information for the currently executing thread. When it's done executing, the thread can pass its thread-specific trace to a management object responsible for maintaining all traces.
   Using ThreadLocal makes sense when you need to store variable instances on a per-thread basis.
   

   ---

   Back to top
3. Volatile variables
   I estimate that roughly half of all Java developers know that the Java language includes the keyword volatile. Of those, only about 10 percent know what it means, and even fewer know how to use it effectively. In short, identifying a variable with the volatile keyword means that the variable's value will be modified by different threads. To fully understand what the volatile keyword does, it's first helpful to understand how threads treat non-volatile variables.
   In order to enhance performance, the Java language specification permits the JRE to maintain a local copy of a variable in each thread that references it. You could consider these "thread-local" copies of variables to be similar to a cache, helping the thread avoid checking main memory each time it needs to access the variable's value.
   But consider what happens in the following scenario: two threads start and the first reads variable A as 5 and the second reads variable A as 10. If variable A has changed from 5 to 10, then the first thread will not be aware of the change, so it will have the wrong value for A. If variable A were marked as being volatile, however, then any time a thread read the value of A, it would refer back to the master copy of A and read its current value.
   If the variables in your applications are not going to change, then a thread-local cache makes sense. Otherwise, it's very helpful to know what the volatile keyword can do for you.
4. http://www.ibm.com/developerworks/java/library/j-5things15/index.html
5. My understanding : all threads have local copy of the variables. to give them a global copy, use volatile. How is thread local different from normal thread variables. They are accessible from all the functions which are being called from the thread.
6.  reading a volatile variable is synchronized and writing to a volatile variable is synchronized, but non-atomic operations are not.
7.  What is a transient variable?
   Ans) If some of the properties of a class are not required to be serialized then the varaibles are marked as transient. When an object is deserialized the transient variables retains the default value depending on the type of variable declared and hence lost its original value.
8.  static variables/methods/why aren't non static variables accessible by static methods ?
9.  

Garbage Collection :

1. http://www.quora.com/How-does-garbage-collection-work-in-the-JVM
2. http://java-questions.com/garbagecollection_interview_questions.html
3. http://weblogs.java.net/blog/enicholas/archive/2006/05/understanding_w.html
4. What is a strong reference ?  Specifically, if an object is reachable via a chain of strong references (strongly reachable), it is not eligible for garbage collection. As you don't want the garbage collector destroying objects you're working on
5. A weak reference, simply put, is a reference that isn't strong enough to force an object to remain in memory. Weak references allow you to leverage the garbage collector's ability to determine reachability for you, so you don't have to do it yourself.
6. Reference Queues : Once a WeakReference starts returning null, the object it pointed to has become garbage and the WeakReference object is pretty much useless. This generally means that some sort of cleanup is required; WeakHashMap, for example, has to remove such defunct entries to avoid holding onto an ever-increasing number of dead WeakReferences.
   The ReferenceQueue class makes it easy to keep track of dead references. If you pass a ReferenceQueue into a weak reference's constructor, the reference object will be automatically inserted into the reference queue when the object to which it pointed becomes garbage. You can then, at some regular interval, process the ReferenceQueue and perform whatever cleanup is needed for dead references
7. Soft references are like weak references, however the object they refer to stick around for a while. What defines this while part ?
8.  softly reachable objects are generally retained as long as memory is in plentiful supply.
9. A phantom reference is quite different than either SoftReference or WeakReference. Its grip on its object is so tenuous that you can't even retrieve the object -- its get() method always returns null. The only use for such a reference is keeping track of when it gets enqueued into a ReferenceQueue, as at that point you know the object to which it pointed is dead. How is that different from WeakReference, though?
10. The difference is in exactly when the enqueuing happens. WeakReferences are enqueued as soon as the object to which they point becomes weakly reachable. This is before finalization or garbage collection has actually happened; in theory the object could even be "resurrected" by an unorthodox finalize() method, but the WeakReference would remain dead. PhantomReferences are enqueued only when the object is physically removed from memory, and the get() method always returns null specifically to prevent you from being able to "resurrect" an almost-dead object.
11. When a weak reference dies, the object enters the reference queue and using an unorthodox finalize method, that object can be got back.However, when a phantom referenced object dies, this kinda method is not going to work as a phantom reference doesn't even support the get method.
12. Phantom references allow you to determine exactly when an object was removed from memory
13. http://weblogs.java.net/blog/enicholas/archive/2006/05/understanding_w.html
14. What is island of isolation ?  an island of isolation is a group of objects that reference each other but they are not referenced by any active object in the application http://stackoverflow.com/questions/792831/island-of-isolation-of-garbage-collection
15.  In brief, the GC can walk through the web of references from the known static and stack objects, and either
    
    • copy all objects found to a new memory pool, automatically leaving behind any "dead" objects (this is the "young generation" strategy), or
    • mark all objects found, so that once the whole web of references is walked traversed, it can delete all unmarked objects (this is the "old/tenured generation" strategy).
16. What are the different ways to call Garbage Collector ? System.gc() and Runtime.getRuntime.gc()
17. What is the purpose of overriding finalize() method?
    Ans) The finalize() method should be overridden for an object to include the clean up code or to dispose of the system resources that should to be done before the object is garbage collected.
18. Runtime.getRuntime().runFinalizersOnExit(boolean value)

Questions on the Main Method in Java  :

1. 1. Main method must be declared public, static and void in Java otherwise JVM will not able to run Java program.
   
   
   2. JVM throws NoSuchMethodException:main if it doesn't find main method of predefined signature in class which is provided to Java command. E.g. if you run java Helloworld than JVM will search for public static void main String args[]) method in HelloWorld.class file.
   
   
   3. Main method is entry point for any Core Java program. Execution starts from main method.
   
   
   4. Main method is run by a special thread called "main" thread in Java. Your Java program will be running until your main thread is running or any non-daemon thread spawned from main method is running.
   
   
   5. When you see "Exception in Thread main” e.g.
   Exception in Thread main: Java.lang.NullPointerException it means Exception is thrown inside main thread.
   
   
   6. You can declare main method using varargs syntax from Java 1.5 onwards e.g.
   public static void main(String... args)
   
   
   7. Apart from static, void and public you can use final, synchronized and strictfp modifier in signature of main method in Java.
   
   
   8. Main method in Java can be overloaded like any other method in Java but JVM will only call main method with specified signature specified above.
   
   
   9. You can use throws clause in signature of main method and can throw any checked or unchecked Exception.
   
   
   10. Static initializer block is executed even before JVM calls main method. They are executed when a Class is loaded into Memory by JVM.
   
   
   http://java67.blogspot.com/2012/12/main-method-interview-questions-in-java-answers.html

SCJP Practice Questions

1. http://stackoverflow.com/questions/5515050/scjp-question-to-figure-when-object-gets-garbage-collected?rq=1
2. http://stackoverflow.com/questions/5801732/scjp-mock-question-how-many-objects-are-eligible-for-garbage-collection?rq=1
3. sd
4. sd

Collections :

1. http://stackoverflow.com/questions/1440134/java-what-is-the-difference-between-implementing-comparable-and-comparator
2. Comparable : an object can compare with itself
3. Comparator : an object can compare two different objects. When the source code is not available and you have to compare client's code, then you use comparator
4. LinkedList implements both the List and the Queue interfaces

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

eBay interview questions

1. http://www.vogella.com/articles/JavaDatastructures/article.html - practice the array implementation of hashmap. It will clear your generics concepts and gives the basic way a hashentry is created first
2. http://docs.oracle.com/javase/6/docs/api/java/util/WeakHashMap.html
3. http://stackoverflow.com/questions/34510/what-is-a-race-condition
4. http://stackoverflow.com/questions/519520/difference-between-static-class-and-singleton-pattern - A singleton can implement an interface, hence, it can be a singleton implementation of an interface. However, an all static methods class cannot implement an interface
5. Hashtable and collision resolving techniques : How is it done in java ?
6. Heap implementation
7. LCA
8. Coins DP
9. Eggs problem
10. http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17
11. http://www.regular-expressions.info/examples.html - you need to know all kinds of validations - date, email, IP and all kinds of regexes for that.

Why should you use Generics instead of Objects ?

http://stackoverflow.com/questions/5207115/java-generics-t-vs-object

What is the difference between the two ?

public Object doSomething(Object obj) {....}
public T doSomething(T t) {....}

compile time safety that that like works. If the Object version is ued, you won't be sure if the method always returns Foo. If it returns Bar, you'll have a ClassCastException, at runtime.

How would you design an object pool in java ?

1. http://stackoverflow.com/questions/1137118/does-this-basic-java-object-pool-work
2. http://www.javaworld.com/javaworld/jw-06-1998/jw-06-object-pool.html
3. http://sourcemaking.com/design_patterns/object_pool/java
4. The basic interface of the object pool should like this
5. public interface ObjectPool<T> {
       T borrowObject();
       void returnObject(T borrowed);
   }
   
6. http://commons.apache.org/pool/

DBMS Interview Questions

1. http://tuandao.info/html/career/SQL.pdf
2. http://www.techinterviews.com/sql-interview-questions-and-answers
3. create table branch
           (branch_name  char(15),
            branch_city  char(30) not null,
            assets  integer,
            primary key (branch_name))
4. insert into account
     values ('A-9732', 'Perryridge', 1200)
5. delete from account
6. select distinct branchname from loan
7. select all branchname from loan
8. Rename operation :
   select customer_name, borrower.loan_number as loan_id, amount
   from borrower, loan
   where borrower.loan_number = loan.loan_number
9. select distinct customer_name
     from    borrower, loan
     where borrower loan_number = loan.loan_number and
                 branch_name = 'Perryridge'
     order by customer_name
10. Aggregate functions 
11. select branch_name, count (distinct customer_name)
               from depositor, account
               where depositor.account_number = account.account_number
               group by branch_name
12. Attributes in select clause outside aggregate functions must appear in group by clause
13. Having clause
14. select branch_name, avg (balance)
               from account
               group by branch_name
               having avg (balance) > 1200
15. Predicates in the having clause are applied before forming groups and predicates in the where clause are applied before forming groups
16. sd
17. sd
18. as

• select avg (balance)
    from account  where branch_name = 'Perryridge'
• select count (distinct customer_name)
    from depositor

1. sd