CareerCup

In the simple hash map solution the complexity is o(n) + o(n). To prevent the second pass

We can do this:

Store the pointer to the hash map elements in another link list. This link list maintains the order of characters. That is it has the pointers of the hash map in the same order as the character appears in the sequence.

When you are done traversing the sequence. Look at the link list and check the value of hash map address with count = 1. Keep on counting this until u get nth element.

We can map the streams of characters into a hashmap, and scan the streams again to find n th non repeating number.

Keep the count of characters in a Hash Map of Size 26( A to Z ). Once you are done with updating the hash map. Scan again to find out the nth number which has a count 1.

C++ code,

// Find the nth non-repeating number given a streams of characters in the range of A-Z
    char FindnthNonRepeatNum(char *str, int k)
    {
        if (!str || 0 == k) return '\0';

        char *p = str;
        std::map<char, int> numMap;
        std::map<char, int>::iterator it;

        std::vector<char> numV; // use the vector to save the order of char occurance
        std::vector<char>::iterator itc;

        while (*p != '\0')
        {
            it = numMap.find(*p);

            if (numMap.end() != it)     // current char has been added to map;
            {
                (*it).second += 1;      // count > 1 mean, the number repeats.
            }
            else
            {
                numMap[*p] = 1;
                numV.push_back(*p);     // not found in map, so add it to vecotr.
            }

            ++p;
        }

        int kth = 0;
        for (itc = numV.begin(); itc != numV.end(); ++itc)
        {
            if (kth != k && 1 == numMap[*itc])  // the char only occur once
            {
                kth++;
                if (kth == k) break;
            }
        }

        if (k != kth)
            return '\0';
        else
            return (*itc);
    }

We can maintain an array of 26 size to store the status of each alphabet as it will belong to only A---Z.

getNthRepeatCharacter (n){

int[] repeatStatus = new int[26];

while((s=stream.read())!=null){

if(repeatStatus[mapCharToPosition(s)] !=0){
  repeatStatus[mapCharToPosition(s)] = -1;
}else{
 repeatStatus[mapCharToPosition(s)]=stream.position;
}

}

sort(repeatStatus) // place -1 at end

return repeatStatus[n];

}

Time taken to iterate through whole stream = length of stream;(let say m)
At end time taken to sort 26 element array can be done in n(logn) time .

Total complexity = m+26log26 = O(m).

class Node{
  Character c;
   int count;

  public Node(Character c, int count) {
    this.c = c;
    this.count = count;
  }

  public Character getC() {
    return c;
  }

  public void setC(Character c) {
    this.c = c;
  }

  public int getCount() {
    return count;
  }

  public void setCount(int count) {
    this.count = count;
  }
}


/**
 * @author pmundra
 */
public class nonRepeatingNthCharacterInStream {
  public static void main(String[] args) {
    String s="aaabcdeeffghh";
    Map<Character,Node> m= new HashMap();
    List<Node> l=new LinkedList();
    int i=0;
    while(i<s.length()){
     Character c= s.charAt(i++);
     Node n= m.get(c);
      if(n==null){
        Node newNode=new Node(c,1);
        m.put(c,newNode);
        l.add(newNode);
      }
      else{
       n.setCount( n.count+=1);
      }
    }
    i=0;
    for(Node n:l){
      if(n.count==1){
        System.out.println(n.c);
        i++;
      }
      if(i==5){
        System.out.println(">>>>>>>>> "+n.c);
      }
    }
  }
}

#include <iostream>

using namespace std;

class NthNonRepeat {
public:
static char find(string str, int n);
};

char NthNonRepeat::find(string str, int n) {
int counts[26];
int cur = 0;

for (int i = 0; i < 26; ++i) {
counts[i] = 0;
}
for (int i = 0; i < str.length(); ++i) {
if (counts[str[i]-'a'] == 0) {
cur++;
}
counts[str[i]-'a']++;
if (cur == n)
return str[i];
}
return 0;
}

int main() {
string str = "kkkaaabbbcjjjmmmtteepp";
int n = 5;
cout << NthNonRepeat::find(str, n) << endl;
}

use LinkedHashMap