Amazon Interview Question Software Engineer / Developers
0of 0 votesfirst non repeating character from a given string
Team: payments team
Country: India
Interview Type: In-Person
wondering why down voted. You should be nice enough to point the error if you down vote it. Or better still, post the question more appropriately!
How u will get the result by xoring all the character.
Try this one
abdcccbd
u will not get right character.
This is where a question is not clear to me ---
in a string aaaabccdddd - b is the first non-repeating character
in a string abaaaaaaabb - b isthe first non-repeating character.
The question was not quite clear. My solution assumes the above is the question.. you've to remember first and keep xoring with that.
you can just count the num of occurrences of each character. then
scan the first 26 characters of the arrray for value.
O(n), no temporary space.
Provided you're dealing with an English string. Have you considered a string in Chinese?
Have a map<char, int>. Have a timestamp value initialised to 0. Loop through the string, incrementing timestamp at each step. Assign value of current timestamp to map[string[i]]. Once done through the loop, you need a linear search for getting the minimum timestamp value, which is your answer. O(n) time, O(n) space.
public static char firtNonRepeatingCharCaseSensitive(char[] s) {
int[] counts = new int[256]; // uses buffer
for (char c : s) {
counts[c]++;
}
for (int i = 0; i < s.length; i++) {
if (counts[s[i]] == 1)
return s[i];
}
return Character.UNASSIGNED // anything that indicates no character found;
}
Complexity: O(n)
# include<stdio.h>
int main()
{
char str[10];
printf("\n enter the string:");
scanf("%s", str);
sort(str);
printf("\n sorted %s", str);
firstnonrepeat(str);
}
void sort(char *str)
{
int i,len,j;
char temp;
len=strlen(str);
for(i=0;i<len;i++)
{
for(j=i;j>0;j--)
{
if(str[j]<str[j-1])
{
temp=str[j-1];
str[j-1]=str[j];
str[j]=temp;
}
}
Maintain a HashMap that tracks if a character has been seen once, or more than once. Loop over the string once, and if the char has the seen once value in the hashmap then set its value to seen twice. Then loop through the string again and return the first character whose value in the hashmap is seen once.
import java.util.*;
class firstNonRepeated {
public static void main(String []args){
HashMap charHash = new HashMap();
int i, length;
char c;
Object seenOnce = new Object();
Object seenTwice = new Object();
if(args.length == 1){
String input = args[0];
length = input.length();
for(i=0;i<length;i++){
c = input.charAt(i);
Object o = charHash.get(c);
if( o == null ){
charHash.put( c, seenOnce );
} else if( o == seenOnce ){
charHash.put( c, seenTwice );
}
}
for(i=0;i<length;i++){
c = input.charAt(i);
if( charHash.get(c) == seenOnce ){
System.out.println(c);
return;
}
}
System.out.println("All letters are repeated");
} else {
System.out.println("Incorrect Arguments. Requires one string.");
}
}
}
Two possible solutions:
1. If string contains only ASCII characters. [0 ... 255 ]
2. String contains not only ASCII characters.
1.
public static char firstNonRepeatedCharAscii(String str){
checkForNull(str);
int[] charsCountArr = new int[ASCII_MAX_CODE + 1];
int strLength = str.length();
char ch;
for( int i =0; i < strLength; i++ ){
ch = str.charAt(i);
++charsCountArr[ch];
}
for( int i =0; i < strLength; i++ ){
ch = str.charAt(i);
if( charsCountArr[ch] == 1 ){
return ch;
}
}
return EMPTY_CHARACTER;
}
2.
public static char firstNonRepeatedChar(String str){
checkForNull( str );
Map<Character, Integer> charsCount = new HashMap<Character, Integer>();
int strLength = str.length();
char ch;
for( int i =0; i < strLength; i++ ){
ch = str.charAt(i);
int code = ch;
if( code >=0 && code <= 255 ){
}
Integer curChCount = charsCount.get(ch);
if( curChCount == null ){
curChCount = Integer.valueOf(1);
}
else {
++curChCount;
}
charsCount.put( ch, curChCount );
}
for( int i =0; i < strLength; i++ ){
ch = str.charAt(i);
if( charsCount.get(ch) == 1 ){
return ch;
}
}
return EMPTY_CHARACTER;
}
public class FirstNonRepeat {
public static void main(String[] args) {
String str = "hhhelloworld";
int[] allChars = new int[256];
for(int i=0;i < str.length(); i++) {
allChars[(int)str.charAt(i)]++;
}
StringBuilder sb = new StringBuilder(str);
for(int i=0; i< sb.length(); i++) {
if(allChars[(int)sb.charAt(i)] > 1) {
sb.deleteCharAt(i);
i--;
}
}
System.out.println("First non repeating char: " + sb.charAt(0));
}
}
char findFirstNonRepeatingCharInaString(char* arr, int size) {
int a[256] = {0};
int c = 0;
int min = -1;
for (int i = 0; i < size; i++) {
c = arr[i];
//if repeated then make it negative
if (a[c] > 0)
a[c] = -1;
//store the index instead of the number of occurences
else if (a[c] == 0)
a[c] = i;
else {
}
}
//find the minimum index in the array
for (int i = 0; i < 256; i++) {
if (a[i] > 0 && a[i] < min)
min = a[i];
}
if (min >= 0)
return arr[min];
else
return 0;
}
Below is the code to fidn out first non repeating character in a given string :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
char *str="aabbbccccddeffffgg";
char non_repeat;
bool nr=false;
int len=strlen(str);
int i=0,j;
for(i=0;i<len;i++)
{
non_repeat=str[i];
nr=true;
for(j=0;j<len;j++)
{
if(i!=j)
{
if(str[i]==str[j])
{
nr=false;
break;
}
}
}
if(nr==true) // first non repeating character found
break;
}
if(nr)
printf("The non repeated character is %c\n", non_repeat);
else
printf("There are no non repeated characters in the string\n");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
char *str="aabbbccccddeffffgg";
char non_repeat;
bool nr=false;
int len=strlen(str);
int i=0,j;
for(i=0;i<len;i++)
{
non_repeat=str[i];
nr=true;
for(j=0;j<len;j++)
{
if(i!=j)
{
if(str[i]==str[j])
{
nr=false;
break;
}
}
}
if(nr==true) // first non repeating character found
break;
}
if(nr)
printf("The non repeated character is %c\n", non_repeat);
else
printf("There are no non repeated characters in the string\n");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
char *str="aabbbccccddeffffgg";
char non_repeat;
bool nr=false;
int len=strlen(str);
int i=0,j;
for(i=0;i<len;i++)
{
non_repeat=str[i];
nr=true;
for(j=0;j<len;j++)
{
if(i!=j)
{
if(str[i]==str[j])
{
nr=false;
break;
}
}
}
if(nr==true)
break;
}
if(nr)
printf("The non repeated character is %c\n", non_repeat);
else
printf("There are no non repeated characters in the string\n");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
char *str="aabbbccccddeffffgg";
char non_repeat;
bool nr=false;
int len=strlen(str);
int i=0,j;
for(i=0;i<len;i++)
{
non_repeat=str[i];
nr=true;
for(j=0;j<len;j++)
{
if(i!=j)
{
if(str[i]==str[j])
{
nr=false;
break;
}
}
}
if(nr==true)
break;
}
if(nr)
printf("The non repeated character is %c\n", non_repeat);
else
printf("There are no non repeated characters in the string\n");
return 0;
}
public class FirstNonRepeatedCharacterEfficient {
public static void main(String [] args){
CharCountAndPosition [] array=new CharCountAndPosition[256];
for(int i=0;i<256;i++)
{
array[i]=new CharCountAndPosition();
}
Scanner scan=new Scanner(System.in);
String str=scan.next();
int len=str.length();
for(int i=0;i<len;i++){
char c=str.charAt(i);
int index=c-'a';
int frequency=array[index].frequencyOfchar;
if(frequency==0)
array[index].firstIndex=i;
array[index].frequencyOfchar=frequency+1;
//System.out.println(c+" "+array[index].frequencyOfchar);
}
boolean flag=false;
int firstPosition=Integer.MAX_VALUE;
for(int i=0;i<256;i++){
if(array[i].frequencyOfchar==1){
//System.out.println("character="+(char)(i+(int)'a'));
if(firstPosition> array[i].firstIndex){
firstPosition=array[i].firstIndex;
flag=true;
}
}
}
if(flag==true)
System.out.println(str.charAt(firstPosition));
else
System.out.println("There is no such type of character");
}
}
class CharCountAndPosition{
int firstIndex;
int frequencyOfchar;
}
public class FirstNonRepeatedCharacterEfficient {
public static void main(String [] args){
CharCountAndPosition [] array=new CharCountAndPosition[256];
for(int i=0;i<256;i++)
{
array[i]=new CharCountAndPosition();
}
Scanner scan=new Scanner(System.in);
String str=scan.next();
int len=str.length();
for(int i=0;i<len;i++){
char c=str.charAt(i);
int index=c-'a';
int frequency=array[index].frequencyOfchar;
if(frequency==0)
array[index].firstIndex=i;
array[index].frequencyOfchar=frequency+1;
//System.out.println(c+" "+array[index].frequencyOfchar);
}
boolean flag=false;
int firstPosition=Integer.MAX_VALUE;
for(int i=0;i<256;i++){
if(array[i].frequencyOfchar==1){
//System.out.println("character="+(char)(i+(int)'a'));
if(firstPosition> array[i].firstIndex){
firstPosition=array[i].firstIndex;
flag=true;
}
}
}
if(flag==true)
System.out.println(str.charAt(firstPosition));
else
System.out.println("There is no such type of character");
}
}
class CharCountAndPosition{
int firstIndex;
int frequencyOfchar;
}
public class FirstNonRepeatedCharacterEfficient {
public static void main(String [] args){
CharCountAndPosition [] array=new CharCountAndPosition[256];
for(int i=0;i<256;i++)
{
array[i]=new CharCountAndPosition();
}
Scanner scan=new Scanner(System.in);
String str=scan.next();
int len=str.length();
for(int i=0;i<len;i++){
char c=str.charAt(i);
int index=c-'a';
int frequency=array[index].frequencyOfchar;
if(frequency==0)
array[index].firstIndex=i;
array[index].frequencyOfchar=frequency+1;
//System.out.println(c+" "+array[index].frequencyOfchar);
}
boolean flag=false;
int firstPosition=Integer.MAX_VALUE;
for(int i=0;i<256;i++){
if(array[i].frequencyOfchar==1){
//System.out.println("character="+(char)(i+(int)'a'));
if(firstPosition> array[i].firstIndex){
firstPosition=array[i].firstIndex;
flag=true;
}
}
}
if(flag==true)
System.out.println(str.charAt(firstPosition));
else
System.out.println("There is no such type of character");
}
}
class CharCountAndPosition{
int firstIndex;
int frequencyOfchar;
}
public class FirstRepeatingAndNonRepeatingElements {
/**
*
* @param elements
* @return
*/
private int firstRepeatedElement(int[] elements) {
int firstRepeatedElement = -1;
if(elements!=null && elements.length>0) {
Set<Integer> setOfElements = new HashSet<>();
for(int i=elements.length-1;i>=0;i--){
if(setOfElements.contains(elements[i])) {
firstRepeatedElement = elements[i];
} else {
setOfElements.add(elements[i]);
}
}
}
return firstRepeatedElement;
}
private int firstNonRepeatedHashSet(int [] elements) {
int firstNonRepatedElement = -1;
Set<Integer> hashOfElements = new HashSet<>();
if(elements!=null && elements.length>0) {
for(int i=elements.length-1;i>=0;i--) {
if(!hashOfElements.contains(elements[i])) {
hashOfElements.add(elements[i]);
firstNonRepatedElement = elements[i];
}
}
}
return firstNonRepatedElement;
}
/**
* @param args
*/
public static void main(String[] args) {
FirstRepeatingAndNonRepeatingElements firstNonRepeatingElement =
new FirstRepeatingAndNonRepeatingElements();
int[] input = new int[]{1,5,3,4,3,5,6,1};
int firstRepeatedElement = firstNonRepeatingElement.
firstRepeatedElement(input);
System.out.println(" The First Repating Element is "
+ firstRepeatedElement);
int firstNonRepeatedElement = firstNonRepeatingElement.
firstNonRepeatedHashSet(input);
System.out.println(" The First Non Repating Element is "
+ firstNonRepeatedElement);
}
public class FirstRepeatingAndNonRepeatingElements {
/**
*
* @param elements
* @return
*/
private int firstRepeatedElement(int[] elements) {
int firstRepeatedElement = -1;
if(elements!=null && elements.length>0) {
Set<Integer> setOfElements = new HashSet<>();
for(int i=elements.length-1;i>=0;i--){
if(setOfElements.contains(elements[i])) {
firstRepeatedElement = elements[i];
} else {
setOfElements.add(elements[i]);
}
}
}
return firstRepeatedElement;
}
private int firstNonRepeatedHashSet(int [] elements) {
int firstNonRepatedElement = -1;
Set<Integer> hashOfElements = new HashSet<>();
if(elements!=null && elements.length>0) {
for(int i=elements.length-1;i>=0;i--) {
if(!hashOfElements.contains(elements[i])) {
hashOfElements.add(elements[i]);
firstNonRepatedElement = elements[i];
}
}
}
return firstNonRepatedElement;
}
/**
* @param args
*/
public static void main(String[] args) {
FirstRepeatingAndNonRepeatingElements firstNonRepeatingElement =
new FirstRepeatingAndNonRepeatingElements();
int[] input = new int[]{1,5,3,4,3,5,6,1};
int firstRepeatedElement = firstNonRepeatingElement.
firstRepeatedElement(input);
System.out.println(" The First Repating Element is "
+ firstRepeatedElement);
int firstNonRepeatedElement = firstNonRepeatingElement.
firstNonRepeatedHashSet(input);
System.out.println(" The First Non Repating Element is "
+ firstNonRepeatedElement);
}
sol-1: Sort the string as an array based on ascii code. Next, do a linear scan.
Time complexity=O(n)
sol-2: Use a LinkedHashtable and maintain a occurrence-count for every character. At the end, again scan thru the hashtable to find an entry with count as 1. As soon as u find, print and exit.
TimeComplexity=O(n). SpaceComplexity=O(n)
public static char firtNonRepeatingCharCaseSensitive(char[] s) {
int[] counts = new int[256];
for (char c : s) {
counts[c]++;
}
for (int i = 0; i < s.length; i++) {
if (counts[s[i]] == 1)
return s[i];
}
return Character.UNASSIGNED;
}
Used extra space and Complexity : O(n)
XOR the characters - as you read the string. when it's non-zero - that's the first non repeating character.
- gabhijit November 04, 2012