James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , 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

Image Galleries

.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 ]

Powered by: