Microsoft Interview Questions
- 5of 5 votes
AnswersA link list contains following elements
struct node{ int data; node* next; node* random; }
Given head of such a linked list write a function who copies such a linked list and returns the head of the new list. So if in the original list first node points to fourth node in random the copy should have the same relation. The random pointer can point to any node including itself and more than two nodes can have random pointer to the same node.
- vik September 13, 2013 in United States
Required time complexity O(n) and no extra space can be used (apart from the newly allocated memory which you will need to create the new list)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures - -2of 4 votes
AnswersWrite a thread safe data structure such that there could be only one writer at a time but there could be n readers reading the data. You can consider that incrementing or decrementing a variable is an atomic operation. If more than one threads try to write simultaneously then just select one randomly and let others wait
- vik September 13, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures Operating System - 4of 4 votes
Answersinput - 2D array of characters and a text pattern. program to find if pattern is present in array or not. a cell can't be used twice for pattern matching. return 1 if true or 0 otherwise.
- pop_front September 11, 2013 in United States
eg :
Matrix
{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i', 't'}
and search for "microsoft"| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 0of 0 votes
AnswersGiven below is a tree/trie
- anilkumar.bhaskara September 10, 2013 in United States
A
B c D
e F
a<b<e<>>c<>d<f<>>>
above string represents the following trie/tree (visualize) and assume that there exisits a serialize method that performs above.
Now, write a deserialize method so that above string to an object model of the following
TreeNode
TreeNode[] children| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1.
- pretonesio September 02, 2013 in United States for Powerpoint
For instance, the matrix:
00100001
00010010
00001100
00001100
00010010
00100001
Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix
101
010
101
Will return a value of 3, as the diagonal is 3. Write such program,| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 5of 7 votes
AnswersWhat is the minimum representation in bits of two positions on an 8x8 chessboard?
- pretonesio August 28, 2013 in United States for Outlook| Report Duplicate | Flag | PURGE
Microsoft SDE1 Brain Teasers - 2of 2 votes
AnswersFind the majority element which occurs more than n/2 times in an array of n size, which contains duplicate elements in minimum time and space complexity.
- saran August 07, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Arrays - 2of 4 votes
AnswersC program to Delete a node from SLL, in which the last node points to the middle node( in case of even no of nodes, it points to the first middle node) and update the SLL.
- saran August 06, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Program Manager Intern Linked Lists - 0of 2 votes
AnswersConvert a base 2 number to a base 4 number
- vgeek August 02, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - -1of 1 vote
AnswersI have heard this question many times in microsoft interviews. Given two arrays find the intersection of those two arrays. Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
- vgeek August 02, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - -3of 3 votes
Answersplease read full question before ans,
- vivek August 01, 2013 in United States
time complexity to merge k sorted arrays of size n each where space is not constraint and merge them with in m swap( m is total no of element i.e m=k*n )
Example:
Input:
k = 5, n = 4
arr[][] = { {3, 33, 55, 71},
{29, 63, 64, 88},
{100,999, 1100, 1800}
{18,99, 155, 180}
{360,480, 590, 620}} ;
Output: 3 18 29 33 55 63 64 71 88 99 100 155 180 360 480 590 620 999 1100 1800
==> ( " sort this array with in 15 swap or insertion ")| Report Duplicate | Flag | PURGE
Microsoft Computer Scientist Algorithm - 0of 0 votes
AnswersGiven array of words, group the anagrams
- abhinav27rulez July 29, 2013 in United States
IP:{tar,rat,banana,atr}
OP:{[tar,rat,atr],[banana]}| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 0of 0 votes
AnswersDesign a parking meter.
- coder July 29, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Intern Application / UI Design - 0of 0 votes
AnswersProblem of concurrent transactions done by two persons of a joint account at two different ATM Machines. How is it managed without introducing any inconsistency in balance of the account holders?
- coder July 29, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Intern - 0of 0 votes
AnswersTwo airline companies, Kingfisher and Jet airways want to do a merger. Design a database migration scheme, so that no inconsistencies and redundancy occur. Assume suitable data and brief on the problems you might face.
- coder July 29, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Intern - 0of 0 votes
AnswersGiven notes of different denominations ( 1,2,5,10) , WAP to find in how many ways can you make an amount ‘x’ ?
- coder July 27, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Intern Algorithm - 15of 15 votes
AnswersGiven an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.
- vgeek July 27, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersMaximum value Continuous Subsequence:
- pirate July 25, 2013 in United States
Given array A[n] find continuous subsequence a[i]..a[j] for which sum of elements in the subsequence is maximum.
Ex: {-2, 11, -4, 13, -5, -2} --> 11 - 4 +13 = 20
{1, -3, 4, -2, -1, 6} --> 4 -2 -1 +6 = 7
Time complexity should O(nlogn)| Report Duplicate | Flag | PURGE
Yahoo Microsoft Linkedin Software Engineer / Developer Algorithm Arrays - 1of 1 vote
AnswersTwo 32-bit integers n and m are given and positions i,j,k,l are given.Write a method to copy the contents of m from position k to l into n from position i to j.
- vgeek July 17, 2013 in United States
(example n=1010000000,m=10101010,i=3,j=5,k=5,l=7..output=10'101'00000)| Report Duplicate | Flag | PURGE
Microsoft - 2of 2 votes
AnswersGiven a N * M matrix, you have to rotate it by 90 degree.
- SK July 07, 2013 in India for Bing
I gave him solution with transpose matrix & then reverse each row.
He was satisfied but after asked that this required each element to be touched twice. Can you do it like all elements will be touched once only.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersThe object of this exercise is to fix 3 known issue with the existing code, and add a new feature to the tool.
- Purushotham Kumar July 05, 2013 in Ireland for CPL Recruitment Team @Microsoft
The known issues to address are:
· The current implementation of the tool incorrectly ignores white space (spaces and tabs) between words, which is a bug. Modify the code so that white space differences are correctly detected
· Tool doesn't report difference if second file is larger than first file
· For large input files the tool consumes considerable RAM. Modify tool to address this performance bug
The new feature to implement is:
· Add a new command line switch -i and functionality to allow case-insensitive comparison
Running the tool requires you to supply 2 command line arguments – these will be the paths to 2 text files that should be compared. You are responsible for creating this test data.
/*
* New Requirement:
* - Add a new command line switch -i and functionality to allow case-insensitive comparison.
*
* Issues to fix:
* - The current implementation of the tool incorrectly ignores white space (spaces and tabs) between words, which is a bug.
* Modify the code so that all white space differences are correctly detected and reported along with differences in words.
* - Tool doesn't report difference if second file is larger than first file.
* - For large input files the tool consumes considerable RAM. Modify tool to address this performance bug.
*
* Please ensure you include all test files that you create for each of your test cases along with your submission.
*/
namespace CsDiff
{
using System;
using System.Collections.Generic;
using System.IO;
class Program
{
static void Main(string[] args)
{
if (!ProcessArgs(args))
{
return;
}
using (FileReader sourceFile = new FileReader(args[0]))
using (FileReader targetFile = new FileReader(args[1]))
{
IEnumerator<string> sourceEnum = sourceFile.Words.GetEnumerator();
IEnumerator<string> targetEnum = targetFile.Words.GetEnumerator();
for (int word = 1; sourceEnum.MoveNext() && targetEnum.MoveNext(); word++)
{
if (sourceEnum.Current != targetEnum.Current)
{
Console.WriteLine("Difference at position {0}: '{1}' different to '{2}'",word,sourceEnum.Current, targetEnum.Current);
}
}
}
}
static bool ProcessArgs(string[] args)
{
if (args.Length != 2)
{
Console.WriteLine("Please specify [source] and [target] file paths");
return false;
}
for (int arg = 0; arg <= 1; arg++)
{
if (String.IsNullOrEmpty(args[arg]) || !File.Exists(args[arg]))
{
Console.WriteLine("File '{0}' not found", args[arg]);
return false;
}
}
return true;
}
}
public class FileReader : IDisposable
{
string[] words;
public FileReader(string path)
{
string fileData = File.ReadAllText(path);
words = fileData.Split(new char[] { ' ', '\t' });
}
public IEnumerable<string> Words
{
get
{
return this.words;
}
}
public void Dispose()
{
}
}
}| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test - 1of 7 votes
Answersif we open a new tab in a browser,is it a new process or thread?and what if we open a new window of the browser?
- Amit July 01, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Operating System - 7of 9 votes
AnswersImagine an alphabet of words. Example:
- hani.amr June 30, 2013 in United States
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.
Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.
Input Output
ab 27
ba 0
aez 441
Note: Brute-force is not allowed.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersInput: Consider a file containing a list of 100,000 license plate numbers which follow the format ABC-123 and could be any value ranging from AAA-001 to ZZZ-999.
- racejakebannon June 30, 2013 in India
This data is expected to be read-in and stored in memory based on following requirements:
• The list can be reconstructed using the stored data. Original sequence does not need to be maintained.
• Perform searches efficiently on the stored data using the first 3 characters of the number as given below :
• List all licenses starting with ‘MMM’
• Count the total number license numbers starting with ABC| Report Duplicate | Flag | PURGE
Microsoft Software Architect Algorithm - 1of 1 vote
AnswersImplement T9 dictionary for mobile phone
- anim June 29, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Algorithm Application / UI Design Data Structures Object Oriented Design Problem Solving - 1of 1 vote
AnswersGiven an mxn matrix, design a function that will print out the contents of the matrix in spiral format.
Spiral format means for a 5x5 matrix given below:[ 1 2 3 4 5 ] [ 6 7 8 9 0 ] [ 1 2 3 4 5 ] [ 6 7 8 9 0 ] [ 1 2 3 4 5 ] path taken is: [ > > > > > ] [ > > > > v ] [ ^ ^ > v v ] [ ^ ^ < < v ] [ < < < < < ] where ">" is going right, "v" going down, "<" is going left, "^" is going up.
The output is:
- masrur.macece June 26, 2013 in United States for Windows Hyper-V1 2 3 4 5 0 5 0 5 4 3 2 1 6 1 6 7 8 9 4 9 8 7 2 3
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 0of 0 votes
AnswersOpen two instances of Microsoft Word and print to printer simultaneously. How would the underlying printer driver work? How would you design the printer driver?
- masrur.macece June 26, 2013 in United States for Windows Hyper-V| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Computer Architecture & Low Level - 0of 0 votes
AnswersDesign an algorithm to find all the nouns and verbs present in a book. Discuss and explain your decision as to why you chose that algorithm.
- Jeanclaude June 21, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test - 1of 1 vote
Answers"Write test cases for reversing words of string ". For eg. "This is nice" is input string and output is "nice is This".
- LAP June 19, 2013 in India
I gave him -
" "
"Hello"
"bye! Mr. X Y. Kumar"
But he didn't seem satisfied.
Can u plz tell what general guidelines should I follow for writing efficient test cases.
What more test cases should I have written for this question ?| Report Duplicate | Flag | PURGE
Microsoft Intern