CareerCup

Maintain a double linked list (lets call the node LNode) and HashMap<char, LNode*>.
Read each character:
If this character is not present in hash, then add a LNode to the tail of linked list, and add the character, LNode* tuple to hashMap.
If this character is present in the HashMap and LNode is not NULL, then get the pointer to LNode and delete it from linked list
If this character is present in HashMap and LNode is NULL, continue.

At the end, the double linked list will only contain characters that are not repeated. The first node in list is the first non repeating character in the string. Since we are using double linked list, insertion and deletion is o(1).
Total space complexity o(2n) and time complexity o(n)

Have an array of 127 (it's only ASCII) /structs/, where the struct contains: index of first sighting, and count (or a tri-state of: 'haven't seen', 'have seen once', 'have seen 2+ times').

Walk along the sentence, setting the array elt at the position in ASCII of the char (eg 'A' will be pos 65). If we haven't seen the char before, mark index of first sighting, and change the state / bump the count. If we have seen it before, just bump count or change its state to '2+'. At the end, scan the whole array for the lowest 'first sighting' that's been seen only once. (Is O(n) with initialization + scan costing 127 (ie O(1)) each.

If you can't write it, then tell him to write it. See if he is bullsh-ting you.. because if he can't write it on the spot, he shouldn't ask you the question.

O[n] + O[n] = 2*O[n] which is again O[n] as we do not consider constants in Big Oh notations.

using xor technique , we can do it in O(n)

char *ptr="aabccss\0";
char c=*ptr;
ptr++;
while(*ptr)
{
char t=*ptr;
c=c^t;
ptr++;
}
printf("%c\n",c);

See the below code.
The logic here is, we will check if the HashMap contains the character or not.
If not, we will continue pushing the character, and if present that means, we found the first repetitive character. Now that character can be the first character in the String or not.
For eg.
abca = Here, non repetitive char is b, so, if the repetitive character is first element, we will take the 2nd element
or, abcb = Here no repetitive char is a, so, if the repetitive character is NOT first element, we will take the 1nd element.

private char usingHashing(String s)
{
  Map m = new HashMap();
  for (int i=0;i<s.length();i++)
  {
    char c = s.charAt(i);
    if (! m.containsKey(c))
    {
	m.put(c,i);
    }
    else
    {
	int j = ((Integer)m.get(c)).intValue();
	if (j==0)
	{
		return s.charAt(1);
	}
	else
		return s.charAt(0);
	}
  }
  return ' ';
}

Maintain 2 data structures 1)min heap and 2) HashTable
follow these steps (
1) Extract characters of string
2) check the hash table. If not present put in min heap with priority equal to index.
Put also in Hash Table with key = character and value = index
If present in hash table.. Get the index from hash table. modify the heap with priority = Max_Priority and then heapify.

Complexity Memory o(n) + o(n) but run time o(n)

Here is O(n) solution:

char search(char*Str)
{
    unsigned char flag[256];
    unsigned char*S=reinterpret_cast<unsigned char*>(Str);
    memset(flag,0,256);
   int nLen=strlen(str);
  char result=0;
  for(i=0; i<nLen;++i)
    {
   ++flag[S[i]];
    if(flag[S[i]]==1)
    result=S[i];
   else if(flag[S[i]]==2){
     if(result==S[i])
        result=0;
   }
   else 
     flag[S[i]]=3;  
     }
   return result;
}

Sort the string (perf: n log n, heap sort), traverse string to check for current and current – 1(perf: n) items are same. If chars are not same then we get unique char in string. (toal perf: n log n + n)

does this logic work?

1.find the string length.
2.traverse from the last.
3.try to add each character in the hash.
4.if (already in hash)
4.1 ignore.
else
4.2 update firstNonRepeated with that character.
5.result = firstNonRepeated


As we are coming from last, this algorithm returns expected result i think.

please add me if i am not completed.

I just get an idea to decrease the complicity to be O(n+256). I think this method has great use if n is really large.
struct node{
char times;
int position;
};
I will first create a table size 256
typedef struct node{
char times;
int positon;
}node;
int firstnondup(const char* input)
{
node* record = new node[256];
memset(record,0,256*sizeof(node));
int i =0 ;
int temp;
while(i<strlen(input))
{
temp = input[i] - ' ';
cout<<record[temp].times<<endl;
if(record[temp].times == 0)
{
record[temp].times ++;
record[temp].positon = i;
}
else if(record[temp].times == 1)
{
record[temp].times = 2;
}
i++;
}
int min = 256;
for(i = 0;i<256;i++)
{
if(record[input[i] - ' '].times == 1)
{
if(record[input[i] - ' '].positon<min)
min = record[input[i] - ' '].positon;
}
}
return min;
}

represent string as array
sort the array
start from first index say i , loop until a[i] != a[i+1]
a[i] is the first non repeated char

represent string as array
sort the array
start from first index say i , loop until a[i] != a[i+1]
a[i] is the first non repeated char

Sorting will not work,

hhglla

You get 'a' if you sort, but 'g' should be the answer.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

using namespace std;

void print_unique(string& sentence)
{
  size_t ALPHABET_SIZE = 256;
  vector<int> b;
  vector < vector<int> > n_appears(ALPHABET_SIZE, b);
 
  for ( size_t i = 0; i < sentence.size(); ++i )
   {  
      n_appears[ sentence[i] ].push_back(i);
   }
   
   int unique_index = numeric_limits<int>::max(); //also the min index
   for ( size_t i = 0; i < ALPHABET_SIZE; ++i )
   {
      if (n_appears[i].size() == 1 && n_appears[i].at(0) < unique_index) {
        unique_index = n_appears[i].at(0);
      }
   }
   cout << "unique character: " << sentence[unique_index] << endl;
}

int main(int argc, char** argv)
{
  string sentence(argv[1]);
  print_unique(sentence);
  return 0;
}

char find_first(const char *str, size_t len) {
if (len == 0) return 0;

char arr[255] = {0};

const char *p = str+len-1;

char first = *p--;
arr[(int)first] = 1;

while (p >= str) {
if (arr[(int)*p] == 0) first = *p;
arr[(int)*p] += 1;
--p;
}

return first;
}

I think if its a ASCII character ..we could approach the problem using an array of 256 characters.That would be o(1) space only and not o(n)...