Little Puzzlers: First Non-Repeating Character

<< The light at the end of the tunnel | Home | Solution–Little Puzzlers: First Non-Repeating Character >>

Little Puzzlers: First Non-Repeating Character

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

The Problem

Given an unbounded sequence of characters, find the value and position of the first non-repeated character.

e.g., in the stream: A,B,C,D,C,B,A,F,A,F the first non-repeated character is D.

For the purposes of this exercise, consider the following interface as the source of the stream:

        1: // C#

       2: public interface ICharStream

       3: {

       4:     bool HasNext { get; }

       5:     char GetNext();

       6: }

Spoiler Alert

Fair Warning: discussion of the problem and potential solutions may be discussed in the comments below.

Share This Post:
Short Url: http://wblo.gs/g60

Print | posted on Monday, March 9, 2015 9:22 AM | Filed Under [ My Blog C# .NET Little Puzzlers ]

Feedback

# re: Little Puzzlers: First Non-Repeating Character

un·bound·ed
ˌənˈboundəd/
adjective

having or appearing to have no limits.
"the possibilities are unbounded"
synonyms: unlimited, boundless, limitless, illimitable; More

If the sequence is infinite then we must assume the possibility that every character may be repeated at some point. Assume the possibiliy, as it may well be that the infinite set of characters in a sequence may well omit a spcific character,

3/10/2015 8:56 AM | puzzled

# re: Little Puzzlers: First Non-Repeating Character

I'd have to agree with puzzled. The sequence of characters has to be finite for this to work, as the code needs to know the value of the last character.

Now, if you mean "unbounded" to mean a non-fixed-length, but still finite sequence, then there's some fun LINQ to be had.

3/10/2015 12:15 PM | Mike C

# re: Little Puzzlers: First Non-Repeating Character

I have a decent solution, but I'm not sure it's the best. Will there be an "official" solution later, or a cutoff for not posting solutions so we can see what other people came up with?

3/10/2015 12:34 PM | Stephen W

# re: Little Puzzlers: First Non-Repeating Character

Also, thanks for posting this! It's nice to start the day with a little puzzler. Looking forward to the rest of the series.

3/10/2015 12:36 PM | Stephen W

# re: Little Puzzlers: First Non-Repeating Character

Thanks for interesting puzzle! Please post more of these.

3/10/2015 3:26 PM | bazile

# re: Little Puzzlers: First Non-Repeating Character

The sequence being unbounded is not really a concern. If it was, the program would never halt :)

Rather read it as: Given an unbounded sequence, at any point of time, give the answer required.

3/11/2015 12:01 AM | leppie

# re: Little Puzzlers: First Non-Repeating Character

I would use 2 BitArray(char.MaxValue + 1) to check for "present" & "repeated" characters
That's 16 KB.. reasonable.

3/11/2015 12:33 PM | Wizou

# re: Little Puzzlers: First Non-Repeating Character

@puzzled: yes, it is fully possible there will be NO non-repeated character.

@Mike C: not necessarily. In the grand scheme of things, yes it's finite... but it's possible to know at each character read what the first non-repeated character after processing all previous characters is.

@Stephen W: You're welcome! I will post a sample solution after a week from posting it. Of course, answers will vary... Or, you can email your solution and I can reply with advice. Just please don't post the answer in the comments since it could spoil it for others potentially.

@bazile: you're welcome, will do.

@Leppie: that's one way to look at it, yes.

@Wizou: that would certainly be compact and work quite well, yes.

3/11/2015 1:13 PM | Feedback...

# re: Little Puzzlers: First Non-Repeating Character

@Jordan: hey, I got your email, no worries. I purged your solution from the comments for now. Once I post my solution in the next post everyone is welcome to dog-pile on with their solutions as well.

3/11/2015 1:41 PM | Your solutions, eventually

# re: Little Puzzlers: First Non-Repeating Character

@wizou: That will only give to a map of usage. After you've scanned the stream and collected the data, you'd then have to scan the map to see which characters were present but not repeated. Then you've have to figure out came first.

Let's see if we can improve that, Instead of 2 BitArrays, how 'bout a single IntArray(char.MaxValue + 1) (256KB which is still manageable). Store the position is each character. If the item isn't 0, it's a repeated character, so store something else (Int.MaxValue would work). Then scan the map for the lower position.

3/11/2015 4:39 PM | James Curran

# re: Little Puzzlers: First Non-Repeating Character

@James Curran
"If the item isn't 0, ...."
0 would be a perfectly leagal index if the character is the first non repeated character at the beginning of the stream would it not?

@Puzzle setter
1. Can we assume the stream will consist of only upper case alpha numeric characters as may be inferred from your sample?
2. Optimise for speed, size or elegance?

3/12/2015 3:20 AM | puzzled

# re: Little Puzzlers: First Non-Repeating Character

I went for practical.. unless there's a cash prize, I'm satisfied with solving the puzzle :)

3/12/2015 9:06 AM | Jordan

# re: Little Puzzlers: First Non-Repeating Character

@puzzled: in cases like this, I would ask the question to be purposefully ambiguous and hope that the interviewee would ask me clarifying questions (in fact, this lines up with one of the Amazon leadership principles: Deals with Ambiguity.

Then, I would probably have them code it one way, then when they were done ask them how they'd do it differently if I went the other way.

As for your questions:
1. Yes, I would allow that assumption.
2. It depends, we want it to be performant in terms of algorithmic complexity, but I'm not as concerned with micro-optimizations. Smaller size is a plus, but not at the expense of speed or clarity.

3/12/2015 9:24 AM | James Michael Hare

# re: Little Puzzlers: First Non-Repeating Character

indeed my first solution did not remember which non-repeating character was first..
I've got a new solution with a List<char> for non-repeating Chars, and a BitArray for repeated chars. It is very elegant and the algorithm takes only 7 lines of code :)

3/12/2015 9:41 AM | Wizou

# re: Little Puzzlers: First Non-Repeating Character

@puzzled: 0 would be a perfectly legal index .... if you were stupid. The array will be filled with zeros to start. You could spend a lot of effort replacing those zeros with some other out-of-range value, or you can spend no effort at all, and start counting characters with 1 (having the added advantage of putting you in alignment with the entire rest of the world)

Note that CharStream isn't providing an index --- you have to keep count yourself, which mean the starting index value is completely up to your whim.

And note that the problem definition asks for the "position" (which is usually 1-based) and not the "index" (usually 0-based)
And if for some reason you want you want a 0-based answer, that's easy enough also -- just subtract one before printing it out.

3/12/2015 11:14 AM | James Curran

# re: Little Puzzlers: First Non-Repeating Character

However, if we are allowed to assume only uppercase letters, than wizou's initial idea (and my variation) becomes way more practical, as the array that would need to be scanned is only 26 elements long instead of 32767.

3/12/2015 11:20 AM | James Curran

# re: Little Puzzlers: First Non-Repeating Character

@James Curran
"0 would be a perfectly legal index .... if you were stupid."

If you are using 1 based positions then you are trading off the initialization (to which there are some pretty efficient methods) to the '1' addition on each element of the input stream to determine the array index. One might be wise not to discount this cost too quickly.

3/13/2015 3:10 AM | Puzzeld

# re: Little Puzzlers: First Non-Repeating Character

@puzzled: no, I'm not, because we aren't talking about the index to the array, but the value stored there. (i.e., the array is the inverse of the stream -- the index into the array is based on the character from the stream, and the position is the value stored in the array.) The position is based on a counter I initialize & increment. Initializing to 1 is as fast as initializing to 0, hence no penalty.

3/13/2015 9:00 AM | James Curran

# re: Little Puzzlers: First Non-Repeating Character

@Mike C: Not necessarily. LINQ can actually work quite well with infinite sequences. As an experiment I built a small library of extensions, which support this more functional programming paradigm.

Check it out:
https://github.com/tompazourek/Endless

3/16/2015 10:19 AM | Tomas Pazourek

# re: Little Puzzlers: First Non-Repeating Character

What's your preference, folks? Would you rather see the solution as a separate post? Or just put a link to it here?

3/16/2015 4:23 PM | James Hare

# re: Little Puzzlers: First Non-Repeating Character

The first non-repeated character in the sequence or the first non-repeated character in collation order.

given DCBACB, is the answer D or A?

3/20/2015 3:16 PM | Pedant

# re: Little Puzzlers: First Non-Repeating Character

@Pedant: The first non-repeated character in the sequence (i.e. the one that occurs first in the stream)

3/20/2015 3:24 PM | James Michael Hare

James Michael Hare

My Links

News

Blogs I Read

Tag Cloud

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

Little Puzzlers: First Non-Repeating Character

The Problem

Spoiler Alert

Feedback

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character

# re: Little Puzzlers: First Non-Repeating Character