Interviewing Problem Solving

A large cosmetics company had a problem that some of the soap boxes coming off the production lines were empty. The problem was quickly isolated to the assembly line, which transported the packaged boxes of soap to the delivery department: some soap boxes went through the assembly line empty.
The management asked its engineers to solve the problem. They spent much time and money in devising an X-ray machine with high-res monitors manned by staff to watch all the boxes on the line to make sure they weren't empty.
A workman hearing about this, came up with another solution. He got a powerful industrial fan and pointed it at the assembly line. As each soap box passed the fan, the empty boxes were blown off the line. Moral: the simplest solution is usually the best!

 In Chinese the character for danger and opportunity is the same. Well maybe not but it sounds good!

A study in the Personality and Social Psychology Bulletin suggests you are more likely to succeed if you solve a difficult problem on another person’s behalf rather than for yourself. One of the problems was:
A prisoner was attempting to escape from a tower. He found a rope in his cell that was half as long enough to permit him to reach the ground safely. He divided the rope in half, tied the two parts together, and escaped. How could he have done this?
Students were asked to think of either themselves or a stranger stuck in the tower. 66% of the students who imagined a stranger in the tower, found the solution compared with 48% of those who envisaged themselves in the tower. THe authors said if we imagine that our problems belong to someone else, we might find better solutions. The solution, by the way is to split the rope lengthwise.

It's not that I'm so smart, it's just that I stay with problems longer.

Albert Einstein

Leaders are problem solvers by talent and temperament, and by choice.

Harlan Cleveland

Problems are only opportunities in work clothes.

Henri Kaiser

Difficulties are opportunities to better things; they are stepping-stones to greater experience.... When one door closes, another always opens.

Brian Adams

Every exit is an entry somewhere else.

Tom Stoppard

There are no foolish questions and no man becomes a fool until he has stopped asking questions.

Saul Steinberg

The most serious mistakes are not being made as a result of wrong answers. The truly dangerous thing is asking the wrong questions.

Peter Drucker

It is better to know some of the questions than all of the answers.

James Thurber

The mere formulation of a problem is far more often essential than its solution.

Albert Einstein

For every failure, there's an alternative course of action. You just have to find it. When you come to a roadblock, take a detour.

Mary Kay Ash

When life gives you a lemon, make lemonade.
If you really want something you can figure out how to make it happen.

Cher

The creation of a thousand forests is in one acorn.

Ralph Waldo Emerson

Whether you believe you can, or whether you believe you can't, you're absolutely right.

Henry Ford

Never doubt that a small group of thoughtful, committed citizens can change the world. Indeed it's the only thing that ever has.

Margaret Mead

It is easier to tone down a wild idea than to think up a new one.

Alex Osborne

The best way to get a good idea is to get a lot of ideas.

Linus Pauling

Even if you are on the right track, you will get run over if you just stand there.

Will Rogers

The human mind is like a parachute - it functions better when it's open.

Cole's Rules

The man with a new idea is a crank - until the idea succeeds.

Mark Twain

Martin Luther King said "I have a dream", not "I have a plan. 


Example 1
This is an example in which you can find a solution once you analyze and understand the unknowns and data.

Problem: A survey of TV viewers shows the following results:
To the question "Do you watch comedies ?", 352 answered "Yes".,
To the question "Do you watch sports ?", 277 answered "Yes", and
To the question "Do you watch both comedies and sports ?", 129 answered "Yes".

Given these data, find, among people who watch at least one of comedies and sports, percentages of people who watch at least one of comedies and sports watch only comedies, only sports, and both comedies and sports.

Let us try to solve this problem following the framework presented above.

Understanding the Problem: This is a "find" type problem. So we try to identify unknowns, data and conditions.
The unknowns are the percentage of people who watch only comedies, the percentage of people who watch only sports, and the percentage of people who watch both comedies and sports.
The data are the three numbers: 352, 277 and 129, representing the number of people who watch comedies, sports, and both comedies and sports, respectively. Note that 352 includes people who watch both comedies and sports as well as people who watch only comedies. Similarly for 277.
The conditions are not explicitly given in the problem statement. But one can see that the percentages must add up to 100, and they must be nonnegative.

Devising a Solution Plan: Here we first examine the principal parts in detail.
First let us consider the unknowns in more detail. To calculate the percentage of the people who watch only comedies, for example, we need the number of people who watch at least one of comedies and sports, and the number of people who watch only comedies. Thus actually two unknowns are involved in each of the required percentages, and the real unknowns are the number of people in each of the categories, and the number of people who watch at least one of comedies and sports.

Next let us look at the data. First the number 352 is the number of people who watch comedies. But that is not necessarily that of the people who watch only comedies. It includes that and the number of people who watch both comedies and sports. Similarly for the second number 277.

Let us use symbols to represent each of the unknowns: Let C represent the number of people who watch only comedies, S that of the people who watch only sports, and T that of the people who watch at least one of those programs.
Then we have the following relationships among the unknowns:
C + 129 = 352
S + 129 = 277
C + S + 129 = T

From these equations we can easily obtain C = 223, S = 148, and T = 500 .
Thus the required percentages are 44.6%, 29.6%, and 25.8%, respectively.

All we had to do to solve this problem is to analyze relationships between the data and the unknowns, that is, nothing much beyond "understanding the problem".


Next -- Problem Solving -- Example 2

Back to Schedule
Back to Table of Contents








Example 2
This is a problem which you can solve using similar known results.

Problem: Find the (length of) diagonal of a rectangular parallelepiped given its length, width and height.

Again let us try to solve this problem following the framework presented above.

Understanding the Problem: This is a "find" type problem. So we try to identify unknowns, data and conditions.
The unknown is the diagonal of a rectangular parallelepiped, and the data are its length, width and height. Again there are no explicitly stated conditions. But the unknown and data must all be a positive number.

Before proceeding to the next phase, let us make sure that we understand the terminologies.
First a rectangular parallelepiped is a box with rectangular faces like a cube except that the faces are not necessarily a square but a rectangle as shown below.



Next a diagonal of a rectangular parallelepiped is the line that connects its two vertices (corner points) that are not on the same plane. It is shown in the figure below.



Devising a Solution Plan: Here we first try to find relevant facts. Relevant facts often involve the same or similar words or concepts. Since the unknown is a diagonal, we look for facts concerning diagonal. Note that drawing figures here is quite helpful.
One of the facts that immediately comes to our mind in this problem is Pythagoras' theorem. It has to do with right triangles and is shown below.



Let us try to see whether or not this theorem helps. To use this theorem, we need a right triangle involving a diagonal of a parallelepiped. As we can see below, there is a right triangle with a diagonal x as its hypotenuse.



However, the triangle here involves two unknowns: x and y. Since x is what we are looking for, we need to find the value of y. To find y, we note another right triangle shown below.



Applying Pythagoras' theorem again, we can obtain the value of   y.
Thus   y² = a² + b²
is obtained from the second triangle, and
x² = c² + y²
is derived from the first triangle.
From these two equations, we can find that x is equal to the positive square root of   a² + b² + c² .
 

Basic Programming Questions

http://blogs.msdn.com/b/nikhilsi/archive/2011/07/16/programming-interview-questions-and-answers.aspx

 

 Simple coding questions–Part 1

During an interview (either in person or over phone), many interviewers like to ask very simple coding questions. This is usually to check how fast the interviewee can do a context switch in her mind, her ability to think about some very basic problem, etc.
So, let’s tackle a few of such coding problems in this post. I am using C# as the programming language in this example, but you can do the same in almost any modern language.

How to find the largest of 3 numbers

using System;

namespace SimpleCodingQuestions
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindLargestNumber(6, 3, 9));
        }

        /// <summary>
        /// Find the largest of three numbers
        /// </summary>
        /// <param name="a">first parameter</param>
        /// <param name="b">second parameter</param>
        /// <param name="c">third parameter</param>
        /// <returns></returns>
        public static long FindLargestNumber(long a, long b, long c)
        {
            // assume that the first value is the biggest
            long biggest = a;

            // check if b is the biggest
            if (b > biggest)
                biggest = b;

            // check if c is the biggest
            if (c > biggest)
                biggest = c;

            return biggest;
        }
    }
}

My next follow-up question is: Can you find the largest number in a variable length argument list? For those who come from the C/C++ background, this is the same as va_args list. In C#, this is referred by the the params keyword.

The params keyword lets you specify a method parameter that takes a variable number of arguments.

You can send a comma-separated list of arguments of the type specified in the parameter declaration, or an array of arguments of the specified type. You also can send no arguments.

No additional parameters are permitted after the params keyword in a method declaration, and only one params keyword is permitted in a method declaration.

For more details, refer to the MSDN article at http://msdn.microsoft.com/en-us/library/w5zay9db.aspx

Find the largest number in a variable length argument list

using System;

namespace SimpleCodingQuestions
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindLargestNumber(6, 3, 9));
            Console.WriteLine(FindLargestNumber(6));
            Console.WriteLine(FindLargestNumber(6, 3, 9, 2, 5, 8));
        }

        /// <summary>
        /// Find the largest number in a variable list 
        /// </summary>
        /// <param name="a">first parameter. Required.</param>
        /// <param name="numbers">variable list of longs</param>
        /// <returns></returns>
        public static long FindLargestNumber(long a, params long[] numbers)
        {
            // assume that the first value is the biggest
            long biggest = a;

            // loop through all the arguments passed
            foreach (long x in numbers)
            {
                // check if the current number is the biggest
                if (x > biggest)
                    biggest = x;
            }

            return biggest;
        }
    }
}

I hope this post helped you grasp an important concept. No question is simple. Even trivial questions can catch you off guard. Keep your focus razor sharp at all times. We will discuss a few more simple coding questions in the coming blog posts

 

 

 How to find if a number is a Palindrome?

Read the question. Listen very carefully to the question. Each word may have a meaning. In my experience, I have seen many interviewees just hear the last word: palindrome. Then I start getting solutions and examples of palindrome words. But note the question: It says a number. String operations are way more costly than number crunching.

Let's now dive into some possible solutions for this problem.

public static bool IsPalindrome(long number)
{
bool isPalin = true;

// inefficient solution - convert number to string
string numAsStr = number.ToString();

// more inefficiency - looping through the entire string
// could have achieved the same by traversing just half the string
for (int i = 0, j = numAsStr.Length - 1; i < numAsStr.Length - 1; i++, j--)
{
if (numAsStr[i] != numAsStr[j])
{
// the corresponding locations do not match
isPalin = false;
// some people forget to break out of the loop
// extremely bad - no need to do any further comparisons
break;
}
}
return isPalin;
}

The above solution was an in-efficient solution. It works, but does not get you any points. So, now let's see what improvements can be made to the above program.

public static bool IsPalindrome2(long number)
{
bool isPalin = true;

// inefficient solution - convert number to string
string numAsStr = number.ToString();

// we can find if a string is palindrome or not by just traversing half the string
for (int i = 0, j = numAsStr.Length - 1; i < (numAsStr.Length) / 2; i++, j--)
{
if (numAsStr[i] != numAsStr[j])
{
// the corresponding locations do not match
isPalin = false;
// some people forget to break out of the loop
// extremely bad - no need to do any further comparisons
break;
}
}
return isPalin;
}

In the above solution, we cut our execution time by almost half. Better, but not good enough. At this point, the interviewer should have a pretty good idea of your skills on reviewing code and making changes to improve it. Let's assume that he still wants you to keep digging.

public static bool IsPalindrome3(long number)
{
// since the input is a number, one very fast way way would be 
// to reverse the number and compare to original
long revNum = ReverseNumber(number);

return (number == revNum);
}

private static long ReverseNumber(long number)
{
long retVal = 0;
do
{
// get the last digit by using the modulo (remainder) operator
retVal = (retVal * 10) + (number % 10);
// drop the last digit from the number
number = number / 10;
}
while (number != 0);
return retVal;
}

If you run some performance tests with larges number sets on the above solutions, you will find that the 3rd solution is the most performant. I hope this example has shown you one way to attempt to solve a coding question. Remember, it is not just about the answer. The interviewer is trying to find your ability to think, debug and troubleshoot a problem.

Linked lists demystified

Linked lists have been a great source of interview questions. They are small, powerful and if you don’t fully understand the concepts, complicated. The interview coding solutions involving linked lists are quick and small. So, what are the typical questions on linked lists? Well, to start with, traverse, insert, delete and modify a linked list are pretty standard operations and are almost parts of a larger question. Other more complicated questions revolve around doubly linked lists, circular lists, trees, graphs and similar data structures. In this blog post, we will explore a small subset of simple linked list operations.
The basic data structure for a linked list involves 2 components: the data itself and the link to the next element. Together (data + link) this structure is typically called a Node. There are generally 2 pointers involved: a head pointer, pointing to the start of the list; and a tail pointer, pointing to the last element of the list. The key property of the last node is that it’s next pointer points to nothing (NULL).
Graphically, a linked list can be represented as a series of nodes as shown below:

In the above diagram, the node consists of an int (data) value and a pointer to the next node. The complete list contains 4 elements (2, 4, 6 and 8).
 

How to represent a linked list node?

The easiest representation of a linked list node is wrapping the data and the link in a struct and giving the (typedef’ing) the struct as a Node pointer. An example representation is
 

typedef struct linked_list
{
    int data;
    struct linked_list *next;
} Node;

How do you traverse a linked list?

Before we can do any operations on a linked list, it is best to understand how to traverse a linked list. This involves starting at the first node (using the head pointer), printing the node data, and then using the next pointer to move along the list till we reach the last node (i.e. the next pointer’s value is NULL).
 

void PrintLinkedList(Node *start)
{
    printf("\nHEAD ->");
    while (start != NULL)
    {
        printf("%d ->", start->data);
        start = start->next;
    }
    printf("NULL\n\n");
}

How to insert a node at the beginning of the list?

Inserting a node at the beginning of the list is probably the easiest of all operations. Let’s talk about what is involved here referring to the diagram above. This involves creating a new node (with the new data, say int 10), making its link point to the current first node pointed to by head (data value 2) and lasting changing head to point to this new node. Simple, right?

Node *head;
void InsertNodeInLinkedListAtFront(int data)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; // this line is not really needed

    // 2. insert it at the first position
    temp->next = head;

    // 3. update the head to point to this new node
    head = temp;
}

How to insert a node at the end of the list?

This case is a little bit more evolved. If you have a tail pointer, it is as easy as inserting at the beginning of the list. If you do not have a tail pointer, you will have to create the new node, traverse the list till you reach the end (i.e. the next pointer is NULL) and then make that last node’s next pointer point to the new node.

void InsertNodeInLinkedListAtEnd(int data)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; 

    // check if the list is empty
    if (head == NULL)
    {
        head = temp;
        return;
    }
    else
    {
        // 2. traverse the list till the end
        Node *traveller = head;
        while (traveller->next != NULL)
            traveller = traveller->next;

        // 3. update the last node to point to this new node
        traveller->next = temp;
    }
}

How to insert a node in a random location in a list?

This is the case when you would like to insert a node into the linked list at a given position. As above, you would first create the new node. Now if the position is 1 or the list is empty, you would insert it at first position. Otherwise, you would traverse the list till either you reach the desired position or the list ends. Then you would insert this new node. Inserting in the middle is the tricky case as you have to make sure you do the pointer assignment in the correct order. First, you would set the new nodes next pointer to the node before which the new node is being inserted. Then you would set the node pointing to the position to point to the new node. Review the code below to get more clarification.

void InsertNodeInLinkedList(int data, int position)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; 

    // check if the position to insert is first or the list is empty
    if ((position == 1) || (head == NULL))
    {
        // set the new node to point to head 
        // as the list may not be empty
        temp->next = head;
        // point head to the first node now
        head = temp;
        return;
    }
    else
    {
        // 2. traverse to the desired position
        // or till the list ends; whichever comes first
        Node *t = head;
        // remember, we already covered the 1st case
        int currPos = 2; 

        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }

        // 3. now we are at the desired location
        // 3.a. first set the pointer for the new node
        temp->next = t->next;
        // 3.b. now set the previous node pointer
        t->next = temp;
    }
}

How to delete a node at a specific location?

Deleting a node requires you to pay careful attention to the next pointers. If you do not sequence your operations correctly, you will land up with orphaned lists.Review the function below carefully.

// delete node from the list at the specified 
// position. return a 0 if deletion fails
// assumption: head is defined elsewhere
int DeleteNodeFromLinkedList(int position)
{
    // if the list is empty, return 0
    if (head == NULL)
        return 0;

    // special case: deleting first element
    if (position == 1)
    {
        // set the head to point to the node 
        // that head is pointing to
        head = head->next;
    }
    else
    {
        // deleting at any other position
        // traverse to the desired position
        // or till the list ends; whichever comes first
        Node *t = head;
        // remember, we already covered the 1st case
        int currPos = 2; 

        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }

        // now comes the tricky part
        // you have to point the current node to its next node
        if (t->next != NULL)
            t->next = t->next->next; // NOTE THIS
        else
            return 0; // could not find the correct node
    }
    // deletion successful
    return 1;
}

In this lesson, we covered a lot of ground. We first looked at the basics of a linked list, review the data structure followed by inserting elements in a linked list at various points. Finally we reviewed how to delete elements from a linked list. Please feel free to post a comment if you would like me to discuss any other operations.

Recursion–concepts and code

Recursion is a simple yet powerful concept that has been around for some time in our lives. In simple terms, recursion is the process in which the function keeps calling itself (with possibly a different set of arguments) till some base condition is met. For a procedure to be truly recursive, it should have 2 parts – an end condition (a statement that returns a value) and one or more calls to itself. Let’s see this with a common example – factorial.

Find the factorial of a number using recursion

public static long Factorial(long number)
{
    // base condition - if the number is 0 or 1, return 1
    if (number <= 1)
        return 1;
    else
    {
        // recursive call to get the factorial again
        return number * Factorial(number - 1);
    }
}

As you can see in the above example, there is a base condition that allows the recursive call to terminate and then there is the recursive call itself. Let’s look at another example: Fibonacci sequence.

 

Fibonacci Sequence Generation using Recursion

The Fibonacci sequence is a classic example of recursion:

• Fib(0) is 0 [base case]
• Fib(1) is 1 [base case]
• For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

public static int GenerateFibonacci(int count)
{
    if (count <= 1)
        return 1;
    else
        return GenerateFibonacci(count - 1) + GenerateFibonacci(count - 2);
}

Apart from these 2 classic recursion problems, another one that I love to ask is how to find the GCD (greatest common divisor) of 2 numbers. For example, the GCD for 4 and 8 is 4, for 6 and 8 is 2, for 13 and 45 is 1 and so on. Let’s see how we can solve this using recursion.

Find Greatest Common Divisor (GCD) of 2 numbers using recursion

public static int Gcd(int number1, int number2)
{
    // find the remainder
    int remainder = number1 % number2;
    // base condition - if the number divide
    if (remainder == 0)
        return number2;
    else // recurse
        return Gcd(number2, remainder);
}

Recursion is a very powerful technique and extreme care should be exercised to make sure you have a valid base condition and the recursive call. If not coded properly, it is very easy to have stack overflow from recursion.

very good explanation.A little observation for the GCD code, the last line should be :
Gcd(number2, remainder);
and not
return Gcd(number2, remainder);

http://www.vogella.com/articles/JUnit/article.html

 A unit test is a piece of code written by a developer that executes a specific functionality in the code under test. Unit tests ensure that code is working as intended and validate that this is still the case after code changes.

1.2. Unit Testing with JUnit

JUnit 4.x is a test framework which uses annotations to identify methods that are tests. JUnit assumes that all test methods can be executed in an arbitrary order. Therefore tests should not depend on other tests.
To write a test with JUnit

• Annotate a method with @org.junit.Test
  
• Use a method provided by JUnit to check the expected result of the code execution versus the actual result
  

You can use Eclipse or the class "org.junit.runner.JUnitCore" to run the test.

2. Installation of JUnit

If you use Eclipse you can use the integrated JUnit in Eclipse for your testing.
If you want to control the used JUnit library explicitly, download JUnit4.x.jar from the JUnit website at http://www.junit.org/ . The download contains the "junit-4.*.jar" which is the JUnit library. Add this library to your Java project and add it to the classpath.

3. Using JUnit

3.1. Preparation

Create a new project de.vogella.junit.first. We want to create the unit tests in a separate folder. The creation of a separate folder for tests is not mandatory. But it is a good practice to keep the code separated from the regular code. You might even create a separate project for the test classes, but we skip this step to make this example simpler.
Create a new source folder test via right-clicking on your project, select "Properties" and choose the "Java Build Path". Select the "Source" tab.

Press "Add folder" then press "Create new folder". Create the folder "test".

Alternatively you can add a new source folder by right-clicking on a project and selecting New → Source Folder.

3.2. Create a Java class

In the "src" folder, create the de.vogella.junit.first package and the following class.

    
package de.vogella.junit.first;

public class MyClass {
 public int multiply(int x, int y) {
  return x / y;
 }
}
   

3.3. Create a JUnit test

Right click on your new class in the Package Explorer and select New → JUnit Test Case. Select "New JUnit 4 test" and set the source folder to "test", so that your test class gets created in this folder.

Press "Next" and select the methods which you want to test.

If the JUnit library in not part of your classpath, Eclipse will prompt you to do so.

Create a test with the following code.

    
package de.vogella.junit.first;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MyClassTest {

 @Test
 public void testMultiply() {
  MyClass tester = new MyClass();
  assertEquals("Result", 50, tester.multiply(10, 5));
 }
}
   

3.4. Run your test via Eclipse

Right click on your new test class and select Run-As → JUnit Test.

The result of the tests will be displayed in the JUnit View.

The test should be failing (indicated via a red bar).
This is because our multiplier class is currently not working correctly (it does a division instead of multiplication). Fix the bug and re-run test to get a green bar.
If you have several tests you can combine them into a test suite. Running a test suite will execute all tests in that suite.
To create a test suite, select your test classes → right click on it → New → Other → JUnit → Test Suite.

Select "Next" and select the methods for which you want to create a test.
Change the code to the following to make your test suite run your test. If you develop another test later you can add it to @Suite.SuiteClasses.

    
package mypackage;

import org.junit.runner.RunWith;
import org.junit.runners.Suite;

@RunWith(Suite.class)
@Suite.SuiteClasses( { MyClassTest.class })
public class AllTests {
}