## Microsoft Interview Question for Software Engineer / Developers

• 0
of 0 votes

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 6 vote

use a inverted hash table. This is similar to how search engine works. for every digit(0-9) associate each digit with a set of phone nos(which have that digit). once the query is fired, just take the intersection of the sets.

Comment hidden because of low score. Click to expand.
0
of 0 votes

So, according to this approach, there will be n array of 10[for digits-0 to 9]probably an array of linked list. Whenever a phone number needs to be inserted, we will take out each digit & associate its pointer[through which we can display the phone number] to the linked list. Good thinking, But what to do when the phone number contains duplicates.

Also, don't you think that we will be storing the same phone numbers multiple times?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Duplicates: The inverted index should have tf scores associated with each phone number. So for example, phone# 898765432 will have tf score of 2 for index 8.

Yes, the same phone number will be stored at most 10 times and this will make the inverted index very large. We can avert this by increasing the size of the dictionary from 10 to say 100. Now the indices will be from 00 to 99 instead of 0 to 9.

Comment hidden because of low score. Click to expand.
4
of 12 vote

I have thought one approach.More like as suggested by @eugene.
Let me know whether it is efficient.

Use TRIE data structure where phone numbers will be inserted in sorted order. In the leaf nodes, we will have pointers to the original phone number[the phone numbers will be in the form of strings right!].
In order to handle collisions[two different phone numbers after sorting may represent the same leaf node],
we can have linked list at the leaf nodes. Whenever a new phone number is being inserted & the leaf node is already having pointer to some other phone number, we will chain this phone number[create a new node in the linked list & insert its pointer there].
Now, During search operation, lets say 321, first sort the string to be searched[say 123 in this case].
After reaching 123, an inorder traversal would be sufficient.Whenever a leaf node is encountered, all the strings[phone numbers] can be accessed through single linked list.
Comments are welcome.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are right..we will have to first sort all the numbers and storing actual numbers in the leaf nodes.

Comment hidden because of low score. Click to expand.
0
of 0 votes

As far as I understand, trie is used for kind of pattern matching. If I understand your proposal correctly, it means that we can reach a list of numbers (stored in leaf node) following the digit pattern of phone number (sorted) from trie root.
Perfectly fine till now. But, what if the number is 1234567890 and we are supposed to find number which include 456. There is no path from root for digit '4'. In trie, you have to have a path from root for each key to reach to key's value (which is our case is a list of phone numbers containing key digits).

In case I have misunderstood, please help to clarify.

Comment hidden because of low score. Click to expand.
0
of 0 votes

easy, we will keep on searching until we do not find 456.

Comment hidden because of low score. Click to expand.
0
of 0 votes

We will ignore all other digits and will keep searching till we find required digits or we reach the leaf node.
If we find all the digits till we reach the leaf or before, we will give all the numbers stored in that leaf node.
Since all numbers are sorted , we will have to search in all branches which have number less than the first digit of pattern..(pattern is also sorted.)

Comment hidden because of low score. Click to expand.
0
of 0 votes

As we have 10 numbers in phone number. What's the point of making trie for it . All phone number will appear in leaf node of single link of trie i.e. 0->1->2->3....->9 -> all nodes of numbers. so we can display all numbers.

Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it is a right way.Also we can have each node in the trie such that they contain the position last matched number from the sequence and the subsequent nodes can either contain the position in the parent node or a next position depending on whether at that node we dont find the matching number of the required sequence or we do find matching number

Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik
Can you please elaborate your answer.
Because you have told different phone numbers will have same leaf.. how is it possible? we can have linked list at the leaf nodes. Whenever a new phone number is being inserted & the leaf node is already having pointer to some other phone number, we will chain this phone number[create a new node in the linked list & insert its pointer there].? i am not clear with this..

suppose phone number is 9840404040 then 44 , 04, 84 etc all shud give this number..

it would be great if u can explain it with an example.

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is bullshit. If you traverse all branches when you search for "456", why do you need this extra data structure? We can easily compare "456" with each phone number in O(1) time.

Comment hidden because of low score. Click to expand.
2
of 2 vote

For every phone number create 10 bit value. Set in "1" those bits whose digit presents in the phone number.
For example number 9456 will have value 1001110000

For searching match numbers check following condition:
(A & B) == B

A - value for number from phone book
B - value for typed number

Comment hidden because of low score. Click to expand.
0
of 0 votes

well done

Comment hidden because of low score. Click to expand.
0
of 0 votes

What about duplicates digits? Phone numbers can also contain duplicates,right.
Also , user may want to type number like 2324

Comment hidden because of low score. Click to expand.
0
of 0 votes

to shondik:
Good question :-)
It is not clear in desctiption about duplicates.

But anyway I don't like this my solution. The second my solutions in this thread is better. It work fast and work good. But somebody vote "-1" without any explanation.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this could work if there is a restriction on size of input............
For Ex, if the input is assumed to be only 4 digit long.....Then your method can be modified by now using 2 bit instead of 1 bit for each digit....

2207

(00)(00)(01)(00)(00)(00)(00)(10)(00)(01)

Comment hidden because of low score. Click to expand.
0
of 0 votes

Not a good solution. Since each new digit in the input causes whole phone number list traversing.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Were you asked to implement the datastructure or just name it?

Comment hidden because of low score. Click to expand.
0
of 0 votes

just data structure

Comment hidden because of low score. Click to expand.
0
of 2 vote

Trie is the datastructure to be used.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I suppose a Ternary Search Tree would give a fitting solution, but I am not confident about its implementation.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene, if the phone numbers be sorted then how the TRIE is going to be handy.
Say numbers are 9657 & 9756.
After sorting both reduce to same number. How you are going to store them in TRIE.

Comment hidden because of low score. Click to expand.
1
of 1 vote

There is no need to sort the mobile number strings. We make an array of TrieNodes of size 10. The indices of this array would represent numbers from 0-9. Now each of these 9 slots in the array would have another array of TrieNodes of size 10 and so on.
So if 6 is entered then everything under the first array[5] would be displayed.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene You mean to say that the mobile numbers are stored somewhere else as strings and the those mobile numbers are stored in the trie in sorted way.
And since every mobile number is 10 digits we can have the pointer to the string (actual mobile no.) in the last node itself.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene I think u are correct since order is not important.......But I don't understand why u are storing the pointers to the actual strings......Instead u can just store a count in each node of tries

Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh....I got it.....thnx

Comment hidden because of low score. Click to expand.
0
of 0 vote

What do you mean by "any order " here ??
Do 69234567... also appear in the search result ??

Comment hidden because of low score. Click to expand.
0
of 0 votes

No, the substring 926 has to be present, in the input.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Its already present in this example. x92xxx6x.

Comment hidden because of low score. Click to expand.
0
of 0 votes

It mean the string *9*2*6* and a good pattern search algorithm for the same.

Comment hidden because of low score. Click to expand.
0
of 0 vote

string f = "926";

HashSet<string> data = new HashSet<string>();
data.Add("2916");
data.Add("932678");
data.Add("92678");
data.Add("222222");
data.Add("722629");
data.Add("9777726");
data.Add("926926");

bool isToDisplay;
int lastInx;
foreach (var d in data)
{
lastInx = 0;
isToDisplay = true;
foreach (var i in f.Select((v, i) => new { Value = v, Index = i }))
{
if (!d.Contains(i.Value) || (lastInx > d.IndexOf(i.Value))) { isToDisplay = false; break; }
lastInx = d.IndexOf(i.Value);
}
if (isToDisplay) Debug.WriteLine(d);
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

String NumbersList = "9934176,993424,9923206,9933736,9837236,9344636,9639236";
String SearchList = "926";
foreach (string match in NumbersList.Split(','))
{
bool matched = false;
foreach (char hasnum in SearchList.ToCharArray())
{
if (match.Contains(hasnum))
{
matched = true;
}
else
{
matched = false;
}
if (matched == false)
{
break;
}
}
if (matched == false)
{
continue;
}
Console.WriteLine("matched with " + match);
}
Console.Read();

Comment hidden because of low score. Click to expand.
0
of 0 votes

when you insert 629, 296, 269 is also matched although shouldn't it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. A 10 bit array indicating whether digit is there in number or not
2. A 100 bit array indicating two consecutive digits. For convenience this can be shrunk to 50 bits by binning arbitrarily
So now we have 60 bits to represent the phone number, great it fits in a long int.

For input number we find what the first array of 10 bits should be, and what the second array should be, let's call this bit pattern B. AND with the input and check if identical to B, this is a candidate - now we can verify if the input number is there or not. For 1 digit no need to verify. For 2 digits take account of binning if using 50 bits. For more digits need to check each match which shouldn't be so difficult because potential number of matches will be small.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved using prime numbers

Let's say A is an array which contains first 10 prime numbers
A = { 2,3,5,7,11,13,17,19,23,29}

unsigned long int multnum =1, multsearchnum =1 ;
foreach digit of number
{
multnum *= A[digit];
}

foreach digit of (searchNumber)
{
multsearchnum *= A[digit];
}

if { multnum % multsearchnum == 0} {
print ( "all digits of search string are present in the number");
}

I didn't find any failing case till now. Please let me know if you find any failing case.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

From the examples given, there is a pattern I could find that the number starts from 9 and then 26 together can come anywhere. Is that the case?
I could think of TRIE with additional search in the subtrees for the remaining numbers.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Create 10 linked lists of pointers at phone numbers.
Phone number 9456 will be presented in "9" and "4" and "5" and "6" linked lists at the same time.
When user press number "9" we print all items from "9" linked list.
Then user press number 6 we print all items from "9" and "6" linked lists.

For protect from printing the same number many times we can make variable "checked" for every phone number and don't print checked numbers. It work if linked list have only pointers at phone numbers.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More