## Amazon Interview Question for SDE1s Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 7 vote

double linkedlist + hashtable. hash table maps the character to its pointer in linked list. Pointer NULL means duplicate.
When a character arrives, if it is in the hash table (pointer not NULL), remove it from the linkedist and reset the pointer, otherwise insert it into hash table and the tail of linked list. When answering an query, return the first character in the double linked list.

Time: all the operations are O(1),
space: O(s), s = number of DISTINCT characters,

Comment hidden because of low score. Click to expand.
0

Thanks. But a code implementation will still give more details..

Comment hidden because of low score. Click to expand.
0

I liked the algorithm, however I think the worst case lookup time for this approach can be of the order O(n). Consider the case when your stream has all distinct characters for the first half and the same stream repeats in the next half and there is just one more element at the end that is appearing the first time.
eg. c1,c2,c3,c4,...,cN,c1,c2,c3,c4,...cN,c(N+1)
In this case, your linked list would be value(c1)->value(c2)-> ... -> value(cN)->value(c(N+1))
The lookup will be of the order of O(N) since all the values are null from the root till tail except the last one since those had duplicates.

Of course, you can argue that number of characters are distinct constant. If that is acceptable assumption, O(1) stands good.

Comment hidden because of low score. Click to expand.
0

How can the linked list be value(c1)->value(c2)-> ... -> value(cN)->value(c(N+1))?

if the input is c1,c2,c3,c4,...,cN,c1,c2,c3,c4,...cN,c(N+1),
the list is c2,c3,c4,…,cN, when encountering the second c1, ie. c1 is removed from the linked list but kept in the hash table when encountering a duplicate c1.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Good. The design pattern used here is the same one used for hash-DLL for a version of LRU algorithm (but LRU would have more movements within the DLL instead of simply deleting on the 2nd occurrence).

Comment hidden because of low score. Click to expand.
0

Reasonable solution. It will be better to add some explanation about why use a DLL instead of SLL. Intuitively I thought SLL is good enough to keep track of order, but later realized that DLL is good for removal.

Comment hidden because of low score. Click to expand.
0

DLL remove() operation is O(1) only if we have the entry pointer to the element. Which pointer you are saving in the HashMap? Your algorithm was good but implementation is not straightforward in Java. How will you get a pointer to an element of the DLL??

This problem is a simple counting problem which can be solved in O(n) time and O(1) space as follows:

``````public static char getFirsUnique(char[] buf)
{
int count = {0};
for (int i=0;i<buf.length;i++)
count[buf[i]]++;
for(int i=0; i<buf.length;i++)
if(count[buf[i]] == 1) return buf[i];

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Code according to above algorithm

``````typedef struct doubly_link_list dll;

{
char key;
dll *prev;
dll *next;
};

class DLL
{
dll *tail;

public:
DLL ()
{
}

dll *append (char c)
{
dll *node = new dll;
memset (node, 0, sizeof(dll));
node->key = c;
node->next = NULL;
node->prev = NULL;

{
}
else
{
tail->next = node;
node->prev = tail;
tail = node;
}
return tail;
}
void remove (dll *node)
{
if (!node)
{
cout << "Bluffff" << endl;
return;
}

{
}
else
{
node->prev->next = node->next;
if (node->next)
{
node->next->prev = node->prev;
}
}
delete node;
}

dll *top()
{
}
};

void first_non_repeating_char (char input[], size_t size)
{
DLL d_list;
vector< pair<bool, dll*> >hash;
hash.reserve(256);

pair<bool, dll*> vectorInit(false, NULL);
hash.insert(hash.begin(), 256, vectorInit);

for (int i = 0; i < size; i++)
{
if (hash[ input[i] ].first == false )
{
hash[ input[i] ].first = true;
hash[ input[i] ].second = d_list.append(input[i]);
}
else
{
if (hash[ input[i] ].second)
{
d_list.remove (hash[ input[i] ].second);
hash[ input[i] ].second = NULL;
}
}
}

dll *result = d_list.top();
if (result)
{
cout << "First Non_repeating character in array:" << input << " is: " << result->key << endl << endl;
}
else
{
cout << "No Non_repeating character in array: " << input << endl << endl;
}
}``````

Comment hidden because of low score. Click to expand.
2
of 4 vote

This is very simple!

1. Take a boolean[] ascii=new boolean;
2. For each character in stream,make ascii[ascii value of that character]=true;
3. if a new character comes, if(ascii[ascii value of that character]==false) return that character;
else {
ascii[ascii value of that character]=true;
go to next character;
}
Note:- We don't have to store the characters coming in the stream..its just sufficient to check which character is 1st non repeating character

Time Complexity: O(n)
Space Complexity: O(1)

Comment hidden because of low score. Click to expand.
1
of 1 vote

works but once the stream ends, we can give the answer in O(1) yours is O(n) for the "answer query"

Comment hidden because of low score. Click to expand.
0

No..if the stream ends,my answer is O(1) because, we would have got the answer already before stream ends..and no need to modify it as more characters are not there

Comment hidden because of low score. Click to expand.
0

This wont work,
"For each character in stream,make ascii[ascii value of that character]=true; "
Do you mean to read the stream twice ? - confused ..
if you just read the stream only once and using the below code, then you wont get the first occurrence of NON-Repeating char.

"if a new character comes, if(ascii[ascii value of that character]==false) return that character;
else {
ascii[ascii value of that character]=true; // It is already true.. why need to set it back true ?
go to next character;
}"

Comment hidden because of low score. Click to expand.
0

Karthik CHTYA dude nothing is simple

First understand the question, we need first char in the input stream which is not repeating.

Your solution would work for input string in alphabetical order e.g. abcdeab
but wont for random string.

Comment hidden because of low score. Click to expand.
1
of 3 vote

This question only works when whole stream finished, so why does samotgun keep asking about stream. No way to get answer earlier mid stream.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Stream is stream. You cannot assume you know the length of the string.

So some iteration code has to be there.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static char findFirstNonRepeatedChar(String inputString) {
Map<Character, Integer> charMapCountOne= new LinkedHashMap<Character, Integer>();
Set<Character> repeatedCharSet = new HashSet<Character>();
for (char c : inputString.toCharArray()) {
if (charMapCountOne.get(c) == null && !repeatedCharSet.contains(c)) {
charMapCountOne.put(c, 1);
} else {
charMapCountOne.remove(c);
}
}
if (charMapCountOne.isEmpty()) {
return " ".charAt(0);
}
return charMapCountOne.keySet().iterator().next();
}``````

Comment hidden because of low score. Click to expand.
0

The order of insertion is not maintained in the HashMap. So you can not be sure that you will get the "first" non repeating char while iterating the CharMapCountOne.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````package CollectionAndOtherDataStructures;

import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class FirstNonRepeatingChar {

public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
StringBuilder str = new StringBuilder((scan.nextLine()));
int len = str.length();

for(int i=0;i<len;i++)
{
if(!map.containsKey(str.charAt(i)))
{
map.put(str.charAt(i),true);
}
else
{
map.put(str.charAt(i),false);
}
}

System.out.println(map);
for(Entry<Character, Boolean> e : map.entrySet())
{
if(e.getValue())
{
System.out.println(e);
break;
}

}
scan.close();
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

How about a BiHashMap?, but we may need to maintain the order of insertion into the map of values

So Map goes both ways
insert a, b, c, d, e, f, c, d, g etc by looking up hash of each character, and increase the count
While looking for the non-repeating character, look for count 0, and display the first character

Of course implementing a LinkedBiMap is the fun part , just references within the Map to the objects is not that bad, so it should be ok

Comment hidden because of low score. Click to expand.
1
of 1 vote

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
1
of 1 vote

can't we store all characters in array of characters and corresponding indexes?
While parsing, updating this array with count & first index.After scanning stream, now scan stored array and find out the characters whose count is 1 and whose index is minimum !!!

Comment hidden because of low score. Click to expand.
1
of 1 vote

geeksforgeeks.org/find-first-non-repeating-character-stream-characters/

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use a LinkedHashMap. Before adding, check if the element is already present. If so remove it. Else add it to the map. Finally iterate the map and get the first element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````<?php

\$hist = [];
\$min = strlen(\$str) + 1;

for (\$i = 0; \$i < strlen(\$str); \$i++) {
\$char = \$str[\$i];

if (isset(\$hist[\$char])) {
\$hist[\$char] = \$min;
continue;
}

\$hist[\$char] = \$i;
}

\$char = "non";

foreach (\$hist as \$key => \$pos) {
if (\$pos < \$min) {
\$min = \$pos;
\$char = \$key;
}
}

print "\$min \n";
print "\$char \n";``````

Comment hidden because of low score. Click to expand.
0

Thanks. But String str should not be hardcoded as in this case input should be a stream characters like "abcdefghighnjksfdkgdfskgsdjkfgb.............."
Also any java code will help me to understand lot more.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use buckets to solve this problem.

The first loop sets the buckets and the second one just looks for the first one that is not repeated in the bucket.

This solution works well only for ASCII characters because they are only 128 (bucket).

If all the characters are repeated I just return 128; a character that doesn't exist in ASCII.

``````char firstNonRepeating(char *s) {

int i, index;
char buckets = "";

i=0;
while(s[i] != '\0')
{
buckets[s[i]]++;	// Fills the bucket.
i++;
}
i=0;
while(s[i] != '\0')
{
if(buckets[s[i]] == 1) // It appears only once
return s[i];
i++;
}
return 128;
}``````

I hope this helps.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The only thing we can do is maintaining a list of candidates in a count array[char]. A binary search tree can be used to maintain a list of chars with count 1

``(c++ set< pair<long, char> > will do; pair will be sorted based on the position (long) )``

With this setup, the first element in the set will always contain the first non-repeated char from the stream seen so far. O( log 256 ) = O( 1 ), since set update is logarithmic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

store each character and its position in a map. when any character is repeated make its value -1 or some thing. after end of input, go through the map and find character with min value

``````public static char nonRepeatingCharacter(String input){
if(input==null || input.length()==0)
return ' ';
Integer minus = new Integer(-1);
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<input.length(); i++){
char ch = input.charAt(i);
if(map.containsKey(ch)){
map.put(ch, minus);
}else{
map.put(ch, i);
}
}

int min=Integer.MAX_VALUE;

for(Character key:map.keySet()){
Integer value = map.get(key);
if(value!=minus){
if(value<min)
min=value;
}
}

return input.charAt(min);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

my java solution :

import java.util.Iterator;
import java.util.Map;

class Test1
{

public static void main (String[] args)
{
int[] A1 = {3,5,8,2,4,5,3,6,5};
getFirstUniq(A1);
}
public static void getFirstUniq(int[] A1)
{
if (A1.length>0)
{
for (int i = 0 ; i < A1.length ; i++ )
{
if (a1map.containsKey(A1[i]))
{
int value = a1map.get(A1[i]);
a1map.remove(A1[i]);
a1map.put(A1[i],value+1);
}
else
{
a1map.put(A1[i],1);
}
}
Iterator it = a1map.entrySet().iterator();
while(it.hasNext())
{
Map.Entry<Integer, Integer > current = ( Map.Entry)it.next();
if (current.getValue() == 1)
{
System.out.println(current.getKey());
break;
}
}
}
}
}

Comment hidden because of low score. Click to expand.
0

This works for known array input. How about stream of characters.?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package inter;
import java.util.*;

public class NonRepeatingChar {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char givenArray[]={'a','b','c','d','b','z','c','a','d','e','a','f','e'};
char newVal=givenArray;
char flag='N';
List present=new ArrayList();
for(int i=0;i<givenArray.length;i++){
if(present.contains(givenArray[i])){
flag='Y';
}
else{
for(int j=i+1;j<givenArray.length;j++){
if(givenArray[i]==givenArray[j]){
flag='Y';
}
}
}
if(flag!='Y'){
newVal=givenArray[i];
System.out.println("NewVal :"+newVal);
break;
}
flag='N';
}
System.out.println("First Non Repeating char :"+newVal);

}

}``````

Comment hidden because of low score. Click to expand.
0

This works for known array input. How about stream of characters.?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Define the obvious hash function h:{alphabet} --> {0,1,2,...,25}. Since we are looking for the first "non-repeating" character, this means there should be a point when the characters stop "streaming" and we can actually determine this. So lets suppose the streamed characters are contained in a character array A. Then we can use count sort to find the first non-repeating character

``````B = integer array of length 26

//initialize array
for i=0, i< 26, i++
B[i]=0

//count streamed characters
for i=0, i < A.length, i++
B[h(A[i])]++

//find first non-repeating character
i = 0
while B[h(A[i])] > 1
i++

return i //or A[i] if you want the actual character``````

If the characters continue to stream, then the array A will have letters appended to it and you can continue to check all the values >= N.

It is odd to say that the characters are "streaming" and that you want to compute the "first non-repeating" (aka unique) character. For if the characters are truly streaming (indefinitely) then how can we know if any character will remain unique?

Comment hidden because of low score. Click to expand.
0
of 2 vote

This problem is a simple counting problem which can be solved in O(n) time and O(1) space as follows:

``````public static char getFirsUnique(char[] buf)
{
int count = {0};
for (int i=0;i<buf.length;i++)
count[buf[i]]++;
for(int i=0; i<buf.length;i++)
if(count[buf[i]] == 1) return buf[i];

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java.

``````package com.practice;

public class NonRepeatingCharTest {

public static void main(String[] args) {
NonRepeatingCharTest nct = new NonRepeatingCharTest();

// First non repeating character in the list in this example is c
// though 2, 4, d also qualifies for non repeating characters
char[] list = new char[] {'a','b','c','2','4','b','a','d'};
System.out.println("No non repeating character in the list");
}
else {
System.out.println("First non repeating character in the list is " + (char)answer);
}
}

public int getFirstNonRepeatingChar(char[] list) {
int[] listAscii = new int;
// Count the number of character for each asccii character
for(int i=0; i < list.length; ++ i) {
listAscii[list[i]] ++;
}

for(int i=0; i < list.length; ++ i) {
if(listAscii[list[i]] == 1)
return list[i];
}
return -1;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>

using namespace std;

#define ASSERT(x);
const int TOTAL_ALPHABET = 26;

//
// input - the input stream to search
// size - size of the input stream in characters
//
// returns first non repeat charcter if found else returns char equivalent of -1
char firstnonrepeatingcharacter(char* input, int size)
{
char result = -1;
char char_index[TOTAL_ALPHABET];
int char_count[TOTAL_ALPHABET] = {0};
int chartoint;
int charindex = -1;

// scan the input once O(n)
for (int i = 0; i < size; i++)
{
chartoint = tolower(input[i])-'a';
if (++char_count[chartoint] == 1)
{
ASSERT(charindex <= TOTAL_ALPHABET);
char_index[++charindex] = tolower(input[i]);
}
}

// scan char index array to find first letter with char count 1 O(1) operation
for (int i = 0; i <= charindex; i++)
{
if (char_count[char_index[i]-'a'] == 1)
return char_index[i];
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

package pck;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FirstNonRpt {

public static void main(String[] args)
{

//Input String

char[] input=str.toCharArray();

//set of character till visited
Set<Character> set=new HashSet<Character>();

//list of chars (to maintain order)
List<Character> list=new ArrayList<Character>();

for(int i=0;i<input.length;i++)
{

Character data=new Character(input[i]);

//if fetched char has already been visited,it will be removed from list(because we are removing Object will be done O(n)
//else it will be added in set as well as in list
if(!set.contains(data))
{
}
else
{
list.remove(data);
}
}

//first char in list will be our desired result
if(list!=null && list.size()>0)
System.out.println(list.get(0));

else
System.out.println("None");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class test{
string s = "abcba";
char[] c = s.toCharArray();
List l = c.ArrayasList();
for(i=0;i<c.len;i++){
if(l.indexof(i)-l.lastindexof(i)==0){
system.out.println(list.get(i));
}

}

}

Comment hidden because of low score. Click to expand.
0

This will print the first character of the list as the condition is accepted in if loop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#in Ruby

str = "II have many words"
mm = {}
str.each_char do |x|
mm.merge! x => 1 if mm.delete(x).nil?
end

puts mm.keys

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

public class FindNonRepeatingChar {

/**
* @param args
*/
public static void main(String[] args) {

char[] stream = s.toCharArray();

char firstNonRepeatingChar='\0';
int arrayLength=stream.length;
for(int index=0;index<arrayLength;index++)
{
if(!map.containsKey(stream[index]))
{
map.put(stream[index],1);
}
else
{
int value=map.get(stream[index]);
map.put(stream[index], ++value);
}
}

for(Entry<Character, Integer> obj : map.entrySet())
{

if(obj.getValue().equals(1))
{
System.out.print("First non-repeating character in the stream : "+ obj.getKey());
break;
}
}

}

}``````

Comment hidden because of low score. Click to expand.
0

This is very simple approach :) even i have tried it for decoding the character problem asked by amazon .

Comment hidden because of low score. Click to expand.
0
of 0 vote

Groovy Code

``````def firstNonRepatingCharacterCount(input)
{
map = [:]
for(ch in input)
{
entryValue = map.find{c,count->  ch.toUpperCase() ==c }
if(entryValue == null)
{
map.putAt(ch.toUpperCase(), 1)
}
else
{
entryValue.value++
}

}
println map.size()
entry = map.find{c,count -> count==1}
println "\$entry.key"
}
firstNonRepatingCharacterCount("test code")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

how this stream look like? AAAAAAAAAAABAAA?
where B is first non-repeating character(except first A)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are talking about letters only, than it is probably better to use 2 bitmasks instead of hash tables.
So if we meet letter first time we set the corresponding bit to 1 in the first bitmask, if second (we check the first bitmask) then to second bitmask. Then xor both bitmasks and get LSB.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in C++ below. I keep track of the position where each character which has appeared only once so far was. I do it using an array of integers with constant size (the size of the alphabet) :

``````#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

char firstNonRepeating(string s) {
int pos;
fill_n(pos, sizeof(pos) / sizeof(int), -1);
for (int i = 0; i < s.length(); ++i) {
pos[s[i]] = (pos[s[i]] == -1) ? i : -1;
}
int m = -1;
char c = '\0';
for (int i = 0; i < 256; ++i) {
if (pos[i] != -1 && (pos[i] < m || m == -1)) {
m = pos[i];
c = i;
}
}
return c;
}

int main(int argc, char **argv) {
if (argc == 2) {
cout << firstNonRepeating(string(argv)) << endl;
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Did you try "aaabbd" or "aabbbd" (3 repeating characters in a roll)?

For the first string, it would return 'a', and the second one, you guess it, 'b'. This is wrong. Right?

Comment hidden because of low score. Click to expand.
0

As mentioned by the comment above, there is a bug in my previous answer. Consider this one instead:

``````char firstNonRepeating(string s) {
int pos;
fill_n(pos, sizeof(pos) / sizeof(int), -1);
for (int i = 0; i < s.length(); ++i) {
if (pos[s[i]] >= 0)
pos[s[i]] = -2;         // Flag as seen twice or more
else if (pos[s[i]] == -1)
pos[s[i]] = i;
}
int m = -1;
char c = '\0';
for (int i = 0; i < 256; ++i) {
if (pos[i] >= 0 && (pos[i] < m || m == -1)) {
m = pos[i];
c = i;
}
}
return c;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure about the space complexity but time complexity could be O(n) ??

``````public class Test{
public static void main(String[] args) {
Scanner c = new Scanner(System.in);
char a[] = c.nextLine().toCharArray();
int smaller = 0;
int[] n = new int;
int[] n1 = new int;

for (int i = 0; i < a.length; i++) {
n1[a[i]] = i;
n[a[i]]++;

}

for (int i = 0; i < 127; i++) {
if (n[i] == 1) {
if (smaller == 0) {
smaller = i;
}

if (n1[i] < smaller) {
smaller = i;
}
}
}
System.out.format("%c is the first character that does not repeat",
smaller);

}
}``````

Comment hidden because of low score. Click to expand.
0

@heman if we use Hashmap(in java or C#) at-least one time we scan the text array till the length of the array. so obviously it will take O(n) complexity .

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python

``````import collections
import sys

def main(file):
cnt=collections.Counter()
fp=open(file, 'r')
cnt[str] += 1
print cnt, 'First non-repeating string is ', cnt.keys()[cnt.values().index(1)]

if __name__=='__main__':
main(sys.argv)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package problemSets;

public class FirstNonRepeatingCharacter {

public static void main(String[] args) {

Character[] data = {'a','a','b','b','c','c','c','d','e','d'};

int j = 0;
int matches = 0;
for (int i = 0; i < data.length; i++) {

if (data[i] != data[j]) {
if (matches == 1) {
break;
} else {
data[j] = data[i];
matches = 1;
}
} else {
matches++;
}
}

System.out.println(data[j]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static char getFirstNonRepeatingChar(char[] streamChars)
{
int[] charTracker = new int; // assumming aschii
for(int i=0; i< charTracker.length; i++)
{
charTracker[i]=0;
}

// track the count of the chars we observe and also use the queue to know what we have seen first
for(int i=0; i < streamChars.length; i++)
{
int index = (int)streamChars[i];
if(charTracker[index] == 0)
{
}
charTracker[index]++;
}

// now that the tracking is done let return the char the meets the requirement.
while(observedCharsQueue.isEmpty() == false)
{
Character ch = observedCharsQueue.remove();
int index = (int)ch.charValue();
if(charTracker[index] == 1)
{
return ch.charValue();   // we have the char we are looking for...
}
}
// no luck!
return '\0';``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This gives the 1st non repeating char (feed string into char array first). in On^2 time. However, it seems that the amortized complexity wud be much less. Please correct me if anything is wrong in this.

``````public static char getFirstNonRepeatation(char[] a){
int char1;
int char2;
//char retChar = '\0';

for(int i =0; i<a.length; i++){
char1 = (int)a[i];
//int j = 0;
//while(j<a.length && j!=i){
for(int j = 0; j<a.length; j++){
char2 = (int)a[j];
if(char1 == char2 && j!=i){
//j = a.length;
break;
}
if(j == a.length-1){
return a[i];
//i = a.length;
}
//j++;
}
}
return '\0';
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Having counter variable initialized to 1
2. Store each character from start in hash map with key as the counter variable value
3. Insert this counter variable value into a min Heap
4. increment Counter variable
5. Before adding a character to a check if the character already exists in the the hash map, If it exists delete the character in the hashmap and delete the corresponding the counter variable value from the min heap and update the heap
6 once the stream is scanned completely, extract root of min heap and display the corresponding value from the hasp map

Comment hidden because of low score. Click to expand.
0
of 0 vote

static void bruteForce(int [] n){
for(int i = 0; i < n.length; i++){
boolean flag = false;
for(int j = i+1; j < n.length; j++){
if(n[i] == n[j])
flag = true;
else
continue;
}//end of for
if(flag){
continue;
}
else{
System.out.println("First non repeating character = "+n[i]);
break;
}
}//end of for i

}//end of bruteFore method

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo Using C#:

1. Create a dictionary with a key being the character of the stream and value being its occurance.
2. Parse the stream 1 character at a time and add the key value pair in the dictionary. Make sure that you catch exception for the already existing key.
3. in Case of exception of already existing key increment the value of the key.

after the stream is completely parsed. the first key with the value 1 is the First non repeated character in the stream.

Comment hidden because of low score. Click to expand.
0

Code Snippet:

public void TestMethod1()
{
string Test = "dafgdsfsdhmlgcfdsmfsdogdsfmcsdiflmsfcmdsf";
Dictionary<char, int> dict = new Dictionary<char, int>();
foreach(char c in Test)
{
try
{
}
catch(ArgumentException)
{
dict[c] = dict[c] + 1;
}
}
foreach(KeyValuePair<char,int> k in dict)
{
if (k.Value == 1)
{
Console.WriteLine(k.Key.ToString());
return;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string s = "he did thataa";

for (int i = 0; i < s.Length; i++)
{
string  temp = s.Substring(i,1);
if(repeated.Contains(temp))
{
continue;

}
else
{
if (charList.Contains(temp))
{
charList.Remove(temp);
}
else
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Extra int array, size = 26
2. One scan to test case
3. Array: a[index] > 0 indicate its position in string add one(Why add 1? to avoid the first char is non repeat char)
a[index]==0 indicate this char doesn't appear at all
a[index]<0 this char has duplication

``````#include <iostream>
#include <vector>
#include <string>
using namespace std;
const unsigned int M = 26;
int main(int argc, char* argv[]){
string input(argv);
vector<int> v(M,0);
unsigned int size = input.size();
for(unsigned int i = 0; i < size; ++i){
if(v[input[i]-'a'] < 0)	continue;
if(v[input[i]-'a'] > 0){
v[input[i]-'a'] *= -1;
continue;
}
if(v[input[i]-'a'] == 0) v[input[i]-'a'] = i+1;
}
int min = size+1,index = -1;
for(unsigned int i = 0; i < M; ++i){
if(v[i]<=0){
continue;
}else{
if(v[i]<min){
min=v[i];
index = i;
}
}
}
if(index>=0){
cout<<"First non-repeat char = "<<static_cast<char>('a'+index)<<endl;
return 0;
}else{
cout<<"No such char"<<endl;
return -1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I would create a

class Item { char data; int byteIndex;}

List items = new List(); // or use Array if the stream size is known/given.

while( scanning through stream of chars){ // O(n)

}

sort on items with comparable function on data which is char. // using merge sort : O(nlogn)

scan this sorted list till end, compare adjacent items and keep hold of their min byteIndex, and finally this min byteIndex is the first occurance of non-repeating char.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
Karumanchi book Hashing Problem 13-14
Give an algorithm for finding the first non-repeated character in a string. For example, the first non-repeated character
in the string "abzddab" is 'z'
Solution: Create a hash table and read the characters in the input string. Keep count of the number of times
each character appears. After reading the input string, we can read the hash table entries to see which entry has
a count equal to 1.
O(2n) -> O(n) time complexity, O(n) space for the count values
*/
public static char firstNonRepeatedChar(char[] string)
{
int i;
int[] count = new int;
for (i = 0; i < string.length; i++)
{
count[i] = 0;
}
for (i = 0; i < string.length; i++)
{
count[string[i]]++; //new character found so increase counter at specified character value
}
//loop through the char array again and if the count is 1, then it is the first non-repeated character
for (i = 0; i < string.length; i++)
{
if (count[string[i]] == 1)
{
System.out.println(string[i]);
break;
}
}
if (i == string.length)
{
System.out.println("No non-repeated characters");
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Sorry, don't need first for loop...

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char findFirstNonRepeatedChar(String inputString) {

Hashtable<Character,Integer> ht = new Hashtable<Character,Integer>();
int i = 1 ;
for (char c : inputString.toCharArray()) {

if(!ht.containsKey(c)){
ht.put(c,i );

}else{
if(ht.get(c) > 0){
ht.put(c, -i);
}
}
i++;
}
int min = Integer.MAX_VALUE ;
for( Character key : ht.keySet() ) {
int value = ht.get( key );
if(value >= 0 && value < min){
min = value;
}
}
System.out.println(min-1);
return inputString.charAt(min-1);
}

Comment hidden because of low score. Click to expand.
0

System.out.println(findFirstNonRepeatedChar("aazaarrrrbtttdyuuu"));

starting i from 1 because zero can not be negative .

save the index ...negate when repetition occurs ..do not negate if already negative ...check for smallest index ...thats the first non - repetitive index .

Comment hidden because of low score. Click to expand.
0
of 0 vote

char[] array = value.ToCharArray();
int k=0;
char d='\0';

for (int i = 0; i < array.Length; i++)
{
k = 0;
for(int j = 0; j < array.Length; j++)
{
if (i == j)
{
continue;
}
else
{
if (array[i] == array[j])
{
break;
}
else
{
k++;
if (k > array.Length-2)
{
d = array[i];
break;
}
}
}
}
if (k > array.Length-2)
{
d = array[i];
break;
}
}

Console.WriteLine(d);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

const int ciSizeASCII = 256;
const int ciIni       = -2;
const int ciRepeat    = -1;

char firstNonRepeating(string & s)
{
int pos[ciSizeASCII];
fill_n(pos, sizeof(pos) / sizeof(int), ciIni);

for (int i = 0; i < s.length(); ++i)
{
pos[s[i]] = (pos[s[i]] == ciIni) ? i : ciRepeat;
}

int m = ciSizeASCII;
char c = '\0';
for (int i = 0; i < ciSizeASCII; ++i)
{
// The first non repeating char
if (pos[i] != ciRepeat && pos[i] != ciIni && pos[i] < m ) {

// The first repeating char
//if (pos[i] == ciRepeat && pos[i] < m ) {
m = pos[i];
c = i;
}
}
return c;
}

int main()
{
string sString("bfffffffa");
cout << firstNonRepeating(sString) << endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````sum=0
while(true){
b=stream.next()
a=2**b
a & sum? return b:sum+=a
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````sum=0
while(true){
b=stream.next()
a=1<<b
a & sum? return b:sum+=a
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a LinkedHashMap. Before adding, check if the element is already present. If so remove it. Else add it to the map. Finally iterate the map and get the first element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Hashtable;

public class Dri {

public static void main(String[] args) {

String str = "sssss";

System.out.println(getFirstNoneRepeatedString(str));

}

public static char getFirstNoneRepeatedString(String str) {

str = str.toUpperCase();
Hashtable<Character, Integer> table = new Hashtable<Character, Integer>();
char c = 'A';
for (int i = 1; i <= 26; i++) {
table.put(c, 0);
c++;
}// O(n)

for (int i = 0; i < str.length(); i++) {

int n = table.get(str.charAt(i));
table.put(str.charAt(i), ++n);
}

for (int i = 0; i < str.length(); i++) {
if (table.get(str.charAt(i)) == 1)
return str.charAt(i);

}

return 'e';

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

this will give error if this it contains no such element.
PS i dont know about hash map i implemeted with ddl in c++
using <map>.take string in small case

``````#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cstring>

using namespace std;
struct node
{
int info;
node *right;
node *left;

};

map< bool,node*> cn;
map< bool,node*> :: iterator it;

int main()
{
char s;
cin>>s;

int n= strlen(s);
cout<<n<<endl;

bool visited;
memset(visited,false,sizeof(visited));
int flag=0;

node *start=NULL,*q,*r;

for(int i=0;i<n;i++)
{
int val=s[i]-96;
// cout<<val<<endl;
if(visited[val]==true)
{  it =cn[val].begin();

if( (it->first)==false)
{
cout<<"inside"<<endl;

cn[val].insert(pair < bool,node *> (true,it->second));

cout<<(it->second)->info;

if(it->second->right==NULL && it->second->left==NULL)
{
cout<<"last"<<endl;
flag=1;
break;
}
/* 2  */               else if( (it->second)->right==NULL)
{
(it->second)->left->right=NULL;

}

/* 3  */ else if(it->second->left==NULL)
{

it->second= it->second->right;
it->second->left=NULL;
start=it->second;
}
/* 4  */       else
{

(it->second)->left->right=(it->second)->right;
(it->second)->right->left=(it->second)->left;

}

}
}

else //if(visited[val]==false)
{

visited[val]=true;
node *temp;
temp=new node;
temp->right=NULL;
temp->left=NULL;
temp->info=val;
if(start==NULL)
{
start=temp;
cn[val].insert( pair < bool,node *> (false,temp));
}

else
{

q=start;
while(q->right!=NULL)
q=q->right;

q-> right=temp;
temp->left=q;

cn[val].insert(pair<bool,node *>(false,temp));

}

}

q=start;
while(q!=NULL)
{
cout<<q->info;
q=q->right;
}
cout<<endl;

}

q=start;
while(q!=NULL)
{
cout<<q->info;
q=q->right;
}cout<<endl;
char c=start->info+96;

cout<<"non repetative char "<<c<<endl;

//free(start);
//free(r);

//free(q);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be achieved simply using the array data structure as below, which uses a table for storing each character frequencies.

In another iteration over the char array we check its frequency and if its 1, its the first unique char.

``````public class FirstUniqueChar {

public static char findFirstUniqueChar(char[] stringArray) throws Exception{
if (stringArray == null) throw new Exception("Empty array.");

int[] charTable = new int;
for (char c : stringArray) {
charTable[c]++;
}

//O(length)
for(int index = 0; index < stringArray.length ; index++ ) {
if (charTable[stringArray[index]] == 1) return stringArray[index];
}
throw new Exception("no unique char found");
}

public static void main (String[] args) throws Exception {
System.out.println("Enter string to find first unique char : "); //applea
String str = getString(); //args;
char unique = findFirstUniqueChar(str.toCharArray()); //l
System.out.println(str + " has first unique char : " + unique);
}

//reads a string from the keyboard input
public static String getString() throws IOException {
return s;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static Character fisrtNonRepChar(String str) {

HashMap<Character, Integer> H = new HashMap<Character, Integer>();
int strLen = str.length();

for (int i = 0; i < strLen; ++i) {

char c = str.charAt(i);

if (H.containsKey(c))
H.put(c, 1 + H.get(c).intValue());
else
H.put(c, 1);
}

for (int i = 0; i < strLen; ++i) {
char c = str.charAt(i);
if (H.get(str.charAt(i)).intValue() == 1)
return c;
}

return null;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import java.util.*;
public class NonRepeatingCharacters {

public static void main(String[] args) {

//char c [] = {'a', 'b', 'c','d','a'};
String s = "abcda";
char c [] = s.toCharArray();

HashMap <Character,Boolean> hm = new HashMap <Character,Boolean>();

int i =0;
while(i < c.length){
char a = c[i];
if(hm.containsKey(a))
hm.put(a, true);
else
hm.put(a, false);
i++;

}

Set set = hm.entrySet();
Iterator ir = set.iterator();

while(ir.hasNext()){

Map.Entry m = (Map.Entry) ir.next();
if(m.getValue().toString()== "false")
System.out.println("Non Repeting Chars: "+m.getKey());

}

}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.