pbesra

System Design Cheatsheet

Picking the right architecture = Picking the right battles + Managing trade-offs

Basic Steps

1. Clarify and agree on the scope of the system

• User cases (description of sequences of events that, taken together, lead to a system doing something useful)
  • Who is going to use it?
  • How are they going to use it?

pbesra

// programming language: C++
// Running time complexity: O(n+K), where K is the maximum element in the array
// Space complexity: O(n+K)
#include <iostream>
using namespace std;
void countingSort(int* a, int n){

	// initial maximum value
	int mx=a[0];

pbesra

#include <iostream>
using namespace std;
class Node{
	public:
		int data;
		Node* left;
		Node* right;
		int height;
		Node(int data){
			this->data=data;

pbesra

#include <iostream>
using namespace std;

class node{
	public:
		int data;
		node* next;
		node(int d){
			this->data=d;
			this->next=NULL;

pbesra

/*
max heap
*/
#include <iostream>
using namespace std;
int capacity=0;
int maxCapacity=64;
void maxHeapify(int* a, int k, int n){
	int left=2*k+1;
	int right=2*k+2;

pbesra

// Algorithm
// Input: Array A[n], find a peak element in araray A. The peak element is 
//not necessarily a global maxima
/*
For an element,Search(A, 0, A.length-1)
midElement=(start+end)/2
1. If (midElement==end && a[midElement]>=a[midElement-1]) || (midElement==0 && a[midElement]>=a[midElement+1]) || (A[midElement]>=A[midElement-1] && A[midElement]>=A[midElement+1])
    ----> return mid
2. else if(A[midElement-1]>A[midElement])
   -----> Search left array Search(A, sstart, midElement-1)

pbesra

#include <iostream>
#include <cmath>
using namespace std;
int getMid(int x, int y){
	return((x+y)/2);
}
int segTreeUtil(int* a, int* s, int ss, int se, int c){
	if(ss==se){
		s[c]=a[ss];
		//cout << "c: " << c <<  ", s[c]: " << s[c] << endl;

pbesra

#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
// precedence of each operator
bool precedence(char stack_top, char strin){
	if(strin=='-'){
		if(stack_top=='+' or stack_top=='*' or stack_top=='/' or stack_top=='^'){
			return(true);
		}

pbesra

#include <iostream>
using namespace std;
void solution(int n){
	// prints top triangle.
	int m=2*n-1;
	int t1=m/2;
	int t2=m/2;
	int t3=m/2;
	int t4=m/2;
	for(int i=0;i<n;i++){

pbesra

#include <iostream>
using namespace std;
int main(){
	int n=4;
	cout << "enter n: " << endl;
	cin >> n;
	cout << "result: " << endl;
	int start=n-1; // this where * starts in every row.
	int t=0;
	for(int i=0;i<n;i++){