Bloomberg LP Interview Question
Financial Application EngineersCountry: United States
Interview Type: In-Person
hI I have tried the solution in vc++.Please find the code for the question.I have not done unit testing and little care is taken for efficiency.
#include"stdafx.h"
#include<iostream>
using namespace std;
void first_duplicate(char*p)
{
int i,j,count=0;
i=0;
j=1;
int index=0;
while(p[index] != '\0')
{
while(p[i] == p[j])
{
count++;
i++;
j++;
}
if(count)
{
i =j;
j = j+1;
count=0;
}
else if(count ==0)
{
cout<<"fist duplicate found @ "<<p[i]<<endl;
break;
}
index++;
}
}
int main()
{
char string[40]="aabbbbccceeeddffsssk";
first_duplicate(string);
getchar();
return 0;
}
public class Test{
public static void main(String[] args){
String str = "aabbcdcceefff";
int[] arr = new int[26];
int temp = 0;
for(int i=0;i<str.length();i++){
arr[str.charAt(i)-'a']++;
}
for(int i=0;i<str.length();i++){
if(arr[i] == 1){
temp = i;
break;
}
}
System.out.println(temp);
int a = temp + 'a';
char b = (char) a;
System.out.println(b);
}
}
public class Test{
public static void main(String[] args){
String str = "aabbcdcceefff";
int[] arr = new int[26];
int temp = 0;
for(int i=0;i<str.length();i++){
arr[str.charAt(i)-'a']++;
}
for(int i=0;i<str.length();i++){
if(arr[i] == 1){
temp = i;
break;
}
}
System.out.println(temp);
int a = temp + 'a';
char b = (char) a;
System.out.println(b);
}
}
import java.util.*;
public class UniqueLetterInString {
public static void main (String args[]) {
String[] inputString={"a","a","b","b","c","d","d","c","c","e","f","f","f"};
int i,j=0;
HashMap duplicateCount=new HashMap();
for(i=0;i<inputString.length;i++)
{
if(duplicateCount.containsKey(inputString[i]))
{
int count=Integer.parseInt(duplicateCount.get(inputString[i]).toString());
count++;
duplicateCount.put(inputString[i], count);
}
else
{
duplicateCount.put(inputString[i], 1);
}
System.out.println("Key ---->"+inputString[i]+"Value--->"+Integer.parseInt(duplicateCount.get(inputString[i]).toString()));
}
Iterator itr =duplicateCount.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry pairs = (Map.Entry)itr.next();
if(Integer.parseInt(pairs.getValue().toString())==1)
{
System.out.println("The character which is unique is -->"+pairs.getKey());
break;
}
}
}
}
I think this is O(n) implementation, i ve run it and it works!
#include <iostream>
#include <string>
#include <cctype>
#include <utility>
#include <limits>
int main () {
std::string s = "aabbcdccefff";
std::string::const_iterator iter = s.begin();
int i = 0;
int array[26];
for (i = 0; i < 26; ++i) {
array[i] = 0;
}
for (i = 1; iter != s.end(); ++iter, ++i) {
int index = (int) *iter - 'a';
if (array[index] == 0) {
array[index] = i;
} else if (array[index] > 0) {
array[index] *= -1;
}
}
int min_value = std::numeric_limits<int>::max();
int min_index = -1;
for (i = 0; i < 26; ++i) {
if (array[i] > 0) {
if (array[i] < min_value) {
min_value = array[i];
min_index = i;
}
}
}
std::cout << (char) (97 + min_index) << std::endl;
}
I'm not assuming the characters are necessarily lowercase:
import java.util.*;
class FirstNonDuplicate
{
public static void main( String [] args )
{
LinkedHashMap<Character, Boolean> map = new LinkedHashMap<>();
for( Character c : args[0].toCharArray() )
{
Boolean alreadyFound = map.get( c );
if( map.get( c ) == null )
map.put( c, true );
else if( alreadyFound == true )
map.put( c, false );
}
Iterator<Character> iterator = map.keySet().iterator();
Boolean found = false;
while( iterator.hasNext() && !found )
{
Character c = iterator.next();
found = map.get( c );
if( found )
System.out.println( c );
}
}
}
#include <iostream> // std::cout
#include <algorithm> // std::find_if
#include <string> // std::vector
int main ()
{
std::string input = "aabbcdccefff";
for(std::string::iterator itr = input.begin(); itr != input.end(); ++itr)
{
char _in = *itr;
if (1 == std::count(input.begin(), input.end(),_in))
{
std::cout << "First duplicate value: " << _in << '\n';
break;
}
}
return 0;
}
public class findFirstNonDuplicate {
public static void main(String[] args) {
String s ="aabbcdccefff";
char x = 0;int i;boolean flag = true;
for( i = 0;i<s.length();i++){
x = s.charAt(i);
for(int j =0;j<s.length();j++){
if(i!= j && x == s.charAt(j)){
flag = false;
continue;
}
}
if(flag == true){
System.out.println("First Non Duplicate Occurence: "+x);
break;
}
flag = true;
}
}
}
In Ruby (tested with 2.1.1)
string_to_parse = ARGV[0]
def find_first_unique_char_in_string str
return "" if str.nil? || str.empty?
char_hash = Hash.new(0)
# because they aren't ordered, go through each char
str.each_char{|c| char_hash[c] += 1}
# print the key for the first char that appears one time
puts char_hash.select{|k,v| v ==1}.keys.first
end
find_first_unique_char_in_string string_to_parse
#include <stdio.h>
#include <string.h>
static const char*
find_unique(const char *string);
#define MAP_SIZE (256)
#define DUP ((char*)-1)
#define EOS ((char)0)
main() {
char *string = "aabbcDccefff";
const char *unique;
unique = find_unique(string);
if(unique)
printf("unique character at 0x%lx => %c\n", unique, *unique);
}
static const char*
find_unique(const char *string) {
const char *char_map[MAP_SIZE];
const char *c;
memset(&char_map, 0, sizeof(char_map));
for(c = string; *c != EOS; ++c) {
if(*c == EOS)
break;
char_map[*c] = char_map[*c] ? DUP : c;
}
for(c = string; *c != EOS; ++c) {
if(char_map[*c] != DUP)
return c;
}
return NULL;
}
This is the C++ version of harsha's response
#include <iostream>
using namespace std;
int main() {
string data = "aabbcdccefff";
for (int i = 0 ; i < data.length() ; i++) {
if (data.find_first_of(data.at(i)) == data.find_last_of(data.at(i))) {
cout << "answer: " << data.at(i) << endl;
break;
}
}
}
1. take an array of size 256 and initialize it to zero.
- Vin September 24, 20132. scan the input string from beginning and increment corresponding index of array(ie array[input string[i] ]++ ).
3. scan the input string from beginning and check 1 == array[input string[i] ]. if such exist, input string[i] will be the answer.