## Microsoft Interview Question for Software Engineer / Developers

Country: United States

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

use bit vector to store each integer in single bit. 625 integers are required to store 20000 numbers

int arr[625] = {0};

ex: to store data 2000
arr index = 2000/32 = 62
bit position = 2000%32 = 16

now make bit position 16 of array index 62 arr[62] to 1

using this bit vectors we can store data range from 1 - 20000 in 625 integers..

after storing all data in bit vectors, check all bit positions of arr[0], arr[1]..... arr[625]... if any bit position is set to 1 then store back that data into array

lets arr[10] bit position 15 is set to 1 then this is equivalent to data 10*32+15 = 335

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

Simple and awesome :) +1

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

nice solution +1 from me

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

@algos
Can you please also provide the code on how you will sort the numbers

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

``````Below code is to store back the data in sorted order into array

int data[20000] = {97,6,64,37};	// initially given unique data
int arr[625] = {64,32,1,2}; // bit vector array
int index = 0;	// index to store back all data

for(int i=0; i<=625; i++)
for(int j=0; j<32; j++)
if(arr[i] & (1 << j))
data[index++] = i*32 + j;``````

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

awesome man..+1

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

@algos
can you explain for your example how the bit array is filled.
Like for 97/32=3 that is arr[3] and bit position 97%3 is 1 but for 64/32=0 that is arr[0] the bit position is also 0 but how 2 and 32 are coming. Can you please again explain how the values in the bit array are filled. It will be of great help.

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

``````97/32 = 3 and 97%32=1, for arr[3] bit 1 will be set... arr[3] = 2
6/32 = 0 and 6%32=6, for arr[0] bit 6 will be set..... arr[0] = 64
64/32 = 2 and 64%32=0, for arr[2] bit 0 will be set... arr[2] = 1
37/32 = 1 and 37%32=5, for arr[1] bit 5 will be set... arr[1] = 32
36/32 = 1 and 37%32=4, for arr[1] bit 4 will be set... arr[1] = 16 | 32=48 (32 is bit 5 which is already set)``````

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

how to deal with the array with duplicate numbers? Say number x is duplicated y times, use the bit operation, we lost the information y. How to avoid this?

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

Sorry for the last comments. It said unique numbers.

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

@algos
thanks..:)

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

Can we create an array of length 20000 when the question says that we can not load more than 1000 numbers into memory?

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

perfect ... :)

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

nice

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

``````#include <stdio.h>

int main()
{
int arr[] = {97,75,209,435,430,531,990};
int vec[625] = {0};

int i;
int j;
int n = 1;
int index = 0, bit_pos = 0;
for (i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
{
index = arr[i] / 32;
bit_pos = arr[i] % 32;

n = n << bit_pos ;
vec[index] = vec[index] | n;
n = 1;
}
index = 0;
for (i = 0; i < sizeof(vec)/sizeof(vec[0]); i++)
{
for (j = 0; j < 32; j++)
{
if ( vec[i] & ( 1 << j ))
{
arr[index++] = i*32 + j;
}
}
}

for (i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
printf ("%d\n", arr[i]);
return 0;
}``````

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

If you can use C++ bitset, just use it

``````#include <bitset>
using namespace std;

void SpecialSort(int a[], int n = 16000)
{
bitset<20000> bs;
const int isize = sizeof(int) * 8; // 32;

// Iterate all elements in the array
for (int i = 0; i < n; ++i)
{
bs[a[i]] = 1;
}

// Iterate [1, 20000]
for (int i = 1, k = 0; i < 20000; ++i)
{
if (bs[i])
a[k++] = i;
}
}``````

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

This soln. is so easy to understand and working.

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

Here is C# version

``````using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
class Program
{
static void Main(string[] args)
{
Program exe = new Program();
exe.SortWithLimit();
}

private void SortWithLimit()
{
const int intSize = 32;
const int intLimit = 20000;

int[] arr = GetRandomArray(25, 1000);

if (arr.Length > intLimit)
{
return;
}

Console.WriteLine("Unsorted {0}", string.Join(",", arr));

uint[] vec = new uint[intLimit / intSize];

int i;
int j;
int index = 0;

for (i = 0; i < arr.Length; i++)
{
index = arr[i] / intSize;

vec[index] = vec[index] | (uint) 1 << arr[i] % intSize;
}

index = 0;

for (i = 0; i < vec.Length; i++)
{
for (j = 0; j < intSize; j++)
{
if ((vec[i] & (1 << j)) > 0)
{
arr[index++] = i * intSize + j;
}
}
}

Console.WriteLine("Sorted   {0}\n", string.Join(",", arr));
}

private int[] GetRandomArray(int intCount, int intMax)
{
Random r = new Random();
List<int> result = new List<int>();

while (result.Count < intCount)
{
int number = r.Next(intMax);

if (!result.Contains(number))
{
}
}

return result.ToArray();
}
}
}``````

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

We can use external quicksort. In an external quicksort, instead of heaving a single pivot element used for partitioning the array, we have a group of elements called 'middle group' or 'pivot group'. In a generalized algorithm, we use a Doubly Ended Priority Queue, (DEPQ).

``````1.	Read in "maximum possible" elements and insert them into a DEPQ. The elements in the DEPQ will eventually be the middle group of elements.
2.	Read in the remaining elements.
•	If the next element is ≤ the smallest element in the DEPQ,
output this next element as part of the left group.
•	If the next element is ≥ the largest element in the DEPQ,
output this next element as part of the right group.
•	Otherwise, remove either the max or min element from the
DEPQ (the choice may be made randomly or alternately);
if the max element is removed, output it as part of the right
group; otherwise, output the removed element as part of the
left group; insert the newly input element into the DEPQ.
3.	Output the elements in the DEPQ, in sorted order, as the middle group.
4.	Sort the left and right groups recursively.``````

However, the question mentions that the range of integers is pretty much same as the number of elements and also the integers are unique.

``Thus we can use 'counting sort' instead of a 'Doubly Ended Priority Queue' to sort the middle group elements.``

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

``````vector<int> sortUnique(vector<int>&num)
{
int  n = num.size();
bitset<20000> bs;
for (int i=0; i < n; i++) bs[num[i]] = 1;
for (int i=0, k =0; i < 20000; i++)
if (bs[i] == 1) num[k++] = i;
return num;
}``````

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.

### 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.