☕ Web Security Explained

Facebook wants to make Rust mainstream! We explore the benefits of Rust. Plus, an introduction to important terms in web security like CORS and CSRF!

Hey Guys,

Interviewing.io is a fantastic resource I wanted to share with you all.

You can book realistic mock interviews with senior FAANG engineers who will give you detailed and actionable feedback on exactly what you need to work on.

Mastering algorithms on LeetCode and system design on SystemsExpert is great, but they don’t prepare you for the pressure and stress that comes from an actual interview setting.

The best part?

You don’t pay anything until you’re hired.

Check them out here.

Special thanks to Interviewing.io for sponsoring Quastor Daily. I’m a user of the service!

Tech Snippets

• Facebook wants to make the Rust Programming Language Mainstream

  • Facebook has joined the Rust Foundation alongside Google, AWS, Microsoft, Mozilla, and Huawei.

  • Microsoft is exploring Rust for some components of Windows and Azure (Microsoft’s Cloud Computing service) and Google using Rust to build new parts of the Android operating system.

  • Facebook has used Rust in a number of their projects, including their Libra (Diem) stablecoin project (a stablecoin is a type of cryptocurrency where the value is pegged to some external reference).

  • Rust is compiled (machine code not byte code) and has strong static typing.

  The benefits of Rust are

  • Speed

    • The performance of idiomatic Rust is comparable to the performance of idiomatic C++

  • Safety

    • Pointers in Rust are checked at compile time.

      1. The compiler makes sure that every value has only one owner which means no double frees.

      2. The compiler also makes sure that no pointers outlive the owner, which means no dangling pointers.

    • Thread Safety

      • Safe Rust guarantees an absence of data races. However, it does not prevent general race conditions. Read More.

    • No Hidden States

      • No Null Pointers in Rust. All references are guaranteed to not be Null.

      • Therefore, the compiler forces you to put in Null checks and helps you avoid runtime errors.

  • Low Level Control

    • No Garbage Collector or Runtime

      • No garbage collection pauses or memory overhead

      • Can run on systems without an OS since there’s no runtime. Useful for embedded devices!

    • Control allocation and dispatch

      • Variables are all on the stack, but you can opt-in to heap allocation

      • Can opt-in to dynamic dispatch.

• CSRF, CORS, and HTTP Security headers Demystified

  • Securing your web apps is becoming more and more important, so you should know some of the basic terms in web security.

  • CSRF

    • Cross-Site Request Forgery - a third party tricks a user into executing actions against another site where they’re currently logged in.

    • You visit evil.com and evil.com has a hidden form that submits on page load to mybank.com/transfer-funds. You were already logged in to mybank.com so the request is made with your mybank.com cookies and will silently transfer money out of your account.

    • The post goes into how to guard against CSRF.

  • CORS

    • Cross-Origin Request Sharing - a browser security mechanism that allows one origin to make a request to another origin.

    • All browsers follow the Single Origin Policy, meaning that by default a script loaded from one origin cannot make requests to a server on another origin.

    • However, if the server provides properly configured CORS headers, then the Single Origin Policy can be relaxed.

  • XSS

    • Cross-Site Scripting is where an attacker compromises a web server and injects a client-side script into the web pages served by the webserver.

    • The most common way attackers compromise web servers is by leveraging poorly sanitized user inputs to get the web server to run malicious code sent in by the attacker.

Interview Question

You are given a positive integer as input.

Print the next smallest and next largest numbers that have the same number of 1 bits in their binary representation.

We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

• On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"

• On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Previous Solution

As a refresher, here’s the last question

You are given an N x N matrix that contains positive and negative integers.

Write a function that finds the submatrix with the largest possible sum.

Solution

Brute Force Solution

As we stated in our last email, the brute force solution is to look at every possible submatrix and calculate the sum.

We then pick the submatrix with the largest sum.

In order to do this, we’ll have to use 4 nested loops.

The first loop will iterate through the rows in our matrix and use that row as the starting row of our submatrix.

The second loop (nested in the first) will iterate through all the rows after the starting row and use this row as the end row of our submatrix.

The third loop (nested in the second) will iterate through all the columns in our matrix and use that column as the start column of our submatrix.

The fourth loop (nested in the third) will iterate through all the columns after the starting column and use that column as the end column of our submatrix.

Inside the fourth loop, we’ll have our submatrix and we can calculate the sum of all the elements inside it.

Calculating the sum of the elements in our submatrix will take O(N^2) time.

Therefore, running the brute force algorithm takes O(N^6) time as we also had 4 nested loops.

Here’s the Python 3 code.

Optimal Solution

We can solve this faster by using the solution to the maximum subarray problem.

The maximum subarray problem asks that given an integer array, find the contiguous subarray with the largest sum and return that largest sum.

You can use Kadane’s algorithm to solve the maximum subarray problem in O(n) time, and the solution looks like this.

def maxSubArray(nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = nums[0]
        
        for i in range(1, len(nums)):
            curSum = max(nums[i], nums[i] + curSum)
            maxSum = max(curSum, maxSum)
        
        return maxSum

For finding the largest submatrix, we’ll repeat the same brute force process on our rows.

We’ll try every combination of startRow and endRow using a nested for loop.

For the columns, we’ll collect the sums of each column for all the items between startRow and endRow into an array called colSums.

In the nested for loop with endRow, each iteration of the loop will expand our submatrix downward by a single row (endRow increases by 1).

Therefore, we can reuse the colSums array and just add in the items from endRow into their respective column sums.

Then, we’ll use our maxSubArray function to find the maximum contiguous subarray from colSums. That will be the maximum submatrix sum between startRow and endRow.

We’ll compare that to the maximum submatrix sum we’ve seen so far, and if it’s greater then we’ll make that the maximum submatrix sum.

Here’s the Python 3 code.

What’s the time complexity of our solution?

Reply back to this email with your estimate and we’ll tell you if you’re right/wrong!

---

Want more practice with real FAANG software engineers?

Check out Interviewing.io!

You don’t have to pay anything until you get that job at FAANG!