Bloomberg LP Interview Question for Software Engineer / Developers






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

Use quicksort,
Never swap a integer with a character in comparison.

- Manoj March 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this was a brilliant answer! Thanks!

- hm1021@nyu.edu October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a node struct (which has data and pointer to next node)
2. Scan the given string, create a node for each character and store that in a new array. Here next pointer of any node SHOULD point to next node of same type (i.e. a numeric node should point to next numeric node, and non-numeric node should point to non-numeric node)
3. Also have two pointers pointing to the head of numeric and non-numeric linked list.
4. At this point, we have a new array, having two linked list (numeric and non-numeric) inside it and order of nodes are exactly same as input string.
5. Now sort both linked list separately.
6. Print the new array and this is the desired output.

A working C code (used bubble sort here, should be replaced with better sorting code.... tested on cygwin):

#include<stdio.h>
#include<string.h>

struct node
{
char data;
struct node *next;
};

void llist_bubble_sort(struct node *head);

int main()
{
char str[]="ffdf45dfdf23hhnnnabd543";
printf("input string: %s\n",str);
int len=strlen(str);

struct node s[len];
struct node *num_head=NULL, *num_tail=NULL, *str_head=NULL, *str_tail=NULL, *tmp;
int i;

int j=0,k=0;
for(i=0;i<len;i++)
{
if(str[i]-'0' >= 0 && str[i]-'0' <= 9)
{
s[i].data=str[i];
s[i].next=NULL;
if(j==0)
{
num_head=num_tail=&s[i];
j++;
}
else
num_tail=num_tail->next=&s[i];
}
else
{
s[i].data=str[i];
s[i].next=NULL;
if(k==0)
{
str_head=str_tail=&s[i];
k++;
}
else
str_tail=str_tail->next=&s[i];
}
}

llist_bubble_sort(num_head);
llist_bubble_sort(str_head);

i=0;
printf("Sorted String: ");
while(i<len)
{
printf("%c",s[i].data);
i++;
}
printf("\n");
return 0;
}



void llist_bubble_sort(struct node *head)
{
struct node *i,*j;
for(i = head; i != NULL; i=i->next)
{
char c;
for(j = head; j != NULL; j=j->next)
{
if(i->data < j->data)
{
c=i->data;
i->data=j->data;
j->data=c;
}
}
}
}

- Anurag Singh February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Anurag ....its a good solution!

- Anonymous February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain the last part (printing after sorting two linked lists) ?

- Anonymous March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, if you read the algorithm above given before the code, things should be little easy to understand. Here is the deal (per above code):
1. s is an array of structure (size is length of input string)
2. we store each character in input string in structure one by one. character at index i is stored in s[i].
3. s[i] could be a numeric or non-numeric and it's next pointer has address of same type of character which comes next.
e.g. in input ze5s1d3q
s[0] will have z (i.e. s[0].data) and s[0].next points to e (next non-numerix character)
s[1] will have e and s[1].next points to s
s[2] will have 5 and s[2].next points to 1 (next numerix character)
s[3] will have s and s[3].next points to d
and so on

so at this point, input string is just stored in array so if we print all s[i].data from 0 to len-1, input string will be printed. Also in this array, each character knows the next character of it's own type. So just by following the next pointers, we can print only numeric sequence (513) or non-numeric sequence (zesdq)

Now we are sorting numeric and non-numeric sequences so after sorting, numeric sequence becomes 135 and non-numeric sequence becomes deqsz. while sorting numeric sequence, character movement happens only at numeric locations in structure s (non-numeric locations in structure s are not affected) and vice-versa (for non-numeric). This was possible with help of next pointer of each character in structure s.
So after sorting, character type index is maintained in structure s i.e. 1st two index has non-numeric, then, 3rd is numeric etc.
so after sorting, structure s will have
s[0]=d, s[1]=e, s[2]=1, s[3]=q, s[4]=3 and so on.
and same is printed at the end.

- Anurag Singh March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

brilliant !! thanks !!

- Anonymous March 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just one comment.. the data is supposed to be a streaming data meaning there is a continuous flow in the input string.. so to get a sorted list, we might need a priority queue type data structure.. or as the byte stream flows, we can keep inserting them in 2 (one for numeric and one for characters) self balancing binary search tree like an AVL tree or RB Tress. when the output is required, we might do an inorder traversal of both the trees (or enumerate the contents of priority queue) and show the desired output..

does this seem right or better than sorting the linked list implementation?

- Jester January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

simply apply insertion sort two times. first time sort the char staring with i = 0 & incrementing i by 2 instead of usual 1. For second time int will be sorted starting with i = 1 & incrementing i by 2 instead of usual 1.
TC = ((n/2)^2 + (n/2)^2)
Space = O(1).

- Mike February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you assumed that data is coming in a fixed format i.e it will always be a char first followed by an integer like:

CICICI... where C is character & I is the integer.

But the data can be in a any other format also like CCIICCCIC..
Thanks.

- Guess who?? February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct* node {
int value;
char value;
node* intnext;
node* charnext;
}

everytime character comes iterate through integer or character list and insert and update pointers..

- YouMe February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have an array each for number and char. Maintain a queue where 1 is inserted when int arrives and 2 is inserted when char arrives. Sort the 2 arrays. Traverse the queue and get element from corresponding array

- Anonymous February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about build up a binary tree while parsing the incoming stream?

you create two trees for characters and integers,

and then output the result?

i noticed that this question is about "stream", is there any thing we should pay attention when it is a stream, not a file or a array?

- s February 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

maintain two min-heaps each for character and numbers

maintain a queue which keeps a track of the input type from the data stream

when the data comes in, record the type in the queue, and insert in the respective heap

when output is required, extract the minimum from the min heap according to what is
next in the queue

But this is not valid if there is a continuous input and output of data...
any good algorithm for data stream as input and a sorted data stream as output?

- googly February 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort_char_int(char* str)
{
  const int len = strlen(str);
  char* sort_char = new char[len+1];
  char* sort_int = new char[len+1];

  int loop_i = 0;
  int loop_c = 0;
  bool* check = new bool[len];
  for (int i = 0; i < len; ++i)
    check[i] = false;

  for(int i = 0; i < len; ++i)
  {
    int diff = str[i] - '0';
    if (diff >= 0 && diff < 10) {
        check[i] = true;
        sort_int[loop_i++] = str[i];
    }
    else
        sort_char[loop_c++] = str[i];
  }
  sort_int[loop_i] = 0;
  sort_char[loop_c] = 0;
  vector<char> v_int(sort_int,sort_int+loop_i);
  vector<char> v_char(sort_char,sort_char+loop_c);
  sort(v_int.begin(), v_int.end());
  sort(v_char.begin(), v_char.end());
  
  loop_i = 0;
  loop_c = 0;
  for (int i = 0; i < len; ++i)
  {
    if (check[i])
      str[i] = v_int[loop_i++];
    else
      str[i] = v_char[loop_c++];
  }
}

- bigbird March 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey4296" class="run-this">#include <iostream>
#include <cstdlib>

using namespace std;

void sort_stream(char* stream, int length) {
if(!stream || length <=0)
throw("invalid input");

int char_array[256] = {0};
int int_array[10] = {0};

for(int i=0;i<length;++i) {
int index = (int) stream[i];

if(stream[i] >= '0' && stream [i] <= '9') {
index-=(int) '0';
++int_array[index];
}
else
++char_array[index];
}

int j=1, k=0;

for(int i=0;i<length;++i) {
while(!int_array[k]) ++k;
while(!char_array[j]) ++j;

if(stream[i] >= '0' && stream [i] <= '9') {
stream[i] = (char) k + '0';
--int_array[k];
}
else {
stream[i] = (char) j;
--char_array[j];
}
}
}

int main(int charc, char* charv[]) {
try {
int length = atoi(charv[2]);

cout<<"input stream is \n"<<charv[1]<<"\n\n";

sort_stream(charv[1], length);

cout<<"output stream is \n"<<charv[1]<<"\n";
}

catch(...) {
cout<<"exception catched\n";
}

return 0;
}</pre><pre title="CodeMonkey4296" input="yes">I am using counting sort for this problem.
The first for loop count the occurrences of each digit and character encountered in the input stream.
In the second loop, I recreate the stream in sorted order with indexes of digit or characters kept intact.
The solution is simple enough, so I don't think much explanation is required.</pre>

- Abhishek June 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Num,CharNum,NumerNum;
char myarr[MaxNum];
int charindex[MaxNum];
int numindex[MaxNum];


void mswap(int v1,int v2)
{

	int temp=myarr[v1];
	myarr[v1]=myarr[v2];
	myarr[v2]=temp;
}
void sort(int* indexarr,int msize)
{
	for(int i=0;i<msize;i++)
	{
		for (int j=i+1;j<msize;j++)
		{
			if(myarr[indexarr[i]]>myarr[indexarr[j]])
				mswap(indexarr[i],indexarr[j]);

		}
	}
}
int main()
{

	freopen("in.txt","r",stdin);
	Num=0;
	CharNum=0;
	NumerNum=0;
	
	while(scanf("%c",&myarr[Num])!=EOF)
	{
		if(myarr[Num]>='0'&&myarr[Num]<='9')
			numindex[NumerNum++]=Num;
		else
			charindex[CharNum++]=Num;
		Num++;
	}

	sort(charindex,CharNum);
	sort(numindex,NumerNum);

	for(int i=0;i<Num;i++)
	{
		cout<<myarr[i];

	}
	cout<<endl;

	return 0;
}

- Rukun Fan July 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;


int main() {
string input, output;
string number, character;
cin>>input;
string::iterator itr = input.begin();
string::iterator itrNum, itrCha;
// Divid
while( itr != input.end() ) {
if( isdigit( *itr ) )
number.push_back( *itr );
else
character.push_back( *itr );
itr++;
}
// STL sort
sort( number.begin(), number.end() );
sort( character.begin(), character.end() );
// Merge
for( itrNum = number.begin(), itrCha = character.begin();
itrNum != number.end() || itrCha != character.end(); ) {
if( itrCha != character.end() ) {
output.push_back( *itrCha );
itrCha++;
}
if( itrNum != number.end() ) {
output.push_back( *itrNum );
itrNum++;
}
}
cout<<output<<endl;
return 0;
}

- Anonymous February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Codes in C++
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;


int main() {
string input, output;
string number, character;
cin>>input;
string::iterator itr = input.begin();
string::iterator itrNum, itrCha;
// Divid
while( itr != input.end() ) {
if( isdigit( *itr ) )
number.push_back( *itr );
else
character.push_back( *itr );
itr++;
}
// STL sort
sort( number.begin(), number.end() );
sort( character.begin(), character.end() );
// Merge
for( itrNum = number.begin(), itrCha = character.begin();
itrNum != number.end() || itrCha != character.end(); ) {
if( itrCha != character.end() ) {
output.push_back( *itrCha );
itrCha++;
}
if( itrNum != number.end() ) {
output.push_back( *itrNum );
itrNum++;
}
}
cout<<output<<endl;
return 0;
}
// End Codes

- Anonymous February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Codes in C++
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;


int main() {
string input, output;
string number, character;
cin>>input;
string::iterator itr = input.begin();
string::iterator itrNum, itrCha;
// Divid
while( itr != input.end() ) {
if( isdigit( *itr ) )
number.push_back( *itr );
else
character.push_back( *itr );
itr++;
}
// STL sort
sort( number.begin(), number.end() );
sort( character.begin(), character.end() );
// Merge
for( itrNum = number.begin(), itrCha = character.begin();
itrNum != number.end() || itrCha != character.end(); ) {
if( itrCha != character.end() ) {
output.push_back( *itrCha );
itrCha++;
}
if( itrNum != number.end() ) {
output.push_back( *itrNum );
itrNum++;
}
}
cout<<output<<endl;
return 0;
}
// End Codes

- Anonymous February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Declare an array of boolean to mark char/int position
Split chars into a list and ints into another list
Sort the list
Merge them by going through boolean array with position

private static char[] sortArrayAndMaintainIndex(char[] chars) {
        boolean[] positionMarker = new boolean[chars.length];
        int position = 0;
        char zero = '0';
        char nine = '9';
        List<Character> charList = new ArrayList<>();
        List<Integer> intList = new ArrayList<>();
        for (char c : chars) {
            if (c >= zero && c <= nine) { // if c is a number
                intList.add(c - zero);
                positionMarker[position++] = false;
            }
            else {
                charList.add(c);
                positionMarker[position++] = true;
            }
        }

        Collections.sort(charList);
        Collections.sort(intList);

        position = 0;
        for(boolean isCharPosition : positionMarker) {
            chars[position++] = isCharPosition ? charList.remove(0) : (char)(intList.remove(0).intValue() + '0');
        }

        return chars;
    }

- Lawir January 15, 2016 | 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