http://blogs.msdn.com/b/nikhilsi/archive/2011/07/16/programming-interview-questions-and-answers.aspx
Simple coding questions–Part 1
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?
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
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 istypedef 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
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);
No comments:
Post a Comment