Amazon Interview Question
SDE-3sCountry: United States
Interview Type: Phone Interview
int findFirstUniqueIndex(const std::string &str)
{
std::unordered_map<char, int> hmap;
const int size = str.size();
for (int i = 0; i < size; ++i) // O(n)
{
if (hmap.find(str.at(i)) == hmap.end()){ // avg O(1) lookup
hmap[str.at(i)] = 1;
}
else{
hmap[str.at(i)]++;
}
}
for (int i = 0; i < size; ++i){ // O(n)
if (hmap[str.at(i)] == 1){
return i;
}
}
return -1;
}
TEST(String, FindFirstUnique_probe_a)
{
{
std::string str("abcdeadcb");
EXPECT_EQ(findFirstUniqueIndex<void>(str), 4);
}
{
std::string str("abcdabcd");
EXPECT_EQ(findFirstUniqueIndex<void>(str), -1);
}
}
It can be solved with time O(n) and memory O(n)
def find_unique_char(a):
for key, value in Counter(a).iteritems():
if value == 1:
return key
If it is a repeating string we can reduce the memory cost to O(1). If we use the first letter of the cycle and iterate from the end of the array the first non repeating letter must be the one that precedes the first letter of the cycle. This is not clear from the question also it is not clear if the cycle starts from the first letter or you have to find it.
def find_unique_char(a):
for x in xrange(len(a)-1, 1, -1):
if a[x] == a[0]:
return a[x-1]
return a[0]
public void getFirstNonRepeat(String str) {
HashMap<Character,Integer> hash = new HashMap<Character,Integer>();
int num = 1;
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(hash.containsKey(c) && hash.get(c) == 0){
num = 0;
}
hash.put(c,num++);
}
char ret = ' ';
int min = Integer.MAX_VALUE;
for(char c : hash.keySet()){
if(hash.get(c) != 0 && min > hash.get(c)){
min = hash.get(c);
ret = c;
}
}
System.out.print(ret);
}
java O(n) in both space and time.
import java.util.*;
/**
* Created by JuanMa on 5/18/2017.
*/
public class FirstNonRepeating {
public static void main(String[] args) {
char c = findFistNonRepeatingChar("hola hoy no hay lola");
System.out.println(c);
}
public static class CounterMap <K> {
private static final Integer ZERO = 0;
final private Map<K, Integer> counter;
public CounterMap(Map<K, Integer> counter) {
this.counter = counter;
}
public void increment(K key) {
Integer count = counter.putIfAbsent(key, ZERO);
counter.put(key, counter.get(key) + 1);
}
public Set<Map.Entry<K, Integer>> entrySet() {
return counter.entrySet();
}
}
public static char findFistNonRepeatingChar(String in) {
Integer one = 1;
CounterMap<Character> count = loadCounterMap(in);
return count.entrySet().stream()
.filter(es -> es.getValue().equals(one))
.map(es -> es.getKey())
.findFirst().get();
}
private static CounterMap<Character> loadCounterMap(String in) {
CounterMap<Character> count = new CounterMap<>(new LinkedHashMap<>());
for (char c : in.toCharArray()) {
count.increment(c);
}
return count;
}
}
import java.util.*;
/**
* Created by JuanMa on 5/18/2017.
*/
public class FirstNonRepeating {
public static void main(String[] args) {
char c = findFistNonRepeatingChar("hola hoy no hay lola");
System.out.println(c);
}
public static class CounterMap <K> {
private static final Integer ZERO = 0;
final private Map<K, Integer> counter;
public CounterMap(Map<K, Integer> counter) {
this.counter = counter;
}
public void increment(K key) {
Integer count = counter.putIfAbsent(key, ZERO);
counter.put(key, counter.get(key) + 1);
}
public Set<Map.Entry<K, Integer>> entrySet() {
return counter.entrySet();
}
}
public static char findFistNonRepeatingChar(String in) {
Integer one = 1;
CounterMap<Character> count = loadCounterMap(in);
return count.entrySet().stream()
.filter(es -> es.getValue().equals(one))
.map(es -> es.getKey())
.findFirst().get();
}
private static CounterMap<Character> loadCounterMap(String in) {
CounterMap<Character> count = new CounterMap<>(new LinkedHashMap<>());
for (char c : in.toCharArray()) {
count.increment(c);
}
return count;
}
}
public static char getFirstNonRecurringChar(String sample){
LinkedList<Character> sample_list = new LinkedList<Character>();
char arrayChar[] = sample.toCharArray();
for (char aChar : arrayChar)
{
sample_list.add(aChar); // autoboxing
}
Queue<Character> queue1 = new LinkedList<Character>();
sample_list.forEach(chr->{
if( queue1.contains(chr))
queue1.poll();
else queue1.add(chr);});
return 0;
}
public static char getFirstNonRecurringChar(String sample){
LinkedList<Character> sample_list = new LinkedList<Character>();
char arrayChar[] = sample.toCharArray();
for (char aChar : arrayChar)
{
sample_list.add(aChar); // autoboxing
}
Queue<Character> queue1 = new LinkedList<Character>();
sample_list.forEach(chr->{
if( queue1.contains(chr))
queue1.poll();
else queue1.add(chr);});
return 0;
}
public static char getFirstNonRecurringChar(String sample){
LinkedList<Character> sample_list = new LinkedList<Character>();
char arrayChar[] = sample.toCharArray();
for (char aChar : arrayChar)
{
sample_list.add(aChar); // autoboxing
}
Queue<Character> queue1 = new LinkedList<Character>();
sample_list.forEach(chr->{
if( queue1.contains(chr))
queue1.poll();
else queue1.add(chr);});
return 0;
}
#include <iostream>
using namespace std;
#include <unordered_map>
struct entry {
int count;
int index;
entry():count(0), index(0) {}
};
void find_non_repeating(string str) {
std::unordered_map<char, entry> m;
for(int i =0; i <str.length(); i++) {
entry &e = m[str[i]];
e.count++;
e.index = i;
}
int lowest = str.length();
for(std::unordered_map<char, entry>::iterator it = m.begin(); it != m.end(); ++it) {
if (it->second.count >1) {
continue;
}
if (it->second.index < lowest) {
lowest = it->second.index;
}
}
if (lowest < str.length()) {
cout << "Non repeating at index "<< lowest <<" and is " << str[lowest] <<"\n";
} else {
cout << "Not found\n";
}
}
int main() {
// your code goes here
string str("");
find_non_repeating(str);
return 0;
}
The other solution is to have an array of size 256. Initialized to -1. Iterated over the given string, and do a lookup into the array[str[i]] if its equal to -1, update to i; else change the ara[str[i]] to 255.
Iterate over the array[i]. and find the lowest index. such that index != -1.
str[index] is the characted at position index.
<?php
function getFirstNonRecurringChar($string)
{
$length = strlen($string);
for ($i = 0; $i < strlen($string); $i++) {
if ($i >= $length - 1 || strpos($string, $string[$i], $i + 1) === false) {
return $string[$i];
} else {
$string = str_replace($string[$i], '', $string);
$i--;
}
}
return null;
}
<?php
function getFirstNonRecurringChar($string)
{
$length = strlen($string);
for ($i = 0; $i < strlen($string); $i++) {
if ($i >= $length - 1 || strpos($string, $string[$i], $i + 1) === false) {
return $string[$i];
} else {
$string = str_replace($string[$i], '', $string);
$i--;
}
}
return null;
}
public char findFirstChar(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
for (int i=0; i<s.length(); i++) {
char key = s.charAt(i);
if (map.containsKey(key)) {
map.put(key,map.get(key)+1);
} else {
map.put(key,1);
}
for (int i=0; i<s.length(); i++) {
char key = s.charAt(i);
if (map.containsKey(key)) {
if (map.get(key)==1) {
return key;
}
}
}
return ' ';
}
}
public char GetNorRecurring(string data)
{
string result = "";
List<char> nonRepeating = new List<char>();
List<char> repeatCharacters = new List<char>();
int index = 0;
foreach (char c in data)
{
if (!nonRepeating.Contains(c))
{
nonRepeating.Add(c);
}
else
{
repeatCharacters.Add(c);
nonRepeating.Remove(c);
}
}
foreach (char c in nonRepeating)
{
if (index == 0 || data.IndexOf(c) < index)
{
index = data.IndexOf(c);
}
}
return data.ToCharArray().ElementAt(index);
}
public char GetNorRecurring(string data)
{
string result = "";
List<char> nonRepeating = new List<char>();
List<char> repeatCharacters = new List<char>();
int index = 0;
foreach (char c in data)
{
if (!nonRepeating.Contains(c))
{
nonRepeating.Add(c);
}
else
{
repeatCharacters.Add(c);
nonRepeating.Remove(c);
}
}
foreach (char c in nonRepeating)
{
if (index == 0 || data.IndexOf(c) < index)
{
index = data.IndexOf(c);
}
}
return data.ToCharArray().ElementAt(index);
}
I think the first non-repeating char in your example is "d" and not "e".
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
}
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
}
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
}
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
}
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
public static Character firstnonrepeating(String in) {
Character c = null;
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i < in.length(); i++) {
c = in.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
System.out.println(map);
for(int i=0; i < map.size(); i++) {
char c1 = in.charAt(i);
if (map.get(c1) == 1 )
return c1;
}
return null;
}
There is no point of scanning the input string again after it was scanned first time to create a HashMap to keep counter of characters. The input string can be very long and the first non-repeating character may be near the mid or end.
It's easier to have an Ordered map so that the order in which the characters appear is maintained in the map.
Once the ordered map is created, scan it to find the first non-repeating character (if it exists)
public static Character getFirstNonrepeatingChar(String s) {
Character nonRepeatingChar = null;
if (s == null) {
return nonRepeatingChar;
}
if (s.length() == 1) {
return s.charAt(0);
}
Map<Character, Integer> m = new LinkedHashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (m.containsKey(c)) {
m.put(c, m.get(c) + 1);
} else {
m.put(c, 1);
}
}
for (Character c : m.keySet()) {
if (m.get(c) == 1) {
nonRepeatingChar = c;
break;
}
}
return nonRepeatingChar;
}
The following can be a solution for the problem (Write your base cases first):
1. Declare a HashSet and a LinkedHashSet.
a. The purpose of the HashSet is to store characters in the String
b. The purpose of the LinkedHashSet is to maintain the unique characters in the String
and also maintain the order of insertion of unique characters
2. Write a loop starting from zero to the length of the String.
3. Check in the loop if the character is already in the HashSet, remove it from LinkedHashSet; otherwise, add the character to both HashSet and LinkedHashSet.
4. return call to LinkedHashSet iterator method and then next method in a chain.
Note: This algorithm will guarantee to return first unique character of the String.
Here is the Code:
import java.util.HashSet;
import java.util.LinkedHashSet;
public class NonRepeatingCharacter {
public static Character getNonRepeatingCharacter(String testString) throws Exception{
if(testString == null) throw new NullPointerException(); //First ask the Interviewer what to return for base cases
if(testString.isEmpty()) throw new Exception("String is empty"); //First ask the Interviewer what to return for base cases
if(testString.length() == 1) return new Character(testString.charAt(0)); //This is totally valid output, assuming single character as unique character in the String
HashSet<Character> characterSet = new HashSet<>();
LinkedHashSet<Character> uniqueCharacter = new LinkedHashSet<>();
for(int i = 0; i < testString.length(); i++)
{
Character charToAdd = new Character(testString.charAt(i));
if(characterSet.contains(charToAdd)){
uniqueCharacter.remove(charToAdd);
}
else{
characterSet.add(charToAdd);
uniqueCharacter.add(charToAdd);
}
}
return uniqueCharacter.iterator().next();
}
public static void main(String args[]) throws Exception{
String testString = "abcdeadcb";
System.out.println("Expected e, Actual "+ getNonRepeatingCharacter(testString));
testString = "abcdneadcb";
System.out.println("Expected n, Actual "+ getNonRepeatingCharacter(testString));
}
}
public static void main(String[] args) {
System.out.println(firstUniqueChar("abcdeabcd"));
}
private static char firstUniqueChar(String input) {
char[] inputArray = input.toCharArray();
Integer[] frequency = new Integer[26];
List<Character> inputList = new LinkedList<>();
for (char c : inputArray) {
if (frequency[positionOfChar(c)] == null) {
frequency[positionOfChar(c)] = 1;
} else {
frequency[positionOfChar(c)]++;
}
inputList.add(c);
}
for(char c : inputList){
if(frequency[positionOfChar(c)] == 1){
return c;
}
}
return ' ';
}
private static int positionOfChar(char c) {
return (c - 'a');
}
Non repeating characters mean the first occurance of that character is the same as the last occurance.
Space o(1),memory o(n)
In scala
def nonRepeatingChar(text:String):Char= {
val newText = text.filter(a => text.lastIndexOf(a) == text.indexOf(a))
newText.headOption.getOrElse(' ')
}
println(nonRepeatingChar("abcdeabc")) //> d
How about this C++ code:
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int firstNonRepeatingIndex(const string& s)
{
map <char, int> repeatCounts;
size_t index = string::npos;
for_each(s.begin(), s.end(), [&repeatCounts](char ch) {
repeatCounts[ch] ++;
});
auto ii = find_if(s.begin(), s.end(), [&repeatCounts](char ch) {
if (1 == repeatCounts[ch])
return true;
return false;
});
if (ii != s.end())
index = distance(s.begin(), ii);
return index;
}
int main ()
{
string s("abcdeabcd");
size_t idx = firstNonRepeatingIndex(s);
if (idx != string::npos)
cout << "First non-repating character is: " << s[idx] << endl;
else
cout << "No unique character(s) found." << endl;
return 0;
}
How about this C++ code:
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int firstNonRepeatingIndex(const string& s)
{
map <char, int> repeatCounts;
size_t index = string::npos;
for_each(s.begin(), s.end(), [&repeatCounts](char ch) {
repeatCounts[ch] ++;
});
auto ii = find_if(s.begin(), s.end(), [&repeatCounts](char ch) {
if (1 == repeatCounts[ch])
return true;
return false;
});
if (ii != s.end())
index = distance(s.begin(), ii);
return index;
}
int main ()
{
string s("abcdeabcd");
size_t idx = firstNonRepeatingIndex(s);
if (idx != string::npos)
cout << "First non-repating character is: " << s[idx] << endl;
else
cout << "No unique character(s) found." << endl;
return 0;
}
How about this C++ code:
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int firstNonRepeatingIndex(const string& s)
{
map <char, int> repeatCounts;
size_t index = string::npos;
for_each(s.begin(), s.end(), [&repeatCounts](char ch) {
repeatCounts[ch] ++;
});
auto ii = find_if(s.begin(), s.end(), [&repeatCounts](char ch) {
if (1 == repeatCounts[ch])
return true;
return false;
});
if (ii != s.end())
index = distance(s.begin(), ii);
return index;
}
int main ()
{
string s("abcdeabcd");
size_t idx = firstNonRepeatingIndex(s);
if (idx != string::npos)
cout << "First non-repating character is: " << s[idx] << endl;
else
cout << "No unique character(s) found." << endl;
return 0;
}
the first non repeating char in the example is here is 'd' and not 'e'
public class NonRepeatingCharFinder {
public static char findFirstNonRepeatingChar(char[] inputStringArray) {
for(int i = 0; i < inputStringArray.length-1; i ++) {
int spotCount = 0;
for(int j = i+1; j < inputStringArray.length; j++) {
if(inputStringArray[i] == inputStringArray[j]) {
spotCount++;
break;
}
}
if(spotCount==0){
return inputStringArray[i];
}
}
return '\0';
}
public static void main(String[] args) {
String inputString = "abcdeabc";
char[] inputStringArray = inputString.toCharArray();
char firstNonRepeatingChar = findFirstNonRepeatingChar(inputStringArray);
if(firstNonRepeatingChar != '\0'){
System.out.println("First Non Repeating Char is : " + firstNonRepeatingChar);
}
}
}
private static void findFirst(String s) {
char[] chr = s.toCharArray();
for(char c : chr) {
if(hm.containsKey(c)) {
hm.put(c, hm.get(c)+1);
}
else {
hm.put(c, 1);
}
}
// System.out.println(hm);
for(Entry<Character, Integer> entry : hm.entrySet()) {
int val = entry.getValue() - 1;
if(val == 0) {
System.out.println(entry.getKey());
break;
}
}
private static void findFirst(String s) {
char[] chr = s.toCharArray();
for(char c : chr) {
if(hm.containsKey(c)) {
hm.put(c, hm.get(c)+1);
}
else {
hm.put(c, 1);
}
}
// System.out.println(hm);
for(Entry<Character, Integer> entry : hm.entrySet()) {
int val = entry.getValue() - 1;
if(val == 0) {
System.out.println(entry.getKey());
break;
}
}
private static void findFirst(String s) {
char[] chr = s.toCharArray();
for(char c : chr) {
if(hm.containsKey(c)) {
hm.put(c, hm.get(c)+1);
}
else {
hm.put(c, 1);
}
}
// System.out.println(hm);
for(Entry<Character, Integer> entry : hm.entrySet()) {
int val = entry.getValue() - 1;
if(val == 0) {
System.out.println(entry.getKey());
break;
}
}
private static void findFirst(String s) {
char[] chr = s.toCharArray();
for(char c : chr) {
if(hm.containsKey(c)) {
hm.put(c, hm.get(c)+1);
}
else {
hm.put(c, 1);
}
}
// System.out.println(hm);
for(Entry<Character, Integer> entry : hm.entrySet()) {
int val = entry.getValue() - 1;
if(val == 0) {
System.out.println(entry.getKey());
break;
}
}
public class char_rep {
static char check(String s){
char b = 0;
if(s==null||s.length()==0)
return ' ';
else{
for(int i =0;i<s.length();i++){
char a1 =s.charAt(i);
for(int j =0;j<s.length();j++){
if(i==j){
continue;
}
else if ( a1==s.charAt(j)){
break;
}
else{
if(a1!=s.charAt(j)){
if(j==s.length()-1){
return a1;
}
} }
}
}
} return ' ';
}
public static void main(String[] args) {
String get="abegb";
char wer=check(get);
System.out.println(wer);
}
}
int main()
{
string inStr;
int iIndex = 0;
bool bArr[256] = {false};
cout<<"Enter the string"<<endl;
cin>>inStr;
char *p = new char[inStr.length()+1];
strcpy(p, inStr.c_str());
p[inStr.length()] = '\0';
cout<<"Copied string is "<<p<<endl;
for(;iIndex<inStr.length();iIndex++)
{
if(bArr[inStr[iIndex]] == false)
{
bArr[inStr[iIndex]] = true;
}
else
{
cout<<"The non repeating character found at "<<iIndex-1<<" and the character is "<<inStr[iIndex-1]<<endl;
break;
}
}
return 0;
}
Use LinkedHashMap to preserve the order of characters.
import java.io.*;
import java.util.*;
class GetFirstUniqueChar {
public static void main (String[] args) {
String str = "abcdeabc";
Map<Character,Integer> map = new LinkedHashMap<>();
for(int i=0 ; i<str.length(); i++) {
if(map.get(str.charAt(i)) != null) {
int num = map.get(str.charAt(i));
map.put(str.charAt(i),num+1);
}
else
map.put(str.charAt(i),1);
}
for(Map.Entry<Character,Integer> entry : map.entrySet()) {
if(entry.getValue() == 1) {
System.out.println(entry.getKey());
return;
}
}
}
}
from collections import defaultdict
def findFirstOccurrenceOfNonRepeatingCharacters(a):
dictA = defaultdict(list)
temp = 0
for chars in a:
dictA[chars].append(temp)
temp = temp + 1
# Now we will be checking the items whose list length is 1
firstUniqueElement = ''
firstUniqueElementIndex = 0
for key, value in dictA.items():
if len(value) == 1 :
firstUniqueElementIndex = value
firstUniqueElement = key
# Now we have index and value of atleast one element whose presence is unique , we can now use it to compare
for key , value in dictA.items():
if len(value) == 1:
if value < firstUniqueElementIndex:
firstUniqueElementIndex = value
firstUniqueElement = key
print firstUniqueElement
if __name__ == "__main__":
findFirstOccurrenceOfNonRepeatingCharacters("abababfeababab")
We can do it in O(n).
If input string is all lower case english alphabets then we can create a 1-D array
- King@Work May 24, 2017