Salesforce Interview Question Quality Assurance Engineers
Country: United States
Interview Type: Phone Interview
asymptotically not optimal solution.
In case of all distinct characters this is O(n^2) solution.
Using hashtable allows to create O(n) solution.
public class careercup {
public static void main(String[] args) {
String s1 = "Salesforce is the best company to work for";
char[] chars = s1.toLowerCase().toCharArray();
int count;
for (int i = 0; i < chars.length; i++) {
count = 0;
for (int j = i + 1; j < chars.length; j++) {
if (chars[i] == chars[j]) {
count++;
break;
}
}
if (count == 0) {
System.out.println(chars[i]);
break;
}
}
}
}
public void minCharCounter(String word) {
LinkedHashMap<Character, Integer> charcount = new LinkedHashMap<>();
for (int i = 0; i < word.length(); i++) {
if (charcount.get(word.charAt(i)) == null) {
charcount.put(word.charAt(i), 1);
} else {
charcount.put(word.charAt(i), charcount.get(word.charAt(i)) + 1);
} }
int min = Integer.MAX_VALUE; char min_char = (char) 256;
for (Map.Entry<Character, Integer> count : charcount.entrySet()) {
if(count.getValue() < min) {
min = count.getValue();
min_char = count.getKey();
} }
System.out.println(min_char + ":" + min);
}
public void minCharCounter(String word) {
word = word.toLowerCase();
LinkedHashMap<Character, Integer> charcount = new LinkedHashMap<>();
for (int i = 0; i < word.length(); i++) {
if (charcount.get(word.charAt(i)) == null) {
charcount.put(word.charAt(i), 1);
} else {
charcount.put(word.charAt(i), charcount.get(word.charAt(i)) + 1);
}
}
int min = Integer.MAX_VALUE; char min_char = (char) 256;
for (Map.Entry<Character, Integer> count : charcount.entrySet()) {
if(count.getValue() < min) {
min = count.getValue();
min_char = count.getKey();
}
}
System.out.println(min_char + ":" + min);
}
using hashtable do 1st scan and store chars and their frequencies to that hashtable.
Then do 2nd scan and compare each char's frequency to 0. When you hit 0 for the first time - break and return the corresponding char.
First character with 0 frequency may not be the first non repeated element.
We can store the index as part of the key generated or as value while forming the hash table and check during second scan for lower index ,0 frequency char.
in my algorithm first character with 0 frequency will be the first non repeated element, because both scans are done against the input string.
The following solution will be more optimal as you do not have nested loops. The question should also dictate whether you can use the java api or solve the problem using primitive arrays.
public static String findFirstNonRepeatingChar(String string) {
//ascii mapping of char a. Given ascii values are incremental from A-Z we can just subtract ascii value of A
//to give us the count mapping of the char in the array
int ASCII_VALUE_A=97;
int[] charCounts = new int[26]; //0==a, 1==b, 2==c ...
char[] charSequence = new char[26]; //the order in which the chars appeared in the supplied string
int charSequenceCount=0;
for(char character : string.toLowerCase().toCharArray()) {
if(character != ' ') {
//Have we seen this char before?
int countIndex = ((int)character)-ASCII_VALUE_A;
int count = charCounts[countIndex];
if(count == 0) //new char not seen before so store in the char sequence in the next free slot
charSequence[charSequenceCount++] = character;
//increment the number of occurrences count for the given char
charCounts[countIndex]=++count;
}
}
//iterate over the chars in the order they appeared in the supplied string and find the first occurrence where count == 1
for(int i=0; i<charSequenceCount; i++) {
char c = charSequence[i];
if(charCounts[((int)c)-ASCII_VALUE_A]==1) {
return c+"";
}
}
return "No unique characters in sentence : " + string;
}
The following solution avoids the worst case O(n2) by removing the nested loop. Does not use the java api either. Question, ideally would state whether it needs to be solved using raw code or using Java API.
public static String findFirstNonRepeatingChar(String string) {
//ascii mapping of char a.
int ASCII_VALUE_A=97;
//0==a, 1==b, 2==c ...
int[] charCounts = new int[26];
//the order in which the chars appeared in the supplied string
char[] charSequence = new char[26];
int charSequenceCount=0;
for(char character : string.toLowerCase().toCharArray()) {
if(character != ' ') {
//Have we seen this char before?
int countIndex = ((int)character)-ASCII_VALUE_A;
int count = charCounts[countIndex];
//new char not seen before so store in the char sequence
if(count == 0)
charSequence[charSequenceCount++] = character;
//increment the number of occurrences count for the given char
charCounts[countIndex]=++count;
}
}
//iterate over the chars in the order they appeared in the supplied string
for(int i=0; i<charSequenceCount; i++) {
char c = charSequence[i];
if(charCounts[((int)c)-ASCII_VALUE_A]==1) {
return c+"";
}
}
return "No unique characters in sentence : " + string;
}
package com.learning;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
find();
}
public static String find() {
String searchIn = "This is the ue";
char[] searchInArray = searchIn.toLowerCase().toCharArray();
String notRepeated = "notFound";
int counter = 0;
for (char c : searchInArray) {
for (char d : searchInArray) {
if (c == d) {
counter = counter + 1;
}
if (counter > 1) {
break;
}
}
if (counter == 1) {
System.out.println(String.valueOf(c));
return String.valueOf(c);
}
counter =0;
}
return null;
}
}
package com.learning;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
find();
}
public static String find() {
String searchIn = "This is the ue";
char[] searchInArray = searchIn.toLowerCase().toCharArray();
String notRepeated = "notFound";
int counter = 0;
for (char c : searchInArray) {
for (char d : searchInArray) {
if (c == d) {
counter = counter + 1;
}
if (counter > 1) {
break;
}
}
if (counter == 1) {
System.out.println(String.valueOf(c));
return String.valueOf(c);
}
counter =0;
}
return null;
}
}
package com.learning;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
find();
}
public static String find() {
String searchIn = "This is the ue";
char[] searchInArray = searchIn.toLowerCase().toCharArray();
String notRepeated = "notFound";
int counter = 0;
for (char c : searchInArray) {
for (char d : searchInArray) {
if (c == d) {
counter = counter + 1;
}
if (counter > 1) {
break;
}
}
if (counter == 1) {
System.out.println(String.valueOf(c));
return String.valueOf(c);
}
counter =0;
}
return null;
}
}
Scala solution:
def main(strings: Array[String]) = {
val s = "Salesforce is the best company to work for"
val map = mutable.Map[Char, Int]()
s.toCharArray.zipWithIndex.foreach{
case (c, i) =>
val lower = c.toLower
map.update(lower, map.getOrElse(lower, 0) + 1)
}
println(s.toCharArray.find(c => map(c.toLower) == 1))
}
Scala solution:
def main(strings: Array[String]) = {
val s = "Salesforce is the best company to work for"
val map = mutable.Map[Char, Int]()
s.toCharArray.zipWithIndex.foreach{
case (c, i) =>
val lower = c.toLower
map.update(lower, map.getOrElse(lower, 0) + 1)
}
println(s.toCharArray.find(c => map(c.toLower) == 1))
}
public class FirstNonRepeatedCharacter {
public static void main(String[] args) {
String str = "shhrravvannsk";
str = str.toLowerCase();
String nonRepeatedString = firstNonRepeatedCharacter(str, 0);
System.out.println(nonRepeatedString);
}
public static String firstNonRepeatedCharacter(String fullString, int characterIndex) {
if (fullString == null || characterIndex < 0 || characterIndex > fullString.length() - 1) {
return null;
}
String subStringToCheck = fullString.substring(0, characterIndex) + fullString.substring(characterIndex + 1, fullString.length());
if (!subStringToCheck.contains(fullString.charAt(characterIndex)+"")) {
return fullString.charAt(characterIndex)+"";
}
return firstNonRepeatedCharacter(fullString, ++characterIndex);
}
}
public class FirstNonRepeatedCharacter {
public static void main(String[] args) {
String str = "shhrravvannsk";
str = str.toLowerCase();
String nonRepeatedString = firstNonRepeatedCharacter(str, 0);
System.out.println(nonRepeatedString);
}
public static String firstNonRepeatedCharacter(String fullString, int characterIndex) {
if (fullString == null || characterIndex < 0 || characterIndex > fullString.length() - 1) {
return null;
}
String subStringToCheck = fullString.substring(0, characterIndex) + fullString.substring(characterIndex + 1, fullString.length());
if (!subStringToCheck.contains(fullString.charAt(characterIndex)+"")) {
return fullString.charAt(characterIndex)+"";
}
return firstNonRepeatedCharacter(fullString, ++characterIndex);
}
}
public class FirstNonRepeatedCharacter {
public static void main(String[] args) {
String str = "Salesforce is the best company to work for";
str = str.toLowerCase();
String nonRepeatedString = firstNonRepeatedCharacter(str, 0);
System.out.println(nonRepeatedString);
}
public static String firstNonRepeatedCharacter(String fullString, int characterIndex) {
if (fullString == null || characterIndex < 0 || characterIndex > fullString.length() - 1) {
return null;
}
String subStringToCheck = fullString.substring(0, characterIndex) + fullString.substring(characterIndex + 1, fullString.length());
if (!subStringToCheck.contains(fullString.charAt(characterIndex)+"")) {
return fullString.charAt(characterIndex)+"";
}
return firstNonRepeatedCharacter(fullString, ++characterIndex);
}
}
An answer that uses LinkedHashMap (to maintain insertion order). Overall O(n) time
public static Character firstNonRepeating(String s)
{
if(s == null || s.isEmpty()) { throw new IllegalArgumentException();}
if(s.length() == 1) { return s.charAt(0);}
//strip white space
s = s.replace(" ", "");
s = s.toLowerCase();
char[] split = s.toCharArray();
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for(char c : split)
{
if(map.containsKey(c))
map.put(c, map.get(c) + 1);
else
map.put(c, 1);
}
for(Entry<Character,Integer> entry : map.entrySet())
{
if(entry.getValue()==1)
return entry.getKey();
}
return null;
}
I have a question.
Why do I get l with your solution?
Should we get i?
I thought the question is first non-repeatable character for a non-repeatable word in the string. Is it the first non-repeatable character? And, that is why your solution return l. However, the example is shown I as a solution.
Thank you for posting the solution.
O(n), PHP language
function L($str, $position = 1){
$a = str_split(strtolower(str_replace(' ', '', $str)));
for($i = 0, $b = array(); $i < sizeof($a); $i++){
if(!isset($b[$a[$i]])){
$b[$a[$i]] = 0;
}
$b[$a[$i]]++;
}
return array_search($position, $b);
}
echo L('Salesforce is the best company to work for');
loop through the string from back
make an array a[26], where a[0]= count of 'a' and a[25]=count of 'z'
make a temp(find) char variable
if the char is in a[], increment count
if the char is not in a[](a[i]==0), increment count, put it into find
after the end of loop, the value of find is the 1st non-repeated char
char findNonRepeated(string str)
{
int count[27]={0,0,0,0,0,0,0,0,0,0,0....27 times};
char find;
int temp;
for(string::reverse_iterator i=str.rbegin();i!=str.rend(),i++)
{
temp = *i-'a';
if (!(temp>=0 && temp<=25 ))
{
temp = *i-'A';
if (!(temp>=0 && temp<=25 ))
temp=26;//blanc space
}
.if(a[temp]++==0)
find= *it;
}
return find;
}
Initialize an array A[26] with value -1
input_string = input_string.toupper()
for (i=0; i<len(input_string); i++) {
ch = input_string[i] - 'A'
if (A[ch] == -1) {
A[ch] = i
} else if (A[ch] > -1) {
A[ch] = -2;
}
}
min = 1000000
index = -1
for (i=0; i<26; i++) {
if (A[i] >= 0 and A[i] < min) {
min = A[i]
index = i
}
}
print ch(index)+65
s1 = "Salesforce is the best company to work for"
def findFirstNonRepeated(s1):
char_freq = dict()
ranking = {}
for idx,i in enumerate(s1.lower()):
char_freq[i] = char_freq.get(i,0)+1
ranking[i]=idx
#get all non repeating char
score=[ (ranking[k],k) for (k,v) in char_freq.items() if v==1]
print "First non repeating: ", sorted(score,reverse=True)[-1]
First non repeating: (2, 'l')
Python solution
{{
s1 = "Salesforce is the best company to work for"
def findFirstNonRepeated(s1):
char_freq = dict()
ranking = {}
for idx,i in enumerate(s1.lower()):
char_freq[i] = char_freq.get(i,0)+1
ranking[i]=idx
#get all non repeating char
score=[ (ranking[k],k) for (k,v) in char_freq.items() if v==1]
print "First non repeating: ", sorted(score,reverse=True)[-1]
First non repeating: (2, 'l')
}}
Python
s1 = "Salesforce is the best company to work for"
def findFirstNonRepeated(s1):
char_freq = dict()
ranking = {}
for idx,i in enumerate(s1.lower()):
char_freq[i] = char_freq.get(i,0)+1
ranking[i]=idx
#get all non repeating char
score=[ (ranking[k],k) for (k,v) in char_freq.items() if v==1]
print "First non repeating: ", sorted(score,reverse=True)[-1]
First non repeating: (2, 'l')
public static char firstNonRepeatedChar(String str) {
// A good question to ask is what Space is the first non repeated char. Do we consider
// it or not.
if (str.length() == 0 || str == null) {
return ' '; // Depending what interviewer want in this case.
}
// Depending on whether interviewer want take in account UniCode. I am not considering it
// and I am just using 256 ASCII char
int[] charArr = new int[256];
// Question for Interviewer whether we are treating lower and upper case same or not. I am
// treating it same.
String str1 = str.toLowerCase();
for (int i = 0; i < str1.length(); i++) {
int val = (int) str1.charAt(i);
charArr[val]++;
}
for (int i = 0; i < str1.length(); i++) {
int val = (int) str1.charAt(i);
if (charArr[val] == 1) {
return str1.charAt(i);
}
}
return ' ';
}
include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char ceo[50];
int i,j,c,l;
gets(ceo);
l=strlen(ceo);
for(i=0;i<l;i++)
{
c=0;
for(j=0;j<l;j++)
{
if(j!=i)
{
if(ceo[i]==ceo[j])
{
c++;
}
}
}
if(c==0)
break;
}
if(c==0)
printf("%c",ceo[i]);
else
printf("All letters in the string are repeated");
getch();
}
public void firstSingleChar(String word) {
word = word.toLowerCase();
char c[] = word.toCharArray();
for (int i = 0; i < c.length; i++) {
System.out.println(word.lastIndexOf(c[i]) + ":" + word.indexOf(c[i]));
if (word.lastIndexOf(c[i]) == word.indexOf(c[i])) {
System.out.println(c[i]);
break;
}
}
}
public void firstSingleChar(String word) {
word = word.toLowerCase();
char c[] = word.toCharArray();
for (int i = 0; i < c.length; i++) {
System.out.println(word.lastIndexOf(c[i]) + ":" + word.indexOf(c[i]));
if (word.lastIndexOf(c[i]) == word.indexOf(c[i])) {
System.out.println(c[i]);
break;
}
}
}
public class Main {
public static void main(String[] args) {
String s = "Salesforce is the best company to work for";
s = s.toLowerCase();
int ht[] = new int[127];
LinkedList<Character> list = new LinkedList<Character>();
for (int i=0; i < s.length(); i++) {
final char ch = s.charAt(i);
list.add(i, ch);
if (ht[ch] != -1) {
ht[ch]++;
if (ht[ch] > 1) {
ht[ch] = -1;
}
}
}
for (Character c : list) {
if (ht[c.charValue()] != -1 && ht[c.charValue()] == 1) {
System.out.println("First non-repeat character: " + c);
break;
}
}
}
/* (non-Java-doc)
* @see java.lang.Object#Object()
*/
public Main() {
super();
}
String findFirstNonRepeatChar(String input) {
if(input == null || input.length() ==0)
return "";
char[] inputA = input.toLowerCase().toCharArray();
Map<Character, Integer> map = new HashMap<>();
for(char ch : inputA) {
if(!map.containsKey(ch))
map.put(ch, 1);
else
map.put(ch, map.get(ch) + 1);
}
for(char ch : inputA) {
if(map.get(ch) == 1) {
return String.valueOf(ch);
}
}
return "";
}
class MyOwnException extends Exception {
public MyOwnException(String str) {
super(str);
}
}
class NonRepeatavieChar {
public static char getNonRepeatativeChar(String str1) throws MyOwnException {
if (str1.length() == 0 || str1 == null) {
throw new MyOwnException("Given String is not valid");
}
int[] chArr = new int[26];
String str = str1.toLowerCase();
for (int i = 0; i < str.length(); i++) {
int temp = str.charAt(i) - 'a';
if (temp >= 0 && temp < 26) {
chArr[temp]++;
}
}
for (int i = 0; i < str.length(); i++) {
int temp = str.charAt(i) - 'a';
if (temp >= 0 && temp < 26) {
if (chArr[temp] == 1) {
return str.charAt(i);
}
}
}
return '\0';
}
}
public class FirstNonRepeatativeChar {
public static void main(String[] args) throws MyOwnException {
System.out.println(NonRepeatavieChar
.getNonRepeatativeChar("Salesforce is the best company to work for"));
}
}
public class nonRepeated {
private Map<Character, Boolean> charMap;
private Set<Character> dupeSet;
private Set<Character> nonDupeSet;
private char[] cArray;
private String s;
public nonRepeated() {
dupeSet = new LinkedHashSet<>();
nonDupeSet = new LinkedHashSet<>();
charMap = new LinkedHashMap<>();
}
public Integer arraySol(String input){
int[] arr = new int[26];
int index = 0;
cArray = input.toLowerCase().toCharArray();
for(char c: cArray){
index = c-'a';
arr[index] = ++arr[index];
}
for(int i: arr){
if(i == 1)
return i;
}
return null;
}
private Character getFirstEntry() {
Iterator it = charMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry) it.next();
if (!(boolean) pair.getValue()) {
return (char) pair.getKey();
}
it.remove(); // avoids a ConcurrentModificationException
}
return null;
}
public char firstChar(String input) {
cArray = input.toLowerCase().toCharArray();
for (char c : cArray) {
if (!charMap.containsKey(c)) {
charMap.put(c, false);
} else {
charMap.put(c, true);
}
}
return getFirstEntry();
}
public static void main(String[] args){
nonRepeated nR = new nonRepeated();
System.out.println("First non repeated character: " +nR.firstChar("GeeksForGeeks"));
System.out.println("First non repeated index: " +nR.arraySol("GeeksForGeeks"));
}
public class nonRepeated {
private Map<Character, Boolean> charMap;
private Set<Character> dupeSet;
private Set<Character> nonDupeSet;
private char[] cArray;
private String s;
public nonRepeated() {
dupeSet = new LinkedHashSet<>();
nonDupeSet = new LinkedHashSet<>();
charMap = new LinkedHashMap<>();
}
public Integer arraySol(String input){
int[] arr = new int[26];
int index = 0;
cArray = input.toLowerCase().toCharArray();
for(char c: cArray){
index = c-'a';
arr[index] = ++arr[index];
}
for(int i: arr){
if(i == 1)
return i;
}
return null;
}
private Character getFirstEntry() {
Iterator it = charMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry) it.next();
if (!(boolean) pair.getValue()) {
return (char) pair.getKey();
}
it.remove(); // avoids a ConcurrentModificationException
}
return null;
}
public char firstChar(String input) {
cArray = input.toLowerCase().toCharArray();
for (char c : cArray) {
if (!charMap.containsKey(c)) {
charMap.put(c, false);
} else {
charMap.put(c, true);
}
}
return getFirstEntry();
}
public static void main(String[] args){
nonRepeated nR = new nonRepeated();
System.out.println("First non repeated character: " +nR.firstChar("GeeksForGeeks"));
System.out.println("First non repeated index: " +nR.arraySol("GeeksForGeeks"));
}
def repeated(word):
s = list(word.lower())
dct={}
position=[]
length=len(s)
for i in range(int(length)):
if dct.has_key(s[i]):
dct[s[i]] +=1
else:
dct[s[i]]=1
print dct
for i in dct:
if dct[i] == 1:
position.append(s.index(i))
position.sort()
print position
return s[position[0]]
print repeated("Salesforce is the best company")
def repeated(word):
s = list(word.lower())
dct={}
position=[]
length=len(s)
for i in range(int(length)):
if dct.has_key(s[i]):
dct[s[i]] +=1
else:
dct[s[i]]=1
print dct
for i in dct:
if dct[i] == 1:
position.append(s.index(i))
position.sort()
print position
return s[position[0]]
print repeated("Salesforce is the best company")
def repeated(word):
s = list(word.lower())
dct={}
position=[]
length=len(s)
for i in range(int(length)):
if dct.has_key(s[i]):
dct[s[i]] +=1
else:
dct[s[i]]=1
print dct
for i in dct:
if dct[i] == 1:
position.append(s.index(i))
position.sort()
print position
return s[position[0]]
print repeated("Salesforce is the best company")
def repeated(word):
s = list(word.lower())
dct={}
position=[]
length=len(s)
for i in range(int(length)):
if dct.has_key(s[i]):
dct[s[i]] +=1
else:
dct[s[i]]=1
print dct
for i in dct:
if dct[i] == 1:
position.append(s.index(i))
position.sort()
print position
return s[position[0]]
print repeated("Salesforce is the best company")
def repeated(word):
s = list(word.lower())
dct={}
position=[]
length=len(s)
for i in range(int(length)):
if dct.has_key(s[i]):
dct[s[i]] +=1
else:
dct[s[i]]=1
print dct
for i in dct:
if dct[i] == 1:
position.append(s.index(i))
position.sort()
print position
return s[position[0]]
print repeated("Salesforce is the best company")
/**
* This method finds the first non repeated character in a given string.Assuming case-insensitive
*
* @param string Input string
* @return Character first non repeated character
*/
public char getFristNonRepeatedChar(String string){
//Initialising to default value
char output = '\u0001';
//Validating for null and empty string
if(string == null || string.isEmpty())
return output;
//Getting char array form given string
char [] chars = string.toCharArray();
HashMap<Character,Integer> countMap = new HashMap<>();
HashMap<Character,Integer> singleCharMap = new HashMap<>();
for(char c : chars){
c = Character.toLowerCase(c);
//Checking if its an alphabet
if('a' <= c && c <= 'z'){
//If it is already present in count map that means its not unique
if(countMap.containsKey(c)){
singleCharMap.remove(c);
}else{
//If its not in count map then insert into count map and single char map
countMap.put(c,0);
singleCharMap.put(c,0);
}
}
}
//No entry in single char map
if(singleCharMap.size()==0)
return output;
//iterate on char array and break on first hit
for(char c : chars){
if(singleCharMap.containsKey(c)){
output = c;
break;
}
}
return output;
}
/**
* This method finds the first non repeated character in a given string.Assuming case-insensitive
*
* @param string Input string
* @return Character first non repeated character
*/
public char getFristNonRepeatedChar(String string){
//Initialising to default value
char output = '\u0001';
//Validating for null and empty string
if(string == null || string.isEmpty())
return output;
//Getting char array form given string
char [] chars = string.toCharArray();
HashMap<Character,Integer> countMap = new HashMap<>();
HashMap<Character,Integer> singleCharMap = new HashMap<>();
for(char c : chars){
c = Character.toLowerCase(c);
//Checking if its an alphabet
if('a' <= c && c <= 'z'){
//If it is already present in count map that means its not unique
if(countMap.containsKey(c)){
singleCharMap.remove(c);
}else{
//If its not in count map then insert into count map and single char map
countMap.put(c,0);
singleCharMap.put(c,0);
}
}
}
//No entry in single char map
if(singleCharMap.size()==0)
return output;
//iterate on char array and break on first hit
for(char c : chars){
if(singleCharMap.containsKey(c)){
output = c;
break;
}
}
return output;
}
/**
* This method finds the first non repeated character in a given string.Assuming case-insensitive
*
* @param string Input string
* @return Character first non repeated character
*/
public char getFristNonRepeatedChar(String string){
//Initialising to default value
char output = '\u0001';
//Validating for null and empty string
if(string == null || string.isEmpty())
return output;
//Getting char array form given string
char [] chars = string.toCharArray();
HashMap<Character,Integer> countMap = new HashMap<>();
HashMap<Character,Integer> singleCharMap = new HashMap<>();
for(char c : chars){
c = Character.toLowerCase(c);
//Checking if its an alphabet
if('a' <= c && c <= 'z'){
//If it is already present in count map that means its not unique
if(countMap.containsKey(c)){
singleCharMap.remove(c);
}else{
//If its not in count map then insert into count map and single char map
countMap.put(c,0);
singleCharMap.put(c,0);
}
}
}
//No entry in single char map
if(singleCharMap.size()==0)
return output;
//iterate on char array and break on first hit
for(char c : chars){
if(singleCharMap.containsKey(c)){
output = c;
break;
}
}
return output;
}
/**
* This method finds the first non repeated character in a given string.Assuming case-insensitive
*
* @param string Input string
* @return Character first non repeated character
*/
public char getFristNonRepeatedChar(String string){
//Initialising to default value
char output = '\u0001';
//Validating for null and empty string
if(string == null || string.isEmpty())
return output;
//Getting char array form given string
char [] chars = string.toCharArray();
HashMap<Character,Integer> countMap = new HashMap<>();
HashMap<Character,Integer> singleCharMap = new HashMap<>();
for(char c : chars){
c = Character.toLowerCase(c);
//Checking if its an alphabet
if('a' <= c && c <= 'z'){
//If it is already present in count map that means its not unique
if(countMap.containsKey(c)){
singleCharMap.remove(c);
}else{
//If its not in count map then insert into count map and single char map
countMap.put(c,0);
singleCharMap.put(c,0);
}
}
}
//No entry in single char map
if(singleCharMap.size()==0)
return output;
//iterate on char array and break on first hit
for(char c : chars){
if(singleCharMap.containsKey(c)){
output = c;
break;
}
}
return output;
}
There are 3 options to do this :
1) Scan array 1 char at a time and compare with remaining chars. If no duplicate found return, you have just found the first non-repeated char. Time complexity : o(n*n)
2) Sort the array. Scan array by comparing adjacent element. If you find element which is different than its adjacent element, return it. Time complexity : o(n log n) + o(n)
3) Use a hashMap of character and its count. Scan array to populate this map. Finally Scan array and check the count on each char from this hashMap. If it is 1, return that element. Time complexity : o(n) but needs additional o(n) space for hash map.
use a queue
import java.lang.*;
import java.util.*;
public class FirstNonRepeatingCharacter
{
public static void main(String[] args)
{
Queue<Character> charQueue = new LinkedList<Character>();
String input = "Salesforce is the best company to work for";
Character first = Character.toLowerCase(input.charAt(0));
charQueue.add(first);
for(int i = 1; i < input.length(); i++){
Character currentChar = Character.toLowerCase(input.charAt(i));
if(currentChar.equals(charQueue.peek())){
charQueue.remove();
}else{
charQueue.add(currentChar);
}
}
System.out.println(charQueue.remove());
}
}
Use a queue
import java.lang.*;
import java.util.*;
public class FirstNonRepeatingCharacter
{
public static void main(String[] args)
{
Queue<Character> charQueue = new LinkedList<Character>();
String input = "Salesforce is the best company to work for";
Character first = Character.toLowerCase(input.charAt(0));
charQueue.add(first);
for(int i = 1; i < input.length(); i++){
Character currentChar = Character.toLowerCase(input.charAt(i));
if(currentChar.equals(charQueue.peek())){
charQueue.remove();
}else{
charQueue.add(currentChar);
}
}
System.out.println(charQueue.remove());
}
}
C# Solution with Dictionary and Linq
public static char FindFirstNonRepeatedCharWithExtraSpace(string input)
{
if (string.IsNullOrEmpty(input))
{
return char.MinValue;
}
var chars = new Dictionary<char, int>();
for (int i = 0; i < input.Length; i++)
{
if (input[i] == ' ')
{
continue;
}
var key = char.ToLower(input[i]);
if (chars.ContainsKey(key))
{
chars[key]++;
}
else
{
chars.Add(key, 1);
}
}
Console.WriteLine("FindFirstNonRepeatedChar - " + chars.FirstOrDefault(k => k.Value == 1).Key);
return chars.FirstOrDefault(k => k.Value == 1).Key;
}
#include<string>
#include<set>
#include<iostream>
int main()
{
std::string input="Salesforce is the best company to work for";
std::set<char> counter;
char output;
for (auto it = std::rbegin(input); it != std::rend(input); ++it)
{
char value = std::tolower(*it);
if( counter.find(value) == std::end(counter))
{
output=value;
counter.insert(value);
}
}
std::cout << output << "\n";
}
Correct me, if i am wrong. This does not identify anything,neither first nor the last character.
if String = "aabccddeea", your code gives 'e' as the output (neither first, nor last)
public void minCharCounter(String word) {
LinkedHashMap<Character, Integer> charcount = new LinkedHashMap<>();
for (int i = 0; i < word.length(); i++) {
if (charcount.get(word.charAt(i)) == null) {
charcount.put(word.charAt(i), 1);
} else {
charcount.put(word.charAt(i), charcount.get(word.charAt(i)) + 1);
}
}
int min = Integer.MAX_VALUE; char min_char = (char) 256;
for (Map.Entry<Character, Integer> count : charcount.entrySet()) {
if(count.getValue() < min) {
min = count.getValue();
min_char = count.getKey();
}
}
System.out.println(min_char + ":" + min);
}
public static void main(String[] args) {
- Anonymous January 28, 2016String s1 = "Salesforce is the best company to work for";
char[] chars = s1.toLowerCase().toCharArray();
int count;
for (int i = 0; i < chars.length; i++) {
count = 0;
for (int j = i + 1; j < chars.length; j++) {
if (chars[i] == chars[j]) {
count++;
break;
}
}
if (count == 0) {
System.out.println(chars[i]);
break;
}
}
}