One headlight

I have this evil idea to reorganize the lyrics of this song I am recently addicted. Honestly, I don't even know why I love this song, probably because of the current mess (thesis, defense, moving...) I am dealing with. I used my old Markov Chain code and it's indeed a beautiful song: no matter how I try to destroy it, it still means something.

As in the original lyric:
"This place is always such a mess
Sometimes I think I'd like to watch it burn"


Here is my favorite one:
"same

But me and Cinderella

We can drive it all together

We can drive it all together

We can drive it all together

We put it all together

We put it all together

We put it home With one headlight

Well it home With one

headlight Well it home With one headlight

She ran until she's out of cheap wine cigarettes

This place is forever

There's got to be something better than In the middle But me

Hey come on try a little

Nothing is always seemed such a little

Nothing is old

It feels just like a little Nothing is dead

We'll run until

there's got to be an opening

Somewhere here in front of cheap wine cigarettes This place

Hey , Hey come on try a little

Nothing is always such a little

Nothing is forever

There's got to be an opening

Somewhere here in between the end

it's cold

It feels just her window ledge

Hey , I'd like to watch it

must be something better than In the county line ."

It's hard to be in spotlight

It's also hard to be a wallflower. 

Silicon Valley S2E1: What does Erlich Bachman's binary T-shirt mean?

I saw this Quora question today. It's interesting. Of course as shown in the answer, we can use a binaryToText converter, but what's the fun part if I don't write my own. I am learning Python, so here is the Python and Java version:

Python:

import math
def binaryToText(binary):
 l = len(binary)
 c = 0
 i = 0
 for ch in binary:
  c += math.pow(2, l - i - 1) * (ord(ch) - ord('0'))
  i += 1
 return chr(int(c))

def main():
 Tshirt = ['01000010','01101001','01110100','01100011','01101111','01101001','01101110']
 for t in Tshirt:
  print(binaryToText(t), end = '')
 print('\n')

main()

Java:

public class BinaryToText {
 public static char binaryToText(String binary){
  int c = 0;
  int l = binary.length();
  for(int i = 0; i < l; i++)
   c += (int)Math.pow(2, l - i - 1) * (int)(binary.charAt(i) - '0');
  System.out.println(c);
  return (char)c;
 }

 public static void main(String[] args) {
  String[] Tshirt = {"01000010",
       "01101001",
       "01110100",
       "01100011",
       "01101111",
       "01101001",
       "01101110"
  };
  for(String t : Tshirt)
   System.out.print(binaryToText(t));
  System.out.println();
 }
}

Probably I still haven't got rid of the whole Java class concept, I don't find many advantages of using Python. But, just for fun.

Data Structures in Python compared with Java: Sets

A set is an unordered collection with no duplicate elements. Set models the mathematical set abstraction. Both Python and Java use hashtable as the underlying data structure of set.

Creating a set
Also allows different types of element

#empty set
basket = set()
basket = {'shirley',2014}

Python also allows for creating a character set using the following method:

basket = set('abaabab')

Duplicate elements will be removed.

In Java:

Set basket = new HashSet ()

Of course only one type is allowed.
Java also provide constructor to create a hash set from another collection, if created from a collection that contains duplicate elements, duplicate ones will be removed.

List listA = new ArrayList ();
  listA.add(1);
  listA.add(2);
  listA.add(1);
  Set t = new HashSet (listA);

Union
In Python, it is the same way as you do binary operation:

>>> a = {'shirley',2015}
>>> b = {'dora', 2014}
>>> a | b
{'shirley', 'dora', 2014, 2015}

In Java, we use addAll(Collection<? extends E> c) method:

a.addAll(b);

Complements
Python:

>>> a = set('aabbccabc')
>>> b = set('abdd')
>>> a - b
{'c'}

It will return the elements in a that is not in b.

In Java, we use removeAll(Collection<? extends E> c) method:

a.remveAll(b);

Intersection
Python:

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a&b
{'a', 'b'}
>>> 

Java: retainAll(Collection<? extends E> c) method:

a.retainAll(b);

XOR (?)
Actually, it is elements in a or b but not both

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a^b
{'d', 'c'}

I couldn't find any built in methods to do this in Java, however, we can always do a little bit coding to acquire the desired result:

Set a = new HashSet ();
  a.add(1);
  a.add(2);
  Set b = new HashSet ();
  b.add(2);
  b.add(6);
  Set c = new HashSet(a);
  c.removeAll(b);
  Set d = new HashSet(b);
  d.removeAll(a);
  c.addAll(d);

Sorted sets:
Java provides TreeSet data structure. It is based on red - black tree implementation (See here for implementations). In Python, I think this needs to be acquired by using lambda function(?). I am not quite familiar with the lambda function, but I will take a look later.



References:
[1]. Not-very-familiar Python doc
[2]. www.grepcode.com
[3]. Beloved Java doc
[4]. www.codatlas.com

Data Structures in Python compared with Java: Array, List, and ArrayList

At the hardware level, most computer architectures provide a mechanism for creating and using 1-D arrays. A one-dimensional array, is composed of multiple sequential elements stored in contiguous bytes of memory. The entire contents of an array are identified by a single name. It holds a fixed number of values of a single type. The length of an array is established and fixed and the array is created.

Python doesn't have a native array data structure. but it has a more general list structure. The list can grow and shrink during execution as elements are added or removed while the size of an array cannot be changed. However, the tradeoff here is that it needs more space, which allows for quick and easy expansion as new items are added to the list.

Another difference is that while the array only allows single type, the list in Python allows multiple types:

list1 = ['shirley','2014']
list2 = ['dora','shine']
list3 = [2011, 2015]

Note that the list is also implemented using an array structure to store the items. When the list() constructor is called, an array structure is created. The array is initially created bigger than needed, leaving the capacity for future expansion. If the number of elements added to the list exceeds the capacity (which is larger than the initial size) of the list, a new array with a larger capacity is created and an array copy is followed.

In Java, the best analogy should be ArrayList. A slight difference is that the ArrayList in Java only allows single type and initialize an array with very small capacity (10) if not predefined.

Creating an empty list:

list = []
#create a list of None with size 256
list = [None]*256
list = list()

In Java, everything is instantiated with the new operator:

int[] array = new int[10];
List arraylist = new ArrayList();

Extending a list:
Python provides built in method to append one list to another:

list2.extend(list3)

In ArrayList in Java, that is:

arraylist.addAll(arraylistB);

Inserting items:
In Java, neither Array or ArrayList allows this operation:

list1.insert(2, "Jesse")

However, since the list is still array based, this operation requires shift the elements from index 2 to the right then insert "Jesse" to index 2.

Slicing:
Slicing is an operation that creates a new list consisting a contiguous subset of elements from the original list. References to the corresponding elements are copied and stored in the new list:

list4 = list1[startIndex(inclusive) : endIndex(exclusive)]

JDK 8 provides a similar method subList(int fromIndex(inclusive), int toIndex(exclusive)) (here for src):

List sublist = arrayList(1, 3);

Creating 2-D array/list:
In Python, this involves creating a list containing m lists initialized to 0:

matrix = [[] for x in range(rows of the matrix)]

Similarly, you have to at least initialize 1 dimension when creating a 2-D array.

Alternatively, you can use library numpy:

import numpy
numpy.zeros((m, n))

Well, in Java, this is much easier:

int[][] matrix = new int[m][n];

References:
[1]. Data structures and algorithms using Python. Wiley Publishing, 2010.
[2]. www.grepcode.com
[3]. Beloved Java doc
[4]. www.codatlas.com

Note on Python

Interpreted
A program written in a compiled language like C or C++ is converted from the source language i.e. C or C++ into a language that is spoken by your computer (binary code) using a compiler with various flags and options. When you run the program, the linker/loader software copies the program from hard disk to memory and starts running it.
Python, on the other hand, does NOT need compilation to binary. You just run the program directly from the source code. Internally, Python converts the source code into an intermediate form called bytecodes and then translates this into the native language of your computer and then runs it. All this, actually, makes using Python much easier since you don't have to worry about compiling the program, making sure that the proper libraries are linked and loaded, etc. This also makes your Python programs much more portable, since you can just copy your Python program onto another computer and it just works.

String

'What\'s your name?'

or

"What's your name"

Always use raw strings when dealing with regular expressions. Otherwise, a lot of backwhacking may be required.

self:
The reason you need to use self is because Python do methods in a way that makes the instance to which the method belongs to passed automatically, but not received automatically: the first parameter of methods is the instance the method is called on. That makes methods entirely the same as functions, and leaves the actual name to use up to you. self is not special to the code, it's just another object.

pass:
This statement is used when a statement is required syntactically but you do not want any command or code to execute.
The pass statement is a null operation. nothing happens when it executes. The pass is also useful in places where your code will eventually go, but has not been written yet.

JSON (JavaScript object Notation)
A lightweight data-interchange format. It is easy for machines to parse and generate. It is based on a subset of Javascript. JSON is a text format that is completely language independent but uses conventions that are familiar to programers of the C-family languages.

JSON is built on two structures:

• A collection of name/value pairs. In various languages, this is realized as an object, record, struct, dictionary, hash table, keyed list or associative array.
• An ordered list of values. In most languages, the is realized as an array, vector, list, or sequence. 

inspect module: 
get the doc source file of a module

import inspect
inspect.getsourcefile(array)

chr() and ord()
chr() returns a string of one character whose ASCII code is the integer i:

>>> print(chr(97))
a

ord(): Given a string of length 1, return an integer representing the Unicode code point of the character when the argument is a unicode object.

>>> ord('a')
97

leading and trailing underscores:

• single leading underscore (_function): weak "internal use" indicator. e.g., "from M import X" does not import objects whose name starts with an underscore
• single trailing underscore (function_): used by convention to avoid conflicts with Python keyword. e.g., class_='ClassName'
• double leading underscore(__function): when naming a class attribute, invokes name mangling.

name mangling: 

If your class is intended to be subclassed, and you have attributes that you do not want subclasses to use, consider naming them with double leading underscores and no trailing underscores. This invokes Python's name mangling algorithm, where the name of the class is mangled into the attribute name. This helps avoid attribute name collisions should subclasses inadvertently contain attributes with the same name.Python mangles these names with the class name: if class Foo has an attribute named __a , it cannot be accessed by Foo.__a . (An insistent user could still gain access by calling Foo._Foo__a .) Generally, double leading underscores should be used only to avoid name conflicts with attributes in classes designed to be subclassed.

• double leading and trailing underscore: "magic" objects or attributes that live in user - controlled namespaces. e.g., __init__, __file__. Never invent such names, only use them as documented.

__all__

It's a list of public objects of that module, it overrides the default of hiding everything that begins with an underscore. 

[An overflow post] Longest valid subsequence

Given a string s, and a function isValid(String str), write a function to check the longest subsequence in s that is valid. For example, a subsequence in "whreat" can be "rat", "eat", "what" or "wheat". Please don't speculate the implementation of isValid(String str) function. 

I was asked this question yesterday. It bothered some much that the person who asked me this question and I could not agree on the solution. Plus I had a rough day&night last night, so I decide to break my rule to write this overflow post (256).

At first I thought it should be a DP problem, however, since we cannot assume anything about the isValid function, we can not break down the problem to smaller problem, i.e., "wh" is true will not indicate "what" is also true. So the only bloody brutal solution I can think of is backtracking.

public class LongestValidSubSequence {
 private static boolean isValid(String str){
  if(str.equals("what") || str.equals("wheat") || str.equals("eat") || str.equals("rat"))
   return true;
  return false;
 }
 static String max = "";
 public static String longestValidSubsequence(String str){
  getSubsequence(str, new StringBuilder(), 0);
  return max;
 }
 
 private static void getSubsequence(String str, StringBuilder sb, int start){
  if(isValid(sb.toString())){
   String tmp = sb.toString();
   if(max.length() < tmp.length()){
    max = tmp;
   }
  }
  for(int i = start; i < str.length(); i++){
   sb.append(str.charAt(i));
   getSubsequence(str, sb, i + 1);
   sb.deleteCharAt(sb.length() - 1);
  }
 }
 public static void main(String[] args) {
  String s = "whreat";
  System.out.println(longestValidSubsequence(s));

 }

}

Determine if an array is almost sorted, if not, how to sort it efficiently?

Given an array A of distinct elements with length n, determine if the array is 90% sorted.

1. Considering the following algorithm:

• Choose an element with index i independently and uniformly at random from 0 < i < n - 1;
• Compare the element with A[i - 1], output false if they are not sorted correctly;
• Compare A[i] with A[i + 1], output false if they are not sorted correctly.

Prove that the algorithm will return false with probability at least 2 / 3 if A is not 90% sorted only the algorithm is repeated k = Ω(n). 

Given the following counter example:
A[n/2 + 1, ..., n, 1, 2, 3, ... n / 2].
It is obvious that A is not 90 % sorted. So if we want to use the above algorithm to prove that A is not 90% sorted, each iteration we need to choose the first element to be 1, and then compare it with n, or the first element must be n, which will return false when compare with the next element.
Either case, the probability is 2 / n. Now this leads the probability of not in either of the above case 1 - 2/n.
Moreover, we know that the algorithm will be terminated once either the above case is determined. So:

(1 - 2/n)^k <= 1/3

We know that ( 1 - 1 / x)^x < 1 / e

so performing a little bit math leads to k >= (ln3)/2 *n = Ω(n). 

2. Consider performing binary search on an unsorted array. Given key1 and key2 in A, it will return index i and j. We know that if key1 < key2, then i < j (why?). Now consider the following randomized algorithm:
Randomly pick up index i from A, performing binary search with key A[i], which will return index j. If i != j, return false. 
Show that the algorithm is correct and will return false with probability at least 2/3 if the list is not 90% sorted if k is sufficiently large constant. 

First, it is easy to understand that if the array is sorted, then BST will always return true. Now we want to know that if the array is not 90 % sorted, then it will return false with probability 2 / 3 with a proper k. Alternatively we can translate the problem into a typical probability problem:

Given a bag of balls, we know that at least 10% balls are blue, and the others are red, how many balls do we have to draw from the bag to get a blue ball with the probability at least 2/3? 

Similar to the first question we can get:

(9/10)^k <= 1/3

k >= (ln3)/(ln(10/9))

So if we iterate the algorithm greater than (ln3)/(ln(10/9)), we will find an unsorted element with probability 2/3.

3. So what if we want to check if the array is not (1 - ε) sorted? 

The same:

(1- ε)^k <= 1/3

k >= (ln3)/ε

4. Prove that if the given array is partially sorted in k slots, e.g., 

A={7, 8, 9, 4, 5, 6, 1, 2, 3}, then k = 3

Using insertion sort will lead to O(nk) complexity. 

We know that since that each element is in the right order within its slot, so elements in the first slot need not move, the second slot will move number of elements in the first slot, and so on. Given n elements and k slots, each slot will contain n / k elements. So we will have the following equation:

(n/k) * 0 + (n/k) * 1 + ... + (n/k) * (k - 1) = n(k-1)/2 = O(nk)

5. Find an algorithm that sort this partially sorted array in O(nlog k) times, where k is number of slots. 

This is just merge k sorted array algorithm. We use a priority queue, insert the first element in each slot into the queue, since the size of the queue is always k, inserting an element takes O(logk) time, we have n elements, thus merge the whole array takes O(nlogk) time.