Bloomberg LP Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
var Str1 = "ad7f6ysh";
var Str2 = "1234567";
var Str2Arr = Str2.split("");
var minIndex = -1;
var Elem = "";
for(var i=0; i<Str2Arr.length;i++){
currentElemIndex = Str1.indexOf(Str2Arr[i]);
if( currentElemIndex != -1){
if(minIndex == -1){
minIndex = currentElemIndex;
Elem = Str2Arr[i];
}else if(minIndex > currentElemIndex){
minIndex = currentElemIndex;
Elem = Str2Arr[i];
}
}
}
if(minIndex != -1){
console.log(Elem+ " Element is found at index "+ minIndex);
}
One optimization I could think of was to put the shorter string in the HashMap. This could be helpful in the 1st and last cases:
public class findIndexOfChar {
public static void main(String[] args) {
System.out.println(findIndexOfChar("adf6ysh","12345678762364798723577857398476089023857435826"));
System.out.println(findIndexOfChar("adfysh","12345678"));
System.out.println(findIndexOfChar("adf6as6h","12345678"));
System.out.println(findIndexOfChar("1234567876236479872357826798347534509809384509384509","adfh6ysh"));
}
private static int findIndexOfChar(String str1, String str2) {
HashMap<Character,Integer> hm = new HashMap<Character, Integer>();
String longer;
String shorter;
boolean str1IsLonger;
if(str1.length()>str2.length()){
longer = str1;
shorter = str2;
str1IsLonger = true;
}
else{longer = str2;
shorter = str1;
str1IsLonger = false;
}
int index = 0;
for (Character ch : shorter.toCharArray()) {
if (!hm.containsKey(ch)) {
hm.put(ch,index);
}
index++;
}
for (int i = 0; i < longer.length(); i++) {
if (hm.containsKey(longer.charAt(i))) {
if(str1IsLonger) {return i;}
else {return hm.get(longer.charAt(i));}
}
}
return -1;
}
}
public class LPMain001 {
static int indexOf(String str1, String str2 ) {
for (int i=0; i<str2.length(); i++ ) {
char c = str2.charAt(i);
if ( str1.indexOf(c)>-1 ) {
return str1.indexOf(c);
}
}
return -1;
}
public static void main(String[] args) {
String str1 = "adf6ysh";
String str2 = "123678";
String str3 = "12378";
assert indexOf(str1,str2) == 3;
assert indexOf(str1,str3) == -2;
}
}
//
// Returns the zero based index of the first occurance of
// any character of str2 in str1
//
// (c) 2016 Perry Anderson
// http://perryanderson.com/
//
public class LPMain001 {
static int indexOf(String str1, String str2 ) {
for (int i=0; i<str2.length(); i++ ) {
char c = str2.charAt(i);
if ( str1.indexOf(c)>-1 ) {
return str1.indexOf(c);
}
}
return -1;
}
public static void main(String[] args) {
String str1 = "adf6ysh";
String str2 = "123678";
String str3 = "12378";
assert indexOf(str1,str2) == 3;
assert indexOf(str1,str3) == -1;
}
}
public class Driver {
public static void main(String[] args) {
StringMatching sm = new StringMatching();
String str1 = "adfysh26";
String str2 = "123678";
System.out.println(sm.match(str1, str2));
}
}
class StringMatching {
public int match(String str1, String str2) {
for (int i = 0; i < str1.length(); i++) {
char xchar = str1.charAt(i);
if (Character.isDigit(xchar)) {
int idx = str2.indexOf(xchar);
if (idx >= 0) {
return idx;
}
}
}
return -1;
}
}
public class Driver {
public static void main(String[] args) {
StringMatching sm = new StringMatching();
String str1 = "adfysh26";
String str2 = "123678";
System.out.println(sm.match(str1, str2));
}
}
class StringMatching {
public int match(String str1, String str2) {
for (int i = 0; i < str1.length(); i++) {
char xchar = str1.charAt(i);
if (Character.isDigit(xchar)) {
int idx = str2.indexOf(xchar);
if (idx >= 0) {
return idx;
}
}
}
return -1;
}
}
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class RegExpr8 {
public static void main(String[] args) {
String str1 = "adf6ysh7";
String str2 = "123678";
Pattern p = Pattern.compile("[\\d]");
Matcher m1 = p.matcher(str1);
boolean isFound = false;
while (m1.find()) {
String strTemp1 = m1.group();
System.out.println("Finding " + " --- " + strTemp1);
Matcher m2 = p.matcher(str2);
while (m2.find()) {
String strTemp2 = m2.group();
if (strTemp1.equals(strTemp2)) {
System.out.println("Found " + " --- " + strTemp2 + " at " + m2.start());
isFound = true;
break;
}
}
if (isFound)
break;
}
}
}
public static void main(String args[]) {
String s1 = "adf6ysh";
String s2 = "123678";
int length;
if (s1.length() > s2.length()) {
length = s1.length();
}
else {
length = s2.length();
}
for (int i = 0; i < length; i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1 == c2) {
System.out.println(c1);
break;
}
}
}
Check this out
public static int FindFirstOccurrence(string str1, string str2)
{
// error condition checks
var charcount = Dictionary<char,int>();
for(int i = 0 ; i < str2.Length;i++)
{
if(!charcount.Contains(str2[i]))
{
charcount[str2[i]] = 1;
}
else
{
charcount[str2[i]]++;
}
}
for(int i = 0 ; i < str1.length;i++)
{
if(charcount.Contains(str1[i])
{
return i;
}
}
return -1;
}
Complexity of this is O(n) + O(1), as the char count is constant.
public static int FindFirstOccurance(string str1, string str2)
{
int retVal = -1;
for (int i=0; i<str1.Length - 1; i++ )
{
if (str2.IndexOf(str1[i]) > -1)
return i;
}
return retVal;
}
import java.util.*;
public class FirstOccurrences{
public static void main(String[] args){
String str1 = "adf6ysh";
String str2 = "1234567";
HashSet<Character> s2 = new HashSet<Character>();
for(int i = 0; i < str2.length(); i++){
s2.add(str2.charAt(i));
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < str1.length(); i++){
char c = str1.charAt(i);
if(s2.contains(c)){
map.put(c, i);
s2.remove(c);
}
}
for(Character c : map.keySet()){
System.out.print(c + ": " + map.get(c));
}
}
}
import java.util.*;
public class FirstOccurences{
public static void main(String[] args){
String str1 = "adf6ysh";
String str2 = "1234567";
HashSet<Character> s2 = new HashSet<Character>();
for(int i = 0; i < str2.length(); i++){
s2.add(str2.charAt(i));
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < str1.length(); i++){
char c = str1.charAt(i);
if(s2.contains(c)){
map.put(c, i);
s2.remove(c);
}
}
for(Character c : map.keySet()){
System.out.print(c + ": " + map.get(c));
}
}
}
#include <iostream>
using namespace std;
int main()
{
string first,second;
cin>>first>>second;
int index=0;
int i=0,j=first.length()-1;
int p=0,q=second.length()-1;
while(i<j&&p<q)
{
if(first[i]==second[p])
{
index=i;
break;
}
i++;
p++;
}
if(index==0&&first[i]==second[p])
{
index=i;
}
cout<<index;
return 0;
}
public class FirstOccurence {
public static void main(String[] args){
String s1 = "adf6ysh";
String s2 = "1234567";
boolean found = false;
int[] s2Count = new int[96]; // Assuming alphabet, number and special characters only in s1 and s2 ASCII(127-31)
for(char c:s2.toCharArray()){
s2Count[(c-' ')]++;
}
char[] s1Array = s1.toCharArray();
for(int i=0;i<s1Array.length;i++){
if(s2Count[s1Array[i]-' ']>0)
{
System.out.println("Character at "+i+"+1 Matches");
found = true;
}
}
if(!found){
System.out.println("No Match");
}
}
}
I think this code in C is good for this case assuming ASCII chars - O(n) runtime, O(1) space.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// assuming ASCII chars
#define NUM_CHARS 256
// define boolean
typedef enum { false, true } bool;
// find the first occurence of any char from s2 in s1
// in no such occurence found return -1
int firstOccurence(char * s1, char * s2) {
int index = -1;
unsigned int i;
// array to indicate which chars are in s2
bool charMap[NUM_CHARS];
// init values with -1
for (i = 0; i < NUM_CHARS; i++) {
charMap[i] = false;
}
// fill in array where chars show in s2
for (i = 0; i < strlen(s2); i++) {
int cVal = s2[i];
if (charMap[cVal] == false) {
charMap[cVal] = true;
}
}
// find first char in s1 that appered in s2
for (i = 0; i < strlen(s1); i++) {
int cVal = s1[i];
if (charMap[cVal] == true) {
index = i;
break;
}
}
// if no occurence found, index will be -1
// else index will be the first occurence of any char from s2 in s1
return index;
}
int main() {
// strings
char s1[] = "abdgilcnhjfcs";
char s2[] = "oooooci";
// expect 4 for this example... as i from
// s2 appears first in s1 at index 4 (zero based).
int first = firstOccurence(s1, s2);
printf("First occurence is %d\n", first);
}
public int findFirstOccurence(String str1, String str2) {
int[] table = new int[128];
char[] charArrayStr1 = str1.toCharArray();
for(char character : charArrayStr1) {
table[character]++;
}
char[] charArrayStr2 = str2.toCharArray();
for(int i = 0; i < charArrayStr2.length; i++) {
if(table[charArrayStr2[i]] > 0) return i;
}
return -1;
}
public class LPMain001 {
static int indexOf(String str1, String str2 ) {
for (int i=0; i<str2.length(); i++ ) {
char c = str2.charAt(i);
if ( str1.indexOf(c)>-1 ) {
return str1.indexOf(c);
}
}
return -1;
}
public static void main(String[] args) {
String str1 = "adf6ysh";
String str2 = "123678";
String str3 = "12378";
assert indexOf(str1,str2) == 3;
assert indexOf(str1,str3) == -2;
}
}
// ZoomBA
- NoOne September 13, 2016d_1 = rfold( str1.toCharArray , dict() ) as { [ $.o.key , $.o.i ] } found_index = lfold( str2.toCharArray , -1 ) as { break( $.o.key @ d_1 ){ $.o.value } }