Programming Pearls Col 5 – A Small (but very important)Matter of Programming

Col 5 is all about the Science and Art of Testing (rules and where, when and how to apply the rules).

-Define expected output

-Cover all cases

-C/C++ Compile-time assertions:

Further reading: https://www.embedded.com/electronics-blogs/programming-pointers/4025549/Catching-errors-early-with-compile-time-assertions

-When the algorithm is part of a big program, use scaffolding/automated testing/line-by-line debugger

-When the algorithm is stand-alone, print statements might be faster

-Be wary of bugs in different environments, experiment with them frequently to gain insights for fixing bugs

 

 

Advertisements

Programming Pearls Col 4 – Writing Correct Programs

This column uses a simple and almost trivial example of writing the code for a binary search algorithm. Even programmers who so confidently claim that they can write flawless code ended up writing buggy code, and it’s simply because humans are always prone to error and we need to accept that.

Two principles to verify an iterative(loop) control structure:
-Define the invariant precisely (conditions for loops)
-Maintain the invariant as we write each line of code – key to converting algorithm/pseudo code to code

How to do the second one:

  1. Initialization: invariant is true at first iteration
  2. Preservation: invariant remains true at end before next iteration
  3. Termination: set clear termination conditions

Tools Used:

  • Assertion statements to enunciate states of the program
  • Do this then that control
  • Choose from cases control

Here’s the iteration control structure discussed in this column, simplified:

Drawing.png

Reflection:

This column touched on one of the most important topics – testing and verification. I think it gave that further explanation needed of so many things that computer science students were taught in class to do when they test the programs they write but never prompted to think deeply about the reasons behind them.

You may know what assertions are for, but why use assertions instead of just print statements? You know logical proofs are good for exercising your mathematical senses but how can it be applied to programming? Why do we need to write the obvious preconditions and postconditions for every class method? Why do we want to be able to explain every single line of code, besides just for the sake of being able to explain every single line of code? Why do we always have to be so meticulous about sanity checks?

It’s such a simple principle, yet so many people have overlooked it: it all boils down to that in order to be a “lazy programmer”, one that is different from a “hardworking programmer” who writes hundreds of lines of code for a simple program and spends days debugging it. Writing messy code to save time on the spot and then debugging like you’re trying to find that one needle in the bottom of the ocean is pure suicide. We need to be aware of those tools and keep looking for the best way to be efficient and save more time and effort in the long-term, thus being “lazy” in the smartest way possible.

After reading this column, I’m convinced that every college computer science student deserves to be fed all the knowledge in this column right after they finish any kind of “fundamentals of computing” classes because I’ve already made countlessly many connections to my data structures, discrete math, and assembly classes.

 

 

Programming Pearls Col 3 – Data Structures

Column 3 talked about how to design a program to be as clean and efficient as possible using data structures. After all data structures are the building blocks of any system.

Important topics (all about writing good code => good programs!)

-Separation of data from logic: reusable code when data changes

E.g. Tax bracket problem

-Object-oriented design: encapsulated objects => more readable, maintainable code

-Data structures and data representation:

E.g. arrays, containers, databases, etc.

Programming Pearls Col 2 – Aha! Algorithms

Column 2 introduced models to solutions to the classical “group anagrams”, “string rotation” and “finding duplicates” problems. The author used very simple mathematical principles to design solutions and called them aha! insights. Then variations to the principles are applied in the implementation of the solution in regards to the problem.

Group anagrams: using a signature for each group of anagrams (sorting one of the anagrams and using as key to bucket in hash map)

String rotation:

  1. x modulo n – x is the length of the string and n is the number of rotations. This solution ends up using constant memory and linear time. But it only works when x is divisible by n. (slow in time, efficient in memory)
  2. Reversal: String as ab, a is characters [0, i). Place a in its final position, then reverse the rest recursively. (spikes in intervals)
  3. Block reverse: Separate string into a and b and reverse recursively: in every step, reverse a to get a’, reverse b to get b’, and (a’b’)’ to obtain ba. Apply this principle to convert three partitions (abc to cba) – reverse either ab or bc, reverse the rest, then reverse the whole string. (fastest long-term)

Finding duplicates:

  1. Extracting a small portion of data each time to use binary search on it. This solution has stable performance.
  2. Another solution I was thinking is XORing bit patterns and output the first bit pattern that outputted 0. Although its worst case is O(N), it can potentially reach the goal faster than binary search in some cases

Programming Pearls Col 1 – Cracking the Oyster

Before starting to read Programming Pearls, I have never seriously considered the true importance of approaches stemmed from algorithms. Whenever I tried my hands on harder problems on LeetCode, I’ve always thought that coming up with an optimal solution in the blink of an eye is an activity reserved to only the geniuses and the brightest of them all.

But after just reading col. 1 from Programming Pearls, I realized how forgetful I am of all the power I have from the knowledge of algorithms. And from asking a simple question as “How do I sort a disk file?”, the approach of asking the right questions and framing a problem properly is not reserved to computer science Ph.D.’s only – everyone should be able to do so.

Consider the file sorting problem. We ask some questions first to make proper assumptions about data: What is the input? What is the desired output? What is the data? What are the constraints on the data? How big is the input file? What are the time and memory constraints?

As soon as we have answers to these questions, we formally define the problem by listing the input, output, and constraints.

Now we begin to construct several solutions and compare them. In this case, solutions using merge sort (time-efficient) and a multipass sort (memory-efficient) were proposed.

Some may stop here and pick one to end problem-solving process, but we can even dream bigger and go further, because we haven’t exploited all the conditions we have.  Can we do better than O(nlogn) sorting with non-specialized data? No. But can we save space by compressing data (representing data in a different way)? Definitely.

Then we arrive at the bitmap representation of numbers. Since the file contains unique numbers only, this satisfies the requirements for our problem. This marks the end of the disk file sorting problem, but there are many other considerations left to explore for the reader.

What was especially interesting to me were the design problems proposed at the end of the chapter. These are questions designed to challenge how the reader, after being inspired by the disk file sorting problem, thinks about other tricky problems. I have been afraid of the large scope of a design-oriented problem, but this chapter encouraged me to think about all the tools I have at hand to propose as many solutions as possible and compare them at the end.

~Moving over to Devpost for my current and future hackathon/side projects~

I’ve decided to migrate to Devpost entirely for future projects, since I’ve been working on bigger team and collaborative projects lately. Devpost is by far the easier and cleaner way to organize relevant information (e.g. logistics, responsibilities of teammates, the fact that the project description was crafted by the whole team, etc.) than posts on my personal blog.

See my Devpost profile~~~ https://devpost.com/jluo9612

With that said I will dedicate my blog as a place where I gather learning resources and share my thoughts on things from now on.

Why is Wi-Fi so much slower than wired connections?

Wi-Fi is probably used a lot more commonly these days than wired connections. The wireless 802.11 protocol was actually based on the Ethernet protocol (802.3).

Because data transmission processes are all decentralized, multiple access protocols are needed to minimize the number of collisions when there are a large number of hosts. There were the O.G.’s like Pure ALOHA, but CSMA/CD is probably the best protocol used for Ethernet connections.

But why doesn’t 802.11 also use CSMA/CD? This is because Wi-Fi devices use radio waves, and because of huge frequency differences between send frequencies and receive frequencies, they cannot send and receive at the same time. Thus Collision Detection (CD) becomes unviable.

This exact property slows down Wi-Fi performance because Wi-Fi uses Collision Avoidance (CA) and involves a lot of wait time periods for requests-to-send and permissions-to-send back-and-forth.

Knowledge from this reading: https://hpbn.co/wifi/#

Browser rendering and performance

In order to deliver one web page, a ton of hard work needs to be done in the browser. As developers having a good understanding of how the browser works gives us insights into how to optimize performance. Here are some study notes I took. Hats off to browser developers!!!

The rendering a webpage in the browser can be broken down into 4 steps:

1. Parsing:

HTML and CSS are parsed to construct parse trees, which will be turned into DOM trees.

HTML is forgiving syntax-wise for better browsing experiences. Even if tags are not closed the browser will recognize tags and construct a parse structure tree with all tags. This is done through the tokenizer, which recognizes symbol characters as special things like a “start tag”.

Things like <script>, <link> and <style> JavaScript/CSS specified in HTML can halt the parser from continuing to parse the rest of the HTML.

Performance insight: But because modern browsers will look for these tags, fetch and process any external scripts, images and stylesheets in a multi-threaded manner, it’s considered best practice to always include JavaScript and CSS externally. There is an exception for CSS, though. Since inline CSS has the highest priority, inline CSS will always be parsed prior to other CSS. One can use this property to improve the speed of CSS parsing/rendering.

If JavaScript changes the DOM structure, such as adding an element, HTML needs to be re-parsed and that takes more time.

2. Form Render Object tree:

This maps the respective nodes, styles of the nodes, and boxes of elements in the DOM.

3. Layout:

Once browser gets the render tree it starts constructing the layout according to this tree. It will traverse each render object recursively, laying out children first, and then parent elements.

If the user interacts with the page and cause changes, browser will detect changes and apply in batches. But if the changes are large-scale, for example, font changes and browser resizing, the layout will have to be reconstructed and that slows down rendering a lot.

Performance insight: The JavaScript best practice is to batch all reads and all writes separately to avoid having to re-layout a lot of things every step of the way.

4. Painting:

RenderLayers is constructed from RenderObject. It produces layers to correctly display the position, transparency, etc. of the nodes. There can be multiple nodes on the same layer depending on their CSS properties.

Performance insight: The browser will utilize the GPU to produce bitmaps of each layer to be displayed on the user’s screen.

Similar to scalable temporal video coding, the problem of re-layout delay can be solved by “delta last bitmap”, comparing last to current bitmaps so that it only needs to re-draw a small portion of the page.

The rendering process is a constantly ongoing loop, since the user will constantly be interacting with the page in session. There are also a lot of tips and tricks as to how to optimize browsing experience, such as using fixed height, delaying/asyncing scripts and stylesheets to speed up first paint, etc.

 

My technical interview experience with Dropbox, Twitter, Amazon, Box (2017-18)

Dropbox [90min] [OA]

Grid Illumination: Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on, that query get turned off. The ranges for the variables/arrays were about: 10^3 < N < 10^9, 10^3 < lamps < 10^9, 10^3 < queries < 10^9.

This problem was quite hard for an internship OA. I got it in first semester freshman year with next to zero coding practice, not to mention reading up CTCI to learn the “right way” to solve problems.

Tips: Use time accordingly to plan solution.

Twitter [easy – medium] [45min] [onsite]

Technical:

1 Given two numbers as strings, output their sum as a string.

Straightforward. For this question, be careful in the way you handle the carry. Make sure to consider a lot of different cases when testing.

2 Given an array of integers with duplicates, find the int that isn’t a duplicate (this int is guaranteed in the input array). followup: given that your solution will be used as a backend utility function, how to design a return value for invalid inputs?

You can approach it with a straightforward hash map and expect the interviewer to follow up asking for improvement in space complexity (hint: use bit manipulation). For the followup example answers are exception handling mechanisms or constants. I bombed the followup because I simply did not know how to answer it with a lack of design knowledge, but it seems like most of the time interns don’t get this kind of questions.

Behavioral: why major, what’s your proudest achievement, talk about a challenge you’ve encountered in group/team setting

Tips: Follow the process strictly but(!) also listen closely and communicate frequently with interviewer.

Amazon [easy] [OA * 2 + video interview]

OA1:

debugging and logical questions (straightforward but time goes by really fast so manage it well!)

OA2*:

  1. amazon fulfillment center, find two boxes whose weight is less or equal to maximum weight

Classic combinatorial optimization, a variant to the knapsack problem.

  1. amazon data center, round-robin style access, find average waiting time of all clients

This problem was very hard in the sense that there were a lot of things one needs to keep track of when crafting a solution. You need a crystal clear understanding of the problem and plan your solution meticulously.

*Rumors say that if you did exceptionally well in OA2 they will skip the last round of interview and give you an offer

1-on-1 video interview [45min]:

Behavioral:

Introduce yourself

Tell me about a project you’ve worked on with a tight time frame and how you got it done on time

General software engineering knowledge:

What is the difference between an array and linked list?

What is a foreign key in database?

What is TCP? How is reliable data transmission implemented?

Technical:

1 Find the nth Fibonacci number

I bombed this question because I tried to recall an optimal bottom-up solution but was blanking out on the details of it. After being stuck for about 10 minutes I had to go back to the basic recursive solution, talked about optimization with memoization but ran out of time to actually implement it. I was sure that this left a bad impression; it showed the interviewer that I was unorganized and hasty by trying to jump to code without thinking through my solution first.

2 Check if a string is palindrome

Straightforward. Make sure you can go beyond the solution using something like reverse()

Tips: Don’t pretend to know something that you don’t actually. Never, ever try to come up with an optimal solution upfront without being 100% sure how it works and how to explain it. Start by talking about a naive solution and build it up elegantly to better solutions.

 

Box (Security Automation) [easy, specialized] [OA]

OA:

1 Check if a string is valid ipv4 or ipv6 address

2 DNS

3 Parse base url

Tips: Familiarize yourself with Python features. Know how to use regexp.

 

Practice/communication tips:

* Make sure your interviewer understands every step you take

* Practice problems, see patterns of best solutions (clean code, high performance)

* Be highly comfortable and familiar with one coding language (Python recommended because it’s used pretty ubiquitously at companies for interviews, UNLESS if you’re interviewing with Amazon because only Java and C++ are allowed for OAs)

 

Good luck and practice often!

Essay Partners and my first internship experience at Panopath

demo.gif

I started learning Angular for about two weeks on my own, and it got me an opportunity right away at Panopath to work with another engineer and gain hands-on experience maintaining code and developing a hybrid app with the Ionic Framework.

DATE

Late July 2017

TIME SPENT

~3 weeks

WHAT IT DOES

It pairs you up with another high school student who is also working on college applications. Until both of you finish your application essays, you two will be “essay partners” and helping each other build plans on this app.

Each partner has their own plan which both partners can view and edit. To make it more user-friendly, we used local cache to store form data so the user’s name is displayed after registration.

HOW IT’S BUILT

Angular and the Ionic Framework provided the foundation and structure. The app itself looked and felt like a native mobile app and can use native functionalities because of Ionic.

CHALLENGES

Some of the biggest ones:

  • Improving code quality and readability, designing and planning the project before hammering away on keyboard coding.
  • Making sure that other engineers on the team can read my code, grasp the project structure and get their hands on the project as soon as possible.
  • Writing efficient documentation that has good usage examples for the above purposes.
  • Working at a student-run startup without an established management structure, many situations require everybody to take charge at least once at some point. Fortunately, my inputs were almost always valued by my colleagues. It’s hard to communicate technical details and requirements to management and/or design people who usually think the bigger pictures. But I will also say that putting myself in their shoes and thinking about what the project means for our organization helped a lot in build understanding and trust between us.

WHAT I LEARNED

There have been so many day-to-day eye-openers, mostly coming from being exposed the first time to the real world of software development and how developers really do their jobs. Comparing to doing personal side projects that weren’t really rigorous, working with others in a relatively fast-paced manner while learning new concepts and technical terms was big to me. As a result, the area I had the most growth in is writing quality and maintainable code by using a consistent coding style throughout the project.

BUILT WITH

  • Angular
  • Ionic
  • Sass
  • Gulp.js (task automation)
  • Laravel
  • XAMPP