Here Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
Here is the solution in Python, it is O(n+m), where n is the length of the string and m the number of unique characters the string has, which ends up being O(n) in runtime. The defaultdict class has the ability to initialize every instance that occurs with a predetermined value, in this case 0, so we just increment it for each time we found an occurrence of a character. At last, we traverse the defaultdict with an iterator that return a tuple of (key, value), but just printing the ones just appeared once (whose value is 1)
from collections import defaultdict
def charCounter(char_string):
counter = defaultdict(lambda : 0)
for char in char_string:
counter[char] += 1
for char in counter.iteritems()
if char[1] == 1:
print "%s ocurred one time" % char[0]
>>> charCounter("twinkle twinkle little star")
a ocurred one time
s ocurred one time
r ocurred one time
Here is the solution in Python, it is O(n+m), where n is the length of the string and m the number of unique characters the string has, which ends up being O(n) in runtime. The defaultdict class has the ability to initialize every instance that occurs with a predetermined value, in this case 0, so we just increment it for each time we found an occurrence of a character. At last, we traverse the defaultdict with an iterator that return a tuple of (key, value), but just printing the ones just appeared once (whose value is 1)
from collections import defaultdict
def charCounter(char_string):
counter = defaultdict(lambda : 0)
for char in char_string:
counter[char] += 1
for char in counter.iteritems()
if char[1] == 1:
print "%s ocurred one time" % char[0]
>>> charCounter("twinkle twinkle little star")
a ocurred one time
s ocurred one time
r ocurred one time
package com.str;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Given a string of english characters. Find the character that appears only once.
* @author Tanu
*
*/
public class CharThatApp1 {
public static void main(String[] args) {
String input = "baba black sheep";
List<String> tokens = Arrays.asList(input.split(""));
Map<Character,Integer> tokenMap = new HashMap<Character,Integer>();
for(String token: tokens){
for(int i=0;i<token.length();i++){
char c = token.charAt(i);
if(tokenMap.get(c)==null)
tokenMap.put(c,1);
else{
int reocc = tokenMap.get(c);
reocc++;
tokenMap.put(c, reocc);
}
}
}
System.out.println(" "+tokenMap.toString());
}
}
public class CharThatApp1 {
public static void main(String[] args) {
String input = "baba black sheep";
List<String> tokens = Arrays.asList(input.split(""));
Map<Character,Integer> tokenMap = new HashMap<Character,Integer>();
for(String token: tokens){
for(int i=0;i<token.length();i++){
char c = token.charAt(i);
if(tokenMap.get(c)==null)
tokenMap.put(c,1);
else{
int reocc = tokenMap.get(c);
reocc++;
tokenMap.put(c, reocc);
}
}
}
System.out.println(" "+tokenMap.toString());
}
}
you can use set also..and print the value which is stored into set....because set does not allow duplicate value... you can traverse through string and take one character of the string at a time and put that character into set...if set already has that character then that character will not stored into the set and if set has not that character then that character is stored into the set....
The interviewer is actually right, he/she was trying you to use a hash structure, in which you use the character as the index and the hash function will be just the times that characters was present, then you can find the characters whose values are one. In python, that would be something like this:
- Anonymous July 19, 2015