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

College friends

Met an old friends from college. Glad that she is going to take the leap of faith and do Hack Reactor too. Wish her the best of luck.

Career change is never an easy decision, especially after getting a PhD in one field. We need to believe that we have learned a lot of transferal skills in graduate school. Also the sheer determination that helped us get through graduate school will also help us tremendously down the road, no matter which road we end up taking.

Standard

Crossroad

Two roads diverged in a wood, and I, I took the one less traveled by. Such a cheesy sentence. I was never trying to be different, but I ended up walking down a non-traditional path.

All those interviews gave me the opportunity to tell my story over and over again. The byproduct is that I was forced to reflect many times. Where did all this start? Was the double major in Economics? Or the business plan competition? Or trying to sell computers to fellow students? Or DealsVista?

I am once again given the privilege to make choices. I am sure the right choice will be apparent ten years from now, but I have to make a decision based on the imperfect information I have at this point. Oh well…

Standard

Functional CSS

Come across a blog post talking about functional CSS. It cleared a lot of confusion I had with CSS conventions.

– Namespace your classess with string prefixes, faking scope and minimizing surprises
– Use composition instead of overriding rules
– Try avoid enforcing DOM structure

Standard