Re: Самая длинная непрерывная последовательность
От: SuhanovSergey  
Дата: 01.08.12 18:05
Оценка: 5 (3) +3 :))) :))
интервьювер: нужно написать Linq запрос, выбирающий самую длинную непрерывную последовательность

кандидат: как-то так

var maxElt = SplitToEqualRanges(s).Aggregate((Tuple<object, int>)null, (max, i) => max == null || i.Item2 > max.Item2 ? i : max);

 static IEnumerable<Tuple<T, int>> SplitToEqualRanges<T>(IEnumerable<T> sequence)
{
    T current = default(T);
    int currentLen = 0;
    foreach (var i in sequence)
    {
        if (currentLen == 0)
        {
            current = i;
        }
        else if (!current.Equals(i))
        {
            yield return new Tuple<T, int>(current, currentLen);
            current = i;
            currentLen = 0;
        }
        ++currentLen;
    }
    if (currentLen > 0)
        yield return new Tuple<T, int>(current, currentLen);
}


интервьювер: тут мало Linq-а и слишком императивно

кандидат: зато
— это понятнее, чем многоэтажный Linq
— гарантированно потребляет минимум ресурсов (O(1) памяти и O(n) времени)
— проходит по последовательно один раз, что позволяет передавать последовательности неизвестной заранее длины

интервьювер: чтобы пройти наш тест ваше решение должно содержать как минимум 5 Linq вызовов

кандидат: хорошо. Вот новое решение со всеми достоинствами предыдущего, и удовлетворяещее вашему требованию

var maxElt2 = 
    s.Zip(Enumerable.Range(0, s.Length), (elt, i) => new { Elt = elt, Idx = i })
    .ZipWithPrev()
    .Where(i => i.Item1.Idx == 0 || !i.Item1.Elt.Equals(i.Item2.Elt))
    .Select(i => i.Item1)
    .Concat(Enumerable.Repeat(new { Elt = (object)null, Idx = s.Length }, 1))
    .ZipWithPrev()
    .Skip(1)
    .Select(i => new {Elt=i.Item2.Elt, Len = i.Item1.Idx - i.Item2.Idx})
    .Aggregate((max, i) => max == null || i.Len > max.Len ? i : max);

static IEnumerable<Tuple<T, T>> ZipWithPrev<T>(this IEnumerable<T> s)
{
    T prev = default(T);
    foreach (var i in s)
    {
        yield return new Tuple<T, T>(i, prev);
        prev = i;
    }
}


интервьювер: совсем другое дело! хоть сейчас в продакшен!
Re: Самая длинная непрерывная последовательность
От: Аноним  
Дата: 02.08.12 05:26
Оценка: 1 (1)
V>Может кто знает способ попроще.
Может так?

public void PrintSequences() {
  var list = "waabbbfawwab".ToCharArray();
  var groupped = list.Select((x, i) => new {
    Prev = list.ElementAtOrDefault(i - 1),
    Curr = x,
    Count = list.Skip(i).TakeWhile(c => c == x).Count(),
  })
  .Where(z => z.Prev != z.Curr);

  foreach (var item in groupped) {
    Console.WriteLine("{0}: {1}", item.Curr, item.Count);
  }
}
Самая длинная непрерывная последовательность
От: vorona  
Дата: 01.08.12 11:42
Оценка:
На собеседовании попросили написать Linq запрос, выбирающий самую длинную непрерывную последовательность.
У меня получилось так:

using System;
using System.Linq;

static class Program
{
    static void Main(string[] args)
    {
        Object[] s = { "w", "a", "a", "b", "b", "b", "f", "a", "w", "w", "a", "b" };
        var result = s.Select((k, i) => new { k, i }).GroupBy(p => p.k, p => p.i).SelectMany(g => g.Select((i, j) => new { k = g.Key, c = i - j }))
            .GroupBy(p => new { p.k, p.c }, p => p.k, (k, e) => new { k = k.k, c = e.Count() }).Aggregate((p1, p2) => p1.c > p2.c ? p1 : p2);
        Console.WriteLine(String.Format("{0} встречается - {1} раз", result.k, result.c));
    }
}


Может кто знает способ попроще.
Re: Самая длинная непрерывная последовательность
От: arkhivania  
Дата: 01.08.12 13:27
Оценка:
Здравствуйте, vorona, Вы писали:

V>На собеседовании попросили написать Linq запрос, выбирающий самую длинную непрерывную последовательность.

V>У меня получилось так:

V>
V>using System;
V>using System.Linq;

V>static class Program
V>{
V>    static void Main(string[] args)
V>    {
V>        Object[] s = { "w", "a", "a", "b", "b", "b", "f", "a", "w", "w", "a", "b" };
V>        var result = s.Select((k, i) => new { k, i }).GroupBy(p => p.k, p => p.i).SelectMany(g => g.Select((i, j) => new { k = g.Key, c = i - j }))
V>            .GroupBy(p => new { p.k, p.c }, p => p.k, (k, e) => new { k = k.k, c = e.Count() }).Aggregate((p1, p2) => p1.c > p2.c ? p1 : p2);
V>        Console.WriteLine(String.Format("{0} встречается - {1} раз", result.k, result.c));
V>    }
V>}
V>


V>Может кто знает способ попроще.


Я вот такой придумал, не думаю, что он сильно правильнее:

var symbols = new[] { "w", "a", "a", "b", "b", "b", "f", "a", "w", "w", "a", "b", "b", "b" };
                var max_count_item = new int[symbols.Length]
                    .Select((w, index) => symbols.Skip(index)).
                    Select(w => new
                    {
                        Item = w.FirstOrDefault(),
                        ItemsAfterCount = w.TakeWhile(w2 => w2 == w.FirstOrDefault()).Count()
                    }).OrderByDescending(w => w.ItemsAfterCount).
                    Select(w => 
                        new { Count = w.ItemsAfterCount, Item = w.Item }).First();
                Console.WriteLine(String.Format("{0} встречается - {1} раз", max_count_item.Item, max_count_item.Count));


Вам бы посоветовал на собедесованиях не использовать переменные в один символ
Re[2]: Самая длинная непрерывная последовательность
От: arkhivania  
Дата: 01.08.12 13:33
Оценка:
Можно Enumerable.Range(0, symbols.Length) использовать вместо new int[]


var max_count_item = Enumerable.Range(0, symbols.Length)
                    .Select((w, index) => symbols.Skip(index)).
                    Select(w => new
                    {
                        Item = w.FirstOrDefault(),
                        ItemsAfterCount = w.TakeWhile(w2 => w2 == w.FirstOrDefault()).Count()
                    }).OrderByDescending(w => w.ItemsAfterCount).
                    Select(w => 
                        new { Count = w.ItemsAfterCount, Item = w.Item }).First();
                Console.WriteLine(String.Format("{0} встречается - {1} раз", max_count_item.Item, max_count_item.Count));
Re[3]: Самая длинная непрерывная последовательность
От: arkhivania  
Дата: 01.08.12 13:34
Оценка:
Поспешил, вот так аккуратнее:

var max_count_item = Enumerable.Range(0, symbols.Length)
                    .Select((w, index) => symbols.Skip(index)).
                    Select(w => new
                    {
                        Item = w.FirstOrDefault(),
                        ItemsAfterCount = w.TakeWhile(w2 => w2 == w.FirstOrDefault()).Count()
                    }).OrderByDescending(w => w.ItemsAfterCount).First();
Re[4]: Самая длинная непрерывная последовательность
От: arkhivania  
Дата: 01.08.12 13:37
Оценка:
Да, нет предела совершенству

var max_count_item = Enumerable.Range(0, symbols.Length)
                    .Select(w => symbols.Skip(w)).
                    Select(w => new
                    {
                        Item = w.FirstOrDefault(),
                        ItemsAfterCount = w.TakeWhile(w2 => w2 == w.FirstOrDefault()).Count()
                    }).OrderByDescending(w => w.ItemsAfterCount).First();
                Console.WriteLine(String.Format("{0} встречается - {1} раз", max_count_item.Item, max_count_item.ItemsAfterCount));
Re: Самая длинная непрерывная последовательность
От: Thorik  
Дата: 02.08.12 10:41
Оценка:
Здравствуйте, vorona, Вы писали:
V>Может кто знает способ попроще.

var result = s.Select((v, i) => new {c = s.Skip(i).TakeWhile(v1 => v1 == v).Count(), el = v}).OrderByDescending(v => v.c).FirstOrDefault();
Re: Самая длинная непрерывная последовательность
От: Аноним  
Дата: 02.08.12 12:27
Оценка:
V>Может кто знает способ попроще.

var arr = new char[] {'a', 'b', 'c', 'c', 'c', 'a','d','d','d','a', 'a', 'a', 'a'};
var maxSeq = arr.
  Select(
    (ch1, idx) => arr.Skip(idx).TakeWhile(ch2 => ch2 == ch1).ToArray()).
  Aggregate((agg, next) => next.Length > agg.Length ? next : agg);
Re[2]: Самая длинная непрерывная последовательность
От: 1067  
Дата: 03.08.12 22:56
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>интервьювер: нужно написать Linq запрос, выбирающий самую длинную непрерывную последовательность


SS>кандидат: как-то так


SS>
SS>var maxElt = SplitToEqualRanges(s).Aggregate((Tuple<object, int>)null, (max, i) => max == null || i.Item2 > max.Item2 ? i : max);

SS> static IEnumerable<Tuple<T, int>> SplitToEqualRanges<T>(IEnumerable<T> sequence)
SS>{
SS>    T current = default(T);
SS>    int currentLen = 0;
SS>    foreach (var i in sequence)
SS>    {
SS>        if (currentLen == 0)
SS>        {
SS>            current = i;
SS>        }
SS>        else if (!current.Equals(i))
SS>        {
SS>            yield return new Tuple<T, int>(current, currentLen);
SS>            current = i;
SS>            currentLen = 0;
SS>        }
SS>        ++currentLen;
SS>    }
SS>    if (currentLen > 0)
SS>        yield return new Tuple<T, int>(current, currentLen);
SS>}
SS>


SS>интервьювер: тут мало Linq-а и слишком императивно


SS>кандидат: зато

SS>- это понятнее, чем многоэтажный Linq
SS>- гарантированно потребляет минимум ресурсов (O(1) памяти и O(n) времени)
SS>- проходит по последовательно один раз, что позволяет передавать последовательности неизвестной заранее длины

SS>интервьювер: чтобы пройти наш тест ваше решение должно содержать как минимум 5 Linq вызовов


SS>кандидат: хорошо. Вот новое решение со всеми достоинствами предыдущего, и удовлетворяещее вашему требованию


SS>
SS>var maxElt2 = 
SS>    s.Zip(Enumerable.Range(0, s.Length), (elt, i) => new { Elt = elt, Idx = i })
SS>    .ZipWithPrev()
SS>    .Where(i => i.Item1.Idx == 0 || !i.Item1.Elt.Equals(i.Item2.Elt))
SS>    .Select(i => i.Item1)
SS>    .Concat(Enumerable.Repeat(new { Elt = (object)null, Idx = s.Length }, 1))
SS>    .ZipWithPrev()
SS>    .Skip(1)
SS>    .Select(i => new {Elt=i.Item2.Elt, Len = i.Item1.Idx - i.Item2.Idx})
SS>    .Aggregate((max, i) => max == null || i.Len > max.Len ? i : max);

SS>static IEnumerable<Tuple<T, T>> ZipWithPrev<T>(this IEnumerable<T> s)
SS>{
SS>    T prev = default(T);
SS>    foreach (var i in s)
SS>    {
SS>        yield return new Tuple<T, T>(i, prev);
SS>        prev = i;
SS>    }
SS>}
SS>


SS>интервьювер: совсем другое дело! хоть сейчас в продакшен!


Хватило бы и обычного foldl:


Object[] s = { "w", "a", "a", "a", "b", "b", "b", "b", "f", "a", "w", "w", "a", "b" };

var foldResult = s.Aggregate(new Tuple<int,object,int,object> (0, null, 0, null), (acc, item) => {
    if(acc.Item2 != item)
    {
        // Reset
        acc = new Tuple<int, object, int, object>(1, item, acc.Item3, acc.Item4);
    }
    else
    {
        // Increase
        acc = new Tuple<int, object, int, object>(acc.Item1+1,acc.Item2, acc.Item3, acc.Item4);
    }

    if(acc.Item3 < acc.Item1)
    {
        // Maximum
        acc = new Tuple<int, object, int, object>(acc.Item1, acc.Item2, acc.Item1, acc.Item2);
    }

    return acc;
});

Console.WriteLine("(Item:Count) -> ({0}:{1})", foldResult.Item4, foldResult.Item3);
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.