Technical Interview Questions

Reverse Minesweeper

2010-08-01T23:52:00.000-07:00

Question: The interviewer first discussed the game of minesweeper and the gave a reverse minesweeper problem where the specifications were as follows: 1. A block of M rows by N columns is given 2. Each item can either be a mine or not a mine 3. The location of the mines in the block is given by the character * 4. Normal/safe squares are marked by '.' (dots) See the below table and write a

How and why to prevent class inheritance in C#/.NET

2009-11-23T10:26:00.000-08:00

Question: In .NET/C#, how does one prevent a class from being inherited by another class? In other words can the inheritance of class be blocked? Also, what is the reason one might want to block the inheritance chain? The sealed keyword/modified in .NET can be used to block derivation from a class. An attempt to inherit from a class marked as sealed will result in a compile time error. Also, a

Difference Between calloc, malloc, and realloc

2009-11-16T04:01:00.000-08:00

Question: What is the difference between malloc(), calloc(), and realloc() malloc, calloc, and realloc are functions used for memory allocation in C/C++ languages. There are some fundamental differences on how the above functions work. realloc() First of all realloc() is actually a reallocation function. It is used to resize a previously allocated (using malloc(), calloc(), or realloc()) block

Must Read Books for Technical/Programming Interview Preparation

2009-11-03T20:02:00.000-08:00

Coding, Program Design and Interview Questions: Programming Interviews Exposed: Secrets to Landing Your Next Job ~ John Mongan, Noah Suojanen, and Eric Giguère Programming Pearls (2nd Edition) ~ Jon Bentley Expert C Programming: Deep C Secrets ~ Peter van der Linden Puzzles for Programmers and Pros ~ Dennis Shasha More Programming Pearls: Confessions of a Coder ~ Jon Bentley Programming

Implement Two stacks using one array

2009-04-02T15:48:00.001-07:00

Problem: How to implement/code two stacks using one array. Solution: The obvious solution is to have the two stacks at the two ends of the array. The stacks will grow in opposite direction. When the two stacks collide and there is no more room in the array the stacks will over flow. This problem is probably one of the easier problems and targeted towards exercising your array index manipulation

Determine and display all anagrams in a string array

2009-03-22T23:28:00.001-07:00

Question: Given an array of strings (string[] inputStrings). Devise a way and write the code to determine and display all the anagrams in the array. Solution: With any interview question one should get the specifics of the problem and the input data before designing the solution. In this particular case, we should ask about the approximate number of strings in the array, average length of each

Print 2D Array Matrix Spiral Order

2009-03-03T18:15:00.000-08:00

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10. Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to

DNA Sequence Pattern Match/ String Search Problem

2009-03-01T17:02:00.000-08:00

Question: The DNA double helix consists of a long strand of four bases: adenine (abbreviated A), cytosine (C), guanine (G) and thymine (T). Thus, it can be represented as a long string containing the characters A, C, G, and T. The field of bio-informatics involves storing and searching of DNA sequence data. What is a good data structure to facilitate storage and string match/search operation on

Database Isolation Levels in Sql Server and ADO.NET

2009-02-20T14:33:00.000-08:00

Isolation level refers to I in the ACID properties for a Transaction. ACID stands for Atomicity, Consistency, Isolation, Durability. Isolation level refers to sensitivity of a database transaction to other changes in other transactions. You can set the isolation level for a transaction using the following command in T-SQL: SET TRANSACTION ISOLATION LEVEL can be one of

Database Normalization Basics

2009-02-19T11:40:00.000-08:00

First Normal Form (1NF): Identify related groups of data (ex: orders, customers, products) and create separate tables for each group.All tables should have a Primary Key identifying an individual row in a table.No two columns in a table should have the same information and each column can contain only one attribute.In essence 1st normal form is about removing redundant data and creating tables

SQL Server Index Fragmentation and Resolution

2009-02-18T14:29:00.000-08:00

What is Index Fragmentation and how do you resolve it in SQL Server? Answer: I came across and excellent article on index fragmentation and 4 ways to resolve it on Sql-Server-Performace.com which describes it in great detail.

Find an Item in a Sorted Array with Shifted Elements

2009-02-10T14:39:00.000-08:00

Problem: You are given a sorted array with shifted elements. Elements can be shifted to the left or right by 'i' number of places. The sign of 'i' denotes the direction of the shift. For positive 'i' direction of shift is right and left for negative 'i'. For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would

Database SQL Interview Questions

2009-02-01T21:39:00.001-08:00

Write a SQL Query to find first day of month?Why there is a performance difference between two similar queries that uses UNION and UNION ALL?How to choose between a Clustered Index and a Non-Clustered Index?How you can minimize deadlock situations in a database server? When you should use low fill factor?Explain First, Second, and Third database normalization form with examples?What are the

Array: Find the number with odd number of occurrences

2009-01-28T19:23:00.001-08:00

Problem: You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer. Solution: A naive approach would be to loop over the elements of the given array and keep a count of each integer in a hash table or another counter array. But, this quickly becomes unfeasible as the range of integers could be 2^31 (one less). This is

Fibonacci Sequence Dynamic Programming

2009-01-21T13:49:00.000-08:00

Problem: Write the code for nth Fibonacci number. Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first. The Fibonacci series is defined as follows F(n) = 0 for n = 0 1 for n = 1 F(n-1) + F(n-2) for n > 1 If we translate that to the C language we get: int RecursiveFibonacci(int n) { if(n == 0)

Store a stream of numbers along with the counts

2009-01-14T15:18:00.000-08:00

Problem: Given a stream of numbers, suggest a data structure to store the numbers in the stream along with their number of occurrences. Solution: Before solving any problem make sure you lay down all the assumptions you are making and validate them with the interviewer. Assumptions here: The numbers are 32 bit integers. The size of the set (cardinality) is very small compared to the possible

Fly plane around the world half fuel puzzle

2009-01-13T14:21:00.000-08:00

There is an air force base on an island. You are given a plane to fly around the world without landing (except at the island where you started). The island lies on the equator and you will be flying around the equator, essentially a circle. The plane can carry enough fuel for half the journey. You can take help from other planes that can transfer fuel to your plane instantaneously while in

Microsoft Developer Interview Questions

2009-01-13T14:19:00.000-08:00

---------------------------- Interview 1 --------------------------------- - Why is a database useful? Why not use a file instead? - What are stored procedures and what are the benefits? - Write a program to get the nth Fibonacci number - Discussion about patterns and practices - What is database normalization? When would you use it and when would you not? What data can be left denormalized in a

Merge 2 Sorted Arrays (one has empty slots)

2009-01-07T12:48:00.000-08:00

Question: There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n). Solution: The trick to solving this problem is to start filling the destination

Largest Sum Sub-Sequence Integer Array

2009-01-03T19:46:00.001-08:00

Problem: Given an array on n integers, find a contiguous sub-sequence / subarray with largest sum. Example: For an array of following elements { -1, 2, -4, 1, 3, -2 }, the sub-sequence with largest sum is 1,3 Solution: static int Find_Max_Sum_Sub_Sequence(int[] array) { //historical max and corresponding indexes int maxSoFar = 0; int maxStart = 0;

Dynamic Programming Questions

2008-12-30T23:50:00.001-08:00

1. Longest Common Subsequence http://en.wikipedia.org/wiki/Longest_common_subsequence_problem 2.longest common substring problem http://en.wikipedia.org/wiki/Longest_common_substring_problem

Object Oriented Programmings OOPS Concepts

2008-12-29T22:57:00.000-08:00

Explain polymorphism with examples What are the 4 basics of OOP? Define Data Abstraction. What is its importance?

Design Questions

2008-12-29T19:43:00.000-08:00

Design a class library for writing card games. Design an elevator control system. Buttons are present on every floor and supporting multiple elevators. (What objects/methods/properties/how components communicate) How would you design the infrastructure front half of a very large web ecommerce site? what if it was very personalized? (how sessions are handled? where and what you can cache? how to

Questions

2008-12-29T19:17:00.000-08:00

Array How would you detect a repeated element in an integer array? Design an algorithm and write code to find two numbers in an array whose sum equals a given value. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like. Given an array containing both positive and negative integers and

Virtual Functions/Methods Runtime-Polymorphism

2008-12-28T20:04:00.000-08:00

Question: Explain the significance of virtual methods and describe how they are invoked? Virtual methods are used to support runtime polymorphism in object oriented languages.

Difference between an interface and an abstract class

2008-12-28T19:55:00.000-08:00

Two most important differences are: 1. A class can implement several interfaces but can inherit from a single abstract class (or any class for that matter) 2. Interfaces do not contain any implementation while abstract classes can contain some default implementation of methods.

Function to perform Binary Search on a Sorted Array

2008-12-28T19:18:00.001-08:00

Problem: Write a function to perform a binary search on a Sorted Array. Solution: The recursive solution below runs in O(log(n)) because the problem size is halved with each recursive call. // returns the index of the target element if found, else returns -1 static int Binary_Search(int[] arr, int start, int end, int target) { int medianIndex = (end - start) /2 +

Telephone Words Using Recursion

2008-12-28T18:50:00.001-08:00

Problem: Given a telephone number print or produce all the possible telephone words or combinations of letters that can represent the given telephone number. Solution: O(3 ^ n) (approximately - since there are 2 digits that have 4 letters) class Program { static void Main(string[] args) { int[] phoneNumber = new int[]{2,3,4}; List telephoneWords

String: Combinations Using Recursion

2008-12-28T17:33:00.000-08:00

Problem: Given a string of N characters, write a program to produce all combination of the characters. String "abc" should produce "a", "b", "c", "ab" , "ac", "bc", "abc". Solution: The recursive solution proposed below runs in O(2 ^ n). Pseudo Code: 1. If input string length = 1 return a list with the input string in it 2. if input string length > 1 a. Get list of combinations

String: Permutations Using Recursion

2008-12-28T15:03:00.001-08:00

Problem: Write the code for producing/printing permutations of the characters in a string. For example: If "abc" is the input string, output permutations should be "abc", "bac", "bca", "acb", "cab", "cba". Solution: There are at least 2 approaches to solving this problem. Even though both approaches use recursion, there is a subtle difference between the two. The second approach uses more number

String: Convert Integer to String itoa

2008-12-26T00:27:00.001-08:00

// val: integer that needs to be converted to string representation // destBuffer: buffer where the output string will be written // radix: is the radix of the numbering system (10 for decimal, 16 for Hexadecimal, // 2 for binary) char * my_itoa(int val, char * destBuffer, int radix) { if(val == 0) { destBuffer = "0"; return destBuffer; } bool isNeg = false; // if

String: Convert String To Integer atoi

2008-12-25T20:29:00.000-08:00

Problem: Implement atoi function in C language and give the test cases. atoi function converts a string to an integer. The function prototype is as follows: int my_atoi(const char str[]); Solution: The key is to be able to find out the int value of a numeric character. ASCII value of a numeric character - ASCII value of the character '0' = int value of numeric character. Ex: '8' - '0'

String: Remove Specified Characters

2008-12-25T16:25:00.000-08:00

Problem: You are given 2 strings. The first string is the input string that needs to be cleaned (in place) and the second string contains characters that need to be removed from the the first string. For example if string1 = "teetotaller" and removeString= "ae" then the output (cleaned string) will look like "ttotllr". Solution: The naive approach is as follows: Create an output buffer the same

String: Find First Non-Repeated Character

2008-12-25T13:31:00.000-08:00

Problem: Find the 1st non-repeated character in a string. Example: teetotaller The 1st non-repeated character is o. Solution: The solution involves keeping track of what characters in the string have a count of more than one. The choice of data structure we will use depends on the type of string. If the string is an ASCII string with 256 possible values then an array of size 256 would be

Tree: Find Lowest Common Ancestor

2008-12-25T12:17:00.000-08:00

Problem: Given a binary search tree and 2 values find the lowest common ancestor. Solution: Lets take a sample tree and see what finding the lowest ancestor means. The figure to the left shows the sample tree. To take an example, lets say the problem asked us to find the lowest common ancestor for nodes 10 and 14. Visually we can tell that node 12 is the lowest common ancestor. 15 is also a

Tree: PreOrder Traversal without Recursion

2008-12-25T11:13:00.000-08:00

Problem: Write the code for pre-order traversal of a binary tree without recursion. Solution: Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees

Tree: Traversal (PreOrder, InOrder, PostOrder)

2008-12-24T20:25:00.000-08:00

Problem: What are the different ways of traversing a non-empty Tree? Solution: Tree traversal can be divided into 2 major methods. First is Depth-First-Traversal and the second is Breadth-First-Traversal. Depth-First-Traversal(DFT or DFS): The idea is to recursively keep visiting the nodes in the left branch. When all nodes are visited in the left branch, visit the right branch recursively

Implement a Queue using two Stacks

2008-12-24T19:18:00.000-08:00

Problem: Implement a queue using 2 stacks Solution: The solution involves using one of the stacks as inbox stack. Incoming items are pushed onto this stack. The other stack is used as an outbox. When items need to be dequeued from the Queue and the outbox stack is empty, all the items from the inbox stack are popped and pushed on to the outbox stack. From there they can be popped until the

Tree: Breadth First Search

2008-12-24T18:37:00.000-08:00

Problem: Write code for doing a breadth first search in a Tree data structure. Solution: Breadth first search inspects items one level at a time starting with the root node. This is unlike the Depth First Search where the nodes in the left most branch are visited until there are no more nodes and then backtracks. The problem with implementing a breadth first search is that we have to remember

Implement a Queue using an Array

2008-12-24T18:16:00.000-08:00

Problem: Implement a queue using an Array. Make efficient use of the space in the array. Solution: Queue is a data structure that supports Enqueue and Dequeue methods. The Enqueue method adds an item to the end of the list and Dequeue method removes an item from the beginning of the list. This means that the Queue is a FIFO (First In First Out) data structure. Theoretically speaking a Queue

Interview Preparation Books

2008-12-18T16:47:00.000-08:00

1. Programming Interviews Exposed 2. Programming Pearls 3. C# 4. ASP.NET 5. T-SQL Recipes 6. Operating Systems 7. Networking TCP/IP 8. Compilers 9. More Programming Pearls 10. Algorithms 11. Head First Patterns 12. Object Oriented Analysis and Design 13. Writing Secure Code 14. Code Complete

Microsoft Technical Phone Screen Interview Questions

2008-12-16T21:59:00.000-08:00

General Questions - What do you work on and what is your preferred area? - What do you not like to work on? Patterns & Design - What patterns have you used? - Whats a pattern that implements event driven programming model? - When would you use inheritance vs encapsulation? Xml Questions - How do you validate an Xml document? Whats the difference between XSD and DTD? - When do you use an

String: Palindrome Check

2008-12-12T01:39:00.000-08:00

Problem: Find if a given string is a palindrome. Palindrome is a word or a phrase that reads the same in either direction. Ex: A man, a plan, a canal, panama! Punctuation and spaces can be ignored. Solution: The solution is pretty straight forward and involves comparing the characters at both ends, incrementally moving towards the center of the string. This is similar logic we used for reversing

String: Reverse Words

2008-12-11T23:24:00.000-08:00

Problem: Reverse the words in a sentence. For example "Hello World" should become "World Hello". Comment: This is one of most frequently asked interview questions on string manipulation. Solution: First we reverse the entire string and then reverse each word of this reversed string. "Hello World" | reverse | v "dlroW olleH" | | reverse reverse | | v v "

String: Reverse in place

2008-12-11T07:33:00.000-08:00

Problem: Given a string of unknown length reverse it in place. Solution: Lets take a sample string "hello". When reversed it should read as "olleh". For those who are new to C/C++, a string has null terminator at the end. This null terminator denotes the end of the string. So, when you say declare a string in C language like: char *str = "hello"; How many bytes of memory does it take to store

Linked List Loop/Cycle Detection

2008-12-10T01:16:00.000-08:00

Problem: Given the head pointer to a singly linked list with a loop or cycle in it. If you were to walk this list you never arrive at the end or the tail of the linked list. Find whether the list contains a loop in O(n) time and space complexity. Observation: A linked list with a loop will have a node that is being pointed from 2 different node. Solution 1: This problem was solved in the late

Links

2008-12-09T02:42:00.000-08:00

http://www.tekpool.com/ http://maxnoy.com/interviews.html http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm http://www.geekinterview.com/Interview-Questions/Programming http://halcyon.usc.edu/~kiran/msqs.html http://www.softwareinterview.com/ http://savenseek.com/page/Microsoft_Google_Algorithm_Interview_Questions__brainDead http://savenseek.com/page/

Linked List: Merged List Problem

2008-12-09T01:51:00.000-08:00

Problem: There are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join. Solution 1: Find length of both linked lists, say len1 and len2.Make current pointers for both lists equidistant from the common node. If one of the lists is longer we need to advance its current pointer

Linked List: Reverse

2008-12-09T00:21:00.000-08:00

Question: Given the head pointer to a singly linked list reverse the list. Solution 1: Recursive Approach - We can recursively traverse the linked list till we arrive at the last but one node. We then set the next pointer of the last node to point to the current node. We keep reversing the links as we unwind the recursive calls. Code:// Takes a pointer to the head node of a singly linked list

Linked List: Delete Node

2008-12-08T02:31:00.000-08:00

Question: You are given a pointer to a node in a singly linked list. The head pointer is not available. Your task is to delete the specified node. Solution: Typically, deleting a node from a singly linked list requires us to have the pointer to the node before the node to be deleted. We need this previous pointer so we can set it's Next pointer to the node after the specified node to be deleted.

Linked List: Find the middle element

2008-12-08T01:09:00.000-08:00

Question: Given a singly linked list, find the node in the middle. Solution 1: Walk the linked list to find the length of the list. Lets say n is the length of the list. Walk the list again upto ⌊ n/2 ⌋. Solution 2: Use two pointers. Move one pointer at twice the speed of the second. When the 1st pointer reaches the end of the list, the 2nd pointer will be pointing to the middle node. Note: If

Linked List: Find n-th element from the tail

2008-12-08T01:01:00.000-08:00

Question: Given a singly linked list find the n-th node from the back. Solution 1: Reverse the linked list and select the n-th node from the head of the linked list. Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node. Notes: Both solutions take O(n) time but Solution 2 is more elegant. Code: //define