Microsoft Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

Use BitArray, because of the limited memory requirement

BitArray store = new BitArray(10000000, false);
            int num = GetNum();
            while (num != -1)
            {
                if (!store.Get(num - 1))
                    store.Set(num - 1, true);

                num = GetNum();
            }


            for (int i = 0; i < store.Length; i++)
            {
                if (store.Get(i))
                    Console.WriteLine(i + 1);
            }

- vh.vahan January 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Assumption: "if a repetition, shoud not store it" means only store the number once, if repetition should flag the number as not being printed, below discussion requires double the memory.

1. Option, big-O-optimized version:
- Store the numbers in a bit-vector, that is aprox 1.3 MB of Memory for range 1-10 Mio
since 1 - 10 Mio is given this is O(1) ...
- Printing, iterate over 1..10Mio and print the number if flagged, this is O(1), too

If this fits into memory, is it better than storing a btree or something on disc? It most certainly is, because we insert n times, and printing requires about 160'000 iterations over a 64 bit integer and only needs to drill into the integer if it is not 0. This is all in data and execution cache.

If only a few numbers, like 10000 or so occure before -1, it is slower. Depending on the memory size, we could optimize the small amount of numbers with some sort of tree and throw the tree away as soon as we exceed a certain amount of numbers.

Going to disc is an alternative, there it makes sense to create a number of files with fixed size (according to the available memory), each sorted and merge sort them when printing on the fly. This solution now is O(n) because we create constant size files and sort them which is O(1) due to the constant but we require to traverse each number when printing (whether it was a dublicate or not).

Conclusion:
if n is expected to be > 100'000 (or even >> 10 Mio) and almost uniform: use bitfield if oyu can afford that memory.
if n is >> 10 Mio: use bitfield on disc
if n << 10 Mio: use the merge sort approach on disc (maybe one get's lucky often and the -1 comes before the first file was written...)

- Chris November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Create a array of long so that its size can be 10,000,000. Now for each getNum() value, treat the number as index and put 1 there. check the condition for -1 and exit when getNum() returns it. While writing, just read all values starting from index 0 till last index where value is 1 and print index as expected value. this will have o(n) printing, o(1) inserting and only need o(n) size.

- Rahul December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simplest is storing into a file, and then use standard sorting techniques to sort them later.
Given the digits are fixed, we can create a directory tree with LSB at the top, and MSB in the leaf, while the leaf storing the number of repetitions.
So, 1023456 would be stored as :

/6/5/4/3/2/0/1/[count=1]

while 1024 would be stored as :

/4/2/0/1[count=1]

Now, what happens when we do postorder traversal on the tree with children in sorted order? All one needs to do is to store the path from root, and reverse it, and then we have our answer. For multiple occurrence, simply repeat the same count no of times, and we are good.

The max depth of that tree would be 8 ish in base 10.

- NoOne November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use binary sort while fetching and inserting the number in a array. the final print would just print the array from first to last element. Complexity would be O(log n) for searching and inserting. and O(n) for printing the final array.

- Nitin November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use binary search and insertion for each element generated. The O(log n) will enable you for minimum memory utilization assuming only half array will be in memory for each computation. We can publish the array to the disk. Keeping the array in sorted order can help in generating a stream for the same and printing while fetching from any disk storage.

- Nitin November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A trie is perfectly suited for this. A trie by definition does not contain duplicates.

10 Million is 10,000,000. The max depth is 8.

Once the trie is built, the numbers can be constructed in sorted order by doing a level by level left to right traversal appending the value at each node to the parent.

- Learner November 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

long[] la = new long[];
    for(long index=0;index<=10000000; index++)
      la[index]=0
    
    while(true)
    {
      int num = getNum();
      if (num == -1)
        break;
      if (la[num] != 1)
        la[num] = 1;
    }
    
    for (long index=1; index < 10000000; index++)
      {
        if (la[index] == 1)
          System.write(index.toString());
      }

- Rahul December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C# using SortedSet in System.Collections.Generic the solution is as follows

SortedSet<int> hs = new SortedSet<int>();
			int i;
			while (true)
			{
				i = getNum(-1, 1000000);
				if (i == -1)
					break;
				hs.Add(i);
			}
			foreach (int j in hs)
			{
				Console.WriteLine(j);
			}

- Keerthana P January 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

when we know the number range from 1 to 1M in radom fashion with repetions (those repetions we can ignore so we can just say numbers between 1 to 1M it only prints -1 when out of numbers means all numbers will be printed at least once). SO just print the numers in or loop from 1 to M, the moment we receive a -1.

- poonam February 10, 2017 | 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