Amazon Interview Question Software Engineer in Tests
Here is C implementation
#include<stdio.h>
#include<string.h>
int main()
{
int a[256]={0};
char *b="Helloworldd";
int i;
for(i=0;i<strlen(b);++i)
a[b[i]]++;
for(i=0;i<strlen(b);++i)
if(a[b[i]]>1)
{
printf("First Repeating %c\n",b[i]);
break;
}
for(i=strlen(b)-1;i;--i)
if(a[b[i]]>1)
{
printf("Last Repeating %c\n",b[i]);
break;
}
}
Change the if condition as
if(a[b[i]]==1) to get the first/last Non-repeating Character
Use hashmap (key = char, value = index).
Keep adding every character(and its index) of the string to the map only if the char dowsn't already exist in the map.
If the character already exist in the map, remove that entry from the map.
Once you are done with the traversal, iterate through the entries in the map and store the least value(index).
This method will return "w" as the first non-repeating character for "wwwa" which is wrong. Instead of removing the entry from hashtable if it repeats, we can change the index of it to -1. So finally while traversing through the code we can find the character with the least index other than -1.
Use a structure like this
typedef struct node {
char key;
int index;
} Map;
Map a [10];
1. Insert the incoming data in this sorted array using using binary search.
2. Use binary search again to fetch the char that is already stored in the array. (n logn)
Scan the whole input array till the last char and fetch the first element in the array searching for index 0 .n logn
Overall complexity = nlogn+nlogn =2nlogn.
:THIS IS ONLY IN CASE U DONT WANT TO USE MAP(STL CONTAINERS):
"Scan the whole input array till the last char and fetch the first element in the array searching for index 0 .n logn"
This wont work. What if the index 0 entry is a repeated one. I assume that in the array Map array you are storing results sorted by chars.
i forgot to add one step in between in case the char to be inserted is found in the array, delete the entry.That way we would ensure that the only non-repeating char are present in the array, and first non-repeating at index 0.
Also i agree it could be done using map<char,int> STL but in case it were to be implemented using array
char* Amazon_001(){
char *x = "wwwamazoncom";
char *p = x;
char *q = p+1;
while(*q){
int res = *p + *q;
if( res/2 != *p ){
break;
}
p++;
q++;
}
return q;
}
public static char findNonRepeateChar(String str) {
Set chSet = new LinkedHashSet();
char[] charArray = str.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (!chSet.add(charArray[i])) {
chSet.remove(charArray[i]);
}
}
if (chSet.isEmpty())
return '-';
else
return (Character) (chSet.toArray())[0];
}
can be easily done in the O(n) :)
just take a array of 256
code :
char FirstNotrepeating(char *str)
{
static int flag[256];
int i;
for(i=0;str[i]!='\0';i++)
flag[str[i]]++;
for(i=0;i<=255;i++)
{
if(flag[i]==1)
return str[i];
}
puts("all characters are repaeated");
return 0;
}
I think we will need to use
1-Hashmap for storing key-char and value-0 or 1 (0-nonrepeating, 1-repeating) .
2-Queue for maintaing sequence of characters.
import java.util.HashMap;
/** Method for getting first non repeating character in a string
/*@param String str Input string
/*@return char q
*/
public char getFirstNonRepeatChar(String str){
Hashmap<String,int> map = new Hashmap<String,int>();
Queue q= new Queue();
//put chars in queue and hashmap
for(int i=0;i<str.length();i++){
if(map.containsKey(str.charAt(i))){
map.put(str.charAt(i),1);//set key value to 1(set for dequeue)
}else{
map.put(str.charAt(i),0);//set key value to 0(non repeating value)
q.enqueue(str.charAt(i))//add new char to queue
}
}//end of for
//loop till queue is empty or we find a first non repeating char
while(!q.isEmpty()){
char v=q.seek();//get char value at first pointer
if(map.get(v)==0){//if char is non repeating
return v;//found the first non repeating char
}
q.deqeue();
}
return null;
}
<pre lang="" line="1" title="CodeMonkey905" class="run-this">How about this. Changed the code by "geeks" a bit?
#include <stdio.h>
#include <limits.h>
struct node{
int count;
int pos;
};
int FirstNotrepeating(char *str)
{
static struct node flag [256];
int i;
int minpos=INT_MAX;
for(i=0;str[i]!='\0';i++)
{
flag[str[i]].count++;
flag[str[i]].pos = i;
}
for(i=0;i<=255;i++)
{
// if it is seen only once
if(flag[i].count==1)
{
// check the minimum pos
if(flag[i].pos < minpos)
{
minpos=flag[i].pos;
}
}
}
if(minpos < INT_MAX)
printf("The first non rep char is %c ",str[minpos]);
else
printf("No non-rep chars");
return 0;
}
int main()
{
char a[] = "aabbccddeffgghhijj";
FirstNotrepeating(a);
return 0;
}
</pre><pre title="CodeMonkey905" input="yes">
</pre>
1.take an array of size 256 itialised to 0.
2.traverse the string and increment the value at that position(ASCII value of that character) for each finding of thet character in the string.
3.Finally the array consists of the number of occurences of each character.
4.Traverse the string again and check that position(ASCII value of that character) in the indexed array whether it is one or not,if it is one then it is the first non repeating character otherwise keep traversing till u find such an element.
I am assuming that we want to show the first char comin in input string that is not going to be repeated:
public class FirstNonRepeatingChar
{
public static void main(String[] args)
{
System.out.println("[FirstNonRepeatingChar] in main()");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the string:");
try {
String str= br.readLine();
int i=0;
for( ;i<str.length()-1;i++ )
{
Character ch =str.charAt(i);
if(!(str.substring(i+1).contains(ch.toString()) || str.substring(0,i).contains(ch.toString()) ))
{
System.out.println("First Non-repeated character is: "+ch);
break;
}
}
if(i==str.length()-1)
{
System.out.println("No Non-repeated character ");
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
With better time complexity than previous:
public class FirstNonRepeatingChar
{
public static void main(String[] args)
{
System.out.println("[FirstNonRepeatingChar] in main()");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the string:");
try {
String str= br.readLine();
Map<Character,Integer> map = new HashMap();
for( int i=0;i<str.length();i++ )
{
Character ch =str.charAt(i);
if(map.get(ch)==null)
map.put(ch, 1);
else
map.put(ch, map.get(ch)+1);
}
int i=0;
for( ;i<str.length();i++ )
{
Character ch =str.charAt(i);
if(map.get(ch)==1)
{
System.out.println("First Non-repeated character is: "+ch);
break;
}
}
if(i==str.length())
{
System.out.println("No Non-repeated character ");
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public static void main(String ard[]) {
String name = "navdeepjain";
char nameArray[] = name.toCharArray();
Set nameset = new HashSet();
for (int i = 0; i < nameArray.length; i++) {
nameset.add(nameArray[i]);
}
System.out.print(nameset);
Set newSet=new HashSet();
for(int i=0; i<nameArray.length; i++)
for(int j=i+1; j<nameArray.length; j++){
if(nameArray[i]==nameArray[j]){
System.out.print(nameArray[i]);
newSet.add(nameArray[i]);
}else{
// System.out.println(nameArray[i]);
}
}
nameset.removeAll(newSet);
System.out.println(nameset);
}
public class JavaArrayTest {
public static void main(String[] args)
{
String test="avinashavinashavinashakvinashainashmishra";
char[] ch=test.toCharArray();
Set lSet=new HashSet<Character>();
Set delSet=new HashSet<Character>();
for (int i=0;i<ch.length;i++)
{
if(!lSet.add(ch[i]))
{
delSet.add(ch[i]);
lSet.remove(ch[i]);
}
}
lSet.removeAll(delSet);
System.out.println(lSet);
}
}
char firstNonRepeatChar(string s){
queue<char> Q;
int charArr[255];
for(int p=0;p<255;p++)charArr[p]=0;
for(int i=0;i<s.size();i++){
charArr[s[i]]++;
Q.push(s[i]);
}
while(!Q.empty()){
if(charArr[Q.front()]==1)return Q.front();
Q.pop();
}
cout<<"No non-repeat char in the string!"<<endl;
}
public class Q7 {
static public char firstC(String s) {
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
int flag = 0;
for (int j = 0; j < cs.length; j++) {
if (cs[i] == cs[j]) {
flag++;
}
if (flag > 2) {
break;
}
}
if (flag == 1) {
return cs[i];
}
}
return 0;
}
public static void main(String[] args) {
String s = "sadjkwedfks";
System.out.println(Q7.firstC(s));
}
}
public void FirstNonRepeatChar(string inputStr)
{
char[] inputCharArray = inputStr.ToCharArray();
Dictionary<char,int> counters = new Dictionary<char,int>();
for(int i = 0 ; i <= inputCharArray.Length-1; i++)
{
if(counters.ContainsKey(inputCharArray[i]))
{
counters[inputCharArray[i]] += 1;
}
else
{
counters.Add(inputCharArray[i],1);
}
}
foreach (char c in inputCharArray)
{
if (counters[c] == 1)
{
Console.WriteLine("First Non Repeating Char is {0}", c.ToString());
return;
}
}
}
public static Character getFirstNonRepeatingChar() {
String test="jitendrajkuitendlkummajlr";
char[] chArr=test.toCharArray();
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
for(char ch : chArr){
if(map.containsKey(ch))
map.put(ch, map.get(ch)+1);
else{
map.put(ch,1);
}
}
for(Map.Entry<Character, Integer> entry : map.entrySet()){
if(entry.getValue() == 1)
return entry.getKey();
}
return null;
}
instead of using hashmap requiring auxiliary space , we can use two integers - 1 bit vector(check) to keep whether a character has already been appeared or not and a parallel bit vector to keep track of candidate repeating chars .
int check = 0x00000000;
int candidate = 0xFFFFFFFF;
for each char in string
int ch = 1<<char-'a'
if(candidate&ch)
if check & ch
candidate&=~ch
check|=ch
iterate over the string again and check the first candidate
for each char in string
int ch=1<<char-'a'
if(candidate&ch)
return char
package com.QAE_Amazon_site;
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatingcharHashMap {
public static void main(String[] args) {
String s="amazon";
String t="aabb";
firstNonRepChar(s);
firstNonRepChar(t);
}
public static void firstNonRepChar(String s)
{
Map<Character,Integer> hmap=new HashMap();
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
int value=hmap.get(s.charAt(i));
hmap.put(s.charAt(i), value+1);
}
else{
hmap.put(s.charAt(i), 1);
}
}
boolean flag= false;
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
if(hmap.get(s.charAt(i))==1)
{
System.out.println(s.charAt(i));
flag=true;
break;
}
}
}
if(!flag)
System.out.println("none");
}
}
package com.QAE_Amazon_site;
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatingcharHashMap {
public static void main(String[] args) {
String s="amazon";
String t="aabb";
firstNonRepChar(s);
firstNonRepChar(t);
}
public static void firstNonRepChar(String s)
{
Map<Character,Integer> hmap=new HashMap();
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
int value=hmap.get(s.charAt(i));
hmap.put(s.charAt(i), value+1);
}
else{
hmap.put(s.charAt(i), 1);
}
}
boolean flag= false;
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
if(hmap.get(s.charAt(i))==1)
{
System.out.println(s.charAt(i));
flag=true;
break;
}
}
}
if(!flag)
System.out.println("none");
}
}
package com.QAE_Amazon_site;
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatingcharHashMap {
public static void main(String[] args) {
String s="amazon";
String t="aabb";
firstNonRepChar(s);
firstNonRepChar(t);
}
public static void firstNonRepChar(String s)
{
Map<Character,Integer> hmap=new HashMap();
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
int value=hmap.get(s.charAt(i));
hmap.put(s.charAt(i), value+1);
}
else{
hmap.put(s.charAt(i), 1);
}
}
boolean flag= false;
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
if(hmap.get(s.charAt(i))==1)
{
System.out.println(s.charAt(i));
flag=true;
break;
}
}
}
if(!flag)
System.out.println("none");
}
}
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatingcharHashMap {
public static void main(String[] args) {
String s="amazon";
String t="aabb";
firstNonRepChar(s);
firstNonRepChar(t);
}
public static void firstNonRepChar(String s)
{
Map<Character,Integer> hmap=new HashMap();
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
int value=hmap.get(s.charAt(i));
hmap.put(s.charAt(i), value+1);
}
else{
hmap.put(s.charAt(i), 1);
}
}
boolean flag= false;
for(int i=0;i<s.length();i++)
{
if(hmap.containsKey(s.charAt(i)))
{
if(hmap.get(s.charAt(i))==1)
{
System.out.println(s.charAt(i));
flag=true;
break;
}
}
}
if(!flag)
System.out.println("none");
}
}
IN JAVA
it is very easy....you can do it without collection in java..
only using a for loop
public class FirstNonRepeatedString{
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String input = sc.next();
char process[] = input.toCharArray();
boolean status = false;
int index = 0;
for (int i = 0; i < process.length; i++) {
for (int j = 0; j < process.length; j++) {
if (i == j) {
continue;
} else {
if (process[i] == process[j]) {
status = false;
break;
} else {
status = true;
index = i;
}
}
}
if (status) {
System.out.println("First non-repeated string is : " + process[index] + " INDEX " + index);
break;
}
}
}
}
My approach for this in Python
1. First solution - using HASHMAP
def first_non_rep_char(string:str)->str:
counter = {}
for char in string:
if char in counter:
counter[char] += 1
else:
counter[char] = 1
for char in string:
if counter[char] == 1:
return char
return ''
2. Second solution - using inbuild count() method
def first_non_rep_char2(string:str)->str:
counter = {}
for char in string:
if string.count(char) == 1:
return char
return ''
First Non Repeating Character:-
Stores the sequence in a Queue and hashmap to store the count.
If you want the last non repeating character replace the Queue with a Stack :)
- Dev February 22, 2012public Character firstNonRepeating(String s) { char[] strChars = s.toCharArray(); HashMap<Character, Integer> charMap = new HashMap<Character, Integer>(); Queue<Character> strQueue = new LinkedList<Character>(); for(int i = 0; i < strChars.length; i++) { if(charMap.containsKey(strChars[i])) { charMap.put(strChars[i], charMap.get(strChars[i]) + 1); } else { charMap.put(strChars[i], 1); strQueue.add(strChars[i]); } } while(!strQueue.isEmpty()) { char firstUnique = strQueue.poll(); if(charMap.get(firstUnique) == 1) { return firstUnique; } } return null; }