Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:  1---2---3---4---5---6--NULL          
|
7---8---9---10--NULL
|
11--12--NULL
Output: 1-2-3-7-8-11-12-9-10-4-5-6-NULL
"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        stack = list()
        cur = head
        
        while cur:
            if cur.child:
                if cur.next:
                    stack += [cur.next]
                cur.next = cur.child
                cur.next.prev = cur
                cur.child = None
           
            if not cur.next and stack:
                temp = stack.pop()
                cur.next = temp
                temp.prev = cur
                
            cur = cur.next
        
        return head

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1    
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:

1  
\
2
\
3
\
4
\
5
\
6
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        node, stack = root, []
        
        while node:
            if node.right:
                stack.append(node.right)
            node.right = node.left
            node.left = None
            
            if not node.right and stack:
                temp = stack.pop()
                node.right = temp
            
            node = node.right

Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution:
This quiz is a classical application of the stack data structure. Here we can store indexes of each element which is waiting a bigger element in a stack, and calculate the difference between the current index and stored indexes when the current element is bigger than previous elements. The while loop part is really elegant and tricky, in which judging whether the stack is empty and comparing elements.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)

        stk = list()

        for c_index, value in enumerate(T):
            while stk and T[stk[-1]] < value:
                p_index = stk.pop()
                ans[p_index] = c_index - p_index
            stk.append(c_index)

        return ans

Piles of Boxes

Several days ago, I’ve joined a Hackathon that sponsored by Facebook.

As qualifying people to this event, they hand out an easy algorithm question. Shortly, you need to calculate how less time to move a bunch of boxes in same heigh.

Here is a solution for reference:


import collections

def box(boxesInPiles):
    sortBoxes = collections.OrderedDict(sorted(collections.Counter(boxesInPiles).items()))
    count = 0
    for index, key in enumerate(sortBoxes):
        count += index * sortBoxes[key]
    return count

print(box([4, 5, 5, 2, 4]))

Musician

Let’s say there are two persons, Composer and Performer.

The Composer randomly selects three different Pitch which constructed by two part, Note and Octave. Note in the range of “A” to “G”, Octave in the range of “1” to “3”.

For example, here is a typical Pitch combined by ‘A’ and ‘1’, in which ‘A’ is the Note, and ‘1’ is the Octave.

Once Composer selected a Combination, Performer needs to guess it as quick as possible. After each guess, Performer get a feedback which indicates that:

  • how many pitches in the guess are included in the target (correct pitches)
  • how many pitches have the right note but the wrong octave (correct notes)
  • how many pitches have the right octave but the wrong note (correct octaves)

Now, the question is how to get the corrected answer as less times as possible.

--  Subject  : UniMelb 2019 SM1 COMP90048 Declarative Programming
--  File     : Proj1.hs
--  Author   : Mingzhe Du
--  Origin   : Mon Apr 8 2019 
--  Purpose  : This program for guessing a target chord. In each round of the game,
--             the program will generate a chord from a possible set, and then a feedback 
--             against the guess will be given. Depanding on these feedbacks, the aim of this
--             program is get the correct chord with as less as possible guess times.


module Proj1 (Pitch, GameState, toPitch, feedback, initialGuess, nextGuess) where

-- Pitch structure
data Pitch = Pitch { note :: Char, 
                     octave :: Char   
                   } deriving (Eq)
instance Show Pitch where
    show (Pitch note octave) = [note, octave]

-- Game State
data GameState = GameState { times :: Int,                  -- Guess times
                             cCombinations :: [[[Char]]]    -- Possible set
                           } deriving (Eq, Show)

-- Converting String to Pitch                          
toPitch :: String -> Maybe Pitch
toPitch (a:b:t)
    | not (null t) = Nothing
    | (elem note' ['A'..'G']) && (elem octave' ['1'..'3']) = Just Pitch {note = note', octave = octave'}
    | otherwise = Nothing
    where note' = a
          octave' = b

-- Comparing target chord and guessed chord
feedback :: [Pitch] -> [Pitch] -> (Int,Int,Int)
feedback pitch_a pitch_b
    | (length pitch_a == 3) && (length pitch_b == 3) = (c_p, c_n - c_p, c_o - c_p)
    | otherwise = (0,0,0)
    where get_key key = foldr (\x acc -> key x:acc) []
          c_p = getCounter pitch_a pitch_b 0                              -- Correct pitches
          c_n = getCounter (map note pitch_a) (map note pitch_b) 0        -- Correct notes
          c_o = getCounter (map octave pitch_a) (map octave pitch_b) 0    -- Correct Octaves

-- Initial guess
initialGuess :: ([Pitch], GameState)
initialGuess = (currentGuess, gameState)
    where currentGuess = combinationToPitch  (cGuess)
          gameState = GameState 0 all_combinations 
          all_items = getCombination "ABCDEFG" "123"
          cGuess:all_combinations = subsequencesOfSize 3 all_items        -- New guess and new possible set
          getCombination p_note p_octave = foldr (\x acc -> (map (\y -> y:[x]) p_note) ++ acc) [] p_octave
          combinationToPitch combinations = map (\(Just x) -> x) $ map toPitch combinations     -- Converting String to Pitch

-- Get the next guess
nextGuess :: ([Pitch], GameState) -> (Int,Int,Int) -> ([Pitch],GameState)
nextGuess (pGuess, pGameState) pFeedback = (cGuess, cGameState)
    where cGuess':cCombs = getNewCombination pGuess pCombinations pFeedback
          pCombinations = cCombinations pGameState
          cGuess = toChord cGuess'
          cGameState = GameState ((times pGameState) + 1) cCombs 
          toChord = map (\x -> Pitch (x !! 0) (x !! 1))

-- Help Functions 

-- remove an item from a list
removeItem :: (Eq a) => a -> [a] -> [a]
removeItem _ [] = []
removeItem x (y:ys) 
    | x == y = ys
    | otherwise = y : removeItem x ys 

-- get the number of same elements in two lists
getCounter :: (Eq a) => [a] -> [a] -> Int -> Int
getCounter [] y c = c
getCounter  (x:xs) y c
    | elem x y = getCounter xs (removeItem x y) (c+1)
    | otherwise = getCounter xs y c
 
-- Generate combinations by a specifc size    
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs in if n>l then [] else subsequencesBySize xs !! (l-n)
    where subsequencesBySize [] = [[[]]]
          subsequencesBySize (x:xs) = let next = subsequencesBySize xs in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

-- Converting a string list to pitch list
toChord :: [[Char]] -> [Pitch]
toChord a = map (\x -> Pitch (x !! 0) (x !! 1)) a 

-- retrive a new guess
getNewCombination :: [Pitch] -> [[[Char]]] -> (Int, Int, Int) -> [[[Char]]]
getNewCombination guess allCombinations pFeedback = foldr (\x acc -> if checkFeedback (toChord x) then  x:acc else acc) [] allCombinations
    where checkFeedback nChord = if pFeedback == (feedback guess nChord) then True else False

Haskell moment

Here are some Haskell code chunks, which both are simple recursion algorithms.

Quicksort is a sort of poster child for Haskell because everyone does it to showcase how elegant Haskell is.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSoted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSoted
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "List is empty!"
maximum' [x] = x
maximum' (x:xs) = (max x (maximum' xs))

replicate' :: Int  -> b -> [b]
replicate' n x
    | n <= 0 = []
    | otherwise = (x:(replicate' (n-1) x))

take' :: Int -> [a] -> [a]
take' n (x:xs)
    | n <= 0 = []
    | otherwise = x:(take' (n-1) xs)

reserve' :: [a] -> [a]
reserve' [] = []
reserve' (x:xs) = (reserve' xs) ++ [x]

Sunset

今天无意中看到了几张以前拍的照片,都是晚霞,觉得很漂亮。

这是在 St Kilda拍的 远处就是Melbourne City
这张也是在St Kilda拍的 不过不是同一次
这张其实就是上面那张的加长版 去玩完几天之后 Google Assistant自动帮我把照片给合成在了一起
这张实在 Swinburne University的理工主教学楼上拍的 那天忘记带钥匙了 去房东小哥工作的地方去钥匙 偶遇了火烈一般的晚霞
这张是在Poole St家门口拍的 有一种很南国的感觉 看到这张照片总会想到一个人
Flemingtion的公寓有一个漂亮的天台 North Melbourne的景色尽收眼底
Royal park的巨大草坪 每天早上和晚上都会有很多人来这里遛狗和跑步
之前在郊区住的时候 每天晚上都有这样的景色 旁边就是墨尔本电车博物馆
第一次去St Kilda海边的时候拍的 那个时候还在上语言班
Flinder Station的晚霞 那天刚从图书馆出来 感觉整个人都沐浴在光里