Entrevista de árbol monoidal en Haskell -- performance campo con beginner campo con haskell campo con tree campo con interview-questions camp codereview Relacionados El problema

Monoidal tree interview in Haskell


3
vote

problema

Español

Estaba trabajando en la siguiente pregunta de la entrevista:

Dada una matriz de enteros, devuelva una nueva matriz de modo que cada elemento en el índice i de la nueva matriz es el producto de todos los números en el ARRAY ORIGINAL, excepto el en i .

Por ejemplo, si nuestra entrada fue [1, 2, 3, 4, 5] , la salida esperada sería [120, 60, 40, 30, 24] . Si nuestra entrada fue [3, 2, 1] , el La salida esperada sería [2, 3, 6] .

Seguimiento: ¿Qué pasa si no puede usar División?

Decidí hacer la pregunta de seguimiento en Haskell:

  9988776655544336  

El algoritmo se ejecuta en Î~ (n log n) que creo que es óptimo. Nuevo en Haskell para que todos los comentarios sean bienvenidos.

Original en ingles

I was working on the following interview question:

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

I decided to do the followup question in Haskell:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-} import Control.Monad (join) import Control.Arrow ((***)) import Data.Sequence (Seq) import qualified Data.Sequence as Seq import Data.Monoid (Product(..), getProduct)  mapTuple = join (***)  pattern Empty   <- (Seq.viewl -> Seq.EmptyL) pattern x :< xs <- (Seq.viewl -> x Seq.:< xs)  data Tree a = Leaf a | Branch a (Tree a, Tree a) label :: Tree a -> a label (Leaf a) = a label (Branch a _) = a  {- Create a complete binary tree, such that each subtree contains the concat of all  - elements under it. -} makeTree :: Monoid a => Seq a -> Tree a makeTree Empty = undefined makeTree (label :< Empty) = Leaf label makeTree s =   let midpoint = Seq.length s `div` 2 in   let subseq = Seq.splitAt midpoint s in   let subtrees = mapTuple makeTree subseq in   let subtreeLabels = mapTuple label subtrees in   let label = uncurry mappend subtreeLabels in   Branch label subtrees  {- Zippers. -} data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) type Breadcrumbs a = [Crumb a] type Zipper a = (Tree a, Breadcrumbs a)  goLeft :: Zipper a -> Zipper a goLeft (Branch x (l, r), bs) = (l, LeftCrumb x r:bs) goLeft (Leaf _, _) = error "Nothing to go left into"  goRight :: Zipper a -> Zipper a goRight (Branch x (l, r), bs) = (r, RightCrumb x l:bs)   goRight (Leaf _, _) = error "Nothing to go right into"  -- Concat of all elements except the one corresponding to the given crumbs concatAllExcept :: Monoid a => Breadcrumbs a -> a concatAllExcept = concatAllExceptRev . reverse where   concatAllExceptRev [] = mempty   concatAllExceptRev ((LeftCrumb _ subtree) : xs) =     concatAllExceptRev xs <> label subtree   concatAllExceptRev ((RightCrumb _ subtree) : xs) =     label subtree <> concatAllExceptRev xs  -- Return a list of zippers pointing to the leafs of the tree dfsList :: Tree a -> [Zipper a] dfsList t =   reverse $ dfsListHelper (t, []) [] where     dfsListHelper zipper@(Leaf _, _) accum = zipper : accum     dfsListHelper zipper@(Branch _ _, _) accum =       -- Since this is a Branch node, both [goLeft] and [goRight] will work.       let l = goLeft zipper           r = goRight zipper in       dfsListHelper r (dfsListHelper l accum)  {- Produces a list such that the ith element is the concat of all elements in the  - original list, excluding the ith element. -} concatAllExceptEach :: Monoid a => [a] -> [a] concatAllExceptEach = map (concatAllExcept . snd) . dfsList . makeTree . Seq.fromList  answer :: [Integer] -> [Integer] answer = map getProduct . concatAllExceptEach . fmap Product  main = do   print $ answer [3, 10, 33, 4, 31, 31, 1, 7]   print $ answer [1, 2, 3, 4, 5]   print $ concatAllExceptEach ["A", "B", "C", "D"] 

Algorithm runs in xcex98(n log n) which I believe is optimal. New to Haskell so all feedback welcome.

              
   
   

Lista de respuestas

1
 
vote

¡Bienvenido! Aquí están mis pensamientos lo que podría mejorarse:

  1. Para declaraciones de nivel superior, siempre incluyen tipos. Estoy bastante seguro en unas pocas semanas, será difícil darse cuenta de lo que

      def print_calendar(offset, month_length)   puts "Mon Tue Wed Thu Fri Sat Sun"   dates = [nil] * offset + (1..month_length).to_a   dates.each_slice(7) do |week|     puts week.map { |date| date.to_s.rjust(3) }.join(' ')   end end 4  

    significa sin saber que su tipo es

      def print_calendar(offset, month_length)   puts "Mon Tue Wed Thu Fri Sat Sun"   dates = [nil] * offset + (1..month_length).to_a   dates.each_slice(7) do |week|     puts week.map { |date| date.to_s.rjust(3) }.join(' ')   end end 5  

    Además, ya que no necesita flechas en ningún otro lugar, tiene sentido especializar el tipo para evitar errores accidentales y obtener mensajes de error más agradables.

  2. Pondría una nueva línea entre los datos "... 'y' etiqueta '. Mantener el estilo consistente ayuda a la legibilidad Muy Mucho.

  3. No necesita anidar las expresiones 'deje'. Puedes escribir solo

      def print_calendar(offset, month_length)   puts "Mon Tue Wed Thu Fri Sat Sun"   dates = [nil] * offset + (1..month_length).to_a   dates.each_slice(7) do |week|     puts week.map { |date| date.to_s.rjust(3) }.join(' ')   end end 6  
  4. En lugar de crear una secuencia y luego convertirla en un árbol equilibrado, puede convertir una lista directamente en un árbol equilibrado en o (n) . ¡Este es un buen ejercicio por sí mismo!

  5. Use haddock markup en comentarios, puedes Luego genere una documentación agradable muy fácilmente.

  6. El algoritmo se ejecuta en Î~ (n log n) que creo que es óptimo.

    ¿Estás seguro?

 

Welcome! Here are my thoughts what could be improved:

  1. For top-level declarations, always do include types. I'm pretty sure in a few weeks it'll be difficult to realize what

    mapTuple = join (***) 

    means without knowing that it's type is

    mapTupple :: (b' -> c') -> (b', b') -> (c', c') 

    Also as you don't need arrows anywhere else, it makes sense to specialize the type to avoid accidental errors and get nicer error messages.

  2. I'd put a newline betweek 'data...' and 'label'. Keeping consistent style helps readability very much.

  3. You don't need to nest 'let' expressions. You can write just

    let midpoint = Seq.length s `div` 2     subseq = Seq.splitAt midpoint s     ... in Branch label subtrees 
  4. Instead of creating a sequence and then converting it into a balanced tree, you can convert a list directly into a balanced tree in O(n). This is a nice exercise on its own!

  5. Use Haddock markup in comments, you can then generate nice documentation very easily.

  6. Algorithm runs in xcex98(n log n) which I believe is optimal.

    Are you sure?

 
 

Relacionados problema

1  Cuenta las precipitaciones acumuladas en una cadena de montaña 2D  ( Count the accumulated rainfall in a 2d mountain range ) 
desafío: cuenta cuánta lluvia se recogerá en los valles entre los picos de una cordillera en un mundo 2D. La gama de montaña se define por una única ...

2  Cola de bloqueo delimitada  ( Bounded blocking queue ) 
¿Puede alguien por favor revise este código para mí? No he implementado todos los métodos para la simplicidad. NSUSerDefaults1 Preguntas abiertas: l...

8  Escriba un método para reemplazar todos los espacios en una cadena con% 20  ( Write a method to replace all spaces in a string with 20 ) 
He implementado una solución a este agrietamiento la pregunta de la entrevista de codificación: Escriba un método para reemplazar todos los espacios en una ...

11  Optimizando el corrector de anagramas Java (comparar 2 cadenas)  ( Optimizing java anagram checker compare 2 strings ) 
Un anagrama es como una mezcla de las letras en una cadena: pots es un anagrama de detener wilma es un anagrama de ilwma Estoy pasando por el ...

3  Codificación de longitud de ejecución  ( Run length encoding ) 
Dada una cadena de entrada, escriba una función que devuelva la longitud de ejecución Cadena codificada para la cadena de entrada. Por ejemplo, si la cad...

5  Compruebe si dos cadenas son permutaciones entre sí  ( Check if two strings are permutations of one another ) 
Estoy trabajando en mi camino a través de "Cracking The Coding Entrevistion" problemas y ha terminado de implementar esta pregunta: "Dadas, dos cuerdas, escri...

18  Invirtiendo una cadena  ( Reversing a string ) 
Tuve esto como una pregunta de entrevista, y el entrevistador señaló esto. Esto es lo que escribí: //C# Syntax here public string Reverse(string s) { c...

3  Invertir un mapa de puntuación de letras de Scrabble  ( Inverting a scrabble letter score map ) 
Pregunta: El sistema antiguo almacenó una lista de letras por puntaje: 1 punto: "A", "E", "I", "O", "U", "L", "N", "R", "S", "T", 2 puntos: "D", "G", ...

3  Tarea de entrevista de juego de blackjack  ( Blackjack game interview task ) 
Como parte de una entrevista reciente, me asignaron escribir un pequeño programa de blackjack. Después de enviar la solución, recibí una respuesta que "la sol...

2  Contando un ciclo  ( Counting a cycle ) 
Una pregunta de entrevista que tengo - Cada elemento de un int Matriz puntos al otro elemento, eventualmente creando un ciclo. A partir de array[0] , ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos