tag:blogger.com,1999:blog-26827817343681787432017-03-30T06:35:23.118-07:00Technical Interview Questions, Answers, and TipsFrequently asked programming interview questions (with answers) and puzzles asked by google, microsoft, amazon, yahoo, and facebook for SDE/Developer and SDET positions.avid gardenernoreply@blogger.comBlogger53125tag:blogger.com,1999:blog-2682781734368178743.post-52829643986777901132012-04-24T19:32:00.001-07:002012-04-24T19:37:41.810-07:00How to detect repeated elements in an integer array?
This is an open ended question so please ask questions about the nature of the data in the array (size of the data, is it sorted or almost sorted, range of the data). Also, ask about any constraints like runtime or memory usage. You selection of the technique will depend on the answers to those questions. I have listed a few techniques below that touch on some of those points. There are more avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-22948932408701468282010-08-01T23:52:00.000-07:002010-08-01T23:57:53.113-07:00Reverse MinesweeperQuestion: 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 avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-37150561478459866242009-11-23T10:26:00.000-08:002012-02-23T23:00:09.844-08:00How and why to prevent class inheritance in C#/.NET
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 avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-39164176254122128502009-11-16T04:01:00.000-08:002012-03-01T14:29:21.173-08:00Difference Between calloc, malloc, and reallocQuestion: 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 avid gardenernoreply@blogger.com15tag:blogger.com,1999:blog-2682781734368178743.post-60092149931097524292009-11-03T20:02:00.000-08:002009-11-03T20:02:29.544-08:00Must Read Books for Technical/Programming Interview PreparationCoding, 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 avid gardenernoreply@blogger.com1tag:blogger.com,1999:blog-2682781734368178743.post-5589341940293456022009-04-02T15:48:00.001-07:002009-04-03T19:35:59.519-07:00Implement Two stacks using one arrayProblem: 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 avid gardenernoreply@blogger.com10tag:blogger.com,1999:blog-2682781734368178743.post-75946215642606699392009-03-22T23:28:00.001-07:002009-03-23T00:10:38.789-07:00Determine and display all anagrams in a string arrayQuestion: 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 avid gardenernoreply@blogger.com5tag:blogger.com,1999:blog-2682781734368178743.post-69784940981568414352009-03-03T18:15:00.000-08:002009-04-16T18:32:00.420-07:00Print 2D Array Matrix Spiral OrderQuestion: 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 avid gardenernoreply@blogger.com16tag:blogger.com,1999:blog-2682781734368178743.post-60849177740874300492009-03-01T17:02:00.000-08:002009-03-01T17:50:40.281-08:00DNA Sequence Pattern Match/ String Search ProblemQuestion: 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 onavid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-42451340156312814452009-02-20T14:33:00.000-08:002009-02-20T15:38:43.151-08:00Database Isolation Levels in Sql Server and ADO.NETIsolation 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 <level name>
<level name> can be one of avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-28829772210192602392009-02-19T11:40:00.000-08:002009-02-20T15:55:40.760-08:00Database Normalization BasicsFirst 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 avid gardenernoreply@blogger.com2tag:blogger.com,1999:blog-2682781734368178743.post-39085392046632268692009-02-18T14:29:00.000-08:002010-07-27T23:42:01.715-07:00SQL Server Index Fragmentation and ResolutionWhat 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.avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-58594528226525352312009-02-10T14:39:00.000-08:002009-02-20T16:19:48.707-08:00Find an Item in a Sorted Array with Shifted ElementsProblem: 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 wouldavid gardenernoreply@blogger.com2tag:blogger.com,1999:blog-2682781734368178743.post-90112415342262629872009-02-01T21:39:00.001-08:002009-02-23T14:31:12.570-08:00Database SQL Interview QuestionsWrite 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 avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-84266599957572491022009-01-28T19:23:00.001-08:002009-02-20T16:20:26.738-08:00Array: Find the number with odd number of occurrencesProblem: 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 avid gardenernoreply@blogger.com8tag:blogger.com,1999:blog-2682781734368178743.post-53818210539752934492009-01-21T13:49:00.000-08:002009-02-20T16:22:46.089-08:00Fibonacci Sequence Dynamic ProgrammingProblem: 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) avid gardenernoreply@blogger.com3tag:blogger.com,1999:blog-2682781734368178743.post-81196013564254146222009-01-14T15:18:00.000-08:002009-02-20T16:17:57.861-08:00Store a stream of numbers along with the countsProblem: 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 avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-17935554830012387942009-01-13T14:21:00.000-08:002009-02-20T15:39:09.224-08:00Fly plane around the world half fuel puzzleThere 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 avid gardenernoreply@blogger.com1tag:blogger.com,1999:blog-2682781734368178743.post-78884803539537669612009-01-13T14:19:00.000-08:002009-04-29T20:03:32.993-07:00Microsoft Developer Interview Questions---------------------------- 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 avid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-2844634280175315362009-01-07T12:48:00.000-08:002009-10-26T18:53:21.761-07:00Merge 2 Sorted Arrays (one has empty slots)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 avid gardenernoreply@blogger.com7tag:blogger.com,1999:blog-2682781734368178743.post-61900832361287180442009-01-03T19:46:00.001-08:002009-01-03T20:07:56.008-08:00Largest Sum Sub-Sequence Integer ArrayProblem: 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;
avid gardenernoreply@blogger.com4tag:blogger.com,1999:blog-2682781734368178743.post-4453753876863743622008-12-30T23:50:00.001-08:002008-12-31T02:11:22.491-08:00Dynamic Programming Questions1. 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_problemavid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-84125142513404358802008-12-29T22:57:00.000-08:002008-12-29T23:08:46.900-08:00Object Oriented Programmings OOPS ConceptsExplain polymorphism with examples
What are the 4 basics of OOP?
Define Data Abstraction. What is its importance?avid gardenernoreply@blogger.com1tag:blogger.com,1999:blog-2682781734368178743.post-48914170869726934462008-12-29T19:43:00.000-08:002008-12-29T23:01:40.635-08:00Design QuestionsDesign 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 toavid gardenernoreply@blogger.com0tag:blogger.com,1999:blog-2682781734368178743.post-14923917115534640062008-12-29T19:17:00.000-08:002012-04-24T19:34:56.248-07:00Questions
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 avid gardenernoreply@blogger.com0