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

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

Clever answer! See the problem correctly.

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

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

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));

}

}

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

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));

}

}

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);
}``````

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

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

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 counter = 0;
char temp[32];
int last = -1;
while (counter < 32) {
if ((mask & x) != 0){
temp[counter] = '1';
last = counter;
}
else {
temp[counter] = '0';
}
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;
}

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

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 << " ";
}

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

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

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

Nevermind, read the problem wrong :)

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!

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);

}

}

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;
}``````

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 -= 48;
for(int i = 1; i <= num; i++){
System.out.println(recursive(i));
}
} catch (IOException e) {
e.printStackTrace();
}
}``````

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;
}``````

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));
}

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);
}
}``````

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.

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;
}

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);
}
}

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.