Morgan Stanley Interview Question for Sales Development Representatives


Country: India




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

1)use a queue and enqueue 1 in it and intialize a counter as 0.
2)do this step while q is not empty and counter<n
2.a)dequeue the front element and print it.
2.b)append 0 and 1 to the popped element and enqueue it back to the queue.
finally all the element will be printed in binary in o(1)...

- vishal July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Clever answer! See the problem correctly.

- AnthonyNLee August 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

i guess the complexity should be O(logn) for printing each number. It can't be less than that

- kr.neerav July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can take advantage of inbuilt function of Integer class to get binary output

public void printBinary(int num) {
for (int i = 1; i <= num ; i++) {
System.out.println(Integer.toBinaryString(num));

}

}

- OW June 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can take advantage of inbuilt function of Integer class to get binary output

public void printBinary(int num) {
for (int i = 1; i <= num ; i++) {
System.out.println(Integer.toBinaryString(num));

}

}

- OW June 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void printBinary(int n) {
        for (int i = 1; i <= n; i++) {
            doPrintBinary(i);
            System.out.println();
        }
        
    }
    
    public static void doPrintBinary(int n) {
        if (n > 1) {
            doPrintBinary(n >> 1);
        }
        System.out.print(n & 1);
    }

- ktp July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use dp with heuristic as bin(n)=bin(n>>2)+n&1.....

- Anonymous September 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// how does it look like? Constant time. It could be improved by not using a temporary buffer

char* print_binary(int x){
int mask = 1;
int counter = 0;
char temp[32];
int last = -1;
while (counter < 32) {
if ((mask & x) != 0){
temp[counter] = '1';
last = counter;
}
else {
temp[counter] = '0';
}
mask <<= 1;
counter++;
}
char* output = new char[last+2];
for(int i=last;i>=0;i--){
output[last-i] = temp[i];
}
output[last+1] = '\0';
return output;
}

- robertoc July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for n=6 your code prints 110 it should print 1 10 11 100 101 110

- gdg July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//You just call it n times:

for (int i=1;i<=n;i++){
std::cout << print_binary(i);
if (i<n)
std::cout << " ";
}

- robertoc July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You actually need to call it 2^n times. From my understanding n is the number of digits not the upper bound.

- CatFancyCoverModel July 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nevermind, read the problem wrong :)

- CatFancyCoverModel July 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I didn't understand well the question: each number should be printed in O(1) time or the whole sequence? If it is each number the previous solution is fine, otherwise there should be another way to go!

- robertoc July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume this is what is being asked ?
static void Main(string[] args)
{
// Given a number n write a program to print all binary numbers starting from 1. For example n=6, print 1, 10, 11, 100, 101, 110
// Consequent numbers 111, 1000, 1001 1010
string str = "1";
int n = 100;
int nextPosToSearch = 0;
for (int i = 1; i <= n; i++)
{
Console.WriteLine(str);
char[] digits = str.ToCharArray();
for(int j = nextPosToSearch; j >=0; j--)
{
if (digits[j] == '1')
{
if (j == 0)
{
digits = new char[digits.Length + 1];
digits[0] = '1';
for (int k = 1; k < digits.Length; k++)
digits[k] = '0';
nextPosToSearch = digits.Length-1;
}
else
{
digits[j] = '0';
nextPosToSearch = j;
}
}
else
{
digits[j] = '1';
nextPosToSearch = j - 1;
break;
}
}

str = new string(digits);

}

Console.Read();
}

- R July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>

void binary(long n)
{
	int tic = 0;
	for (long i = 1 << 30; i > 0; i = i / 2)
	{
		if ((n & i))
		{
			printf("1");
			tic = 1;
		}
		else
		{
			if (tic == 1)
				printf("0");
		}
	}
	printf("\n");
}
int main()
{
	long n;
	scanf("%d", &n);
	for (long i = 1; i <= n; i++)
		binary(i);
	system("pause");
	return 0;
}

- aleem.javed2007 July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String recursive(int n){
        if(n > 0){
            if((n & 1) == 1){
                return recursive(n >> 1) + "1";
            }else{
                return recursive(n>>1) + "0";
            }
        }
        return "";
    }
    
    public static void main(String[] args) {
        int num = 0;
        try {
            num = System.in.read();
            num -= 48;
            for(int i = 1; i <= num; i++){
                System.out.println(recursive(i));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

- Josempb9 July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bitset>
#include <iostream>
#include <cstdlib>

using namespace std; 

int main()
{
	int n; 
	cin >> n;
	for (int i = 1; i <= n; i++)
		cout << bitset<32>(i) << " ";
	return 0;
}

- SK July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void printBinary(int i){
for(int j=1;j<=i;j++){
System.out.println(Integer.toBinaryString(j));
}

- Deepali October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should work in amortized O(1). The logic is simple, I manually keep on incrementing the number in binary form starting from 1. The operations simulate binary addition. There is no number to binary conversion done.

Code:

public class BinaryStringUptoN {
	public static void printN(int n){
		StringBuilder sb = new java.lang.StringBuilder("1");
		System.out.println(sb);
		for (int i = 1; i < n; i++) {
			System.out.println(incrementBin(sb, sb.length()));
		}
//		System.out.println(incrementBin(new StringBuilder("11011"), 5));
	}
	
	public static String incrementBin(StringBuilder i, int lookAt){
		int n = lookAt;
		if(i.charAt(n-1)=='0'){
			i.replace(n-1, n, "1");
		}else if(i.charAt(n-1)=='1' && n==1){
			i.replace(n-1, n, "0");
			i.insert(0, 1);
		}else{
			i.replace(n-1, n, "0");
			if(n>1 && i.charAt(n-2)=='1'){
				n--;
				incrementBin(i, n);
			}else if(n>1){
				incrementBin(i, n-1);
			}
		}
		return i.toString();
	}
	
	public static void main(String[] args) {
		printN(5);
	}
}

- Juned August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do this in amortized O(1) by starting from 1 and simulating binary addition all the way upto n.

- Juned August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <ctype.h>
#include <string.h>
#include <queue>
using namespace std;
void generate(int n)
{
queue<string> q;
q.push("1");
int i = 1;
while (i++ <= n)
{
q.push(q.front () + "0");
q.push(q.front () + "1");
cout<< q.front() <<' ';
q.pop();
}
}
int main()
{
int n = 2 ;
generate(n);
return 0;
}

- sharlet December 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DecimalToBinary {
public static void main(String[] args) {
int N = 12;
for(int i = 0; i<=N; i++) {
if(i == 0 || i ==1)
System.out.println(i);
else {
decimalToBinary(i);
System.out.println();
}
}

}

public static void decimalToBinary (int num) {
if(num == 0 || num ==1) {
System.out.print(num);
return;
}
decimalToBinary(num / 2);
System.out.print(num % 2);
}
}

- Gajendra July 17, 2018 | 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