Convert an sorted array to a binary search tree

//asume we have Tree() to generate a BST
//each tree has a value, a left pointer and a right pointer
var walker = function(input){
  //base
  if(input.length===0){
    return;
  }
  if(input.length===1){
    return new Tree(input[0]);
  }

  //iter
  var middle_index = Math.floor(input.length/2);
  var left = input.slice(0, middle_index);
  var right = input.slice(middle_index+1, input.length);

  var tree = new Tree(input[middle_index]);
  tree.left = walker(left);
  tree.right = walker(right);

  return tree;
};

walker([1,2,3,4,5,6,7,8,9]);
Standard

All anagrams of a string

Extremely common interview question. You should be able to write it when you are dreaming

var output = [];
var walker = function(prefix, bag){
  var n = bag.length;
  if(n===0){
    output.push(prefix);
    console.log(prefix);
  }
  for(var i=0; i<n; i++){
    walker(prefix+bag[i], bag.substring(0,i)+bag.substring(i+1,n));   
  }
}; 
walker('','abc'); 

To find a job, you should really be able to write this when you are dreaming. I am serious.

Well, there are cases that your interviewer wants the following version for performance reasons. You are welcome. The code is largely based on this article. The ideas are:

  • Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
 
var output = []; 

var swap = function(arr, from, to){   
  var tmp = arr[from];   
  arr[from] = arr[to];   
  arr[to] = tmp; 
}; 

var walker = function(str, index){   

  if(index>=str.length){
    output.push(str);
    console.log(str);
    return;
  }

  for(var i=index; i<str.length; i++){
    swap(str, index, i);
    walker(str, index+1);
    swap(str, index, i);
  }

};

walker(['a','b','c'], 0);
Standard

Getting there

Talked to one really cool and successful entrepreneur today. It is fun to talk about the old technology companies and old stories. History tends to repeat itself. It doesn’t matter whether you are writing assemble languages or JavaScript, we face the same big problems. It is up to the team to choose which problems to tackle. I am excited that the founders are brave enough to tackle those hard problems.

Standard

Solve a big problem

Meet more cool people and one of them is the first employee for a very successful start-up. I asked him on how decided to become a first employee for that start-up, and he said:”I am really fascinated by hard and big problems.”

I guess you have to be dreamer and a believer to do that. I would probably skip that start-up and say, “this problem is too hard and we have no chance of solving it”… I think I should change my attitude to: “I don’t know it was impossible, so I did it”.

Standard

How to speed up page load

This is probably one of the most frequently asked non-data structure questions in my interviews. My answers are:

  • DNS speed. Depending on who is hosting the DNS for you, there might be speed implications. The famous one is, GoDaddy’s DNS server is sometimes unreachable inside China. So, if you want to serve the Chinese market, maybe you should think about DNSPod.
  • Gzip the traffic. Most web servers and browsers support compression such as gzip. Read more on this article
  • Size of the
    • HTML, reduce unecessary markups
    • CSS, minify, uglify
    • JS, minify, uglify
    • Images, compression, trying to serve different sizes for mobile website
  • Number of HTTP requests
    • CSS, combining all into one file
    • JS, combining all into one file
    • Images, CSSsprite, combining many small images into one
  • Cacheing
    • Set expiration headers for all assets, and let them expire way in the future
    • If anything needs to be changed, change the url of the assets. I.e. changing from adfafa.css to adfjileafs.css

Anything else I am missing? A good article to read: http://blog.teamtreehouse.com/speeding-up-page-load-times

Standard

Another class started today

It is a strange feeling when you go back and most people you know are already gone. I think a couple of my classmates started working today. Crazy.

Spent more time with Larry on how to achieve closure using bind. The simple solution is shown below:

var TakesArgs = function(d, e, f) {
  return (function(a, b, c){
    console.log('a: ', a);
    console.log('b: ', b);
    console.log('c: ', c);
  }).bind(window, d, e, f);
};

var TakesABC = TakesArgs('A', 'B', 'C');
TakesABC();
Standard

N ways to clear both

One common problem is that when children divs are floated inside a parent div, the parent div is not aware of the height of children divs.

The code to begin with:


<div class="parent">
  <div class="child">c1</div>
  <div class="child">c1</div>
  <div class="child">c1</div>
</div>

.parent {
  border: 1px solid black;
}
.child {
  float: left;
}

Solution one – change the css of the parent to

.parent {
  border: 1px solid black;
  overflow: auto;
  width: 100%;
}

Solution two – add an extra div, and apply clear:both

<div class="parent">
  <div class="child">c1</div>
  <div class="child">c1</div>
  <div class="child">c1</div>
  <div class="clearfix"></div>
</div>
.parent {
  border: 1px solid black;
}
.child {
  float: left;
}
.clearfix {
  clear: both;
}
Standard