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

- algos July 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple and awesome :) +1

- EOF July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution +1 from me

- vgeek July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- algos July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome man..+1

- Sibendu Dey July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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)

- algos July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry for the last comments. It said unique numbers.

- Anonymous July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@algos
thanks..:)

- vgeek July 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- temp1234 September 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

perfect ... :)

- Ajeet November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice

- bp February 12, 2014 | Flag
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;
}

- rohith August 02, 2013 | Flag Reply
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;
    }
}

- Peter August 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This soln. is so easy to understand and working.

- rachit August 08, 2013 | Flag
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))
                {
                    result.Add(number);
                }
            }

            return result.ToArray();
        }
    }
}

- malacky.lugora August 29, 2013 | Flag Reply
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.

- EOF July 27, 2013 | Flag Reply
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;
}

- Anonymous September 27, 2013 | Flag Reply


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