Microsoft Interview Question: Consider a stack of N number ... | Glassdoor.co.in

Interview Question

Software Development Engineer In Test (SDET) Interview Hyderabad

Consider a stack of N number of cards which are piled up

  and in facing down. Each card has a unique number from the range 1 to N. The card is stacked in such a way that it exhibits the following behavior: Take the first card and put it under the stack without revealing. Now the next card on the top will have the number 1 on it. Next take 2 cards one after the other and put is under the stack without revealing. Yes you guessed it right - the next card on the top will reveal a value of 2. This goes on. Eg. for such a series : 9,1,8,5,2,4,7,6,3,10 [for N=10] Write a program to generate such a series for a given N number of cards so that this behavior can be exercised.
Tags:
algorithms
Answer

Interview Answer

8 Answers

1

Possible implementation in C++
--------------------------------------------------

int CounterStep(int counter,int N);
int LocatePosition(int *cards,int N, int startPointer,int value);

using namespace std;
void main()
{
    int cards[20];
    int N=20;
    int POS = 0,TOP = 0;

    // Initializing everything to zero
    for(int i=0;i

Interview Candidate on 26-May-2013
0

Written in Python although it can be re-written in C/C++ if required.

def generateSpecialSeries(numberOfCards):

    specialSeries = []

    if numberOfCards > 0:

        for i in range(numberOfCards, 0, -1):
            specialSeries.append(i)

        currentSpecialElement = 1
        currentIndex = 1

        while currentIndex < numberOfCards:

            indexOfCurrentSpecialElement = numberOfCards - currentSpecialElement
            specialSeries[currentIndex], specialSeries[indexOfCurrentSpecialElement] = specialSeries[indexOfCurrentSpecialElement], specialSeries[currentIndex]

            currentSpecialElement += 1
            currentIndex += currentSpecialElement + 1

    return specialSeries

specialSeries = generateSpecialSeries(50)

print specialSeries

specialElement = 1
specialElementSum = 1
currentIndex = 1

while currentIndex < 50:
    print specialSeries[currentIndex] == specialElement

    specialElement += 1
    specialElementSum += specialElement
    currentIndex += specialElement + 1

borg drone on 17-Jun-2013
1

// Short and simple C++ algorithm

#define N 10

void compute(int stack[]) // Make sure N elements are allocated
{
    int j=0;
    for(int i=0; i

Bob on 18-Jun-2013
0

#include
using namespace std;
int main(int argc,char **argv){
    int count=20;
    int array[20];
    for(int i=0;i>a;
    return 0;
}

Anonymous on 27-Jul-2013
0

Java implementation

public class App {
    public static void main(String[] args) {
        String arr[] = new String[10];
        int pointer = 0;
        for (int valueToPlace = 1; valueToPlace <= arr.length; valueToPlace++) {
            for (int x = 1; x <= valueToPlace; x++) {
                if (pointer == arr.length - 1)
                    pointer = 0;
                else
                    pointer++;
                if (arr[pointer] != null)
                    x--;
            }
            System.out.println("Placing " + valueToPlace + " at index " + pointer);
            arr[pointer] = valueToPlace + "";
            while (arr[pointer] != null && valueToPlace != arr.length) {
                if (pointer == arr.length - 1)
                    pointer = 0;
                else
                    pointer++;
            }
        }

        for (String str : arr) {
            System.out.print(str + ", ");
        }
    }
}

Sabaat on 05-Sep-2014
0

The algorithm used is:
For each number n (ranging from 1 to 10), we have to skip n places in the array. And then put number n at that position. The catch in the program is that we can skip only, not occupied places (the array places where value is 0 by default). Also, when we reach the end of the array, we have to move back to beginning of array (similar to cards being kept at the bottom of the pile of cards.)

Here, a variable 'pos' is used to store the final position of any element. Initially, pos is at 0.
The skip() takes the array, the current value of pos and the number of skips to be made.
For example, for n=1, the values passed to skip() would be: pos=0, n=1. This means that we have to skip 1 place starting from index 0.
Similarly, for n=2, pos=1. This means we have to skip 2 places starting from index 1.

Java Implementation:

public class StackOfCards {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
      int[] arr = new int[10];

      int pos=0;

      for(int n=1;n0){
            if(arr[pos]==0){
                         //reduce the number of skips to be made
                n--;
            }
            pos++;
                        //if end of array is reached, take pos back to beginning
            if(pos==10){
                pos=0;
            }
        }
                 // keep incrementing pos until a not occupied index is reached.
        while(arr[pos]!=0){
            pos++;
        }
        return pos;

    }

}

Shanky on 13-Jan-2015
0

Here is C# Code...

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 36;
            int[] series = new int[n];
            int LargestNumber = n;
            int SmallestNumber = 1, temp = 1, i;
            bool putLargeNumber = true;
            for (i= 0; i 0))
                {
                    series[i] = LargestNumber;
                    Console.Write("{0} ", series[i]);
                    LargestNumber = LargestNumber - 1;
                    putLargeNumber = false;
                    temp--;
                }
                else
                {
                    series[i] = SmallestNumber;
                    Console.Write("{0} ", series[i]);
                    SmallestNumber += 1;
                    putLargeNumber = true;
                    temp = SmallestNumber;
                }
            }
        }
    }
}

Shital Savekar on 02-Jun-2016
0

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

public class MSQuestion1 {
    static int counter =1;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner in = new Scanner(System.in);
       int n =in.nextInt();

// x 1 x1 x2 2 x3 x4 x5 3 x6
       int[] arr = new int[n];
       int f = 0;
       while(f0))
         {
             arr[f]=counter;
             counter++;
         }
         f++;
       }

       for(int i=0;i

Here is the Java Code . -Siva on 26-Jun-2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.