The odd interview questions and answers

1. What's the next number in this sequence: 10, 9, 60, 90, 70, 66 … ?
Asked at Google

2. You're in a car with a helium balloon on a string that is tied to the floor. The windows are closed. When you step on the gas pedal, what happens to the balloon—does it move forward, move backward, or stay put? 
Asked at Microsoft

3. Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes—without the process taking longer than nine minutes. 
Asked at Google

4. A book has N pages, numbered the usual way, from 1 to N. The total number of digits in the page numbers is 1,095. How many pages does the book have?
Asked at Google

5. A man pushed his car to a hotel and lost his fortune. What happened? Asked at Google

6.How many people are using Facebook in San Francisco at 2:30 p.m. on a Friday? — Asked at Google, Vendor Relations Manager candidate

7.How can I determine the highest floor of a 100 story building that an egg can be dropped from without breaking if I have two eggs?

8.How would you cure world hunger?— Asked at Amazon.com, Software Developer candidate

9.You’re in a row boat, which is in a large tank filled with water. You have an anchor on board, which you throw overboard (the chain is long enough so the anchor rests completely on the bottom of the tank). Does the water level in the tank rise or fall?— Asked at Tesla Motors, Mechanical Engineer candidate

10.You have a bouquet of flowers. All but two are roses, all but two are daisies, and all but two are tulips. How many flowers do you have? — Asked at Epic Systems, Corporation Project Manager/Implementation Consultant candidate

11.You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? Asked at Facebook.

12.Why are manhole covers are round? -- Asked at Google

13.There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? ----Asked at Google

14.How would you explain a database in three sentences to your 8-year-old nephew?---Asked at Google

ANSWERS

1. What's the next number in this sequence: 10, 9, 60, 90, 70, 66 … ?

A. Spell the numbers out: 
Ten
Nine
Sixty
Ninety
Seventy
Sixty-six

They are in ascending order, based on the number of letters in the spelled-out numbers. A correct response will have nine letters: 96, for instance. A cleverer answer is "one googol." That's the huge number that can be written as a "1" with a hundred zeros after it. Google, the company's name, was originally a misspelling of "googol."

2. You're in a car with a helium balloon on a string that is tied to the floor. The windows are closed. When you step on the gas pedal, what happens to the balloon—does it move forward, move backward, or stay put?

A. The near-universal intuition is that the balloon leans backward as you accelerate. Well, the intuition is wrong. Your job is to deduce how the balloon does move and to explain it to the interviewer.
One good response is to draw an analogy to a spirit level. For the not so handy, a spirit level is the little gizmo carpenters use to make sure a surface is horizontal. It contains a narrow glass tube of colored liquid with a bubble in it. Whenever the spirit level rests on a perfectly horizontal surface, the bubble hovers in the middle of the tube. When the surface isn't so level, the bubble migrates to the higher end of the tube. The takeaway here is that the bubble is simply a "hole" in the liquid. When the surface isn't level, gravity pulls the liquid toward the lower end. This pushes the bubble wherever the liquid isn't— toward the opposite end.


Untie the helium balloon and let it hit the moonroof. It becomes a spirit level. The balloon is a "bubble" of lower-density helium in higher-density air, all sealed in a container (the car).

Gravity pulls the heavy air downward, forcing the light balloon against the moonroof.

When the car accelerates, the air is pushed backward, just as your body is. This sends a lighter-than-air balloon forward. When the car brakes suddenly, the air piles up in front of the windshield. This sends the balloon backward. Centrifugal force pushes the air away from the turn and sends the balloon toward the center of the turn. Of course, the same applies when the balloon is tied to something; it's just less free to move. The short answer to this question is that the balloon nods in the direction of any acceleration.

3. Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes—without the process taking longer than nine minutes.

A. Start both hourglasses at 0 minutes. Flip over the four-minute glass when it runs out (at 4:00); ditto for the seven-minute glass (at 7:00). When the four-minute glass runs out the second time (at 8:00), the seven-minute glass will then have one minute of sand in its lower bulb. Flip the seven-minute glass over again and let the minute of sand run back. When the last grain falls, that will be nine minutes.

4. A book has N pages, numbered the usual way, from 1 to N. The total number of digits in the page numbers is 1,095. How many pages does the book have?

A. Every page number has a digit in the units column. With N pages, that's N digits right there. All but the first 9 pages have a digit in the tens column. That's N - 9 more digits.

All but the first 99 pages have a digit in the hundreds column (accounting for N - 99 more digits).

I could go on, but not many books have more than 999 pages. A book with 1,095 digits in its page numbers won't, anyway.

This means that 1,095 must equal:

N + (N - 9) + (N - 99).

This can be simplified to:

1,095 = 3N - 108.

That means that 3N = 1,203, or N = 401. That's the answer, 401 pages.

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

A. He was playing Monopoly.

6.How many people are using Facebook in San Francisco at 2:30 p.m. on a Friday?”

A.40% more than should be, considering 2:30 is when most people are working.

7.How can I determine the highest floor of a 100 story building that an egg can be dropped from without breaking if I have two eggs?

A.Interview candidates never get this correct. It's actually pretty difficult, as most people start down the wrong track. First, everyone assumes binary search- which is wrong. Then everyone tries to minimize the equation

(100/n - 1) + (n - 1)

The first term indicates the maximum number of drops for the first egg, while the second term indicates the maximum number of drops for the second egg. The obvious answer for n is 10, which gives you a maximum of 18. This is wrong.

What we should optimize for instead is always having the same maximum number of drops left regardless of the outcome. Every time the egg doesn't break, we should have n-1 drops remaining; and if the egg does break, we should have n-1 drops remaining. This forces us to always increment our floor by one fewer whenever the first egg does not break. If we were to start at floor 10, we would then have to move to floor 19, then 28, and so on. Thus the floors on which we should drop the first egg (assuming no breaks) are:

n
n + n - 1
n + n - 1 + n - 2
n + n - 1 + n - 2 + n - 3
...

Which, after n iterations, needs to be above 100. To simplify, this basically means we should find the minimum value for n such that that SUM(1..n) >= 100.

n(n+1)/2 > 100 implies n > 13. Thus, n = 14, both our starting floor and the number of iterations required to figure out the strength of the eggs.

8.How would you cure world hunger?

A.(An oft-ignored factor underlying the dramatic growth in economic productivity in East Asia and South Asia in the latter half of the 20th century is the dramatic improvement in crop yields in these regions, an improvement that has yet to occur in most of Sub-Saharan Africa.)
Higher agricultural productivity makes it much easier for a country to be self-sufficient. More food = less hunger, export opportunities, and a larger proportion of the labor force that can get an education and move up to higher-paying jobs.

Achieving this is far from simple, but in India (as well as Pakistan and Mexico), the improvement is attributed largely to the work of people like Nobel Laureate Norman Borlaug, who developed genetically modified grain varieties that were disease-resistant and offered higher yields. This change is often referred to as "The Green Revolution." However, a given improvement often works only in a given climate, and we have largely yet to achieve this same revolution for most of sub-Saharan Africa.

Thus, believe that history tells us that part of the effort to end world hunger should be research for seed varieties and farming techniques that lead to higher crop yields in the world's poorest countries. 

9.You’re in a row boat, which is in a large tank filled with water. You have an anchor on board, which you throw overboard (the chain is long enough so the anchor rests completely on the bottom of the tank). Does the water level in the tank rise or fall?.

A:The water level drops, because while in the boat, the anchor displaces water of equal mass, but when outside the boat, it only displaces water of equal volume, and since the anchor is denser than water, then water of equal mass to the anchor has more volume

10.You have a bouquet of flowers. All but two are roses, all but two are daisies, and all but two are tulips. How many flowers do you have?
A.3 flowers. 1 of each. 

11.You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

A.Break the balls into the following groups: (1,2,3),(4,5,6),(7,8)

Step 1. Weigh (1,2,3) against (4,5,6)
Two possible outcomes: 
The two groups are equally heavy. (Case A)
One of these groups is heavier than the other. (Case B)

Case A --> Weigh 7 against 8. Now you have identified the heavier ball in 2 weighing.
Case B --> Take the heavier group (assume it to be (1,2,3)), take any two balls and weigh them against each other. Either one of these is heavier else the third ball is.

12.Why are manholes cover round?

A.Round covers are used when the hole they are covering up is also round. It's simplest to cover a round hole with a round cover.
We have to look at what is under the cover to answer that question. The hole below the cover is round because a cylinder is the strongest shape against the compression of the earth around it. Also, the term "manhole" implies a passage big enough for a man, and a human being climbing down a ladder is roughly circular in cross-section. So a cylindrical pipe is the natural shape for manholes. The covers are simply the shape needed to cover up a cylinder
http://hebig.org/blog/003029.php

13.There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly?

A.Open the box that is labeled "Apples and Oranges".

You know that since none of the labels are correct, the box must either contain only apples, or only oranges.

Suppose, w.l.o.g., that you remove an apple from that box. Therefore, that box is the "Apples Only" box.

One of the two remaining boxes must be the "Oranges Only" box. However, one of them is labeled "Apples Only", and the other is labeled "Oranges Only". Therefore, the one labeled "Apples Only" is the box that contains only oranges, and the box labeled "Oranges Only" is the box that has both kinds of fruit.

14.How would you explain a database in three sentences to your 8-year-old nephew?

A.You know how you have to put your toys away when you're done playing, so you can find them easily the next time you want to play with them?

A database is like a shelf to put your toys away, except the toys are data instead.

Now, the database can always find the right data easily - whether it's "all the dinosaur toys" or "all the yellow toys," the computer can get everything out to play with very quickly, because it's in a database.

http://techgurustalk.blogspot.com/2011/12/odd-interview-questions-and-answers.html

Unix shortcuts

• Unix LS Command
• Find command
• History command
• Top command
• Sed command
• Awk command
• Perform SSH login without password

My senior interview experience for SDE2 position

Every round had exactly 2 questions. Even if you answer it at first shot, you will be asked to more deeper into it so that half an hour is spent on that.

I:
What is Hashing, hash map
Recursive and Iterative solution for in-order traversal of a binary tree
Implement queue from two stacks.

II:
Design "Customers who bought also bought" section in ecommerce site.
Design a restaurant order management system. 

III:
Given a BST, populate a pointer 'inOrderSuccessor' at every node of the tree. Should not use any global variables. No coding.
Given an array, find the maximum sum obtained by adding as many number of elements as you like, but not including any adjacent elements. No coding.

IV:
Given 3 sorted arrays, find a triplet (3 numbers taken one from each array) whose difference between max and min is minimum.
Eg: (1,2,3), (4,5,6), (7,8,9) - one max triplet is (3,6,7) where the max diff is 4 (7-3).  4 is the lowest among any triplet you consider. Optimize for < n^3. (Use merging technique) Just approach, no coding.
Design a java Vector class which allows a maximum of 3 threads to access add & get methods simultaneously.
J2EE questions - very quick / easy ones.

V:
Conflicts with your manager - how did you solve, how will you handle if your manager asks you to put a hack.
How will you keep yourself upto date with the technology?
How will you code review?
How will you mentor new hires?
Design Chess game. Code the move coin method. - There are actually too many edge cases to consider. Consider check every move, check mate, pawn movements, horse jump, pawn to queen, castling, etc. (Code it down)

 VI:
Tell your current company's architecture.
Find if a tree is a subtree of another tree. (Code it down)
Convert a number to Roman equivalents. (Code it down)

VII:
Architecture for sending pdf to kindle device: Every kindle device has a unique email id. If you want to send a pdf to the kindle device, you compose an email in your personal email client(gmail) and send to the kindle unique email, backend should receive email, convert to kindle's own format and send to the device.(assume you have webservice to send to kindle device over internet). How will you scale now with your architecture. Identify bottlenecks (Eg. conversion from pdf to kindle format takes CPU, etc)

Find if a binary tree is a mirror image at its root. If you cut the binary vertically at the root, the tree should be a mirror image. code it down.

VIII:

You are given a function addLinkedList which takes in 2 parameters - h1 & h2 denoting the head pointers of 2 linked lists. Write a function which returns a list having addition of the two input list.

Sample TestCases:

Input #00:

2->3->9->7

5->1->7

Output #00:

2->9->1->4

Explanation:

The 1st linked list represents the number 2397 and the second represents 517. The sum of these 2 numbers results in the number 2914 which the resultant linked list represents.

-----------------------------

Another Person:

 Ist round:

 a) Merge 2 BST 

 b)  Lexical ordering of permutation -- eg 12354, then what is the next lexical permutation 12435

2nd round

a) Sorted rows and sorted column in a matrix, Find whether an element x is present or not.

b) M[i,j]=1  if j is the descendent of i in nary tree. Construct this matrix.

3rd round:

a) find LCA of 2 nodes in a binary tree.

b) Extend it to k nodes in a binary tree 

  

4th round:

  a) How makefile compilation work, how it is be represented.

  b) Inheritance question and Singleton Thread synchronisation

5th round

 a) Random pointer in a link list, Clone another list, which has the similar structure of 1st list

 b) Run Length Encoding  eg abbcc then ans ab2c2

-----------------

Another person

Round 1:

1. Vertical traversal of binary tree. Your should print nodes in the vertical lines.

2. Given a range (say, 5 to 100) , you should do dictionary operations like insert,delete,search,random operations.

    Note: Initially, i said array, then queue, then map. Interviewer is not expecting exact answer. he is just observing the way we handles the problem.

Round 2:

1. Given binary tree with left and right child, we should create new tree with left child becomes first child and right child becomes sibling of first child. So, the new tree has two pointers, one for first child, and another points to its sibling.

2. Given an array, print all pairs whose sum is also a number in the same array.We should not use hashmap. It's fine, if complexity is more.

Round 3:

1 . Standard Java questions, thread sync problem in singleton pattern (adding extra null check).

Round 4: (Bar Raiser Round)

1. Given n players, where everyone had played against every other person at least once. Now, we have to stand the player in a line such that immediate left of the current player should have lost to him. (I didn't give the correct answer).

2. General questions, like achievements in previous company, any conflict with managers and how u handled that.etc.

Round 5:

1. print two dimensional matrix spirally, (like , from East -> South -> West -> North ),  

2. Given array of integers, we should form another array where each element is the product of elements in the given array except that index. 

For eg:, input is 5,6,1,3,2  .... then, o/p will be 36,30,180,90

Note: we should not use division operator. But, we can use extra space. 

Interview experience with via.com

1)  Asked me brief intro about myself.

2)  Why do you want to change company?

3)  Given a string. Remove duplicate characters from the string in optimum way.

4)  How do u design a stack such that push(), pop() and getMin() opearations are done in O(1) time complexity

5)  Given two sorted arrays. Return Kth maximum sum formed by pairs of elements such that first element in from array1 and second element is from array2.(For this one i gave brute force approach)

6)  Given a sorted rotated array.Write an algorithm to find the element in the array.

7) Did you ever override hashcode() method ? If yes, in which cases you overrode?

8) Advantage of using Thread class over Runnable interface?

Graph questions

• Depth first traversal of a graph
• Breadth first traversal of a graph
• Detect cycle in a graph
• Find if there is a path between two vertices in a directed graph

Detecting and fixing memory leaks in java

What sort of memory leaks are possible in Java and how do I prevent them?

In any language, application-level memory management problems revolve around the deallocation of memory. These problems fall into two categories: premature deallocation (corrupted pointers) and incomplete deallocation (memory leaks).

In the case of incomplete deallocation, there are two subcases: coding bugs and design bugs. Coding bugs are language dependent. In the case of C, this would involve free()ing less than was malloc()ed, while in C++ this might involve using delete in lieu of delete[]. Design bugs, on the other hand, do not depend on the language; instead, they involve simple programmer negligence.

In languages like C/C++, all memory management is handled by the programmer, so all of these problems can arise, even after the programmer has expended much effort to ensure the code is free of such defects. In fact, in C/C++ the more you try to avoid memory leaks, the more likely you are to create corrupted pointers, and vice versa. And, by nature the risk of such bugs increases with code size and complexity, so it's difficult to protect large C/C++ applications from these types of bugs.

In Java, on the other hand, the Java language and runtime together entirely eliminate the problems of corrupted pointers and code-level memory leaks. Here's how:

• In Java, memory is allocated only to objects. There is no explicit allocation of memory, there is only the creation of new objects. (Java even treats array types as objects.)
• The Java runtime employs a garbage collector that reclaims the memory occupied by an object once it determines that object is no longer accessible. This automatic process makes it safe to throw away unneeded object references because the garbage collector does not collect the object if it is still needed elsewhere. Therefore, in Java the act of letting go of unneeded references never runs the risk of deallocating memory prematurely.
• In Java, it's easy to let go of an entire "tree" of objects by setting the reference to the tree's root to null; the garbage collector will then reclaim all the objects (unless some of the objects are needed elsewhere). This is a lot easier than coding each of the objects' destructors to let go of its own dependencies (which is a coding-level problem with C++).

So what about memory leaks caused by poor program design? In such designs, unnecessary object references originating in long-lived parts of the system prevent the garbage collector from reclaiming objects that are in fact no longer needed. Such errors typically involve a failure "in the large" to properly encapsulate object references among various parts of the code.

Another design flaw occurs "in the small," at the level of a faulty algorithm; the use of Collections objects in such cases will typically magnify the error.

As the technology improves, a suitably implemented JVM could help reduce the effects of such designed-in memory leaks by using the garbage collector to track object usage over time. The garbage collector could then rearrange objects in memory according to a freshness factor based on when they were last referenced, for example. Stale objects would become eligible for physical RAM swap-out (even though, for safety, they would still exist).

Ideally of course, programmers would design applications with objects' lifecycles in mind, rather than rely on clever features of state-of-the-art JVM implementations.

In conclusion: Design problems can be mitigated by letting go of object references in one's own classes as soon as one can (knowing that in Java there is no risk of damaging another part of the code).

Tip: The KL Group's JProbe tool can help identify possible sources of memory leaks by showing which objects are holding on to graphs of references to other objects.

Note: Implementations of Sun's JVM prior to HotSpot used a technique called conservative garbage collection, which could introduce memory leaks of its own, beyond those caused by the programmer. To wit, as long as the application contained a 32-bit integer primitive (int) whose value coincided with the address of an object, the garbage collector would not reclaim the object. Although the likelihood was small, it wasn't zero. For this reason, and for the best performance in general, use HotSpot where possible.

Refer :

http://java.dzone.com/news/how-fix-memory-leaks-java 

http://stackoverflow.com/questions/1716597/java-memory-leak-detection-tools 

Vertical sum in a binary tree

Refer : http://www.geeksforgeeks.org/archives/18215

import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.Iterator;

public class VerticalSumInTree {
 public static void main(String[] args) {
  Node root = getTree();
  printVertcalSumsInTree(root);
 }

 private static Node getTree() {
  Node node4 = new Node(4);
  Node node5 = new Node(5);
  Node node6 = new Node(6);
  Node node7 = new Node(7);
  Node node2 = new Node(2, node4, node5);
  Node node3 = new Node(3, node6, node7);
  Node root = new Node(1, node2, node3);
  return root;
 }

 private static void printVertcalSumsInTree(Node root) {

  if (root == null)
   return;

  // Used for storing nodes matches to same horizontal distance
  Map<Integer, List<Node>> map = new HashMap<Integer, List<Node>>();
  calculateVerticalSum(root, map, 0);

  printVerticalSums(map);
 }

 private static void printVerticalSums(Map<Integer, List<Node>> map) {
  if (map == null) {
   System.out.println("Tree is empty");
  } else {
   Set<Integer> keys = map.keySet();

   // Sort the keys
   // convert set to list for sorting.Because collections accepts list
   // for sorting
   List<Integer> keysList = new ArrayList<Integer>(keys);
   Collections.sort(keysList);
   // For each key, get the list of values
   for (Integer key : keysList) {
    List<Node> list = map.get(key);

    // Iterate through the list elements and calculate the sum
    int sum = 0;
    Iterator<Node> it = list.iterator();
    while (it.hasNext()) {
     Node n = it.next();
     sum = sum + n.value;
    }
    System.out.println(sum);
   }
  }
 }

 private static void calculateVerticalSum(Node root,
   Map<Integer, List<Node>> map, int horizontalDistance) {

  if (root == null)
   return;

  // Add this value to the map
  List<Node> list = map.get(horizontalDistance);
  if (list == null) {
   list = new ArrayList<Node>();
  }

  list.add(root);
  map.put(horizontalDistance, list);

  // iterate for left and right trees
  calculateVerticalSum(root.left, map, horizontalDistance - 1);
  calculateVerticalSum(root.right, map, horizontalDistance + 1);
 }

 public static class Node {

  public int value;

  // member variables will be initialized to null by default.
  public Node left;
  public Node right;

  public Node(int value) {
   this.value = value;
  }

  public Node(int value, Node left, Node right) {
   this.value = value;
   this.left = left;
   this.right = right;
  }

 }
}