Amazon Interview Question SDETs
Country: United States
//Find first non-repeating character by iterating through the length of the string only once and by using constant space
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonRepeating {
public static void main(String[] args) {
String a = "abbaraSubbara";
Map<Character, Integer> hmap = new LinkedHashMap<>();
for (char c : a.toCharArray()) {
if (hmap.get(c) != null) {
System.out.println(c);
int freq = hmap.get(c).intValue();
hmap.put(c, freq + 1);
} else {
hmap.put(c, 1);
}
}
System.out.println(hmap);
System.out.println(hmap.entrySet().stream().filter(e -> e.getValue() == 1).findFirst().get());
}
}
Here is a clunky brute force JavaScript solution using a nested for loop. Perhaps there is a greedy algorithm approach?
function getFirstNonRepeatingChar(str){
var charArr = [];
for(var i=0; i<str.length; i++){
if(charArr.length == 0){
charArr.push(str.charAt(i));
} else {
var isRepeated = false;
for(var j=0; j<charArr.length; j++){
if(charArr[j] === str.charAt(i)){
charArr.splice(j, 1);
isRepeated = true;
break;
}
}
if(!isRepeated){
charArr.push(str.charAt(i));
}
}
}
if(charArr.length == 0){
return '';
} else {
return charArr[0];
}
}
// ZoomBA
def first_non_repeat(string){
// use sorted dictionary to keep insertion order
d = fold ( string.value , sdict() ) ->{
if ( $.item @ $.partial ){ $.partial[ $.item] += 1
} else { $.partial[ $.item] = 1 }
$.partial
} // this is now an multi set : search for first entry with count 1
r = find ( d ) :: { $.item.value == 1 }
// Option Monad, either exists or does not
println ( r.nil ? 'Nothing' : r.value.key )
}
first_non_repeat ( "aaaabbbbacccdbbbbeeeg" )
func first_non_repeat(str string) string {
charsCount := map[rune]int{}
charsSingle := map[rune]bool{}
charsPos := map[rune]int{}
pos := 0
for _, r := range str {
charsCount[r]++
if charsCount[r] == 1 {
charsSingle[r] = true
charsPos[r] = pos
} else {
delete(charsSingle, r)
}
pos++
}
minPos := math.MaxInt64
for r, _ := range charsSingle {
if charsPos[r] < minPos {
minPos = charsPos[r]
}
}
return str[minPos:minPos+1]
}
package smapleQuestionsAlgorithms;
public class FirstNonRepeating {
public static char firstNonRepeating(int[] arr, String s){
for(int i=0;i<s.length();i++){
int index=(int)s.charAt(i);
if(arr[index]==0){
arr[index]=i;//we are encountering character for first time
}else{
arr[index]=-1;//means char is repeated.
}
}
int min=Integer.MAX_VALUE;
char first = ' ';
for(int i=0;i<arr.length;i++){
if(arr[i]<min && arr[i]>0){
min=arr[i];
first=(char) i;
}
}
return first;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr=new int[128];//lets assume string is 128 ASCII char set
System.out.println(firstNonRepeating(arr, "abcdefedcab"));
}
}
import java.io.*;
import java.util.*;
class amazon {
public static void main(String[] args)throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
int positionOfCharFromStarting=s.indexOf(c);
int positionOfCharFromEnding=s.lastIndexOf(c);
if(positionOfCharFromStarting==positionOfCharFromEnding){
System.out.println(c);
break;
}
}
}
}
import java.io.*;
import java.util.*;
class amazon {
public static void main(String[] args)throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
int positionOfCharFromStarting=s.indexOf(c);
int positionOfCharFromEnding=s.lastIndexOf(c);
if(positionOfCharFromStarting==positionOfCharFromEnding){
System.out.println(c);
break;
}
}
}
}
import java.io.*;
import java.util.*;
class amazon {
public static void main(String[] args)throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
int positionOfCharFromStarting=s.indexOf(c);
int positionOfCharFromEnding=s.lastIndexOf(c);
if(positionOfCharFromStarting==positionOfCharFromEnding){
System.out.println(c);
break;
}
}
}
}
Can also be implemented with a Dictionary and a HashSet
public char FindFirstNoRepeating(string s)
{
int[] arr = new int[26];
for(int i=0; i < s.Length; i++)
{
int index = Math.Abs('a' - s[i]);
if (arr[index] == -1)
continue;
if (arr[index] > 0)
arr[index] = -1;
else
arr[index] = i + 1;
}
int min = int.MaxValue;
for(int i=0; i < arr.Length; i++)
{
if (arr[i] > 0)
min = Math.Min(min, arr[i]);
}
return s[min - 1];
}
My version of solution:
public class FirstNonRepeatable {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
String s = scanner.nextLine();
System.out.println(firstNonRepeatable(s));
}
}
public static Character firstNonRepeatable(String s) {
if (s.length() == 0) {
return null;
}
Set<Character> nonRepeatable = new HashSet<>();
LinkedList<Character> distinct = new LinkedList<>();
Set<Character> repeatable = new HashSet<>();
nonRepeatable.add(s.charAt(0));
distinct.add(s.charAt(0));
char charToCheck;
for (int i = 1; i < s.length(); i++) {
charToCheck = s.charAt(i);
if (!repeatable.contains(charToCheck)) {
if (nonRepeatable.contains(charToCheck)) {
nonRepeatable.remove(charToCheck);
repeatable.add(charToCheck);
}
else {
nonRepeatable.add(charToCheck);
distinct.add(charToCheck);
}
}
}
if (nonRepeatable.isEmpty()) {
return null;
}
for (char c: distinct) {
if (nonRepeatable.contains(c)) {
return c;
}
}
return null;
}
}
My version is using recursion
static void isOnly(String text, int position){
boolean isRepeat = false;
if(position < text.length()){
char a=text.charAt(position);
for(int i=0; i< text.length(); i++){
if(i!=position){
if(text.charAt(i) == a){
isRepeat = true;
isOnly(text,++position);
}
}
}
if(!isRepeat){
System.out.println(a);
}
}
}
package practice;
import java.util.*;
public class nonrepeatingcharcter {
public static void main(String[] args){
System.out.println(caluclateparantheses("abbcdefgha"));
}
public static String caluclateparantheses(String s){
if(s.length() == 0)return "empty string";
HashMap<String,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
String Current = s.charAt(i) + "";
if(map.containsKey(Current)){
return Current;
}else{
map.put(Current, 1);
}
}
return "no character is repeating";
}
}
package practice;
import java.util.*;
public class nonrepeatingcharcter {
public static void main(String[] args){
System.out.println(caluclateparantheses("abbcdefgha"));
}
public static String caluclateparantheses(String s){
if(s.length() == 0)return "empty string";
HashMap<String,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
String Current = s.charAt(i) + "";
if(map.containsKey(Current)){
return Current;
}else{
map.put(Current, 1);
}
}
return "no character is repeating";
}
}
public static String caluclateparantheses(String s){
if(s.length() == 0)return "empty string";
HashMap<String,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
String Current = s.charAt(i) + "";
if(map.containsKey(Current)){
return Current;
}
}else{
map.put(Current, 1);
}
}
return "no character is repeating";
}
}
package practice;
import java.util.*;
import java.util.Map.Entry;
public class nonrepeatingcharcter_regex {
public static void main(String[] args){
System.out.println(firstNonRepeatingCharWithRegex("aaabbccddeefffggq"));
}
public static char firstNonRepeatingCharWithRegex(String word) {
for (int i = 0; i < word.length(); i++) {
char letter = word.charAt(i);
if (!word.matches("(.*?)" + letter + "(.*?)" + letter + "(.*?)")) {
return letter;
}
}
return ' ';
}
}
package practice;
import java.util.*;
import java.util.Map.Entry;
public class nonrepeatingcharcter {
public static void main(String[] args){
System.out.println(caluclateparantheses("aabbccddeeffgghh"));
}
public static String caluclateparantheses(String s){
if(s.length() == 0)return "empty string";
HashMap<String,Integer> map = new LinkedHashMap<>();
for(int i=0;i<s.length();i++){
String Current = s.charAt(i) + "";
if(map.containsKey(Current)){
map.put(Current,map.get(Current).intValue()+1);
}else{
map.put(Current, 1);
}
}
for (Entry<String, Integer> entry : map.entrySet()) {
if(entry.getValue() > 1)continue;
else return entry.getKey();
}
return "no character is repeating";
}
}
public class FirstNonrepeating {
public static void main(String[] args) {
String str = "TestOfTest";
boolean nonrepeatflag = false;
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for(int i=0;i < str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
} else {
map.put(c, 1);
}
}
for (Map.Entry<Character,Integer> entry : map.entrySet()){
if (entry.getValue() == 1){
System.out.println(entry.getKey());
nonrepeatflag = true;
break;
}
}
if(nonrepeatflag==false){
System.out.println("No non repeating character");
}
}
}
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonrepeating {
public static void main(String[] args) {
String str = "TestOfTest";
boolean nonrepeatflag = false;
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for(int i=0;i < str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
} else {
map.put(c, 1);
}}
for (Map.Entry<Character,Integer> entry : map.entrySet()){
if (entry.getValue() == 1){
System.out.println(entry.getKey());
nonrepeatflag = true;
break;
}}
if(nonrepeatflag==false){
System.out.println("No non repeating character");
}}}
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonrepeating {
public static void main(String[] args) {
String str = "TestOfTest";
boolean nonrepeatflag = false;
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for(int i=0;i < str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
} else {
map.put(c, 1);
}
}
for (Map.Entry<Character,Integer> entry : map.entrySet()){
if (entry.getValue() == 1){
System.out.println(entry.getKey());
nonrepeatflag = true;
break;
}
}
if(nonrepeatflag==false){
System.out.println("No non repeating character");
}
}
}
public class NonRepeatChar {
public static void main(String args[]) {
String value = "abbccddefghijae";
List<Character> characterList = new ArrayList<>();
for (int i = 0; i < value.length(); i++) {
if (characterList.contains(value.charAt(i))) {
characterList.remove((Character)value.charAt(i));
} else {
characterList.add(value.charAt(i));
}
}
System.out.println(characterList.get(0));
}
}
Perhaps I don't get the complexity of a problem or I don't understand the actual question but my solution would be the following. Please correct if I am wrong.
public static char FirstNonRepeatingChar(string str)
{
char result = ' ';
if (string.IsNullOrEmpty(str))
{
return result;
}
else if (str.Length == 1)
{
return result;
}
for (int i = 1; i < str.Length; i++)
{
if (str[i] != str[0])
{
result = str[i];
}
}
return result;
}
Thanks.
The trick here is to know that the different characters size (256, for Java) is a constant value, so we can use an array containing the different characters without breaking the problem rules:
- libertythecoder November 02, 2016public char firstNonRepeated(String str){ Integer[] indexes = new int[256]; char[] chars = str.toCharArray(); for(int i = 0; i < str.length(); i++){ int index = Character.getNumericValue(chars[i]); if(count[index] == null) count[index] = i; else count[index] = -1; } char first = ‘’; int firstIndex = Integer.MAX_VALUE; for(i = 0; i < 256; i++){ if(count[i] != null && count[i] != -1 && count[i] < firstIndex){ first = (char) i; firstIndex = count[i]; } } return first; }