Search Results


66 matches found for 'unlisted'

Python String Tricks - Performance considerations

If a string is changed to become bigger, consider trying to find the maximum size of the final string early on in a quick pass (strive for \(O(n)\)) Consider working from the tail of the string and iterating backwards if, say, 1 character needs to be replaced with 2.


Perfect Squares

Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Examples: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.


Greedy Algorithms

There are many definitions of greedy algorithms, but in general, they have two properties: You build the solution by finding the most optimal answer at each local step. As you go through each local step, you do not backtrack; the answer you've picked for all of the previous steps remain the same.


Working with Production at Amazon Retail Website

A short background Prior to working at Amazon, I was developing software at a couple of startups, mostly working with products that were in the conceptual phase or the development phase. One of the things I desired the most was to have exposure to products that were live in production or to bring a development project to production.


Reversing sublists of singly linked lists

Singly linked lists can be tricky in its own right. Without the convenience of having a pointer to the previous node that is provided in doubly-linked lists, it can be really easy to be wasteful in performance with singly linked lists.


Unique Permutations

Problem Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] Input nums - Array of integers Approach The brute force approach is to generate all permutations of \(nums\) and store them into an array.


Build a Trie in Python

Problem In computer science, a trie (pronounced "try"), also called digital tree, radix tree or prefix tree, is a kind of search treeā€”an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.


Longest Substring Without Repeating Characters

Problem Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.


Buy and Sell Two Stocks

Problem Given an array of integers representing stock prices, with each index representing a different day, find the maximum profit by selling at most two stocks. The buy/sell dates must not overlap.


Decode number of ways

Problem A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).


Flip adjacent colors in a 2D matrix

Problem Given a 2D array of black-and-white points and an entry point, flip the color of all points connected to the entry point (including the entry point itself). Input A: 2D boolean array of size greater than \(n\) \times \(m\), where False represents the color black and True represents the color white.


Primes

Let's discuss primes! A natural number is considered a prime if it is: Greater than 1 Its divisors are only 1 and itself Examples: \(5\) has two divisors: \(\frac{5}{1} = 5\) and \(\frac{5}{5} = 1\) Which means \(5\) is a prime.


Iterative In-Order Traversal

Problem Return the values of a binary tree using in-order traversal, iteratively. Input node: Has 3 properties .val: Integer value of the node .left: A pointer to another node object, or None if null .


Compute the max. water trapped by a pair of vertical lines

Problem An array of integers naturally defines a set of lines parallel to the Y-axis, starting from x = 0 as illustrated in the figure above. The goal of this problem is to find the pair of lines that together with the X-axis "trap" the most water.


P vs. NP

P vs. NP is a millenium-prize problem in Computer Science that has not been proven yet. Are all P in NP? Or are all NP in P? What is NP-Complete? P vs. NP When we talk about P or NP, we generally talk about decision problems, which means the algorithms always output a "yes" or a "no".


Merging Sorted Linked Lists

var jsav = new JSAV("ll"); jsav.label("Two sorted lists"); var ll1 = jsav.ds.list(); var ll2 = jsav.ds.list(); ll1.addLast("5").addLast("7").addLast("9"); ll2.addLast("1").addLast("2").


Merge Intervals

Problem Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].


Find the duplicate number

Problem Given an array nums containing \(n + 1\) integers where each integer is between \(1\) and \(n\) (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.


Merge k sorted linked lists

Problem Merge \(k\) sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Input lists - an array of linked list pointers # Definition for singly-linked list.


Random Permutation

Problem Given an array of integers, and an integer index \(k\), randomly permute the array up to index \(k\). Input \(A\) - Array of integers \(k\) - integer index representing the indices to permute up to Approach Key insights into random permutation with arrays: If only k elements are permuted in an array of size n, the algorithm for random permutation should only cost k in time complexity.


Web Backend Security Headers - 1. CSP Headers

Table of Contents Web Backend Security Headers CSP Headers CSRF Headers HSTS X-Frame-Options and X-XSS-Protection DNS records and SPF Background Content Security Policy (CSP) is a security standard introduced to prevent cross-site scripting, clickjacking and other code injection attacks.


RNN - Recurrent Neural Networks

Recurrent Neural Networks Intuition For sequential modeling, we may have inputs that can vary wildly and depend on more contextual information that a feed-forward neural network (the simplest of neural networks) can't handle.


Javascript Essentials

Hoisting Hoisting is JavaScript's default behavior of moving declarations to the top. Given the following Javascript code, what is the expected output, and why? fcn2(); fcn1(); function fcn2(){ alert("hi"); } var fcn1 = function(){ alert("hey") } The expected output is a pop up alert that says "hi", followed by an error that fcn1 isn't defined.


Detecting a cycle in a linked list

Problem Detect a cycle in a linked list and return the node that represents the start of the cycle. Input head: a pointer to the linked list Approach First, lets concentrate on how to detect a cycle in a linked list.


Rotate a 2D Matrix

var jsav = new JSAV("set"); jsav.label("Before rotation").css({"color": "gray"}); var m = jsav.ds.matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]]); jsav.label("After rotation").css({"color": "green"}); var n = jsav.


What is DDD? What is CQRS?

Domain Driven Design DDD is an approach to developing software systems that is large and complex, and has ever-changing business rules. DDD captures the sweet spot between the business knowledge and the code.


Build a Binary Tree with Pre-order and In-order traversal data

Problem Given a pre-order traversal array of integers and an in-order traversal array of integers, construct a binary tree. Input preorder - array of integers inorder - array of integers # Definition for a binary tree node.


Next Permutation

Problem Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).


Ether and Ethereum is not the same thing

Ether vs. Ethereum Ethereum is... A network built on blockchain technology It's focus is to have decentralized apps (DAPPS) Based on Smart Contracts: A self-executing contract where given an input, a certain is output is guaranteed.


Java Essentials

JVM Java is a statically typed language that is compiled into bytecode (i.e. with javac) and understood only by the JVM, or Java Virtual Machine. The JVM is an interpreter that reads the Java bytecode and translates them into machine code before execution.


Search in a rotated sorted array

var jsav = new JSAV("av-sym"); jsav.label("A sorted array rotated to the left by 3"); var arr = jsav.ds.array([25, 28, 29, 34, 1, 15, 20]); Problem Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.


Reversing words in a string : the double reverse

Problem Reverse all words (separated by space) in a string Input \(s\) - a string Approach Nice case and point for really examining the examples. First, a few examples of reversing words in a string.


CAP Patterns

The CAP Theorem dictates that only two of its three characteristics can be guaranteed at any given time. Intro to CAP Consistency Every read will be based off of the latest write Availability Every request will be given a response, although the response data might be stale Partition Tolerance It can handle network partitions or network failures MTV's The Real World If your service is in the cloud, the P in Partitioning has to always be accounted for.


Recursive multiply function in Python using + and binary shifts

Here is one way to do an arithmetic multiply on two positive integers only using <<, >>, and +, without using the * or / operators. The idea is to keep shifting n1 to the left by 1, as n2 is shifted to the right by 1.


Find a path in a maze from start to finish

Problem Given a 2D array which represents a maze, a start point, and an end point, find a path from the start point to the end point if it exists. Input maze: 2D boolean array of size greater than 1 x 1, where False represents a wall (not traversable) and True represents an empty space (traversable) start: an object with x, y coordinates end: an object with x, y coordinates Approach The key to solving this problem is DFS.


Topological Sorting

There are two ways to do topological sorts: DFS To perform a topological sort via DFS, you will need the following: Adjacency Lists A "visited" set Recursion Recall that DFS itself will not give you nodes in topological ordering.


Validate a BST

Problem With a binary tree as input, determine if the tree is a BST or not Input node: Has 3 properties .val: Integer value of the node .left: A pointer to another node object, or None if null .


DNS

DNS (Domain name system) is essentially a phonebook for internet addresses on the Internet. Every URL with alphanumeric characters are mapped to IP addresses, either IPv4 or IPv6. That means https://google.


Comparison Charts of File Storage Formats

Big Data Encodings These encodings are often used with HDFS or some other distributed file system. Since the data can be as large as terabytes or petabytes, it is crucial to encode files in a space optimal way and also allow themselves to be read or written in an optimal way.


Algorithm Interview Problems

Welcome This page contains solutions to common interview problems that may be encountered. Arrays Longest Substring Without Repeating Characters Rotate a 2D Matrix Buy/Sell Two Stocks Merge Intervals Next Permutation Random Permutation Replace all occurrences of a space with a string Linked Lists Reversing sublists of singly linked lists Cycles in singly linked lists Overlapping singly linked lists Merging two sorted singly linked lists Merge k sorted lists Recursion Counting the path of sums Money Denominations Phone Number Mnemonics Unique Permutation Dynamic Programming Perfect Squares Find the Maximum Min Path Binary Trees Tree Symmetry Iterative In-Order Traversal of a Binary Tree Construct a Binary Tree from Pre-Order Traversal and In-Order Traversal BST Validate a BST Binary Heaps Merge k sorted lists Graphs Find a path in a maze from start to finish Flip colors in a matrix Search Search in a rotated sorted array Find the Duplicate Number Greedy Algorithms Queue Reconstruction By Height Trie Build a Trie in Python Invariant Compute the max.


Design Concepts

In this article, I want to go over some fundamental design concepts that are useful for coming up with system design. Requirements Functional Requirements Describes specific behaviors i.e. If a URL is generated, it is composed of a Base64 encoded alias Non-functional Requirements Describes architectural requirements i.


Tenets of Leetcode

Disclosure I'm a simple guy who did a handful of interviews at tech startups and enterprise companies until I landed an offer at FAANG. I'm also fairly involved with interview loops at my FAANG company.


Replace all occurrences of a space inside an array

Problem Given an array of characters, replace all occurrences of a space with another string. Assume that the array has enough space to contain all of the replacements. Input A - An array of characters which may or may not have spaces word - The string to replace spaces with.


Storing passwords into a database

Don'ts Don'ts Don't put raw passwords in the database Don't put encoded passwords in the database (i.e. Base64) Don't put simple hashed passwords in the database (i.e. MD5, SHA-256) Whys For obvious reasons, putting raw passwords means that the DBA or anyone who has access to the database can steal the passwords.


Scaling Instragram Infrastructure

Notes Sending notifications to a person whose photo you liked: RabbitMQ -> Celery Django / Python for web server / application PostgreSQL to store users, medias, friendships, etc. Master with multiple replicas, where reads happen on replicas (Master-Slave Replication) To deal with increased latency with writes, by batching requests wherever possible Replication lag from Master to slave replicas was not a big issue (for them) Cassandra NoSQL (wide column store) to store user feeds, activities, etc.


Mutual Funds vs. ETF

Open-ended Mutual Fund The fund manager registers their fund to the SEC The fund manager markets the funds to bring in more investors/shareholders Shareholders can buy and sell shares directly with the fund manager The fund manager takes 1% of total earnings as management fees * The fund manager has to keep some money on-hand if the shareholders want to sell their shares back (i.


Software Methodologies

Agile Agile in a nutshell is basically a set of principles laid out to promote fast and efficient development cycles. Scrum Scrum is an Agile methodology, so it attempts to cover the Agile principles by bringing in processes and rules to help facilitate them.


Python Essentials

Scopes Python has closures, similar to Javascript, since functions are first class objects. But unlike Javascript, there are some subtle gotchas in regards to working with function scopes. nonlocal vs.


Authentications

Authentication Authentication means to verify who you are. Basic Auth Sensitive data required for login is encoded with Base64. Base64 is very easy to decode. Not recommended and probably the least secure authentication method, but easy to implement.


Queue Reconstruction by Height

Problem Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h.


Data stores in Software Architectures

Use Cases There are many ways to store your data. In this article we'll walk through some examples of data storage in common system designs. Reminder: There is no single best storage choice and they may vary heavily depending on things such as access patterns and scale.


Misconceptions of Software Engineer interviews at FAANG

There are already so many articles and Quora/Reddit/Blind posts out there on how to interview prep to get into big companies. So instead of covering that in detail, I want to focus more on the angle of common misconceptions.


DataFrames (a software engineer's perspective)

What is a DataFrame? A DataFrame is a special data structure used primarily by data scientists and machine learning algorithms. It contains row and column data in tabular fashion by storing metadata about each column and row.


Data Sharding: Twitter Posts

Scenario Let's begin with a Twitter-like service that allows you to tweet new posts. The service has very high read and write traffic , we'll say ~10k read TPS, or transactions-per-second for starters.


Web Development 101

HTTP vs. HTTPS HTTP stands for Hypertext Transfer Protocol. It typically runs on TCP port 80. It is a protocol for sending data through browsers in the form of webpages and such. One major flaw with HTTP is that it is vulnerable to man in the middle attacks.


Seattle Conference on Scalability: YouTube Scalability

Notes Apache isn't that great at serving static content for a large number of requests vs. NetScaler load balancing Python is fast enough There are many other bottlenecks such as waiting for calls from DB, cache, etc.


2PC - Two Phase Commit and Why it Sucks

Background Two Phase Commit (abbreviated 2PC) is a protocol used to achieve atomic writes in distributed systems. It was a novel concept in the 1970's and had good intentions, but in practice the implementations are not too great.


Big Data Processing: Batching vs. Streaming

Intro In data processing, we often have to work with large amounts of data. The way in which this data is gathered comes in a few variants: batching, where we aggregate a collection of data (e.g., by hourly time), streaming for data that needs to be processed in real-time, and a unified variant which simply does not distinguish the technical difference between batching and streaming, allowing you to programmatically use the same API for both.


NumPy vs. Pandas, and other flavors (Dask, Modin, Ray)

NumPy NumPy is a Python library for numerical computing that offers multi-dimensional arrays and indices as data structures and additional high-level math utilities. ndarray The unique offering of NumPy is the ndarray data structure, which stands for n-dimensional array.


Sharding User IDs of Celebrities

Problem When you are partitioning (or sharding) database writes across multiple nodes based on a User ID, a typical partitioning algorithm is to use a basic hash like MD5 to have a reasonably compact (as in, low number of bits) partition ID.


Distributed scaling with Relational Databases

Background A lot of articles will talk about how to scale databases. Typically, they will talk about the purpose and the general idea of sharding and replication, but often times these topics are explained separately and not so much in conjunction.


Find the maximum min path

Problem Given a matrix of integers, there are many paths to take from the top left to the bottom right. For each path, the smallest number in the path is the min of the path. Of all the min paths, find the maximum min path.


NFT from a Software Developer's perspective

What is a NFT? A NFT (non-fungible token) is: A unit of data for blockchains with smart contracts functionality (i.e. Ethereum, Cardano) Uniquely represents one entity One non-fungible token cannot be equivalent to another non-fungible token What does it contain? It contains these three bare essentials: An ID that guarantees uniqueness An owner The owner may change over time when NFTs are exchanged with buyers A link to the digital asset metadata Can be untrustworthy and centralized http links, or a link to darknet services / P2P distributed storages (i.


Local Secondary Index vs. Global Secondary Index

Secondary Index Recall that a secondary index is used in databases to help speed up queries when we want to grab data from popular columns or if we want to do some type of key range lookup efficiently.


Traditional Message Queues vs. Log-based Message Brokers

Traditional Message Queues Traditional message queues are based off of the JMS / AMQP standard. These message brokers focus on a pub/sub model where publishers write messages to a queue and the queue is consumed by subscribers.


Misconceptions of ASCII and Unicode

Myth: ASCII characters take up one byte ASCII represented characters using numbers between 32 and 127. This accounted for characters used in the English language (lowercase and uppercase) and the numbers between 1-32 were reserved control characters.