Graphs

  • Longest path in DAG (Directed Asyclic Graph): This is a greedy with dynamic programming approach:
    1. Find topological sort
    2. Init distance from source to each node to be minus infinite and zero for the source node.
    3. In the topological order, start from the source node and for each adjacent node update the maximum path from parent to it: max = max(current dist, 1+parent dist)
  • Shortest path in DAG: Same as longest path, but instead of minus infinite, we init with plus infinite and instead of calculating maximum in step 3, we calculate minimum.
  • Cycle in undirected graph (No self edges):
    1. use UNION-FIND: for each edge, assign a representative node. if two nodes are in the same set, then there is a cycle:
    Union-Find: For graph G(V,E), create array with size |V|=n. and init each cell with -1
    Union: for edge {1-2}, let 2 be representative of 1. and for edge {1-3}, representative of 1 is 2, then representative of 3 is 2. e.g, 2 is representative of {1,2,3}
    Find: the representative of 1 is found by jumping to the parent in the arr[1] until arr[i] is -1. then i is the ultimate representative of 1.
    Time complexity: O(ElogV)
    2. Use DFS: for edge u—v, if v is already visited and v is not parent of u (we didn’t reach u from v), then there is a cycle.
    Time Complexity: O(V+E)

Tricks

  • n&(n-1) == 0: check if n is power of 2 or 0
  • numbers between 0 to nInorder, thePre-order lastcan digitrestore will be repeated every 10 numbers. the last two digits of each number will be repeated after 10^2 numbers and the last i digits of each number will be repeated every 10^i numbers
  • a group of integers all distinct and in a given range: we can represent these numbers with bits in integers. If we have 42 numbers, we need two integers.
  • Lagrange’s four-square theorem: {\displaystyle p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}
  • 2^n = 1<<n
  • 10000-1 = 1111 : convert the zeros to 1’s
  • ~0 gives a vector of binary 1’s
  • in order to reach the middle of the list, use fast iterator which go two steps each time:
    while fast and fast.next:
    fast = fast.next.next
    slow = slow.next
  • Implement an algorithm to find the nth to last element of a singly linked list: Two pointers p1 and p2 pointing to the beginning of the list. walk p1 n steps, then walk p1 and p2 until p1 reaches the end of the list. return p2
  • If we turn on a 0 at bit i and turn o a 1 at bit j, the number changes by 2^i – 2^j
  • Bit Manipulation, Add two numbers without arithmatic operation:
    • if you xor two numbers, it is like adding them without the carry
    • if you and two numbers and shift the result, it will give you the carries.

  • Select m random numbers from array with equal probability: the trick here is to select a random index and then swap the selected index with the first index in the array. the next index we randomaized will be after the already selected tail.

Knowledge based

  • Convert decimal fraction to binary: here
  • immutable object(unchangeable[1] object) is an object whose state cannot be modified after it is created.
  • concurrency vs parallelism: In programming, concurrency is the composition of independently executing processes, while parallelism is the simultaneous execution of (possibly related) computations. Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once” – Rob Pike.
  • How to debug segmentation fault: core dump file & gdb; debugfs, dmesg
  • Mutual Exclusion:Resources are unsharable, so if a process acquires a resource, other processes have to wait before using it.
  • Thrashing:Thrashing usually refers to a phenomena in memory and storage. It occurs when OS spends most of time on handling page faults(paging in or paging out) rather than getting anything done. For example:
    1. process A has some pages in hard drive and gets a page fault.
    2. The missing page(not in memory) needs to be swapped into memory.
    3. Suppose the memory is full, pages belong to process B need to be swapped out.
    4. Then process B needs to run, so its pages need to be swapped in and the process A’s pages that were just swapped in need to be swapped out
    5. This could happen indefinitely until the issue is resolved or one of the process finishes its job.

    As we can see the performance is terrible, we need to detect the problem first before solve it(or least alleviate it). Kernel usually keep track of the number page-in and page-out, if the number is too high, the physical memory is almost full and CPU utilization is low, the thrashing is happening. There should be a formula to determine thrashing based on number of page-in and page-out in certain period, etc. In userland, there are some tools like vmstat and atop to help us detect thrashing.

    When thrashing is detected, different OSes may deal with it in different ways. We could either kill a process or swap a process completely into secondary storage. Additionally, we could also add more RAM to the machine:)

Operating Systems

Processes

when linux loads, it starts 2 processes: swapper and then init. each process has pid – integer 32bit. means there can be 32k processes in total. a process can create a child process using fork() or create another totally different process using execv()

execv() will terminate the calling process and start a whole new process

wait(*status) is called by the father in order to wait for its child process to finish.

  • when the shell receives a command, it forks a process which will execute the command and then wait for it to finish, afterward, the shell will move to the next command.

each process has a state, this state can be

  1. TASK_RUNNING: the task is ready to run
  2. TASK_INTERRUPTIBLE: task is waiting for something but that can be stopped by sending the process a signal.
  3. TASK_UNINTERRUPTIBLE: like the previous one but the process waiting can be stopped only by the event that the process is waiting for.
  4. TASK_STOPPED AND TASK_ZOMBIE

A process has a kernel mode stack which is used in order to switch between user space and kernel space.

A process is created with one thread called the primary thread

Threads

clone(): When a process is created, it is created with one thread called the primary thread. it can be duplicated using the call clone().the kernel creates threads using the call sys_clone() and not clone().

threads share the same process environment while creating a new process using for fork is obligated with creating a new environment.

In a process, each thread has its own stack and registers.

threads are supported in the kernel level. basically each thread has a pid as it is considered somehow a process. however, according to the threads standard, for the user, all the threads have the same pid. in the process descreptor fields, the threads pids are available in a variable named thread_group and a variable named tpid which contains the pid that represents all the threads.

when a thread creates a process using fork(), the process has one parent which is that thread. the other threads cannot wait() on this process.

when running execv() inside a thread, it creates a new process with a new thread – the primary thread of the new process. the rest of the threads are killed.

  • Thread safe in java: declare method/class as synchronized
  • Deadlock: happens because of 4 reasons:
    • mutual execution: only one process can use the resource at a given time
    • Hold & Wait: processes already holding the resource can request new ones
    • No Preemption: processes cannot remove a process already using the resource
    • starvation:two or more processes are waiting on different resources

IPC – inter process communication

each process has a table named PDT - Process descriptor table.this table contains the descriptors of the files that are used by the devices.

The communication methods are:

  • Pipes/FIFOs: Used to send data between two processes which have father-son-brother connection. has two file descriptors, one for read and the other for write. the pipe is not mapped in the filesystem. FIFO is a pipe, however is global and appears in the filesystem. it also can be used by all the processes.
  • Signals: asyncronouis call triggered by the kernel or from another process. each signal has a number. a process can decide what to do with the signal. example of sending signal: cpu will send signal if dividing by zero. kill() will send SIGKILL to process.
  • Sockets: is used cross-machine communication

Interrupts

The interrupt is a signal handled in the kernel by the CPU. The CPU Checks for interrupts between each two commands it executes. if there is an interrupt waiting, the kernel switches the user stack to the kernel mode stack of the current process in order to handle the interrupt (in linux, interrupts are handled by the kernel).

IDT – Interrupt Descriptor table: a table loaded by BIOS and pointed by a special register named lidt. This table contains 256 entries mapping each possible interrupt to execution method handler.

There are two types of interrupts

  • Hardware interrupts: sent by external Hardware. This type of interrupt is of course asyncronous.
    • the hardware sends IRQn (Interrupt request #n) to the APIC-Advanced Programmable Interrupt controler
    • The APIC check if the IF - Interrupt flag is turned off so it send it to the CPU.
    • The CPU tells the APIC to block this type of interrupt and allow others – in order to ban collisions in the handler of the received interrupt
    • The interrupt handler code IRS receives several IRQs that may be the ones who sent the interrupt – as to one usb port there may be several connected devices.
  • Software Interrupt(Exceptions): This type of interrupt is syncronous as it is generated by the CPU itself. There are two possible reasons for such interrupt: whether an error in the previous execution command such as division by zero, breakpoint or an interrupt generated by the cpu in multi-cpu machines as a way of communication with other cpu’s.
    • Aborts: Dangrous – accessing bad memory
    • Traps: like breakpoint
    • Faults: like division by zero

Q/A

What is the difference between mutex and semaphore

Simaphore/Binary Symaphore does not have ownership of the thread that locked it while mutex does.

This is how lock on mutex(spinlock) is implemented:

the test-and-set instruction is an instruction used to write 1 (set) to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. If multiple processes may access the same memory location, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process’s test-and-set is finished.

What’s happened in the Linux System after using ‘ls’ command

strace cmd tells us all activities behind the command.

Trees

  • Inorder, Pre-order can restore a tree

Known Problems

  • Longest Increasing sequence: nice trick is to use Arrays.searchBinary(arr,start,end,val) which will return the -(i+1) index that the val should be placed in case it wasn’t found – (if the array is not sorted). Link.
  • sort linked-list: with O(logn) and O(1) space: merge-sort bottom-up as refered here

Algorithms

  • Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a wighted graph,
  • Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step
  • Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

Java’s Interview tools

  • Use protected fields rarely: protected fields are accessible from subclasses of the class where it is declared, and from any class in the declared package.
  • four fundamental OOP concepts: encapsulation, inheritance, polymorphism, and abstraction
  • With composition (also called the decorator pattern), you give your new class a private field that references an instance of the existing class. Instance methods in the new class invoke a corresponding method in the existing class, i.e. method forwarding.
  • If you use PriorityQueue in java, the generic class must implement the interface
    Comparable<Tuple>
    which overrides the method:

    public int compareTo (Tuple that)
  • Count bits:
    Integer.bitCount(5) = 2

Data Structures

  • In Java, Heap is PriorityQueue
  • Divide and Conquir paradigm: In divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the subproblems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those “atomic” smallest possible sub-problem (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem.
  • Binary Heap: is a binary tree where all levels are filled. it can be implemented as an array. navigate to parent/left/right as follows:
    Arr[i/2] Returns the parent node
    Arr[(2*i)+1] Returns the left child node
    Arr[(2*i)+2] Returns the right child node

OOP

  • Encapsulation: Using public, private and protected with getters and setters.

Sort Problems

  • Bucket Sort – Top K Frequent Elements, here

Problems Worth review

  • Kth Smallest Element in a Sorted Matrix: link, Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the kth distinct element.Example:
    matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,
    
    return 13.

    Note:
    You may assume k is always valid, 1 ≤ k ≤ n2.
    Solution: Use a min heap: place the first row and take k-1 times the min element. when an element is out, put in the min heap the next element in the same column

  • Given sorted matrix NxN, you can find a number with time complexity O(logN): divide the matrix to 4 sections, choose the section where the number we are looking for is in the range…and do the same division to this section and so on..
  • Coins change Problem: Given infinite numbers of coins, given the denominations, how many ways there is for change?
    aaa
    S is the group of coins and m is the length of S. x is the sum that we want the change for

    Using dynamic programming: The variables are the number of coins and the value we are trying to calculate. so change[i][j] equals the number of ways to accomplish amount j using first i coins. we are looking for change[|S|][x].
    change[i][j] = change[i-1][j]+change[i][j-coins[i]]
    Means, that the way to accomplish change[i][j] is by using the i’th coin and by not using the i’th coin.
    We can make it more space efficient by using 1-dimention array:
    change[i] equals they number of ways to accomplish value i.
    for each coin, change[i] =change[i] + change[i-coin]

    d

  • Merge two lists: link here, Learn how to write a short solution.
  • Symmetric tree: the iterative solution got a nice twict. link here.
  • Palindrome list: link here, trick how to reach the middle of the list and convert it
  • Shortest Unsorted Continuous Subarray: link here,Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.You need to find the shortest such subarray and output its length.

  • Counting Bits: Bottom’s up paradigm solution. link here.
  • Queue Reconstruction by Height: link here
  • Find the Duplicate Number: here, the trick is two pointers, one fast and one slow. if they meet, then they meet in the loop. we keep the slow pointer rotating in the loop while we start a new pointer from the beginning. they will meet again in the beginning of the loop
  • Unique paths: here, Dynamic programming. what is the number of the paths that a robot who can go right or down tries to start from the up left corner to the bottom right. the solution is to use a matrix and do the bottom’s up approach: : suppose the number of paths to arrive at a point (i, j) is denoted as P[i][j], it is easily concluded that P[i][j] = P[i - 1][j] + P[i][j - 1].
  • Longest Substring Without Repeating Characters: Given a string, find the length of the longest substring without repeating characters.

  • Coin Change: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

  • Find loop in a list: This question is solved using the fast and the slow pointer.
    The slow pointer enters the cycle after k steps. The fast pointer by then walked 2k steps. Therefore, assuming the cycle length is m, then the distance of the slow pointer from the fast pointer is m-k. in order to kill that distance, on each step, the fast pointer will decrease the distance by 1 step as it goes twice faster. Therefore, after m-k steps that the slow pointer do (the fast went 2(m-k)), they will meet.
    However, After those m-k steps, the slow pointer will be k steps before the beginning of the cycle as its length is m.
    We don’t know how much is k. However, we can do a trick in order to find it:
    We send the slow pointer to the beginning and we slow down the fast pointer to go one step at a time. Now we let them run again with one step at a time. After the previously slow pointer moves k step, it will meet the previously fast pointer at the beginning of the cycle as they meet k steps before the beginning.Untitled
  • Amazon – Annapurna: Givan a Tx Queue with length 16bytes. when the queue sends the 5th byte(moving from capacity 5 to 4) an interrupt is sent. your API providessend_tx(buffer,size). implement a drive api with an interrupt handler. The stack API that the drive can use is push_tx(byte). you cannot overflow the queue as the result will not be expected.
    Notice: You are allowed to keep buffers until certain capacity is reached.
    Solution:

References
sort algorithms: https://www.topcoder.com/community/data-science/data-science-tutorials/sorting/
UML: https://www.visual-paradigm.com/guide/uml-unified-modeling-language/uml-aggregation-vs-composition/