Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public static void main (String args[])
{
char returnedValue = repeatedCharacter("stqwbbertygfyaa");
if (returnedValue == '!')
{
System.out.println("String does not contain any duplicate values");
}
else
{
//we found the real character
System.out.println(returnedValue);
}
}
public static Character repeatedCharacter(String myString)
{
char prev = myString.charAt(0);
for(int i = 1 ; i < myString.length() ; i++)
{
if(prev == myString.charAt(i))
{
return myString.charAt(i);
}
prev = myString.charAt(i);
}
return '!';
}
The 'easiest' approach would be any type of associative array with the count as the value. This would be O(n) assuming your associative array is long enough to support the keys required for the string. Some data structures give you O(1) for put / get with 'high probability.'
By "first repeating..." I'm assuming you mean the first time a character repeats in the array.
So, if you have {a,b,d,b,e,e,a}
Your answer would be b, which repeats at index 3, not a which appears first at index 0 and again at 6.
In your associative array, you'll have
[ a=6, b=3,d=-1,e=5 ]
If you have a minimal array, you could traverse over that array, but you'll probably not have one. In most cases, you should traverse over the string again and the character with the lowest number for the value would be the answer. In this example, I used -1 to note that the character did not repeat.
In Java, use a HashSet. Constant insert and lookup (amortized), and unlike an array it's sparse which means the size doesn't depend on the theoretical size of the charset (which for unicode is a lot).
public Character find(String s) {
if (null == s) throw new IllegalArgumentException("Null input");
HashSet<Character> seenCharacters = new HashSet<>();
for (char c:s.toCharArray()) {
if (seenCharacters.contains(c)) return c;
seenCharacters.add(c);
}
return null;
}
fastest way to do is
create a boolean array of size 26. for each letter you find
public char findRepeatedChar(String str){
boolean flag[] = new flag[26];
for (int i = 0; str.length() ; i++){
char c = str.charAt(i);
int index =c - 'a';
if (flag[index]) {
return c;
}else{
flag[index] = true;
}
}
}
}
we can also try bitwise operator on integer (integer == 32 bits)
int test;
if( test & 1 >> (array[i]-'a'))
print duplicate
else
test = test + 1 >> (array[i]-'a')
import java.util.HashSet;
import java.util.Set;
/**
*
*This code assumes the small and capital letters as different elements
*Also it prints whitespace if that is repeating.
*Un-comment the commented part of the code to remove the above assumption.
*
*/
public class StringRepeatingCharTest {
public static void main(String[] args) {
String str = "thunderbird";
//str = str.toLowerCase();
//str = str.replaceAll(" ", "");
char[] strChars = str.toCharArray();
Set<Character> set = new HashSet<Character>();
boolean flag = true;
for(Character c : strChars){
flag = set.add(c);
if(!flag){
System.out.println("First repeating character is : " + c);
break;
}
}
}
}
import java.util.HashSet;
import java.util.Set;
/**
*
*This code assumes the small and capital letters as different elements
*Also it prints whitespace if that is repeating.
*Un-comment the commented part of the code to remove the above assumption.
*
*/
public class StringRepeatingCharTest {
public static void main(String[] args) {
String str = "I am working in Amazon";
//str = str.toLowerCase();
//str = str.replaceAll(" ", "");
Set<Character> set = new HashSet<Character>();
boolean flag = true;
for(int i=0;i<str.length();i++){
flag = set.add(str.charAt(i));
if(!flag){
System.out.println("First repeating character is : " + str.charAt(i));
break;
}
}
}
}
This can be solved in O(n) time. If we only consider ASCII characters array of 256 numbers is required.
Whenever a character is found its corresponding ASCII value index in array is changed to 1 to remember that this character is already seen. Whenever a new character comes in it is checked with its corresponding ASCII value index in array and if it is already seen then loop breaks.
Remeber this code treats upper and lower case letters differently.
char str[] = "tarun gupta";
int l = strlen(str);
int flag[256]={0};
for( i=0 ; i<l ; i++){
if ( flag[str[i]]!=0 ){
printf("The first repeating character is %c", str[i]);
break;
}
else{
flag[str[i]] = 1;
}
}
public class RepeatChar {
static String s = "abcdefa";
static int a[] = new int[65535];
static void findChar(){
for(int i=0; i < s.length(); i++){
if(++a[s.charAt(i)] == 2){
System.out.println(s.charAt(i));
System.exit(0);
}
}
System.out.println("No repetitions");
}
public static void main(String args[]){
if(s.length()==0)
System.out.println("Empty String");
else
findChar();
}
}
Saving it in a temporary DS(in this case, hashmap) and comparing against it for every new char.
private static String findFirstRepeatingChar(String str){
Map<String, Integer> hash= new HashMap<String, Integer>();
for (int i = 0; i < str.length(); i++) {
String temp = str.substring(i, i+1);
if(hash.containsKey(temp))
return temp;
hash.put(temp, 1);
}
return "NOT FOUND";
}
static void firstRepChar(String s){
char [] ch=s.toCharArray();
HashMap<Character, Integer> cMap=new HashMap<Character, Integer>();
int value=0;
for(char c:ch){
value=0;
if(cMap.containsKey(c)){
value=cMap.get(c);
}
value++;
cMap.put(c, value);
}
for(char c:ch){
if(cMap.get(c)>1){
System.out.print(c);
return;
}
}
}
There are several ways to do this, using Vectors, HashMaps, etc.
- Leandro Assad Martins October 22, 2013You can do it creating another String and checking if the next character is at the String.
The first occurrence that returns true, that is your first repeated character.