James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1494 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

Solution–Little Puzzlers: First Non-Repeating Character

This is the way I would go about this problem if I were asked to perform it at an evaluation. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations.

When solving these sorts of problems, the first thing you should do before writing any code is test your assumptions and clarify requirements. Often times tech companies use these sort of questions to see if you just dive into coding with no set design, or if you really think out the edge cases.

First thing I would do would be to question the makeup of the sequence of characters. The example shows only letters, but it's possible the example given was just being simplistic so I shouldn't assume that. If the person asking the problem would reply that yes, indeed, it is only letters (assuming English), I would then ask if they would conflate uppercase and lower case letters or if they'd consider them separate. Once I know my full problem space, I can pick the best data structure for the task.

I would definitely not try to read the entire stream into a list​, as this could get very memory intensive if the stream is extremely long (since it's unbounded). Thus, I should look for ways to solve the problem as I go in one linear pass.

So, for each character, I want to be able to note, in effect, two things:

  1. Have i seen it before, and
  2. Where did i first see it.

So, we could either design a small POCO to hold the position and whether it was found, or we could use the same indicator for both. After all, we only care about position if we don't find a duplicate.

If I were just dealing with uppercase letters, I would build an array of int and initialize all elements to -1. Or if I were dealing with a larger data set, I'd use a Dictionary<char,int>. Then, for each char pass, I'd look it up in the array/table. If the char doesn't exist in the table, or if it's -1 in the array, I'd note the position as the current position.

If the char does exist in the table or in the array, I'd set it to another value such as int.MaxValue. Then, once I've read all the characters, I'd find the minimum position in the table where pos >= 0 (linear pass) and print the pos and the char as long as pos != int.MaxValue.

Let’s assume that the examiner asked for only the uppercase alphabet, but you can imagine how to modify this example for different input variations.

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

// Base interface for char stream 
public interface ICharStream
{
    bool HasNext { get; }
    char GetNext();
}

// Test implementation of char stream 
public class RandomCharStream : ICharStream
{
    private readonly int maxSize;
    private readonly Random generator = new Random();
    private int generatedCount;

    // Creates a random stream of characters 
    public RandomCharStream(int maxSize)
    {
        this.maxSize = maxSize;
        this.generatedCount = 0;
    }

    // Returns true if still characters to generate 
    public bool HasNext
    {
        get { return generatedCount < maxSize; }
    }

    // Generates a random character  
    public char GetNext()
    {
        ++generatedCount;
        return (char)('A' + generator.Next(0, 26));
    }
}

// Solution for problem 1 
public class Problem1
{
    public static void Main()
    {
        var charMap = Enumerable.Repeat(-1, 26).ToArray();
        var stream = new RandomCharStream(20);

        int pos = 0;
        while (stream.HasNext)
        {
            var ch = stream.GetNext();
            var index = ch - 'A';

            Console.Write(ch + " ");
            if (charMap[index] != int.MaxValue)
            {
                charMap[index] = charMap[index] == -1 ? pos : int.MaxValue;
            }
            ++pos;
        }
        Console.WriteLine();
        int firstNonRepeatedPos = charMap.Where(i => i >= 0).Min();

        if (firstNonRepeatedPos != int.MaxValue)
        {
            Console.WriteLine("The first non - repeated char was at position: " + firstNonRepeatedPos);
        }
        else { 
            Console.WriteLine("All characters were repeated at least once.");
        }
    }
}

Print | posted on Sunday, March 15, 2015 8:54 PM | Filed Under [ My Blog C# Software .NET Little Puzzlers ]

Feedback

Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

fails with an empty stream ;-)

Note that restricting the characters to A-Z has great impact upon deciding the optimal algorithm to solve the question
3/16/2015 8:56 AM | Wizou
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

@Wizou: I agree, but that's just example of one way I would go based on how the examiner reacted to my questions.

If the examiner had stated that a much larger set of characters were possible (such as Unicode) I would have probably favored a Dictionary instead.
3/16/2015 9:40 AM | James Michael Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Isn't ICharStream basically the same thing as IEnumerable<char>? Why reimplement the wheel?
3/16/2015 9:48 AM | Tomáš Pažourek
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Tomas: It was part of the original programming question and was meant to be more of a language neutral-ish interface.
3/16/2015 9:53 AM | UGH
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

I posted my solution(s) here: http://honestillusion.com/blog/2015/03/16/first-non-repeating-character-my-solution/
3/16/2015 9:54 AM | James Curran
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Also, I think you failed your own quiz... Your were supposed to print position AND VALUE. You only print position, and you don't have a simple way of finding value.
3/16/2015 10:03 AM | James Curran
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

You're right, I forgot to print the value, but I *do* have a simple way to do it :-)

I'll update the code when I get home, but essentially I just have to take the index of the min value in the array, add 'A' to it, and viola.
3/16/2015 10:21 AM | James Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

@James Hare -- Which would involve scanning the array AGAIN. It would be best to abandon the linq methods, and find both in one foreach loop.
3/16/2015 10:34 AM | James Curran
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

@JamesCurran: It would only involve re-scanning the array *if* i intended to use another LINQ expression, which I did not say that I intended to. Don't assume before I post my update please.
3/16/2015 10:38 AM | James Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

So, in short, I'd change the latter half of the code to the following:

Console.WriteLine();
int minValue = int.MaxValue;
int foundIndex = -1;
for (int i = 0; i < charMap.Length; ++i)
{
if (charMap[i] >= 0 && charMap[i] < minValue)
{
foundIndex = i;
minValue = charMap[foundIndex];
}
}

if (foundIndex >= 0)
{
Console.WriteLine("The first non-repeated char was " + (char)(foundIndex + 'A') + " at position: " + charMap[foundIndex]);
}

else
{
Console.WriteLine("All characters were repeated at least once.");
}

It's not as elegant as Linq's Min() routine, but it works and allows me to grab the index of the item, instead of the min item itself, in one pass, which i can then use to find the first non-repeated character and the position.

As I've said, this is just one of many potential solutions.

And yes, Wizzou, you are right! My first code sample wouldn't have protected against an empty stream. Well caught! This one will.
3/16/2015 10:44 AM | James Hare
Gravatar

# Quick Question?

Now that I think about it, is posting the solution like this a mistake? Does it make it too easy to accidentally spoil it for people who haven't read the problem yet?

I was debating if I should continue a separate post for the solution with a spoiler alert tag, or whether i should just put a link in the comments of the old post to a solution in GutHub or something.

Thoughts?
3/16/2015 12:32 PM | James Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Here is my solution (not sticking to the interface provided ;p):

https://gist.github.com/leppie/a72e28a913992cec04ea
3/17/2015 12:26 AM | leppie
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

my solution



private static void Main() {

const int a = (int)'A';
const int z = (int)'Z';
const int NOT_YET_ENCOUNTERED = -1;
const int SECOND_ENCOUNTER = -2;

// intialize the array value (yes, we are ignoring and wasting elements 0 - 'a', but saves the aritmetic on each incoming element)
int[] locations = new int[z + 1];
for (int i = a; i <= z; i++) {
locations[i] = NOT_YET_ENCOUNTERED;
}

int counter = 0;
int index = 0;
ICharStream charStream = new CharStream();

while (charStream.HasNext) {

// determine the element index
index = (int)charStream.GetNext();

int lastPosition = locations[index];
// if the item has not been encountered before
if (lastPosition == NOT_YET_ENCOUNTERED) {
// set the location
locations[index] = counter;
}
else {
// mark as duplicate
locations[index] = SECOND_ENCOUNTER;
}

counter++;
}

// check which and where is the first non repeating character
char lastChar = ' ';
int lastCharPosition = int.MaxValue;

for (int i = a; i <= z; i++) {
// if it is a single occurence
if (locations[i] >= 0) {

// if it occured prior to the last one
if (locations[i] < lastCharPosition) {
lastCharPosition = locations[i];
lastChar = (char)i;
}
}
}

System.Console.WriteLine(string.Format("first non repeating occurrence is at index {0} with value {1} ", lastCharPosition, lastChar));
System.Console.ReadKey();
}
3/17/2015 4:11 AM | puzzled
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

One nit-pick -- Both James Hare's and Leppie's CharStream is based on a Random object -- which in both cases is default-seeded -- meaning you cannot get repeatable runs, which means you can't benchmark accurately. Which also means that unless you print out the characters as you read them (which James does, but leppie does not), you can't even tell if you got the right answer.

3/17/2015 10:01 AM | James Curran
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Keep in mind James, that it's possible leppie tested his program and then removed the output statements. I preferred the random seed so I could test it multiple times with different data. I was not out to necessarily benchmark the same data set repeatedly.
3/17/2015 10:56 AM | James Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

Just for fun, if we accept a little reduction on the stream maximum length, we could replace James latter half with:

var result = charMap.Select((x, i) => x < 0 || x == int.MaxValue ? int.MaxValue : x * 26 + i).Min();
if (result != int.MaxValue)
Console.WriteLine("Answer: letter " + (char)('A'+result%26) + " at " + result/26);
else
Console.WriteLine("All characters are repeated")
3/17/2015 11:24 AM | Wizou
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

mmmh, in order to handle empty stream, add a .DefaultIfEmpty(int.MaxValue) before .Min()
3/17/2015 11:40 AM | Wizou
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

@James Hare: I found the answer helpful. I didn't have time myself to go through and solve this, but the problem intrigued me. It was interesting to see how you proceeded to solve the problem and your final result. Thanks!
3/18/2015 11:00 AM | Jeff Bridgman
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

@Jeff Bridgman: Thanks! I'll try to keep it up :-)
3/19/2015 10:23 AM | James Michael Hare
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

I never needed to print out the random characters, a simple output would not have been hard. I just assumed it had to be correct (unless someone can prove it otherwise ;p).
3/20/2015 4:49 AM | leppie
Gravatar

# re: Solution–Little Puzzlers: First Non-Repeating Character

I know I'm a bit late but here's my solution:

private static char Solution1(char[] chars)
{
if(null == chars || 0 == chars.Length)
return '_';

if(1 == chars.Length)
return chars[0];

var currIndex = 0;
char currChar;
bool invalid = false;

var invalidChars = new HashSet<char>();

while (currIndex < chars.Length)
{
currChar = chars[currIndex];
if (!invalidChars.Contains(currChar))
{
invalid = false;

for (int i = currIndex + 1; i != chars.Length; ++i)
{
var other = chars[i];

if (invalidChars.Contains(other))
continue;

if (currChar == other)
{
invalidChars.Add(other);
invalid = true;
break;
}
}

if (!invalid)
return currChar;
}

currIndex++;
}

return '_';
}
3/26/2015 11:47 AM | Davide Guida
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: