Bloomberg LP Interview Question
Software Engineer / Developers1. 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;
}
}
}
}
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.
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?
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).
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?
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++];
}
}
<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>
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;
}
#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;
}
// 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
// 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
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;
}
Use quicksort,
- Manoj March 11, 2011Never swap a integer with a character in comparison.