Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
This is just wrong in many parts. It does not print the beginning of the run but the last character, it would always print the 2nd character if it's the same as the first and it wouldn't even print the last run.
I could not understand this question. Please elaborate and help me understand
I couldn't understand meaning of 0,3,5 as output for a given input 0010011
there are 3 one's what does 0 and 5 relate to ?
0 is the offset of the first two zeros, 3 is the offset of the next two zeros, 5 is the offset of the two ones.
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
char str[30] = "001001100011";
char out = str[0];
int count = 1;
int pos = 0;
for (int i = 1; i <= strlen(str); i++)
{
if(out == str[i])
count++;
else
{
if(count > 1)
printf("%d ",pos);
pos = i;
count = 1;
}
out = str[i];
}
getchar();
}
void print_runs_offsets(string s) {
string::iterator it = s.begin();
char current = *it;
int i = 0;
int p = 0;
int run = 1;
++it;
for (;
it != s.end();
++it) {
++i;
if (current == (*it))
++run;
else {
if (run > 1) {
cout << p << " ";
}
p = i;
current = *it;
run = 1;
}
}
if (run > 1)
cout << p << endl;
return;
}
Here is the java code for generalized required offset.. The variable "requiredOffset" takes the parameter of the minimum threshold of the offset. For this case, it is 2.
public static void offsetOfRuns() {
String text = "000010000111";
int requiredOffset = 2;
int startIndexOffset = 0;
if ( text.length() > 0 ) {
int count = 1;
char ch = text.charAt(0);
for ( int i = 1 ; i < text.length(); ++i ) {
if ( text.charAt(i) == ch ) {
count++;
if (count == requiredOffset) {
System.out.println(startIndexOffset);
}
} else {
startIndexOffset = i;
count = 1;
ch = text.charAt(i);
}
}
}
}
public static void longestBinaryRun(String str) {
int count = 1;
boolean flag = false;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
if (count > 1 && flag == false) {
System.out.print((i - 1) + " ");
flag = true;
}
} else {
count = 1;
flag = false;
}
}
}
public static void longestBinaryRun(String str) {
int count = 1;
boolean flag = false;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
if (count > 1 && flag == false) {
System.out.print((i - 1) + " ");
flag = true;
}
} else {
count = 1;
flag = false;
}
}
}
public static void longestBinaryRun(String str) {
int count = 1;
boolean flag = false;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
if (count > 1 && flag == false) {
System.out.print((i - 1) + " ");
flag = true;
}
} else {
count = 1;
flag = false;
}
}
}
A run of length > 1 has the property that at some index, s[i] == s[i - 1]. However, you want to report the beginning of the run, so we must have s[i] == s[i - 1] and s[i - 1] != s[i - 2]. Then (i - 1) is the offset.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main () {
string s = "aabbccdaddddaddaddaeeeddedeeeeeeedsddfffkfkfkkk";
vector<int> offset;
if (s[0] == s[1]) offset.push_back(0);
for (int i = 2; i < s.size(); i++) if (s[i] == s[i - 1] && s[i - 1] != s[i - 2]) offset.push_back(i - 1);
for (auto it = offset.begin(); it != offset.end(); ++it) cout << *it << " ";
return 0;
}
#include <iostream>
using std::cout;
using std::endl;
template<class T>
void printOffSet(const T* a, size_t size) //the input size is acutally size+1
{
int runningCount=1;
for(int i=0;i<size-1;++i)
{
if(a[i]==a[i+1])
{
++runningCount;
}
else
{
if(runningCount>1)
{
cout<<(i-(runningCount-1))<<((i==size-2)?"":", ");
}
runningCount=1;
}
}
cout<<endl;
}
int main()
{
char a[]="00100011";
std::string b("0000110111");
cout<<"a[] is "<<a<<endl;
printOffSet(a,sizeof(a)/sizeof(a[0]));
cout<<"b is "<<b<<endl;
printOffSet(b.c_str(), b.length()+1);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printOffsets(char *);
int main()
{
char str[]="0010011111001";
printOffsets(str);
return 0;
}
void printOffsets(char *str)
{
if(!str)
{
printf("Input string is NULL,SYSTEM EXITING!!\n");
exit(0);
}
int len=strlen(str);
if(len==0 || len==1)
{
printf("String is either empty, or not long enough for calculating offset. SYSTEM EXITING !!\n");
exit(0);
}
int i=0,count=1,start_index=0;
for(i=0;i<len;i++)
{
if(str[i]==str[i+1])
count++;
else
{
if(count>1)
printf("%d ",start_index);
start_index=i+1;
count=1;
}
}
printf("\n");
}
Java solution:
public static void main(String args[]){
Scanner in=new Scanner(System.in);
String input=in.next();
char currentVal=' ';
for(int i=0; i<input.length(); i++){
if(input.charAt(i)!=currentVal && input.charAt(i)==input.charAt(i+1) )
{
System.out.println(i);
currentVal=input.charAt(i);
}
else
{
currentVal=input.charAt(i);
}
}
}
In C++:
#include <iostream>
using namespace std;
int main() {
string s = "0010011";
int i, count = 0, start = 0;
int start_array[s.length()];
for(i = 1;i < s.length();i++){
if(i == start + 1 && s[i] == s[start]) start_array[count++] = start;
if(s[i] != s[start]) start = i;
}
for(i = 0;i < count;i++) cout << start_array[i] << ", ";
return 0;
}
public void printRuns(String s) {
int n = 1;
char c = s.charAt(0);
for (int i = 1; i < s.length(); i++) {
if (c == s.charAt(i))
n++;
else {
c = s.charAt(i);
if (n > 1)
System.out.println(i - n);
n = 1;
}
}
if (n > 1)
System.out.println(s.length() - n);
}
In Java
public class OffsetofRuns {
/**
* @param args
*/
public static void main(String[] args) {
String a = "0010011";
int count =1;
char prevChar = a.charAt(0);
int offset =0;
for(int i=1;i<a.length();i++) {
char c = a.charAt(i);
if(c!=prevChar){
if(count>1){
System.out.print(offset + " ");
}
offset = i;
count =1;
prevChar = c;
}
else {
count++;
}
}
if(count>1){
System.out.print(offset + " ");
}
}
}
package test;
public class PrintBinaryOffset {
public static void printBinOffsets(String s) {
if (s == null) return;
int length = s.length();
if (length < 2) return;
int counter = 1;
int offset = 0;
for (int i = 1; i < length; i++) {
if (s.charAt(i) != s.charAt(i-1)) {
if (counter >= 2) {
System.out.println(offset);
}
offset = i;
counter = 1;
} else {
counter++;
}
}
// DON'T FORGET TO CHECK IN THE END
if (counter >= 2) {
System.out.println(offset);
}
}
public static void main(String[] args) {
String s = "0010011";
printBinOffsets(s);
}
}
Since we dont care about the size of the run, once we find one of size 2 we can burn through the rest of it.
void run_offsets(std::string s){
char last = s[0];
for(int i = 1; i < s.size(); i++){
if(last == s[i]) std::cout << i - 1 << ", ";
while(s[i] == last && i < s.size()) i++;
last = s[i];
}
std::cout << std::endl;
}
A function returns the result in a vector:
std::vector<int> getRuns(const std::string& str) {
vector<int> result;
int pos = 0;
if(str.size()>0) {
while(pos < str.size()) {
char cur = str[pos];
if(cur == str[pos+1])
result.push_back(pos);
while(str[++pos] == cur ); // move to next run
}
}
return result;
}
Here is my version:
#include <iostream>
#include <string>
#include <cstdlib>
using std::string;
using std::cout;
using std::endl;
// WAP to accept non-empty string of 0's & 1's as an argument.
// The program will print the offsets of runs, each run consisting
// of all 0's or all 1's, where runs are longer than 1
// Example:
// I/P: 001001100011
// O/P: 0, 3, 5, 7, 10
void printOffsets(const string &str);
int main(int argc,char **argv)
{
if (argc != 2) {
std::cerr << "usage: offset <pattern string>" << endl;
exit(-1);
}
printOffsets(string(argv[1]));
return 0;
}
void printOffsets(const string &str)
{
int N = str.length();
int count = 1;
int offset = -1,idx = 0;
bool flag = false;
while (idx < N) {
while (str[idx] == str[idx + 1]) {
if (!flag) {
offset = idx;
flag = true;
}
count++;
idx++;
}
if (count > 1) {
cout << offset << " ";
offset = -1;
count = 1;
flag = false;
}
idx++;
}
cout << endl;
}
Here is an O(n) time, O(1) space solution:
We iterate over the string and keep track of the beginning of the current run. If there is a character change, then we print the last run if it was longer than 1 character.
public void printRuns(String s) {
int n = 1;
char c = s.charAt(0);
for (int i = 1; i < s.length(); i++) {
if (c == s.charAt(i))
n++;
else {
c = s.charAt(i);
if (n > 1)
System.out.println(i - n);
n = 1;
}
}
if (n > 1)
System.out.println(s.length() - n);
}
private static void offsetRun() {
String s="00110100011";
int counter = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) != s.charAt(i - 1)) {
if (counter>1){
System.out.println(i-counter);
counter=1;
}
} else {
counter++;
}
}
if (counter > 1)
System.out.println(s.length()-counter);
}
- unknown March 06, 2014