using System;
using System.Collections.Generic;
using System.Linq;
namespace Interview_ConsecutiveSequence
{
class Program
{
public static int GetMaxLengthConsecutiveSequence(int[] numbers)
{
HashSet<int> set = BuildHashSet(numbers);
return AnalyzeHashSet(set);
}
private static HashSet<int> BuildHashSet(int[] numbers)
{
var set = new HashSet<int>();
foreach(int number in numbers)
{
set.Add(number);
}
return set;
}
private static int AnalyzeHashSet(HashSet<int> set)
{
int maxCount = 0;
while(set.Count > 0)
{
int number = set.First();
int count = 0;
int toDelete = number;
while(set.Remove(toDelete))
{
count++;
toDelete++;
}
toDelete = number - 1;
while(set.Remove(toDelete))
{
count++;
toDelete--;
}
if(count > maxCount)
{
maxCount = count;
}
}
return maxCount;
}
private static void Test(string testName, int[] numbers, int expected)
{
if (GetMaxLengthConsecutiveSequence(numbers) == expected)
{
Console.WriteLine(string.Format("{0} passed.", testName));
}
else
{
Console.WriteLine(string.Format("{0} FAILED.", testName));
}
}
private static void Test1()
{
int[] numbers = { 1, 300, 3, 2, 101, 4, 102 };
int expected = 4;
Test("test1", numbers, expected);
}
private static void Test2()
{
int[] numbers = { 1, 2, 3, 4, 5 };
int expected = 5;
Test("test2", numbers, expected);
}
private static void Test3()
{
int[] numbers = { 5, 4, 3, 2 };
int expected = 4;
Test("test3", numbers, expected);
}
private static void Test4()
{
int[] numbers = { 1, 3, 2, 4, 5, 19, 18, 17, 16 };
int expected = 5;
Test("test4", numbers, expected);
}
private static void Test5()
{
int[] numbers = { 1, 6, 3, 5, 9, 7 };
int expected = 3;
Test("test5", numbers, expected);
}
static void Main(string[] args)
{
Test1();
Test2();
Test3();
Test4();
Test5();
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgSW50ZXJ2aWV3X0NvbnNlY3V0aXZlU2VxdWVuY2UKewogICAgY2xhc3MgUHJvZ3JhbQogICAgewogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50IEdldE1heExlbmd0aENvbnNlY3V0aXZlU2VxdWVuY2UoaW50W10gbnVtYmVycykKICAgICAgICB7CiAgICAgICAgICAgIEhhc2hTZXQ8aW50PiBzZXQgPSBCdWlsZEhhc2hTZXQobnVtYmVycyk7CiAgICAgICAgICAgIHJldHVybiBBbmFseXplSGFzaFNldChzZXQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgSGFzaFNldDxpbnQ+IEJ1aWxkSGFzaFNldChpbnRbXSBudW1iZXJzKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIHNldCA9IG5ldyBIYXNoU2V0PGludD4oKTsKICAgICAgICAgICAgZm9yZWFjaChpbnQgbnVtYmVyIGluIG51bWJlcnMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHNldC5BZGQobnVtYmVyKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIHNldDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIGludCBBbmFseXplSGFzaFNldChIYXNoU2V0PGludD4gc2V0KQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1heENvdW50ID0gMDsKICAgICAgICAgICAgd2hpbGUoc2V0LkNvdW50ID4gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IG51bWJlciA9IHNldC5GaXJzdCgpOwogICAgICAgICAgICAgICAgaW50IGNvdW50ID0gMDsKICAgICAgICAgICAgICAgIGludCB0b0RlbGV0ZSA9IG51bWJlcjsKCiAgICAgICAgICAgICAgICB3aGlsZShzZXQuUmVtb3ZlKHRvRGVsZXRlKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICAgICAgICAgIHRvRGVsZXRlKys7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgdG9EZWxldGUgPSBudW1iZXIgLSAxOwogICAgICAgICAgICAgICAgd2hpbGUoc2V0LlJlbW92ZSh0b0RlbGV0ZSkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgICAgICB0b0RlbGV0ZS0tOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGlmKGNvdW50ID4gbWF4Q291bnQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgbWF4Q291bnQgPSBjb3VudDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIG1heENvdW50OwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0KHN0cmluZyB0ZXN0TmFtZSwgaW50W10gbnVtYmVycywgaW50IGV4cGVjdGVkKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKEdldE1heExlbmd0aENvbnNlY3V0aXZlU2VxdWVuY2UobnVtYmVycykgPT0gZXhwZWN0ZWQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHN0cmluZy5Gb3JtYXQoInswfSBwYXNzZWQuIiwgdGVzdE5hbWUpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHN0cmluZy5Gb3JtYXQoInswfSBGQUlMRUQuIiwgdGVzdE5hbWUpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0MSgpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAxLCAzMDAsIDMsIDIsIDEwMSwgNCwgMTAyIH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDQ7CiAgICAgICAgICAgIFRlc3QoInRlc3QxIiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0MigpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAxLCAyLCAzLCA0LCA1IH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDU7CiAgICAgICAgICAgIFRlc3QoInRlc3QyIiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDMoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgNSwgNCwgMywgMiB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA0OwogICAgICAgICAgICBUZXN0KCJ0ZXN0MyIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDQoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgMywgMiwgNCwgNSwgMTksIDE4LCAxNywgMTYgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNTsKICAgICAgICAgICAgVGVzdCgidGVzdDQiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3Q1KCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDEsIDYsIDMsIDUsIDksIDcgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gMzsKICAgICAgICAgICAgVGVzdCgidGVzdDUiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBUZXN0MSgpOwogICAgICAgICAgICBUZXN0MigpOwogICAgICAgICAgICBUZXN0MygpOwogICAgICAgICAgICBUZXN0NCgpOwogICAgICAgICAgICBUZXN0NSgpOwogICAgICAgIH0KICAgIH0KfQo=