chaoxu

\begin{itemize}
  \item Tree reconstruction from inorder and postorder.
  \item find path sum in the tree \url{https://leetcode.com/problems/path-sum-ii/}
  \item longest substring without repeated character. \url{https://leetcode.com/problems/longest-substring-without-repeating-characters/}
  \item Longest Palindromic Substring \url{https://leetcode.com/problems/longest-palindromic-substring/}
  \item Container With Most Water \url{https://leetcode.com/problems/container-with-most-water/solution/}
  \item 3sum, 4sum, ksum
  \item next permutation \url{https://leetcode.com/problems/next-permutation/}
  \item Permutation generation \url{https://leetcode.com/problems/permutations-ii/}
  \item Group Anagrams \url{https://leetcode.com/problems/group-anagrams/}

chaoxu

import Data.List
import Control.Applicative
import Control.Arrow
import Control.Monad
import RankSelection
-- this provides selectRank, which outputs the kth largest element of a list
-- selectRank :: Ord a => [a] -> Int -> a

type Matrix a = (Int->Int->a, Int, Int)

chaoxu

# Logic:
#   a > b --> discard everything to the left of a
#   a < b --> discard everything to the right of b
#   a = b = c --> we know that either
#     a) all elements between a and b are all equal to b, or
#     b) all elements between b and c are all equal to b.
#     time for a linear search.
 
def minvalley(xs, l, r):
   while True:

chaoxu

import           Control.Arrow       (second)
import           Data.List.Extra     (sort, groupSortOn)

-- Assuming we sort through counting sort 
-- Including the sort inside groupSortOn
-- Sorting of tuples is radix sort with base = max coordinate

-- type alias for readability
type Partition x = [[x]]
type EquivalenceClass x = [x]

chaoxu

1. mean 
+/⍵÷(≢⍵)
2. median
{.5×+/(⍵,⍵)[(⍋⍵,⍵)[(≢⍵),1+≢⍵]]}(⌊/⍵),⍵,⌈/⍵
3. mode
{(⍵[;2]=⌈/⍵[;2])/⍵[;1]}{⍺,⍴⍵}⌸,
4. Write a dfn that takes vectors as its left and right arguments and returns them "meshed" into a single vector
formed by alternately taking successive elements from each argument. The arguments do not have to be the
same length. 
{A ← (⍴⍺)⌊⍴⍵ ⋄ (,⍉↑A↑¨⍺ ⍵),⊃,/A↓¨⍺ ⍵}

chaoxu

title
Puzzles

This collection has some hard problems with optimal solutions.

• Let $x=p/q$ be an rational number, where $p$ and $q$ are integers. There is a function $f_x$, such that $f_x(y)$ tells you if $x < y$, $x > y$ or $x=y$. What is the maximum number of queries of $f_x$ needed to find $x$? http://stackoverflow.com/questions/5440688/the-guess-the-number-game-for-arbitrary-rational-numbers

• You have a data stream of a permutation of ${1,\ldots,n}$. However you know $k$ of the elements will be missing because the communication channel has fault. How can you detect which numbers are missing? http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe

• Data structure for loaded dice? http://stackoverflow.com/questions/5027757/data-structure-for-loaded-dice

chaoxu

#!/bin/sh
# See jakobm's code at https://bbs.archlinux.org/viewtopic.php?pid=903057#p903057
( slock && xset dpms 0 0 600 ) &
xset dpms 0 0 2
xset dpms force standby

chaoxu

% ========================-*- LaTeX -*-=========================
%
%   chao.sty -- modified from jeffe.sty
%   jeffe.sty can be found at http://web.engr.illinois.edu/~jeffe/pubs/latex.html
%
% ==========================================================

\RequirePackage{latexsym,amsmath}
\RequirePackage[dvipsnames,usenames]{xcolor}
%\PassOptionsToPackage{hyphens}{url}

chaoxu

This is a python implementation of a subset sum algorithm by Konstantinos Koiliaris and me.

Given a set of n positive integers, the algorithm finds all the values t<=u such that there exists a subset that sums to t.

The running time is O(sqrt(n)u) with some extra polylog factors.

There is also a C++ implementation of the standard dynamic programming algorithm for subset sum. The DP table gets packed into 64 bit unsigned integers. It's probably the fastest possibe implementation of the O(nu) time algorithm without getting into ASM and parallelism.

chaoxu

data = {0, 10, 0, 20, 10, 30, 0};
breaks = MapIndexed[
   With[{pos = First[#2], y1 = First[#], 
      y2 = Last[#]}, {y1 (1 + pos - x) + y2 (x - pos), 
      pos <= x < pos + 1}] &, Partition[data, 2, 1]];
f[x_] := Piecewise[breaks];
Plot[f[x], {x, 1, Length[data]}]
h[lambda_] := 
 lambda + Max[
   Table[MaxValue[{breaks[[i]][[1]] - x,