CareerCup

use bit vector of 95000. He was looking for bit array at that time.

I answered the question with below code and the interviewer was happy with the solution, he also said that using an array with arr[95000] as in the code below is not an efficient way. I was not sure how else can I accommodate a UNICODE character set? And he did not tell me what's an efficient way when the interview got over.

public void FirstNonRepeatedCharacter(string s)
        {
            int i;
            int[] asc = new int[95000];
            char[] ca = s.ToCharArray();
            for (i = 0; i < ca.Length; i++)
            {
                asc[ca[i]] += 1;
            }

            for (i = 0; i < ca.Length; i++)
            {
                if (asc[ca[i]] == 1)
                {
                    Console.WriteLine("first non repeating char is: " + ca[i]);
                    break;
                }
                
            }

}

I was not sure if the interviewer was just trying to test my approach or if we really have a way to represent the unicode char set without using an array of size 95000. But if you folks know a way to use the unicode character set without using a large array of size 95000, please do let me know as well.

I think the more efficient way is that you can use hash table instead of a long array.You can set the count that the character appears as the value of the hash table.And the hash table size is corresponding to the length of the string.
I don't know about Java so,I give a pseudocode.

public void FirstNonRepeatedCharacter(string s)
        {
            int i;
            int[] asc = new int[95000];
            char[] ca = s.ToCharArray();
            for (i = 0; i < ca.Length; i++)
            {
		key = CalculateHastKey(ca[i]);
		HashTable[key] += 1;
            }

            for (i = 0; i < ca.Length; i++)
            {
		key = CalculateHastKey(ca[i]);
                if (HashTable[key] == 1)
                {
                    Console.WriteLine("first non repeating char is: " + ca[i]);
                    break;
                }
                
            }
}

The time complexity would be same with you,but the space complexity would be much smaller if the string is not very long.

How about using bool array instead of int array, it will save a lot of space, e.g.
(p.s. not good at JAVA)

public void FirstNonRepeatedCharacter(string s)
{
            int i;
            bool[] asc = new bool[95000];
            char[] ca = s.ToCharArray();
            for (i = 0; i < ca.Length; i++)
            {
                asc[ca[i]] = 1;
            }

            for (i = 0; i < ca.Length; i++)
            {
                if (asc[ca[i]] == 1)
                {
                    Console.WriteLine("first non repeating char is: " + ca[i]);
                    break;
                }
                
            }
}

public void FirstNonRepeatedCharacter(String s){
		List<Character> candidates = new ArrayList<>();
		HashSet<Character> alreadyExisted = new HashSet<>();
		
		for (int i = 0; i < s.length(); i++) {
			if(!alreadyExisted.contains(s.charAt(i))){
				if(candidates.contains(s.charAt(i))){
					Character c = new Character(s.charAt(i));
					candidates.remove(c);
					alreadyExisted.add(c);
				}
					
				else
					candidates.add(s.charAt(i));
			}
		}
		System.out.println(candidates.get(0));
	}

#!/usr/bin/perl 

#Date: 06.10.2013

use strict;

my $string = qw(wcaowaor);
my @tempArray = split "",$string;
my @values = qw(0);
my %hashtable ;
my $count = 0;

foreach (@tempArray)
  {
	$values[ord($_)] +=1;
  }

for(my $i=0;$i<$#values;$i++)
  {
	$hashtable{$count++} = chr($i) if $values[$i] == 1;
  }

foreach my $key(sort keys%hashtable)
  {
	if(defined $hashtable{$key})
	  {
		print "the first none reapeating item is :","$hashtable{$key}\n";
		last;
	  }
  }

#END

string sentence = "am aα software programmer";

            char character;

            for (int i = 0; i < sentence.Length; i++)
            {
                character = sentence[i];
                string restOfSentence = sentence.Substring(i + 1);

                if (!restOfSentence.Contains(character))
                {
                    break;
                }
            }

sites.google.com/site/spaceofjameschen/home/string/find-the-first-non-repeating-character-in-a-given-string----microsoft

this is to the guy who hs put the question ..... m nt sure but i dont think ur code uld give the first non repeating character what if the string is: abcdeabcdegabcf
now g and f both appear once but ur code i think does not check which comes first...
i ve run the following code but not sure of the efficiency
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
int main()
{
char str[25];
int i,j,length = 0;
gets(str);
i=0;
while(str[i]!='\0')
{
length = length+1;
i=i+1;
}
for(i=0;i<length;i++)
{
if(str[i]!=7)
{
for(j=i+1;j<length;j++)
{
if(str[i]==str[j])
{
str[j]=7;//ascii for bell
break;
}
}
if(j==length)
{
printf("\n%c",str[i]);
break;
}
}
}
getch();
return 0;
}

namespace FirstNonRepeatedCharacter
{
    class Program
    {
        public static char FirstNonRepeatedChar(string str)
        {
            char ch = ' ';

            char[] charArray = str.ToCharArray();
            Dictionary<char, int> chrHash = new Dictionary<char, int>();

            foreach (char chr in charArray)
            {
                if (!chrHash.ContainsKey(chr))
                {
                    chrHash[chr] = 0;
                }
                else
                {
                    chrHash[chr]++;
                }
            }

            foreach (KeyValuePair<char, int> kvp in chrHash)
            {
                if (kvp.Value == 1)
                {
                    ch = kvp.Key;
                    break;
                }
            }

            return ch;
        }
        static void Main(string[] args)
        {
            FirstNonRepeatedChar("siadjtlsrpqjkrp");
        }
    }
}

python:

map = {}
i ="dsjiodsjdeurenreieiekjkejnmenr"
for j in i:
if not j in map:
map[j] = 1
else:
map[j] +=1
for key in i:
if map[key] ==1:
print key

char check(string s)
{
set<char> myset;
unsigned int i=0;
while(i<s.length())
{
if(myset.insert(s[i]).second == 0)
myset.erase(s[i]);
i++;
}
if(myset.size() > 0)
return *(myset.begin());
return '\n'; // you can send any character which represents non-existant of non-repeating character in the string
}

#include <iostream>
#include <map>
#include <string>
#include <conio.h>

using namespace std;

int main(int argc, char *argv)
{
map<char, int>input;

string s;
cout<<"Enter the String:";
cin>>s;

for(int i=0; i< s.length(); i++)
input[s[i]]++;

map<char, int>::const_iterator iter;
for(iter=input.begin(); iter!=input.end();iter++)
if(iter->second == 1)
{cout<<iter->first; break;}

getch();
}

private static int firstnonrepeat(String target) {
char original =target.charAt(0);

for (int i=1; i< target.length(); i++)
{
if(original==target.charAt(i))
{
return i;
}
original = target.charAt(i);

}
return 0;
}

Solution With two Bitsets:

char findFirstNonRepeating(char * str){
	bitset<95000> bs;
	bitset<95000> bsUsed;
	int len = strlen(str);
	for(int i = 0 ; i < len ; i++){
		if(bs.test(str[i])){
			bsUsed.set(str[i]);
			bs.flip(str[i]);
		}
		if(!bsUsed.test(str[i])){
			bs.set(str[i]);
		}
	}
	for(int i = 0 ; i < len ; i++){
		if(bs.test(str[i])){
			return str[i];
		}
	}
}

Space complexity is 95000 * 2 Bits, Much better than using an int array[95000] wich is 95000 * 32 Bits.

public static Character noRepeat(String s) {

//The linked hash set preserves insertion order.
		LinkedHashSet<Character> chMap = new LinkedHashSet<>();

		char[] str = s.toCharArray();

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

			if (chMap.contains(str[i]))
				chMap.remove(str[i]);
			else
				chMap.add(str[i]);

		}

		Iterator<Character> i = chMap.iterator();

		if (i.hasNext())
			return i.next();
		else
			return null;

	}

public void FirstNonRepeatedCharacter(String str){
		HashSet hs=new HashSet();
		boolean bool=false;
		for(int i=0;i<str.length();i++){
			if(!hs.add(str.charAt(i))){
				bool=true;
				System.out.println("First Non repitive char is "+str.charAt(i));
				break;
			}
		}
		if(!bool)
			System.out.println("None of chars are repeating");
}

Use below to get 1st unique value in O(n)

        public char FirstDistinctCharacter(string str)
        {
            Hashtable ht = new Hashtable();
            List<char> val = new List<char>();
            foreach (char c in str.ToCharArray())
            {
                try
                {
                    ht.Add(c, 1);
                    val.Add(c);
                }
                catch (Exception) { 
                    if(val.Contains(c))
                    val.Remove(c);
                }
            }
            return (val.Count!=0)? val[0] : new char();
        }

I have two solutions in Ruby. It seems the author meant to use "non-recurring" in place of "non-repeating". I have implemented both solutions, below:

Non-Repeating:

#!/usr/bin/env ruby 

# Find the first non-repeating character in a string and return its zero-based position.
# A repeating character is a character that occurs multiple times in succession within 
# the same string.

class String
  def index_of_first_nonrepeating
    j = -1
    self.split("").each_with_index do |c,i| 
      if i == 0
        if self.length == 1
          j = i
          break
        end
        next
      end
      if i == self.length - 1
        if c != self[i-1]
          j = i
        end
        break
      end
      if c != self[i-1] && c != self[i+1]
        j = i
        break
      end
    end
    j
  end
end

s = "aaaaabbbdceccccc"

puts "Index of first non-repeating char in \"#{s}\" is i = #{s.index_of_first_nonrepeating}."

Non-Recurring:

#!/usr/bin/env ruby 

# Find the first occurrence of a character that occurs only once in a string.

require 'set'
class String
  
  def index_of_first_non_recurring
    h = Hash.new(0)
    self.split("").each do |c|
      h[c] += 1
    end
    s = h.each_pair.collect do |k,v|
      k if v == 1
    end.compact
    v = s.min{|v| self =~ /#{v}/}
    i = self =~ /#{v}/
  end
  
end

s = "abcdefavcdefgb"
i = s.index_of_first_non_recurring

puts "Index of first non-recurring character in \"#{s}\" is i = #{i} (\"#{s[i]}\")."

Nice