MERGEPORT

mergeport

TL;DR As a developer preparing for interviews with FAANG companies, I found myself struggling with simple algorithms like string traversal and palindrome checks. However, I persevered and, after nine months of hard work, was able to master even more specific algorithms like KMP. During this time, I relied on a notebook and pen to visualise how sorting algorithms work and how numbers are compared. Where it started from When I began preparing for interviews with FAANG companies, I struggled with simple algorithms such as String traversal and palindrome checks. There were times when I almost gave up, but I have always been one to finish what I start. The same approach was applied here, and after nine months of hard work, I went from struggling with simple algorithms to understanding more specific ones like KMP (which I like a lot). On my journey to master these algorithms, I used a notebook and pen to visualise how sorting works, how numbers are compared, and where it all goes. This helped me to better understand the algorithms and improved my ability to work with them. We are all developers So why not create a project that visualises sorting algorithms in a more user-friendly way? Additionally, writing algorithmic solutions in a different language provides an extra opportunity to better understand and learn them. I took advantage of this opportunity to improve my knowledge and develop a stronger understanding of the sorting pathway. By creating a mobile application using Flutter, I was able to utilise my experience with cross-platform development to build an effective tool for visualising complex algorithms, particularly sorting. This allowed me to further improve my knowledge and understanding of these algorithms while also creating a user-friendly platform for others to do the same. Flutter is a handy tool With solid experience in developing cross-platform applications using the Flutter framework, I chose to utilise it to create a mobile application for both Android and iOS operating systems. Currently, the same code can run on web and desktop platforms if I add support. During the process I achieved: I was able to write the same algorithms with Dart on top of Java implementations that I had done previously on and (both great resources for interview preparation). Leetcode AlgoExpert I learned about the (recommended to use ) state management pattern, which was not previously in my development stack. Provider allows for a great separation of logic and UI and reactively updates UI with consumed data, making updates process very smooth. Provider Riverpod I also pushed my imagination beyond the norm and transformed a simple set of numbers into visually-pleasing widgets. To simplify the understanding of the algorithms, users can turn the numbers on and off. My implementation Each sorting algorithm is a descendant of BaseSort, which, in turn, is a ChangeNotifier. The details of each algorithm’s implementation are covered under its specific implementation: BubbleSort, HeapSort, InsertionSort, MergeSort, and SelectionSort. BaseSort only covers the basic parts of each algorithm, such as the references of left and right pointers, as well as the index of the sorted part. This class is responsible for generating random data and notifying each subscriber of a new dataset. class BaseSort with ChangeNotifier {
  BaseSort() {
    generateData();
  }

  List<int> array = List.empty(growable: true);

  int left = -1;
  int right = -1;
  int sorted = -1;

  bool isSorting = false;

  @mustCallSuper
  void generateData() {
    array.clear();
    isSorting = false;
    int counter = 0;
    final rand = Random();
    left = -1;
    right = -1;
    sorted = -1;

    while (counter < 50) {
      // to show anything in case of 0 -> shifting it to 1
      array.add(rand.nextInt(99) + 1);
      counter++;
      notifyListeners();
    }
  }

  Future startSorting() async {}

  Future sleep() async {
    await Future.delayed(const Duration(milliseconds: 150), () {});
  }
} BaseSortWidget is an abstract class that represents a collection of common widget parts, with several abstract methods to be implemented in each specific algorithm widget. abstract class BaseSortWidget extends StatelessWidget {
  @override
  Widget build(BuildContext context) => Card(
        margin: const EdgeInsets.all(8.0),
        elevation: 2.0,
        shape: const RoundedRectangleBorder(
          borderRadius: BorderRadius.all(Radius.circular(12.0)),
        ),
        child: Padding(
          padding: const EdgeInsets.all(12.0),
          child: Column(
            mainAxisAlignment: MainAxisAlignment.center,
            children: <Widget>[
              Text(
                algorithmName(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
              const SizedBox(height: 10),
              consumerWidget(),
              const SizedBox(height: 10),
              Text(
                algorithmComplexity(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
            ],
          ),
        ),
      );
} Each algorithm widget implementation, with the exception of SelectionSort, is simplified to a state of: class HeapSortWidget extends BaseSortWidget {
  @override
  String algorithmName() => HEAP_SORT;

  @override
  String algorithmComplexity() => 'Time: O(n*log(n))  Space: O(1)';

  @override
  Widget consumerWidget() => Consumer<HeapSort>(
        builder: (context, state, _) => Row(
          mainAxisAlignment: MainAxisAlignment.center,
          crossAxisAlignment: CrossAxisAlignment.end,
          children: buildItemsArray(
            state.array,
            state.left,
            state.right,
            state.sorted,
            Colors.cyan,
          ),
        ),
      );
} All the other parts are merely for aesthetic purposes, to create a cleaner and more elegant code. The main screen is a list of sorting widgets. Consumer<SortHolder>(
  builder: (context, types, _) {
    final List<Widget> widgets = types.generateWidgets(context);
    return widgets.isEmpty
        ? Center(
            child: Text(
              '$DRAWER_TITLE\n\n$EMPTY_MESSAGE',
              textAlign: TextAlign.center,
              style: Theme.of(context)
                  .textTheme
                  .bodyLarge
                  .copyWith(fontSize: 18.0),
            ),
          )
        : ListView(
            padding: const EdgeInsets.all(8),
            children: widgets,
          );
  },
) Whenever we add or remove widgets, the screen updates with more or fewer items. To hold data about widgets and to shuffle data/start sorting, we used SortHolder. The view The resulting view of my work looks very neat and is easily understandable. Sorting process Observing the sorting process is a true pleasure. Additionally, it is an easier way to understand the sorting algorithm by seeing which data is being compared. The left pointer is represented by yellow, while the right pointer is represented by red. Enjoy! Summary While preparing to algorithmic and data-structure interviews it might be tricky to master these complex topics. People are using different approaches to make is simpler, and easier to understand. Having no whiteboard, which could help me to visualise data, I have found simple notebook and pen quite useful, but for automatisation of the process and to repeat algorithms again, I have used coding, one instrument I am good at. Now we can observe how these algorithms are working. But I would love to extend this knowledge base with other more complex algorithms, which might be even harder to visualise. But still possible. I am calling everyone, who want to participate in this project, to contribute to my gitHub via pull requests. I am happy to dedicate time for short catch-ups and collaboration. https://github.com/VadymPinchuk/visualizer?embedable=true

From Chaos to Order: Achieving Understanding of Algorithms Through Visualization

Most of the time, when writing code for a Technical Interview or just to on Data Structures & Algorithms skills, sometimes is forgotten two important aspects: and being in the Programming Language being used. brush up Code Quality idiomatic That's why I decided to write this post. This post will go through some concepts. Kotlin Understanding the problem The LeetCode problem the following, states Given an integer array where the elements are sorted in ascending order, convert it to a
height-balanced[^1] binary search tree. nums Before we start off, there are some important observations: is already sorted. nums An is given as an . So, accessing an element will be a constant-time operation . Array input O(1) The length is at most so the time complexity must be one. nums 10^4 a good The resulting Binary Search Tree must be . height-balanced That's the LeetCode definition of a Binary Tree: class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
} Algorithm (Recursive solution) Here's when technique comes into play. Divide and Conquer These are the steps to follow to create the BST: Let the size of the array and the index of the middle element, and pick as the . n A m = n/2 A[m] root of the BST[^2] Consider the two following contiguous subarrays; and respectively with as a 0-indexed array, the left and right sub contiguous subarrays. A[… m-1] A[m+1 …] A Create the left and right subtrees with and sub contiguous subarrays recursively following step . A[… m-1] A[m+1 …] (1) Repeat recursively until an empty subarray is encountered. When this happens the node will hold a value. null The following diagram depicts the idea: Kotlin Implementation class Solution {
    fun sortedArrayToBST(nums: IntArray): TreeNode? {
        fun makeTree(start: Int, end: Int): TreeNode? =
            if (start >= end) {
                null
            } else {
                val mid = start + (end - start) / 2

                TreeNode(nums[mid]).apply {
                    left = makeTree(start, mid)
                    right = makeTree(mid + 1, end)
                }
            }

        return makeTree(0, nums.size)
    }
} Code Analysis Kotlin provides a in the type system. That's the reason the type is instead of . Null safety TreeNode? TreeNode We can know when a value is nullable or not at compile-time. A was created for building the tree. Note that is accessible inside the function. Local function makeTree nums makeTree The and are used as delimiters in the Binary Search. The reason is to avoid the creation of new subarrays. start end When performing a Binary Search within a range, there's a common mistake that leads to integer overflow[^3]. That snippet would cause an overflow val mid = (start + end) / 2 In order to avoid overflow, the index is computed as mid val mid = start + (end - start) / 2 In Kotlin, is an , it returns a value. Taking advantage of that property, either returns an empty node ( ) or a . if expression makeTree null TreeNode Returns if there isn't a valid range to look up in the Binary Search. null A new having as an element the as value and, the left and right subtrees are built recursively. TreeNode mid The function is a . Is used for assigning the values of the and subtrees. It's convenient when modifying the properties of a class in a Kotlin-idiomatic way. apply Scope function left right TreeNode(nums[mid]).apply {
    left = makeTree(start, mid)
    right = makeTree(mid + 1, end)
} Complexity Analysis : , where stands for the size of the array. Time complexity O(n) n : , where stands for the height of the BST. The maximum depth of the recursion in the stack is . Space complexity O(h) h h Ergo, the BST is built in linear time and the space needed is . h [^1]: A binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. height-balanced [^2]: For the sake of simplicity, will stand for Binary Search Tree. BST [^3]: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Convert Sorted Array to Binary Search Tree

Big O Notation, collectively called Bachmann-Landau notation or asymptotic notation, is a way to describe the performance of an algorithm. It is used to describe the worst-case scenario of an algorithm. It is used to compare the performance of different algorithms. It describes the implementation of an algorithm in terms of the input size. Big O notation characterizes functions according to their growth rates: tasks with the same growth rate are considered to be of the same order. It is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify algorithms according to how their run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also called its order. Iteration For loop for (let i = 0; i < n; i++) {
  console.log(i)
} The above code will run n times. The time complexity of this code is O(n). While loop let i = 0
while (i < n) {
  console.log(i)
  i++
} The above code will run n times. The time complexity of this code is O(n). Do while loop let i = 0
do {
  console.log(i)
  i++
} while (i < n) The above code will run n times. The time complexity of this code is O(n). Recursion Factorial function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
} The above code will run n times. The time complexity of this code is O(n). Fibonacci function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
} The above code will run n times. The time complexity of this code is O(n). Searching Linear search function linearSearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return i
    }
  }
  return -1
} The above code will run n times. The time complexity of this code is O(n). Binary search function binarySearch(arr, value) {
  let start = 0
  let end = arr.length - 1
  let middle = Math.floor((start + end) / 2)
  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1
    } else {
      start = middle + 1
    }
    middle = Math.floor((start + end) / 2)
  }
  if (arr[middle] === value) {
    return middle
  }
  return -1
} The above code will run log(n) times. The time complexity of this code is O(log(n)). Sorting Bubble sort function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Selection sort function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      let temp = arr[i]
      arr[i] = arr[lowest]
      arr[lowest] = temp
    }
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Insertion sort function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Merge sort function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  let results = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      results.push(left[i])
      i++
    } else {
      results.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    results.push(left[i])
    i++
  }
  while (j < right.length) {
    results.push(right[j])
    j++
  }
  return results
} The above code will run n log(n) times. The time complexity of this code is O(n log(n)). Quick sort function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start]
  let swapIdx = start
  function swap(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
  }
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++
      swap(arr, swapIdx, i)
    }
  }
  swap(arr, start, swapIdx)
  return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
} The above code will run n log(n) times. The time complexity of this code is O(n log(n)). Tips for Big O Arithmetic operations are constant Variable assignment is constant Accessing elements in an array (by index) or object (by key) is constant In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop Resources Big O Cheat Sheet Big O Notation Big O Notation Originally published . here

The Big O Notation in JavaScript

There is no doubt cracking the Coding interviews of top tech companies like Google, Microsoft, and Amazon is very hard, but you can still crack it by carefully planning and preparing the essential skills which matter most like , , , , and of course, . Data structures and Algorithms System Design Multithreading and Concurrency SQL and Database design problem-solving skills Being an author of Java and a programming blog, I often receive queries about Or how can I get a software development job on Amazon or Facebook? how to prepare for coding interviews? How to pass Google or Microsoft Software Developer interviews? After answering many of my readers one by one on Facebook and LinkedIn, I thought to put together a list of . essential topics for coding interviews This list will give a good head-start for your preparation for any tech company interview like Google and Amazon. However, even if you are not targeting Google and just want a Software developer job, you can still prepare these topics. In fact, preparing for tech giants like Google, Amazon, Apple, and Facebook means you are miles ahead of other candidates, and you will most likely secure many job offers from smaller firms, startups, and investment banks. That's why I suggest aiming higher because even if you don't get what you want, you will still get job offers that are desirable by many programmers. Another critical thing to note is that different interviews need different skills. For example, when you go for a , you are bound to know Java. Similarly, for a Python developer interview, it's expected you to know Python and some popular Python frameworks like and . Java developer interview Django Flask For a Web developer, HTML, CSS, and JavaScript are core skills, and you will be grilled on those, apart from modern web development frameworks like , , and , with a bit of as well. Angular React Vue.js node.js I'll not touch, that topic but I'll share essential skills that are required to pass all of those interviews. They are also known as core programming skills, and it's expected from every Software developer to know that. How to Prepare for Coding and Programming Interviews - Topics and Skills Anyway, without wasting any more of your time, here is my list of topics you can prepare to boost your chances on Google, Amazon, and Microsoft Programming Job Interviews. 1. Data Structure As a programmer, it's OK if you cannot write web apps using or but it's not OK if you don't know how a hash table works and when to use a list over an array? And, Data Structure and Algorithms are the core of computer science and programming, and it's expected for every software developer to have a solid knowledge of fundamental data structure. Django React, what advantages B-Tree offer over an array? It's imperative to have a good understanding of data structure for writing a robust, performant application that your users will appreciate. Imagine, if Facebook or Google takes 1 minute to log you in, you will never go there, forget how important they are. Performance is critical, and unless you understand how your program is working and how your data is stored, you will not go anywhere. In , you will be asked to optimize your solution for time and space. You can't do that unless you have a solid understanding of how your code works and how data is stored and accessed. technical interviews This is probably the most important topic for coding interviews and you should prepare it well. At a bare minimum, you should know about the , , , binary search tree, self-balanced trees like AVL tree, hash table(or map or dictionaries as known in Java and Python) stack, queue, and graph. array linked list binary trees You should understand how to store and access elements from these data structures and the computing cost involved. You should also have a comparative analysis of when to use a particular data structure like for a faster search array, and the hash table is better. Still, for faster addition and deletion, a linked list will outperform an array. If you need a resource to get up to speed, I suggest you pick a data structure course where examples are shown in the language you are most comfortable with. For Java developers, I recommend , and for Python Programmers, I recommend Algorithms and Data Structure in Python course on Udemy. You can check out that course . Data Structure and Algorithms: Deep Dive in Java here 2. Algorithms While it's important to know the essential data structure like an array, linked list, and trees, it's equally important to learn how to work with those data structures. If you don't know the difference between linear search and binary search algorithms, and what it means to run in O(log n) as opposed to O(n^2), you need to spend some time learning algorithms. This can often be the difference between a fine-tuned application and a slow, crappy process that hangs more than it works. At a bare minimum, you should know about sorting algorithms like , , heapsort, etc. searching algorithms like binary search, and some graph algorithms like fastest route-finding algorithms, which are the base of many deliveries and taxi-hailing apps like Uber, Grab, and Ola. quicksort mergesort You should also understand how the library methods you are using for sorting an array work, which algorithm it uses internally, and when a different algorithm would do a better job. I strongly suggest you prepare for this topic in depth. If you need a resource, Thomas H. Cormen's " is the most recommended resource, but it's not for the faint-hearted. For a less intimidating entry, I would recommend the book by Aditya Bhargava and Algorithms course on Coursera. Introduction to Algorithms," Grokking Algorithms 3. System Design This is another crucial topic you need to prepare well for your programming job interviews, especially at big tech companies like , , , and Facebook. You need to have some ideas about how to design your solution from architecture to coding. Google Microsoft Amazon System design is actually very vast. At a high level, it covers things like software architecture, I mean the advantage between monolithic and microservice architecture and choosing between a and . NoSQL SQL database It covers things like how we will design an application that can handle 10000 concurrent users, and includes things like scalability. At a low level, it covers Object-Oriented Programming and Design, which talk about designing your classes and their relationships, following good coding practices, and software design principles like SOLID. Because of this, many candidates struggle to answer system design questions, and if you want to succeed, you must put particular emphasis on this skill. If you need a resource, I recommend you to check about the course on Educative, which is prepared by people who served as hiring managers on those tech companies, and it also walks you through common system design interview questions. Grokking System Design Interview For Object-Oriented design and analysis, I recommend the Head First Object-Oriented design book to learn fundamentals and course on Educative for some practice. Grokking the Object-Oriented Interviews 4. Multithreading and Concurrency Concurrency is one of the most desired skills by employers, and also one of the most advanced topics brought up in interviews. Because it shows your ability to design a program that efficiently uses resources but at the same time it's a very tricky topic to master and that's why interviewers love it. can also be used to gauge your expertise and technical depth and is often uses as a key deciding factor in your overall hiring level. Whether you are just entering your career or are looking to switch jobs, it never hurts to dedicate some time to mastering concurrency. Concurrency At a bare minimum, you should know about threads, processes, shared memory, monitors, locks, critical section, and deferred callbacks. Having a good knowledge of how to avoid race conditions and deadlock can be even better. Practicing classical concurrency interview questions like , Dining Philosopher, and others can also teach you a lot about concurrency and multithreading and give you the confidence to visualize how code and data work when multiple threads run in parallel. Producer-Consumer If you have an interviewing coming up, then I highly suggest you double down on concurrency. This is because I know it can be one of the most challenging topics brought up during most of the interviews, even for experienced developers. However, gaining a mastering concurrency will put you at a considerable advantage over other candidates. If you need resources, I strongly suggest you check out by C.H. Afzal on Educative. This course contains the most common concurrency interview questions solved in Python, Java, C#, and Ruby. Going through those questions will give you a good background on Concurrency and Multithreading. Multithreading and Concurrency Interview Questions 5. SQL and Database Design As a software developer, working with a relational database is a critical skill that you'll need, and it will stick with you no matter where you are in your career. Every company from small to large uses a DBMS, so it's likely that you will come across different data models, type so databases ( and ), and dependencies on various companies. NoSQL SQL Knowing how to structure your data within a DBMS is critical. Should you use an entity-relationship (ER), model? A hierarchical model? A three-schema architecture? The choices can be intimidating, but it's good to know about the different ways to structure your data as that when you switch database vendors like from to or , you can plugin with minimal hand-coding. Oracle SQL Server PostgreSQL As a programmer, you should also know about SQL, not just the syntax but also how the database actually runs your query and how joins are executed, how to index are used, and the difference between table scan, index scan, and index seek. These details are not just important from the coding interview perspective but also from day-to-day jobs. If you need resources, I suggest you go through with , where you will learn about the different concepts and techniques you can use to structure your data and explore why you should use particular approaches for certain problems. Database Design Fundamentals for Software Engineers You will also be exposed to techniques like normalization, which help to increase the efficiency o the database, and avoid duplication. I also suggest you go through an SQL-focused course like by Jose Portilla on Udemy as SQL queries are also an essential part of coding interviews along with database design. I also suggest Use The Index Luke book to better understand how SQL query works in general. The Complete SQL BootCamp 6. AWS, Docker, and Kubernetes While these five are definitely must-have skills for coding interviews, employers are nowadays also looking for modern tech skills like AWS, Docker, and Kubernetes, which makes them important topics for technical interviews. Since cloud computing is the next big thing and this decade of software development will be cloud-native, it's better for a software developer to know about Cloud and modern deployment tools like and . Docker Kubernetes This is also important if you want to stay ahead of the curve and give a reason to your employer to hire you than the next candidate in line. For AWS and Cloud, one more thing you can do is to get a certification, not because you can't get a job without certification but to learn better and get recognition for your skill. For AWS, I suggest you at least have an to showcase necessary cloud skills, and if you prefer Microsoft Azure, then Azure Fundamentals ( ) is an excellent certification to start with. AWS Cloud Practitioner certification AZ-900 Docker is a container, which allows you to run your application as a whole, along with all the dependencies. This makes both development and deployment easier, particularly for . Since the container makes cloud deployment more manageable, they are also easier for the manager to scale up and down. Microservices is a container orchestration tool, which means it can use manager containers at scale. Kubernetes It's easy to deploy and manage a few boxes, but when you have to deploy 100s of containers for your application for a promotion event like Amazon prime Sale and then need to take it down once traffic returns to normalcy is not easy. can do that for you and provide automation and peace of mind. Kubernetes While both Docker and Kubernetes are not mandatory skills for a programmer but definitely essential from the Job perspective. I recommend every Software developer or aspiring programmer to learn Docker and Kubernetes, and if you need a resource, Stephen Grider's online course -** ** on Udemy is a great starting point. Docker and Kubernetes: The Complete Guide That's all about some of the most of companies like Google, Microsoft, Apple, Facebook, and Amazon. Along with these topics, I have also listed some of the and you can take to learn those skills and be better prepared for your next coding interview. important skills and topics you can prepare to crack the coding interview best books courses Other Programming and Java Articles you May like 10 courses to crack Coding Interviews 10 Websites to Practice Coding Problems 10 Books to Prepare Technical Programming/Coding Job Interviews 10 Algorithm Books Every Programmer Should Read Top 5 Data Structure and Algorithm Books for Java Developers My favorite free courses to learn Algorithms in depth 10 Free Data Structure Courses for Java Developers Top 10 Free Courses to learn AWS 10 Free Courses to learn Docker for Programmers 10 Tips and 101 Coding Problems to Crack Programming Interview 10 Best System Design courses for Coding interviews 6 Best Dynamic Programming Courses for Interviews 100+ Data Structure and Coding Problems for Interviews Thanks for reading this article so far. If you find these useful, then please share them with your friends and colleagues. If you have any questions or feedback, then please drop a note. Coding interview skills and topics If you are aiming for FAANG (Facebook, Amazon, Apple, NetFlix, and Google) companies then I also suggest you join the course by Andrei Negaoie on ZTM Academy. FAANG interviews are the toughest to crack and this course is a valuable resource to crack FAANG interviews. P. S. - First Published . here

How to Crack Coding Interviews? Tips, Topics, and Skills

In this article, I will show you how to use the , which hasn’t received significant dissemination among Java developers. ForkJoinPool is one of the ’s implementations. It is used in and Stream API. It was designed to simplify parallelism for recursive tasks by breaking the single task into independent ones until they are small enough to be executed asynchronously. With this class, you can perform a significantly large amount of tasks in a small number of threads. ForkJoinPool ExecutorService CompletableFuture Java has a common implementation that can be created through the static method: ForkJoinPool commonPool() ForkJoinPool forkJoinPool = ForkJoinPool.commonPool(); ForkJoinTask has its own and implementations. These implementations are called and respectively. Each of them has an abstract method, which must be implemented during implementation. returns generic <T> value, returns void. Both of these implementations are inherited from the abstract class. ForkJoinTask Runnable Callable RecursiveAction RecursiveTask compute() RecursiveTask<T>#compute() RecursiveAction#compute() ForkJoinTask To start a task in , use the method : ForkJoinPool T invoke(ForkJoinTask<T> task) ForkJoinTask forkJoinTask = new ForkJoinTaskImpl(...);
forkJoinPool.invoke(forkJoinTask); In addition to the method, has the following methods: and . In terms of usage, the is similar to the . But in the case of a fork-join, the thread may not actually fall asleep, it will rather switch to another task. This strategy is called “work stealing”, it allows more efficient use of a limited number of threads. compute() ForkJoinTask fork() join() ForkJoinTask#join() Thread#join() Fibonacci example Let's look at the simple example of the implementation for calculating the Fibonacci numbers: ForkJoinTask public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    public FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    public Integer compute() {
        if (n < 2) return n;
        FibonacciTask f1 = new FibonacciTask(n - 1);
        FibonacciTask f2 = new FibonacciTask(n - 2);
        f1.fork();
        return f2.compute() + f1.join();
    }
} In this example, implements the method, which creates additional instances and forks them. The method asks the current thread to wait until results are returned by the forked methods. FibonacciTask compute() FibonacciTask join() Merge Sort Let's take a look at the more complex example of - the Merge Sort. It is based on the "Divide and Conquer" principle, old as the world. We need to divide source problems into subtasks, solve them recursively and combine the results: ForkJoinTask For this task we will use as the implementation, since we don't need a return value. We will add as a parameter to the constructor and instantiate the class's field: RecursiveAction ForkJoinTask int[] arr public class MergeSortAction extends RecursiveAction {

    private final int[] arr;

    public MergeSortAction(int[] arr) {
        this.arr = arr;
    }

    @Override
    public void compute() {
        ...
    }

    private void merge(int[] left, int[] right) {
        ...
    }

} Next, we implement the method. It will accept 2 arrays - and parts. We need to merge these unsorted arrays by comparing elements and assigning the smallest element to the appropriate arr index. When one of the arrays will be empty, the loop will break, but the data from another non-empty array part still needs to be merged. To do this we have two additional while loops to get all the data from both arrays: merge() left right while private void merge(int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
} Next, we will write the method to recursively divide the original array and pass the results to the method. To do this we need to calculate the middle index of the array. Then we divide the original array into two parts: and . To fill them we copy original data by calling : compute() merge() left right System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) @Override
public void compute() {
    if (arr.length < 2) return;
    int mid = arr.length / 2;

    int[] left = new int[mid];
    System.arraycopy(arr, 0, left, 0, mid);

    int[] right = new int[arr.length - mid];
    System.arraycopy(arr, mid, right, 0, arr.length - mid);

    ...
} Now, we have two separate arrays. Let’s divide them recursively by creating new tasks and run them asynchronously by passing them into method. To sort and combine two arrays we use method: MergeSortAction invokeAll() merge() @Override
public void compute() {
    if (arr.length < 2) return;
    int mid = arr.length / 2;

    int[] left = new int[mid];
    System.arraycopy(arr, 0, left, 0, mid);

    int[] right = new int[arr.length - mid];
    System.arraycopy(arr, mid, right, 0, arr.length - mid);

    invokeAll(new MergeSortAction(left), new MergeSortAction(right));
    merge(left, right);
} Speed testing We’ve finished our parallel Merge Sort. Let’s test it and compare performance with the non-parallel version. I used to generate random numbers and to calculate the execution time: ThreadLocalRandom ZonedDateTime class MergeSortTest {

    private final List<MergeSort> mergeSortImpls = 
            Arrays.asList(new MergeSortImpl(), new ParallelMergeSortImpl());

    @Test
    void sort() {
        for (MergeSort mergeSort : mergeSortImpls) {
            int[] arr = IntStream
                    .range(0, 100_000_000)
                    .map(i -> ThreadLocalRandom.current().nextInt())
                    .toArray();
            ZonedDateTime now = ZonedDateTime.now();
            mergeSort.sort(arr);
            System.out.printf("%s exec time: %dms\n",
                    mergeSort.getClass().getSimpleName(),
                    ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
            assertTrue(isSorted(arr));
        }
    }

    private boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

} There are the execution results for 100 million of numbers on 8-core CPU: Conclusion In this article, I showed you an example of how to use Fork/Join Framework. I hope you now have a basic idea of how to speed up your applications. The source code is available . over on GitHub

Parallel Merge Sort with Fork/Join Framework

We see algorithms used in pretty much every program that’s larger than a college project. These algorithms sometimes power necessary functionality inside these programs. That’s why it is essential to make sure that they are running efficiently. Even in situations where execution speed doesn’t matter much, it feels good to know that you are not coding a highly inefficient algorithm implementation. Before we begin this article, it is essential to note that memory usage is just as crucial as its runtime. I think this bites new programmers more often than speed inefficiencies because the consequences of exhausting system memory or using so much that there isn’t a reasonable amount left for other running processes can be fatal. By contrast, the only setback people suffer from a slow program is just time wasted waiting. Complexity and Big-O notation Runtime and memory usage are measured using a metric called portrayed in Big-O notation, simply the letter “O” followed by an expression in brackets. There are several different variants of Big-O, but by far, the representation is the most commonly used. Inside the parentheses is a variable such as , representing the input size to the algorithm. Of course, it is possible to use more than one variable inside the parentheses to define other factors and constants. complexity O n Specifically, means that the algorithm runtime or memory usage approaches units as the input size itself approaches infinity. The words used in the definition are very important. Big-O means that we equal an equal or shorter time or space measure at infinite input size. Little-O means the function time or space is strictly less than the complexity expression. While Big-Theta notation means it exactly equals the complexity. You might as see people using exclusively Big-O, but having three different expressions, each referring to , , and complexities. I think that’s an easier way to understand this concept. O(n) n n o(n) Θ(n) best case average worst-case For all the above, the measures of functions are still valid if the complexity expression is multiplied by an unknown constant, in other words. O-notation doesn’t care whether the complexity is or because the complexity in both cases increases honestly. n 30n This brings us to the complexity expressions themselves. Expressions Here are the complexities you will see most often with Big-O notation, with some examples of each: Constant: O(1) — Means the time or space is constant regardless of the input size, such as array access Logarithmic: O(log(n)) — The time/space is logarithmic with respect to the input size, such as binary search Linear: O(n) — The time/space is linear to the input size, such as iteration and linear search Linearithmic or Superlinear: O(n log(n)) — The time/space is linear multiplied by log(n) with respect to the input size, such as quicksort, mergesort, heapsort Quadratic: O(n**2) — The time/space is quadratic to the input size, i.e., for a given input size n the runtime or memory usage is squared. Insertion sort is an example of quadratic complexity. Cubic: O(n**3) — The time/space is cubic to the input size, such as Strassen’s Matrix Multiplication Exponential: O(2**n) — The time/space is exponential to the input size. Note that the 2 is a constant which any other number can replace. An example is the Traveling Salesman Problem Clearly, from the above list, you can see that exponential complexity is the worst possible runtime or space usage, while constant runtime is the best. Everyone wants to use algorithms that have constant complexity, but in most cases, this is not possible because there are no known implementations of those algorithms that have that simple complexity. Generally speaking, each algorithm has a minimum complexity which corresponds to the most efficient known implementation of that algorithm. So, that’s all about algorithmic complexity. Thanks for reading. Also published at https://medium.com/@zenul_abidin/algorithmic-complexity-basics-8c6a2aef54c2

A Brief Introduction to Algorithmic Complexity

In case you missed it, I using a from . Then I built a to serve the model’s predictions. That’s nice and all, but… how is my model? built a neural network to predict loan risk public dataset LendingClub public API good Today I’m going to put it to the test, pitting it against the risk models of the very institution who issued those loans. That’s right, LendingClub included their own calculated loan grades (and sub-grades) in the dataset, so all the pieces are in place for the most thrilling risk modeling smackdown of this century (or at least this week). May the best algorithm win! joblib

prev_notebook_folder = loans = joblib.load(prev_notebook_folder + )
loans.shape import "../input/building-a-neural-network-to-predict-loan-risk/" "loans_for_eval.joblib" (1110171, 70) loans.head() ┌────┬────────────┬────────────┬─────────────┬─────────────────┬─────────────┬─────────────────────┬────────┬──────────────┬───────────────────┬─────────────────┬──────┬────────────┬──────────────────┬────────────────────┬─────────────────┬─────────────────────────────┬─────────────────────┬───────────┬────────┬────────────┬─────────────────┐
│    │ loan_amnt  │   term     │ emp_length  │ home_ownership  │ annual_inc  │      purpose        │  dti   │ delinq_2yrs  │ cr_hist_age_mths  │ fico_range_low  │ ...  │ tax_liens  │ tot_hi_cred_lim  │ total_bal_ex_mort  │ total_bc_limit  │ total_il_high_credit_limit  │ fraction_recovered  │ issue_d   │ grade  │ sub_grade  │ expected_return │
├────┼────────────┼────────────┼─────────────┼─────────────────┼─────────────┼─────────────────────┼────────┼──────────────┼───────────────────┼─────────────────┼──────┼────────────┼──────────────────┼────────────────────┼─────────────────┼─────────────────────────────┼─────────────────────┼───────────┼────────┼────────────┼─────────────────┤
│ 0  │    3600.0  │ 36 months  │ 10+ years   │ MORTGAGE        │    55000.0  │ debt_consolidation  │  5.91  │         0.0  │            148.0  │          675.0  │ ...  │       0.0  │        178050.0  │            7746.0  │         2400.0  │                    13734.0  │                1.0  │ Dec-2015  │ C      │ C4         │         4429.08 │
│ 1  │   24700.0  │ 36 months  │ 10+ years   │ MORTGAGE        │    65000.0  │ small_business      │ 16.06  │         1.0  │            192.0  │          715.0  │ ...  │       0.0  │        314017.0  │           39475.0  │        79300.0  │                    24667.0  │                1.0  │ Dec-2015  │ C      │ C1         │        29530.08 │
│ 2  │   20000.0  │ 60 months  │ 10+ years   │ MORTGAGE        │    63000.0  │ home_improvement    │ 10.78  │         0.0  │            184.0  │          695.0  │ ...  │       0.0  │        218418.0  │           18696.0  │         6200.0  │                    14877.0  │                1.0  │ Dec-2015  │ B      │ B4         │        25959.60 │
│ 4  │   10400.0  │ 60 months  │ 3 years     │ MORTGAGE        │   104433.0  │ major_purchase      │ 25.37  │         1.0  │            210.0  │          695.0  │ ...  │       0.0  │        439570.0  │           95768.0  │        20300.0  │                    88097.0  │                1.0  │ Dec-2015  │ F      │ F1         │        17394.60 │
│ 5  │   11950.0  │ 36 months  │ 4 years     │ RENT            │    34000.0  │ debt_consolidation  │ 10.20  │         0.0  │            338.0  │          690.0  │ ...  │       0.0  │         16900.0  │           12798.0  │         9400.0  │                     4000.0  │                1.0  │ Dec-2015  │ C      │ C3         │        14586.48 │
└────┴────────────┴────────────┴─────────────┴─────────────────┴─────────────┴─────────────────────┴────────┴──────────────┴───────────────────┴─────────────────┴──────┴────────────┴──────────────────┴────────────────────┴─────────────────┴─────────────────────────────┴─────────────────────┴───────────┴────────┴────────────┴─────────────────┘
5 rows × 70 columns This post was adapted from a Jupyter Notebook, by the way, so if you’d like to follow along in your own notebook, go ahead and fork mine or ! Kaggle GitHub Ground rules This is going to be a clean fight—my model won’t use any data LendingClub wouldn’t have access to at the point they calculate a loan’s grade (including the grade itself). I’m going to sort the dataset chronologically (using the column, the month and year the loan was issued) and split it into two parts. The first 80% I’ll use for training my competition model, and I’ll compare performance on the last 20%. issue_d sklearn.model_selection train_test_split

loans[ ] = loans[ ].astype( )
loans.sort_values( , axis= , inplace= , kind= )

train, test = train_test_split(loans, test_size= , shuffle= )
train, test = train.copy(), test.copy()
print( ) from import "date" "issue_d" "datetime64[ns]" "date" "index" True "mergesort" 0.2 False f"The test set contains loans." {len(test):,} The test set contains 222,035 loans. At the earlier end of the test set my model may have a slight informational advantage, having been trained on a few loans that may not have closed yet at the point LendingClub was grading those ones. On the other hand, LendingClub may have a slight informational advantage on the later end of the test set, since they would have known the outcomes of some loans on the earlier end of the test set by that time. I have to give credit to Michael Wurm, by the way, for of comparing my model’s performance to LendingClub’s loan grades, but my approach is pretty different. I’m not trying to simulate the performance of an investment portfolio; I’m just evaluating how well my predictions of simple risk compare. the idea Test metric The test: who can pick the best set of grade A loans, judged on the basis of the independent variable from , the fraction of an expected loan return that a prospective borrower will pay back (which I engineered as ). my last notebook fraction_recovered LendingClub will take the plate first. I’ll gather all their grade A loans from the test set, count them, and calculate their average . That average will be the metric my model has to beat. fraction_recovered Then I’ll train my model on the training set using the same pipeline and parameters I settled on in . Once it’s trained, I’ll use it to make predictions on the test set, then gather the number of top predictions equal to the number of LendingClub’s grade A loans. Finally, I’ll calculate the same average of on that subset, and we’ll have ourselves a winner! my last notebook fraction_recovered LendingClub's turn statistics mean

lc_grade_a = test[test[ ] == ]
print( )

print( )
print(round(mean(lc_grade_a[ ]), )) from import "grade" "A" f"LendingClub gave loans in the test set an A grade." {len(lc_grade_a):,} "\nAverage `fraction_recovered` on LendingClub's grade A loans:" "fraction_recovered" 5 LendingClub gave 38,779 loans in the test set an A grade.

Average `fraction_recovered` on LendingClub's grade A loans:
0.96021 That’s a pretty high percentage. I’m a bit nervous. My turn First, I’ll copy over my function from : run_pipeline my previous notebook sklearn.model_selection train_test_split sklearn_pandas DataFrameMapper sklearn.preprocessing OneHotEncoder, OrdinalEncoder, StandardScaler tensorflow.keras Sequential, Input tensorflow.keras.layers Dense, Dropout X = data.drop(columns=[ ])
    y = data[ ]
    X_train, X_valid, y_train, y_valid = (
        train_test_split(X, y, test_size= , random_state= ) validate (X, , y, )
    )

    transformer = DataFrameMapper(
        [
            (onehot_cols, OneHotEncoder(drop= )),
            (
                list(ordinal_cols.keys()),
                OrdinalEncoder(categories=list(ordinal_cols.values())),
            ),
        ],
        default=StandardScaler(),
    )

    X_train = transformer.fit_transform(X_train)
    X_valid = transformer.transform(X_valid) validate input_nodes = X_train.shape[ ]
    output_nodes = model = Sequential()
    model.add(Input((input_nodes,)))
    model.add(Dense( , activation= ))
    model.add(Dropout( , seed= ))
    model.add(Dense( , activation= ))
    model.add(Dropout( , seed= ))
    model.add(Dense( , activation= ))
    model.add(Dropout( , seed= ))
    model.add(Dense(output_nodes))
    model.compile(optimizer= , loss= )

    history = model.fit(
        X_train,
        y_train,
        batch_size=batch_size,
        epochs= ,
        validation_data=(X_valid, y_valid) validate ,
        verbose= ,
    ) history.history, model, transformer


onehot_cols = [ , , , ]
ordinal_cols = { : [ , , , , , , , , , , ,
    ]
} from import from import from import from import from import : def run_pipeline (
    data,
    onehot_cols,
    ordinal_cols,
    batch_size,
    validate=True,
) "fraction_recovered" "fraction_recovered" 0.2 0 if else None None "if_binary" if else None 1 1 64 "relu" 0.3 0 32 "relu" 0.3 1 16 "relu" 0.3 2 "adam" "mean_squared_logarithmic_error" 100 if else None 2 return "term" "application_type" "home_ownership" "purpose" "emp_length" "< 1 year" "1 year" "2 years" "3 years" "4 years" "5 years" "6 years" "7 years" "8 years" "9 years" "10+ years" Now for the moment of truth: _, model, transformer = run_pipeline(
    train.drop(columns=[ , , , , ]),
    onehot_cols,
    ordinal_cols,
    batch_size= ,
    validate= ,
) X_test = transformer.transform(
    test.drop(
        columns=[ , , , , , ,
        ]
    )
)
test[ ] = model.predict(X_test) test_sorted = test.sort_values( , axis= , ascending= )
ty_grade_a = test_sorted.iloc[ :len(lc_grade_a)] print( )
print(format(mean(ty_grade_a[ ]), )) # Train the model "issue_d" "date" "grade" "sub_grade" "expected_return" 128 False # Make predictions "fraction_recovered" "issue_d" "date" "grade" "sub_grade" "expected_return" "model_predictions" # Gather top predictions "model_predictions" "index" False 0 # Display results "\nAverage `fraction_recovered` on Ty's grade A loans:" "fraction_recovered" ".5f" Epoch 1/100
6939/6939 - 13s - loss: 0.0249
Epoch 2/100
6939/6939 - 13s - loss: 0.0204
Epoch 3/100
6939/6939 - 13s - loss: 0.0202
Epoch 4/100
6939/6939 - 13s - loss: 0.0202
Epoch 5/100
6939/6939 - 13s - loss: 0.0202
Epoch 6/100
6939/6939 - 14s - loss: 0.0201
Epoch 7/100
6939/6939 - 14s - loss: 0.0201
Epoch 8/100
6939/6939 - 14s - loss: 0.0201
Epoch 9/100
6939/6939 - 13s - loss: 0.0201
Epoch 10/100
6939/6939 - 12s - loss: 0.0201
Epoch 11/100
6939/6939 - 13s - loss: 0.0201
Epoch 12/100
6939/6939 - 13s - loss: 0.0201
Epoch 13/100
6939/6939 - 13s - loss: 0.0201
Epoch 14/100
6939/6939 - 13s - loss: 0.0201
Epoch 15/100
6939/6939 - 12s - loss: 0.0201
Epoch 16/100
6939/6939 - 12s - loss: 0.0201
Epoch 17/100
6939/6939 - 13s - loss: 0.0200
Epoch 18/100
6939/6939 - 13s - loss: 0.0200
Epoch 19/100
6939/6939 - 13s - loss: 0.0200
Epoch 20/100
6939/6939 - 14s - loss: 0.0200
Epoch 21/100
6939/6939 - 13s - loss: 0.0200
Epoch 22/100
6939/6939 - 13s - loss: 0.0200
Epoch 23/100
6939/6939 - 12s - loss: 0.0200
Epoch 24/100
6939/6939 - 12s - loss: 0.0200
Epoch 25/100
6939/6939 - 12s - loss: 0.0200
Epoch 26/100
6939/6939 - 13s - loss: 0.0200
Epoch 27/100
6939/6939 - 13s - loss: 0.0200
Epoch 28/100
6939/6939 - 13s - loss: 0.0200
Epoch 29/100
6939/6939 - 13s - loss: 0.0200
Epoch 30/100
6939/6939 - 13s - loss: 0.0200
Epoch 31/100
6939/6939 - 15s - loss: 0.0200
Epoch 32/100
6939/6939 - 13s - loss: 0.0200
Epoch 33/100
6939/6939 - 12s - loss: 0.0200
Epoch 34/100
6939/6939 - 13s - loss: 0.0200
Epoch 35/100
6939/6939 - 13s - loss: 0.0200
Epoch 36/100
6939/6939 - 13s - loss: 0.0200
Epoch 37/100
6939/6939 - 13s - loss: 0.0200
Epoch 38/100
6939/6939 - 13s - loss: 0.0200
Epoch 39/100
6939/6939 - 13s - loss: 0.0200
Epoch 40/100
6939/6939 - 13s - loss: 0.0200
Epoch 41/100
6939/6939 - 13s - loss: 0.0200
Epoch 42/100
6939/6939 - 13s - loss: 0.0200
Epoch 43/100
6939/6939 - 14s - loss: 0.0200
Epoch 44/100
6939/6939 - 13s - loss: 0.0200
Epoch 45/100
6939/6939 - 13s - loss: 0.0200
Epoch 46/100
6939/6939 - 13s - loss: 0.0200
Epoch 47/100
6939/6939 - 13s - loss: 0.0200
Epoch 48/100
6939/6939 - 13s - loss: 0.0200
Epoch 49/100
6939/6939 - 13s - loss: 0.0200
Epoch 50/100
6939/6939 - 13s - loss: 0.0200
Epoch 51/100
6939/6939 - 13s - loss: 0.0200
Epoch 52/100
6939/6939 - 13s - loss: 0.0200
Epoch 53/100
6939/6939 - 13s - loss: 0.0200
Epoch 54/100
6939/6939 - 14s - loss: 0.0200
Epoch 55/100
6939/6939 - 14s - loss: 0.0200
Epoch 56/100
6939/6939 - 13s - loss: 0.0200
Epoch 57/100
6939/6939 - 13s - loss: 0.0200
Epoch 58/100
6939/6939 - 13s - loss: 0.0200
Epoch 59/100
6939/6939 - 13s - loss: 0.0200
Epoch 60/100
6939/6939 - 13s - loss: 0.0200
Epoch 61/100
6939/6939 - 13s - loss: 0.0200
Epoch 62/100
6939/6939 - 13s - loss: 0.0200
Epoch 63/100
6939/6939 - 13s - loss: 0.0200
Epoch 64/100
6939/6939 - 13s - loss: 0.0200
Epoch 65/100
6939/6939 - 12s - loss: 0.0200
Epoch 66/100
6939/6939 - 13s - loss: 0.0200
Epoch 67/100
6939/6939 - 14s - loss: 0.0200
Epoch 68/100
6939/6939 - 13s - loss: 0.0200
Epoch 69/100
6939/6939 - 13s - loss: 0.0200
Epoch 70/100
6939/6939 - 13s - loss: 0.0200
Epoch 71/100
6939/6939 - 13s - loss: 0.0200
Epoch 72/100
6939/6939 - 13s - loss: 0.0200
Epoch 73/100
6939/6939 - 13s - loss: 0.0200
Epoch 74/100
6939/6939 - 13s - loss: 0.0200
Epoch 75/100
6939/6939 - 13s - loss: 0.0200
Epoch 76/100
6939/6939 - 13s - loss: 0.0200
Epoch 77/100
6939/6939 - 13s - loss: 0.0200
Epoch 78/100
6939/6939 - 13s - loss: 0.0200
Epoch 79/100
6939/6939 - 14s - loss: 0.0200
Epoch 80/100
6939/6939 - 13s - loss: 0.0200
Epoch 81/100
6939/6939 - 13s - loss: 0.0200
Epoch 82/100
6939/6939 - 13s - loss: 0.0200
Epoch 83/100
6939/6939 - 13s - loss: 0.0200
Epoch 84/100
6939/6939 - 12s - loss: 0.0200
Epoch 85/100
6939/6939 - 13s - loss: 0.0200
Epoch 86/100
6939/6939 - 13s - loss: 0.0200
Epoch 87/100
6939/6939 - 13s - loss: 0.0200
Epoch 88/100
6939/6939 - 13s - loss: 0.0200
Epoch 89/100
6939/6939 - 13s - loss: 0.0200
Epoch 90/100
6939/6939 - 13s - loss: 0.0200
Epoch 91/100
6939/6939 - 14s - loss: 0.0200
Epoch 92/100
6939/6939 - 13s - loss: 0.0200
Epoch 93/100
6939/6939 - 13s - loss: 0.0200
Epoch 94/100
6939/6939 - 13s - loss: 0.0200
Epoch 95/100
6939/6939 - 13s - loss: 0.0200
Epoch 96/100
6939/6939 - 13s - loss: 0.0200
Epoch 97/100
6939/6939 - 13s - loss: 0.0200
Epoch 98/100
6939/6939 - 13s - loss: 0.0200
Epoch 99/100
6939/6939 - 13s - loss: 0.0200
Epoch 100/100
6939/6939 - 13s - loss: 0.0200

Average `fraction_recovered` on Ty's grade A loans:
0.96166 Victory! Phew, that was a close one! My win might be too small to be statistically significant, but hey, it’s cool seeing that I can keep up with LendingClub’s best and brightest. What I’d really like to know now is what quantitative range of estimated risk each LendingClub grade and sub-grade corresponds to, but it looks like . Does anyone know if loans grades generally correspond to certain percentage ranges like letter grades in academic classes? If not, have any ideas for better benchmarks I could use to evaluate my model’s performance? Go ahead and chime in in the comments below. that’s proprietary Previously published at https://tymick.me/blog/loan-grading-showdown

Can I Grade Loans Better Than LendingClub?

You’ve set the alarm for 2:45pm. The is scheduled for 3:00pm. web developer interview You are patiently and nervously waiting, tension digging deeper in your chest, hands trembling without any tangible reason, for your mobile phone to ring. You’re wondering what web development interview questions the interviewer is going to fire off at you. Your mind is playing on your nerves. Tension rising notch by notch. “Am I really ready for that coding interview?” — you start beating yourself up. You check your phone — it’s 3:05 pm. No missed calls. Nothing. You anxiously recheck your phone — 3:15 pm… still nothing. You are already 30 minutes under pressure, sweating and silently moaning — your heart races. The latent impostor syndrome arises from the depths. You start freaking out… wondering whether or not you’ve given the wrong phone number… or if they might have forgotten about you. Your mind is leading a furious battle to overcome your anxious trains of thought. You, filled with a desperate hope, grab your phone with your sweaty pawl and look at it for one last time… and then… it rings. You pick up and say, “Hello,” trying to hide the trembling notes in your voice, the anxious quiver of your lips and fingers, while battling the excruciating jittery inside your mind. You introduce each other and then… kinds of interview questions for web developers thrown at you, catching you off guard, that you can barely give an adequate answer to. You realize that you are completely f*cked up. The overwhelming anxiety is growing deeper and deeper in you. You feel like you have a 200-kg bench press on your chest that you can’t lift. Vertigo comes along, and you suddenly forget. You forget your location, the person you are talking to… everything. Hands so sweaty that you just can’t hold your phone without it slipping through your fingers. You know that the chances of making a good impression are so damn low that you’d have more luck if you were to bet on racing cockroaches. To avoid that, you need strong preparation for the next coding interview. You need to have a grasp of the interview questions for web developers you are being asked. That will boost your confidence and diminish the anxiety before the phone or onsite interview. In this article, I’ll talk about the principles behind the developer interview process — the most common web developer questions you can expect from interviewers and how to answer them in a fascinating way that will put a WOW expression on their faces (even if they want to rip your head off, rearrange your face, or just clean their shoes ;-) ). A Software Developer Interview Is a Negotiation To start off, you need to realize that the web dev interviewing process is more like a negotiation. You’ve been probably taught as a kid that you need to be flawless during interviews and answer every question accurately to make a good impression and get hired. This couldn’t be further from the truth (coming from someone who got hired by sending out a cold message directly to their employer — no official nor traditional interview process). Yes, of course, you need to make a good impression. But if you think that making a good impression comes down to awkwardly staring at your interviewer, frozen, while answering every developer interview question like a robot… you’re highly mistaken my friend. You need to be able to communicate with your future employer freely while at the same time exuding confidence, knowledge, curiosity, and most importantly, enthusiasm. Here are the main things employers look for when hiring people: . Personality . Basic qualifications . Culture fit . Enthusiasm You need to have a fitting personality, meaning, you need to be able to easily communicate with your team without any hassle whatsoever. You need to ask clear and concise questions while at the same time, giving thorough and detailed answers. Of course, you also need to possess basic qualifications for the job you are applying for. Yet, many people seem to put tons of attention to that one (which is perfectly fine), but it’s just ¼ of the whole equation. Culture fit — this ties back into your personality. You have to be able to sync with your team and develop a culture that everyone enjoys working in. And finally, have a burning passion and enthusiasm for your job. You’ll be surprised how helpful enthusiasm can be. For example, you may not have as good a resume as the guy in the next room that’s also being interviewed… but if you display a burning enthusiasm and willingness to go out of your way, you can beat other candidates and win the job. Of course, that may not always be the case. Still, it’s much more likely for an employer to hire you as a hyper enthusiastic person than as an average employee. Alright, let’s take a look at some of the most common web developer interview questions (and answers) you may encounter. We’ll first start with professional software engineer behavioral questions and then switch over to more technical questions. Whether you are a front-end, back-end, or full-stack software developer, these common computer science interview questions will help you in your preparation for the next coding interview. NOTE: Some of the behavioral questions can also be used in web design interviews. So if you are a web designer, this article will highly prepare you for the next web design interview. 1. What got you into coding? Or Why are you interested in a career as a software developer? Most interviewers start off with introductory questions. Just follow the common sense when answering these software engineer interview questions. Try to be as transparent as possible. Tell them what really sparked your interest in coding and why you applied for this job. 2. What’s your experience with coding so far? If you are applying for an entry-level web developer job, interviewers won’t expect years of experience (they may even skip that question) as you’ve probably just graduated or finished a coding boot camp. Yet, if you are applying for a senior software engineer position, you need to have years of experience to back up your application for that web development job. 3. Do you have any experience with Agile methodologies? You need to get familiar with Agile frameworks such as Kanban and Scrum because nowadays companies are adopting Agile practices and moving away from Waterfall methodologies. Interviewers may also ask you questions about the . SDLC (Software Development Life Cycle) process 4. What specific languages are you working with? As simple as that. You might want to focus on the specific languages that your web development job will require you to use most frequently. Lately, having experience with multiple languages like C++, Java, and Python will definitely widen your interviewer’s eyes in astonishment. 5. What’s your strongest language? Credits to Andrew Mallonee, CEO at Mallonee Media . Be transparent and give a thorough explanation.. Sometimes, the interviewer might follow up with, “Do you get excited by using these languages?” but rarely. Obviously, reply with Yes and explain why you feel excited. 6. Are you interested in further developing your skills? It’s more of a soft skill interview question. Software engineering is a job in which you need to always thrive and sharpen your skills. Employers need to know that their developers are on the cutting edge using the latest technologies and constantly honing their skills. So, the answer to that software developer interview question would obviously be “Yes” — but expand further by telling them what interests you the most when it comes to learning new coding skills. 7. What are your favorite types of projects to work on? Talk about projects similar to the projects you are going to be working on in the position you are applying for. If not, be genuine (always) and tell them what really sparks your passion for software development. 8. Tell me about the software engineering project you’re most proud of. What did you do that worked out particularly well? Here, interviewers particularly want to hear about severe problems, not many people on your team were able to solve, yet you were. Something important to remember is not to try to impress the interviewer — the scales will fall from his eyes immediately. Instead of making a good impression, you’ll make a desperate one. Be casual when talking about the problem that no one was able to solve except you. You, thus, exude confidence and knowledge. Being humble in the answer of this web dev interview question is key. 9. Tell me about the software development project you’re least proud of. What would you do differently? Another soft skill interview question. Life is about learning from your mistakes. Be as transparent as possible and openly admit the mistakes you’ve made in the past. Talk about the lessons you’ve learned. Basically, explain how you coped with your worst failures and came out stronger. 10. What do you know about our company? Research a lot prior to the interview. Go through all of their social media profiles to find little nuggets of information that would impress your interviewer. Show passion and enthusiasm for the company. Enthusiasm plays a huge role in the interview process. 11. Any particular projects at our company that you are excited about? Same as previous — conduct thorough research and analysis before the interview. Show passion and enthusiasm. Tell the interviewer why you would love to work on those particular projects. They can thus see the reason behind that enthusiasm and wind out the thoughts of all that being a mere fluff. These web development interview questions can happen over the phone or onsite. The following technical interview questions typically happen onsite, but sometimes they can take place remotely. If it’s remotely, the interviewer will ask you to share your screen to watch over your shoulder while you are coding and at the same time answering software development interview questions. Keep in mind that the technical questions you are being asked highly depend on the position you are applying for. We’ll try to cover some of the most common software developer interview questions and give you reasonable answers that you can adjust to your situation easily. Technical Interview Questions 12. How do you organize your class modules and assets? Credits to Michael Miller, CEO at VPN Online . There are lots of ways you can write your code, and all of them are correct. The company you want to join probably has a set standard for writing code and will perhaps compare your answer to that standard. Usually, most companies look for developers who take the simplest approach to code and try to weep out those who praise the sophisticated way of coding. That’s because companies want to easily maintain and document their code. 13. Tell me about AJAX (JavaScript) in detail. Can you give me an example of when you last used it? Java developer interview questions are quite common. When interviewers ask you such software engineer “explanatory” questions, the point really is not to explain the definition but to tell how you are going to use it in your code. This signals the interviewer that you can actually “think.” And it also displays the way you approach coding. AJAX is the abbreviation of Asynchronous JavaScript and XML. AJAX is a new technique for creating better, faster, and more interactive web applications with the help of XML, HTML, CSS, and JavaScript. 14. How would you explain APIs to non-technical stakeholders? It’s the messenger between software products. It allows software systems to communicate with each other and synchronize. For example, you can use, say, Facebook’s API to display your Facebook posts on your website. And allow people to share or comment on your posts directly from your website without switching over to Facebook. 15. Explain a non-functional requirement and a functional one? A non-functional requirement describes a system’s type (accessibility, maintainability, security). Whereas a functional requirement describes the specific functionality of that system. 16. What is the difference between black box and white box testing? Black box testing is only used for establishing a correct output given an input. In contrast, white box testing also covers the implementation of that particular function — it tests whether its implementation is correct or not. 17. Can you describe the model-view-controller (MVC) architecture? It separates data from the user interface. The MVC architecture is mostly used for GUI applications. The model layer contains the data, the view layer sends the data to the user, and the controller is the one that makes changes to the model based on user input. 18. What is a recursive function? A function that calls itself directly or indirectly. The recursion continues until it reaches a set of parameters that return a value instead of calling the function recursively. A recursive function can solve specific problems quite quickly. 19. Please explain big-O notation in the simplest terms. The big-O notation tells how fast an algorithm is. This is very important whether you are evaluating other people’s algorithms or your own. Big-O notation, also known as Landau’s symbol, tells how the runtime or space requirement of a function grows as the input grows. Which means that the algorithm speed isn’t measured in seconds but in the growth of the number of operations. 20. How does the A* algorithm work? It’s a computer algorithm widely used in pathfinding and graph traversal. It works with a heuristic function that estimates the cost of going from node A to B. The nodes in each step are huddled together in a priority queue. It uses the formula f(n) = g(n) + h(n) to add every, adjacent to the start node, node into the queue along with their cost estimates. . At each step, the node with the lowest estimated cost f(n) is further expanded. And a path is finished when the final node is the one that expands. g(n) is the actual cost from the start node to node n, whereas h(n) is the heuristic function 21. What’s your experience with object-oriented programming (OOP)? You can refer to about OOP on freeCodeCamp. It breaks down the concept in detail. this thoroughly-explained guide 22. What about your SQL skills? Even though databases may not be at the core of your work, you need to understand how data is structured. Any practical SQL experience that you can tell about will definitely add extra points to your web application interview. 23. Write a function to compute the Nth Fibonacci number. The following code block is borrowed from . It gives a good example. Geeksforgeeks In C++: //Fibonacci Series using Recursion #include<bits/stdc++.h> using namespace std; int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } int main () { int n = 9; cout << fib(n); getchar(); return 0; } // This code is contributed (Credits to Akanksha Rai) 24. Reverse a string reverse string(str: String) An interviewer asking you to reverse a string doesn’t mean they would ask you to actually implement reversed() in your production code. They merely want to see the approach you use to solving problems. Most big tech problems will undoubtedly ask you algorithm questions, especially the FAANG companies. The following code block is borrowed from . It gives the perfect example. Geeksforgeeks // A Simple C++ program to reverse a string #include <bits/stdc++.h> using namespace std; // Function to reverse a string void reverseStr(string& str) { int n = str.length(); // Swap character starting from two // corners for (int i = 0; i < n / 2; i++) swap(str[i], str[n — i — 1]); } // Driver program int main() { string str = “geeksforgeeks”; reverseStr(str); cout << str; return 0; } At the end of the day, companies are looking for smart people, more than anything. Algorithm questions is a great proxy that can weed out a lot of “dumb” candidates. And coding assignments: Credits to Leo Polovets for this one. This is actually a great interview question for software engineers that Microsoft used to ask interviewees. 25. You have a list of N+1 integers between 1 and N. You know there’s at least one duplicate, but there might be more. For example, if N=3, your list might be 3, 1, 1, 3 or it might be 1, 3, 2, 2. Print out a number that appears in the list more than once. (That is, in the first example, you can print ‘1’ or ‘3’ — you don’t have to print both.) The most obvious approach is to compare every number in the list to every other number until you find a duplicate with O(n²) time and O(1) space complexities. 25a. Okay, well let’s say the list is pretty big, so you need something that’s faster than O(n²). I could just use a boolean array and use the integer values as indices with O(n) time complexity to iterate through the list and O(n) space complexity for the array/hash. 25b. Okay, let’s say the list of numbers is quite large, so you’d like to avoid creating a copy of it. Maybe you have 8GB of RAM, and the list takes up 6GB. I could sort the numbers and compare adjacent pairs. That would take O(n*log n) time and O(1) space if I use an in-place sort like mergesort. 25c. What if you want something faster than O(n²) and you can’t afford to use a lot of extra space, but you also can’t manipulate the original list. For example, maybe the list is on a read-only CD. (Almost every candidate needs a hint or two at this point..) I think I can binary search for a duplicated number. For example, I go through the list and count the number of integers between 1 and N/2. If the count is greater than the number of possible integers in that range, then I know there’s a duplicate in that range. Otherwise, a duplicate must exist in the range of N/2+1 to N. Once I know which half of the range the duplicate is in, I can recurse and binary search in that half, then keep repeating the process until I’ve found a duplicated number. The time complexity is O(n*log n) and the space complexity is O(1). So that pretty much makes it for this post — the most common software developer interview questions and answers. Whether you are a junior web developer or a senior software engineer, hopefully, you were able to find these interview questions and answers useful. You can go through the post again to boost your confidence even more. And remember — how you perform at your web development interview means nothing to your software engineering skills. If you screw it up the first few times — no big deal. Just move forward to the next software development interview. Eventually, you’ll land a position at your dream company, and all the developer interviews you went through will all be worth it. Originally Published on Codegiant. If you are searching for a DevOps tool (with an intuitive issue tracker, git repositories, built-in CI/CD, and publishable documentation) feel free to try Codegiant .

Web Developer Job Interview Preparation: 25 Questions, Prompts, and Coding Assignments 

Every programmer needs to know their algorithms and data structures. When studying them, you need to be sure to understand exactly what it does, what it's time and space complexity are they are that way, and be able to not only code it, but perform it by hand. This is what is all about. and why Essential Algorithms Welcome to the first installation of Essential Algorithms, where today, we'll be going over the Merge Sort. Merge Sort is one of the most reliably consistent and well-performing sorting algorithms for sorting large datasets, performing almost 40% fewer comparisons at it's than Quick Sort does on . So let's dig in and see what this algorithm is. worst average The Merge Sort Algorithm To start, let's take a simple array of numbers, that are out of order, which we want to sort: arr = [ , , , , , , , ] var 27 369 63 126 252 990 54 18 The Merge Sort algorithm can take these numbers and put them in order, small to big, or big to small, in consistent and efficient manner. Merge Sort takes a divide and conquer approach recursively; that is, it breaks the array into smaller and smaller ones by calling itself, until each one only has one element inside of it. Then, it compares two numbers at a time, puts them into order and returns them to itself, as it backs out of it's recursively called functions. So, our above array turns into the following sub-arrays: [[ , , , ],
[ , , , ]] 27 369 63 126 252 990 54 18 And again into: [[[ , ], [ , ]], [[ , ], [ , ]]] 27 369 63 126 252 990 54 18 And one final time: [[[[ ], [ ]], [[ ], [ ]]], [[[ ], [ ]], [[ ], [ ]]]] 27 369 63 126 252 990 54 18 With the elements sorted into sub-arrays, each pair needs to be evaluated, so that when merged together, the left value is smaller than the right one.  In this example, only the last pair of single-element arrays has a larger value on the left, so would be merged in as : [54], [18] [18,54] [[[ , ], [ , ]], [[ , ], [ , ]]] 27 369 63 126 252 990 18 54 With the smallest element held at index[0] of the most nested sub-arrays, the sub-arrays can now be merged, in order, in an efficient manner. To do so, compare the very first element of both arrays. Then, take the smaller element from the sub-arrays and put them into the array you are going to return, while taking them out of the arrays you are comparing. Thus, comparing the arrays and , we need only to look at the first item of the arrays. Since 27 < 63, 27 would be taken out of the first array, and added to the one we will return. This leaves us comparing . We need only to look at the first elements again, and see 63 is next, so our returning array is and we still have to compare. We then add 126, are left only with 369, so we add that. In all, the steps look like this: [27, 369] [63, 126] [369], [63,126] [27,63] [369], [126] [ , ] [ , ]
[]

[ ] [ , ]
[ ]

[ ] [ ]
[ , ]

[ ]
[ , , ]

[ , , , ] 27 369 63 126 369 63 126 27 369 126 27 63 369 27 63 126 27 63 126 369 After the second iteration, the arrays look like this: [[ , , , ], [ , , , ]] 27 63 126 369 18 54 252 990 The arrays are then merged again in the exact same way, comparing 27 to 18, then 27 to 54, then 63 and 54, so on, until the entire array is sorted and returned. When I mentioned earlier that each pair would need to be evaluated, and only would need to swap in the first step, both of those were held in their own arrays. This means that one can create a single function to compare the numbers in all instances, by comparing the element at index 0 of both arrays, and removing the lesser item when adding it to the returning array. This will be run until one of the arrays is empty, and the remaining elements of the other array will be appended to the end of the returning elements. [54],[18] The arrays will be merged together like that, recursively, until there is only one array left, and then it will be completely sorted. In a way, you can break it down into two fundamental steps: Merging 2 arrays: Take two arrays. Compare the first element of the two of them. The smaller of the elements should be removed from that array, and added to the end of the array we are returning. When all of the elements are removed from one array, just add the rest of the other one to the sorted array and return it. Divide and conquer: Take an array. Find the middle of it. Pass everything to the left of it into the divide and conquer function, and pass everything to the right of it to the divide and conquer function (so the function has been fed both halves of it), until there is only one. Then, start merging the 2 arrays. Time Complexity and Efficiency Merge Sort, much like Heap Sort, has a time complexity of in its best and worst case scenarios. The reason this doesn't change is because it performs all of the operations necessary to completely sort the list whenever it is called; it does not matter how sorted the list is when Merge Sort gets it. It can be already sorted, or it can be as unsorted as possible, but Merge Sort will still have to perform divisions of the list and comparisons. O(n*log(n)) O(log(n)) O(n) This contrasts with other algorithms like Bubble Sort, which iterate over the list recursively until it is sorted. If given an ideal or already sorted list, Merge Sort's performance at is significantly worse than Bubble Sort's . However, the more unsorted a list is, the more passes Bubble Sort must make over the entire array, so Bubble Sort's average and worst-case scenario is , making it terribly inefficient on average and worst cases. O(n*log(n)) O(n) O(n^2) But is Merge Sort's complexity quasilinear, with a complexity of This is because the longer the list is, the more operations you have to do. That is to say, the algorithm has from it requiring more time proportionate to the length of the array. The comes from the number of divisions of the array that takes place, just like the binary tree. In our example, we had 8 elements, we had to break them from arrays with lengths of 8 => 4 => 2 => 1 to begin to compare them. That's 3 divisions, and 2^3 is 8. By comparison, if we used 16 elements, we'd need to divide 16 => 8 => 4 => 2 => 1, which is 4 divisions, and 2^4 is 16! So here we can see the number of operations to split the arrays grows in a logarithmic fashion with respect to the length of the input. Because of that, it both grows at and , giving us the time complexity. why O(n*log(n))? O(n) O(log(n)) O(log(n)) O(n) O(n*log(n)) Merge Sort, when not sorted in place and implemented efficiently with space in mind, has a space complexity of , meaning the memory required to execute grows proportionally to the size of the input. This means, for every byte of input, one byte must be allocated in memory to hold the output. O(n) Code Examples Enough overview, let's look at a few examples. Both examples will use the same array as above. Reading the above overview, we can break down what we need to do into two basic steps: We need to recursively break the array into smaller sub arrays We need to merge the sub arrays together, sorting it as we fill it. With these 2 main steps, we can now write 2 different functions to implement the Merge Sort algorithm. Bear in mind, these examples are not going to be optimized for anything except code length and readability. I found many examples of the Merge Sort when I was first learning that contained several other parameters and variables, that while they worked and used space efficiently, they were harder to read when first starting out. Example 1: Python The first function we will write will be the one to break the supplied array into sub-arrays, and call our other function. Since this will be the parent function of the algorithm, I'll name this , which will be passed an unsorted list as it's only argument. It will handle breaking the arrays recursively, and passing them to the function that handles the actual merging and sorting, . merge_sort() merge() Since we want to break the unsorted list into 2 separate lists, we need to calculate the midpoint of the list. Dividing the list length in half works, but if you're using Python 3, the does floating-point operations, so use the to specify integer division. We can declare .  With our calculated mid point, we can then pass the halves of the array back into . / // mid = len(sorted)//2 merge_sort() mid = len(unsorted)// left = merge_sort(unsorted[:mid])
    right = merge_sort(unsorted[mid:]) : def merge_sort (unsorted) 2 Now, this works fine if the arrays are longer than 1 element, but once we get down to one, we're gonna start getting errors and infinite loops. So, we need to tell the program to only do this while there's more than one element in each unsorted list passed to the function. When an array or list of 2 or more elements is passed to the function, we want it to return to us the sorted list, which will be our next function. If only one element is passed, we want it to simply return that one element. So, we can wrap this all in an if/else statement, and add return statements, and this function will be complete: len(unsorted) > :
        mid = len(unsorted)// left = merge_sort(unsorted[:mid])
        right = merge_sort(unsorted[mid:])  
        result = merge(left, right) result : unsorted : def merge_sort (unsorted) if 1 2 return else return Calling the function before calling our function ensures that all of the divisions will be done before we start merging. With this in place, we can start to build the function. merge_sort() merge() merge() The function will take 2 arguments, the left and the right arrays. We'll make an empty to hold the returning results, that we'll populate with from the left and right lists. We will use a few while loops to perform this task. merge() sorted_list pop(0) While there are both the left and right unsorted lists, we need to compare the first element. The smaller of the two will be popped from the front of the list into the we will return. sorted_list sorted_list = [] len(left) > len(right) > : left[ ] <= right[ ]:
            sorted_list.append(left.pop( )) :
            sorted_list.append(right.pop( )) : def merge (left, right) while 0 and 0 if 0 0 0 else 0 So what happens when we are left with a list that is empty and one that isn't? Well, nothing. Since we don't know which list will run out first, or how long that list will be, after this loop is completed we need to add two more to check and see if the left and right are still populated, and add them to the before returning. This leaves us with the following function: sorted_list merge() sorted_list = [] len(left) > len(right) > : left[ ] <= right[ ]:
            sorted_list.append(left.pop( )) :
            sorted_list.append(right.pop( )) len(left) > :
        sorted_list.append(left.pop( )) len(right) > :
        sorted_list.append(right.pop( )) sorted_list : def merge (left, right) while 0 and 0 if 0 0 0 else 0 while 0 0 while 0 0 return So now, our entire file looks like this: mergesort.py len(unsorted) > :
        mid = len(unsorted)// left = merge_sort(unsorted[:mid])
        right = merge_sort(unsorted[mid:])  
        result = merge(left, right) result : unsorted sorted_list = [] len(left) > len(right) > : left[ ] <= right[ ]:
            sorted_list.append(left.pop( )) :
            sorted_list.append(right.pop( )) len(left) > :
        sorted_list.append(left.pop( )) len(right) > :
        sorted_list.append(right.pop( )) sorted_list : def merge_sort (unsorted) if 1 2 return else return : def merge (left, right) while 0 and 0 if 0 0 0 else 0 while 0 0 while 0 0 return And we can now test it out and see that it works: And there you go! An easy to read, short implementation in Python. Example 2: Javascript Again, in this example we write our first function in order to break the unsorted array into smaller sub-arrays, calling itself recursively until all of the divisions have been done, before calling the function. merge_sort() merge() Since we need to break this into 2 separate arrays, we again need to calculate the midpoint. Javascript will perform a floating-point calculation for odd numbers, so we'll use to round down, like Python did with the divisor. So, we can set a variable for our midpoint, make our left and right arrays, and pass them back to before calling . Math.floor() // merge_sort() merge() merge_sort = ( { mid = .floor(unsorted.length/ ) left = unsorted.slice( ,mid) right = unsorted.slice(mid,)
}) const ( ) function unsorted var Math 2 var 0 var This works just fine with arrays that are more than one element, but will cause an infinite loop and errors about undefined variables when you have only one item. We will have to wrap this in an if statement, performing this block of code only if has more than one element, and to just return the element if there's only one. We also need to call our function for the left and right arrays, and return that if there are more than one element in the array. unsorted merge() unsorted merge_sort = ( { (unsorted.length > ){ mid = .floor(unsorted.length/ ) left = merge_sort(unsorted.slice( ,mid)) right = merge_sort(unsorted.slice(mid,)) merge(left, right)
    } { unsorted
    }
}) const ( ) function unsorted if 1 var Math 2 var 0 var return else return Now we can start on our function. We'll initialize an array to hold our sorted results in, and while the left and right arrays both contain elements, we'll compare the first element of the two. Whichever element is smaller, will be shifted from that array, and pushed into the results. To keep the code short and compact, and with such a simple statement, I opted to use a one-line ternary operation. If you're not familiar with ternary operations, they're one-line if-statements structured like so: merge() if/else (condition to evaluate) ? ( ) : ( ) do this if true do this if false The expression that would be held in the if-statement is written out first, followed by the . The next expression is what to do if the evaluated statement is true, followed by a , and then what to do if the operation is false. I prefer these in JavaScript and don't like them in Python because I find the readability easier. In Python, the syntax is , leaving the statement to be evaluated in the middle, and the desired operations on each side. Personally, I don't find it as easy to read. It's one of those Python quirks I don't like, much like vs syntax. ? : (do this if true) if (statement to evaluate) else (do this if false) split() join() So, our first loop will contain the ternary function to move the elements between the arrays appropriately, and we'll need to add 2 more loops to check both the left and right arrays for remaining elements after the first loop, and add them to the sorted array. while while merge = ( { sorted = [] (left.length > && right.length > ){
        left[ ] < right [ ] ? sorted.push(left.shift()) : sorted.push(right.shift())
    } (left.length> ){
        sorted.push(left.shift())
    } (right.length> ){
        sorted.push(right.shift())
    } sorted
}) const ( ) function left, right var while 0 0 0 0 while 0 while 0 return Our complete file now looks like this: mergesort.js merge_sort = ( { (unsorted.length > ){ mid = .floor(unsorted.length/ ) left = merge_sort(unsorted.slice( ,mid)) right = merge_sort(unsorted.slice(mid,)) merge(left, right)
    } { unsorted
    }
}) merge = ( { sorted = [] (left.length > && right.length > ){
        left[ ] < right [ ] ? sorted.push(left.shift()) : sorted.push(right.shift())
    } (left.length> ){
        sorted.push(left.shift())
    } (right.length> ){
        sorted.push(right.shift())
    } sorted
}) const ( ) function unsorted if 1 var Math 2 var 0 var return else return const ( ) function left, right var while 0 0 0 0 while 0 while 0 return We can now test it in the browser console to make sure it works: Time Complexity Revisited Now that we have two different examples of the algorithm imposed in 2 different languages, we can come back and analyze it again to understand how and why Merge Sort's complexity is . Both of the examples above create two functions to perform the 2 major components of the algorithm. Both implementations use the parent function to recursively divide the lists it gets passed in half. Because of this, the actual function will be executed several times, and that number of times grows with the logarithm of the size of the list passed to it. So, we can say that the function itself has a complexity of . O(n*log(n)) merge_sort() merge_sort() merge_sort() O(log(n)) On the other hand, the function that gets called by has the task of taking the two inputs and combining them into a single output. The amount of time this will take is determined by the size of the inputs passed to it. So, we can say the function has a complexity of . The function, at gets called for every time gets called, and the number of times gets called is times, giving us our final complexity . merge() merge_sort() entirely merge() O(n) merge() O(n) once merge_sort() merge_sort() log(n) O(n*log(n)) The Merge Sort algorithm is consistently efficient, which is why it is used as the default sorting algorithm in languages like Java and Perl, and part of the hybrid Timsort used by Python. The Time Complexity stays constant, a good thing when considering performance and optimization, and due to the nature of it dividing the input in half recursively, the algorithm can be highly optimized if one has access to multiple CPUs at once. So there you have it, the Merge Sort. Hopefully after this, you have a solid grasp on how to do it, and even actually understand what actually means on an intuitive level. If you enjoyed this or learned something, share it! O(n*log(n))

Essential Algorithms: The Merge Sort

Top 20 Sorting and Searching Algorithms Questions for Interviews A Collection of common coding problems from Interviews based on basic algorithms like searching, sorting, and string algorithms Hello All, If you are preparing for or looking for a new job then you know that it’s not an easy process. You got to be lucky to get the call and make to the first round of interview, not just when you are a beginner but at any stage of your career. Programming job interviews But, Yes, it is the most difficult at the beginner level when you are searching for your first job. That’s why you can’t just take your chance lightly. You got to be prepared to grab that chance and for that, you must know that is expected from you on the interview. What is asked, what topics should you prepare, etc? I have blogged a lot about what you can find helpful articles in this blog but to recap let me tell you that apart from , , and Programming language specific questions like , , or , most of the programming job interviews also ask algorithm based questions. data structure questions System Design Questions Java C++ Scala These are based upon common searching and sorting algorithms like , , , etc. String algorithms binary search graph algorithms It’s important that you practice these Algorithms based questions because even though they seem obvious and easy, sometimes they become tricky to solve in the actual interview, especially if you have never coded them by yourself. Practising these problems before interview not only makes you familiar with them but also gives you more confidence in explaining the solution to the interviewer, which plays a very important role in your selection. It also makes you ready for any twisted questions and alternative problems like Interviewers often like to ask you to solve a particular coding problem using or . Recursion Iteration Sometime, if you use a data structure like the one I have used in , they will ask you to solve that problem without using the Set data structure. That’s just some common example and that’s why practice matters a lot. finding duplicate characters on String Btw, if you are a complete beginner in the world of Data Structure and Algorithms, then I suggest you to first go through a comprehensive Algorithm course like on Udemy which will not only teach you basic data structure and algorithms but also how to use them on the real world and how to solve coding problems using them. Data Structures and Algorithms: Deep Dive Using Java Data Structures and Algorithms: Deep Dive Using Java On the other hand, if you like to read books or prefer books over online courses then you must read a comprehensive book like by Thomas H. Cormen to get an understanding of common Computer Science Algorithms like Searching, Sorting, Cryptography, and some common ones like Fourier Transform. Introduction to Algorithms Graph Algorithms Introduction to Algorithms, 3rd Edition (The MIT Press) 20+ Searching and Sorting Algorithms Questions from Coding Interviews Anyway, here is some of the frequently asked Searching and Sorting Algorithms questions from Interviews. I have linked the solution but you should try to solve the problem before looking at the solution. The purpose of this article is that you should know how to solve these problems on your own, but, yes, if you got stuck and want to compare your solution, you can see the solution. It’s easy, binary search is a divide and conquers algorithm, where the problem is divided into sub-problem and those are solved. It’s a search algorithm which means it is used to find things like a number in an integer array or an item in a catalog. 1. Can you implement a Binary Search Algorithm? ( solution ) The easiest way to implement a is by using Recursion, which is what the solution link contains but you should try it yourself before seeing the solution. binary search algorithm One of the worth noting this is that the input must be sorted, I mean you can only implement binary search in a . sorted array It is even easier than binary search, all you need to do is go through all elements in the array using a or recursive method and compare each element with the one you want to search. when an element matches you either return index or true/false depending upon your requirement. 2. Write a program to implement Linear search Algorithm? ( solution ) for loop For example, if you are writing a you can return true or false to indicate whether an element is present in the array or not. Since you need to scan the whole array to find the element, the time complexity of this algorithm is O(n). contains() method Btw, if you have trouble calculating and understanding time and space complexity of algorithms then you should see a course like to understand them better before going for an interview. Data Structures & Algorithms — Interview You might know that you can replace a recursive algorithm to an iterative one by using a loop and sometimes using a data structure. For binary search also you can do this, just divide the array and compare the middle element until you find the target element or there is no more element into an array. 3. Can you implement a Binary search Algorithm without recursion? ( solution ) Stack If the target element is greater than middle than you got to move towards the right, or otherwise towards left. Btw, if you have trouble understanding recursive algorithm or converting a recursive one to iterative one then I suggest you go through a good online course like and in Pluralsight to learn fundamentals better. Algorithms and Data Structures — Part 1 Part 2 These courses will also teach you about how to calculate time and space complexity which is very important from both Coding Interview perspective as well as improving the performance of an Algorithm. Isn’t this was the first sorting algorithm you learn? Well, I did and that’s why I remember that is about comparing each number with every other number in an array so that after each pass the bubble up to the top. 5. Implement the Bubble sort Algorithm? ( solution ) bubble sort largest or smallest element I mean the number has found it’s placed in the sorting order. This is one of the fundamental sorting algorithms and most of us started learning about sorting using this algorithm. The time complexity of this is O(n ^2) which makes it unusable for a large set of numbers but it does well for a small set of numbers. In level order search you first visit sibling nodes than going down into the next level. You can use a to implement level order search in a binary tree.If you want to learn more, you can check any of these on 4. Write Code to implement Level Order Search in a Binary Tree? (solution) Queue free data structure and algorithms courses freeCodeCamp And, if you are really serious about doing well, you can also check this list of courses to crack your programming job interviews 10 Data Structure, Algorithms, and SQL Courses to Crack Any Programming Job Interview This one was a tricky concept which I didn’t know until long ago. I haven’t come across any practical use case of this one yet but just knowing the concept is Ok from the interview perspective. 6. Difference between a stable and unstable sorting algorithm? ( answer ) In a stable sorting algorithm, the order of the same element remains the same even after sorting but during the unstable sorting algorithm, this changes. A good example is a and where former is unstable while later is a stable algorithm. quicksort mergesort It’s another popular searching algorithm which is mainly used in tree and graphs. This algorithm first visits nodes in depth before searching in the same level, that’s why the name Depth-first search algorithm. 7. What is Depth First Search Algorithm for a binary tree? (solution) It’s tricky to implement but you can use a Stack to implement DFS or Depth-first search algorithm. If you need more information on this topic, I suggest you check the book by Aditya Bhargava, his explanation is probably the best explanation of this topic Grokking Algorithms Obviously without recursion:-). If you remember, I have told you before that you can use a Stack to convert a into an iterative one and that’s what you can do as well to implement Quicksort algorithm without recursion. You can further see the if you need more help with respect to implementation. 8. How is an iterative quicksort algorithm implemented? ( solution ) recursive algorithm solution Just like we have done with other O(n) sorting algorithms like Radix sort and Bucket sort. 9. How do you implement a counting sort algorithm? ( solution ) If you don’t know is another integer sorting algorithm for sorting a collection of objects according to keys that are small integers. Counting sort It has O(n) time complexity which makes it faster than likes of and for a particular set of input. See the solution for more details. Quicksort Mergesort Another tricky question which is easy if you know the trick :-) Well you can swap two numbers without using a temporary or third variable if you can store the sum of numbers in one number and then minus the sum with other number something like 10. How do you swap two numbers without using the third variable? ( solution ) a = 3;b = 5; a = a + b; //8b = a — b; // 3a = a — b; //5 now you have a = 5 and b = 3, so numbers are swapped without using a third or temp variable. This is another integer sorting algorithm with O(n) time complexity. As per Wikipedia, Radix sort is a that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. 11. How is a radix sort algorithm implemented? ( solution ) non-comparative sorting algorithm You can further see and by Robert Sedgewick on to learn more about these O(n) or liner sorting algorithms. The course is free for learning and exploring but you need to pay if you also want a certification. Algorithms, Part I Part II Coursera Have you ever arranged the deck of cards, or maybe shirts in your cupboard? What is common between those two things? Well, you put the next card or shirt into their proper position, or, should I say you insert the next element in its proper position. That’s the for you. 12. How do you implement an insertion sort algorithm? ( solution ) insertion sort This is a tricky Algorithm question but if you have to listen to your teacher in your 2D Maths class then you can solve this problem. There is another trick, check for all the conditions when rectangle will not overlap and if any condition is false it means both rectangles are overlapping with each other. For example, if the upper side of one rectangle is below the lower side of other rectangles then they won’t overlap as they are vertically aligned. 13. Write Algorithm to check if two rectangles overlap with each other? ( solution ) Similar to Quicksort, merge sort is also a divide and conquer algorithm which means you keep divides the problem until you can sort the smallest of them. 14. How is a merge sort algorithm implemented? ( solution ) For example to you divide the array into smaller parts until you know how to sort them like an array with one or zero elements is already sorted. Once you sort small arrays you merge them to get the final result. sort an array of numbers The only is that mergesort is while Quicksort is . This means equal elements retain their spot before and after sorting. difference between Quicksort and Mergesort stable not-stable Another worth noting difference is that even though both have O(NLogN) average time, it’s better to use quicksort than mergesort because Quicksort takes less time for the same number of input, the constant factor is less in Quicksort than merge sort. The Bucket sort is another awesome algorithm which can sort an array without even comparing elements. 15. How do you implement a bucket sort algorithm? ( solution ) It’s known as and can give O(n) performance for the selected input. non-comparison sorting algorithm If you don’t know about the non-comparison based sorting Algorithm, please see book. Introduction to Algorithms An anagram is something where length and character matches but not the order like Army and Mary, both have the same number of characters. 16. Write Algorithms to Check if Two String are Anagram ( Solution ) One trick is to solve this problem is to and check if they are the same or not. sort the character array This one is a very easy sorting algorithm, but only if you have practiced, if not then you may lose your way. Remember, is a which means you keep dividing array, also known as . Then you solve the problem at the smallest level, also known as a base case like when your array contains just one or zero elements. 17. Implement the QuickSort Algorithm in your Favorite Programing language? ( solution ) Quicksort divide and conquer algorithm partitioning As the name suggests, in comparison based sorting algorithms you must compare elements to sort like quicksort, but in non-comparison based sorting algorithm like , you can sort elements without comparing it. Surprised? 19, Difference between Comparison and Non-Comparison Sorting Algorithms? ( answer ) Counting sort Well yes, then I suggest you check out this course to learn more about O(n) sorting algorithms like Radix Sort, Counting Sort, and Bucket Sort. You can further see if you want to learn more about these O(n) sorting algorithms. Data Structures and Algorithms: Deep Dive Data Structures and Algorithms: Deep Dive Using Java There is a simple trick to solve this problem, You can do that by using indexOf or substring method. If the concatenated String contains rotation then given String is a rotation of former. 19. How to check if two String is rotations of each other? ( solution ) just concatenate the String with itself and check if the rotation exists there. This is one of the tough algorithms to implement especially if you don’t remember it :-) Sometime interviewer gives you the explanation but other times you need to remember it. 20. Implement Sieve of Eratosthenes Algorithms for Prime Number? ( solution ) I hope these 20 questions should be enough to get you going on your preparation for Algorithms for Coding interviews. If you need more such coding questions you can take help from books like , by which contains 189+ Programming questions and solution. A good book to prepare for programming job interviews in a short time. Cracking The Code Interview Gayle Laakmann McDowell By the way, the more questions you solve in practice, the better your preparation will be. So, if you think this list of questions is not enough and you need more, then check out these additional for and these and for more thorough preparation. 50 programming questions telephone interviews books courses Now You’re Ready for the Coding Interview These are some of the most common questions outside of data structure and algorithms that help you to do really well in your interview. I have also shared a lot of these questions on my , so if you are really interested, you can always go there and search for them. blog These common coding, are the ones you need to know to successfully interview with any company, big or small, for any level of programming job. data structure, and algorithms questions If you are looking for a programming or software development job, you can start your preparation with this . list of coding questions This list provides good topics to prepare and also helps assess your preparation to find out your areas of strength and weakness. Good knowledge of data structure and algorithms is important for success in coding interviews and that’s where you should focus most of your attention. Resources to Prepare for Interviews , by Cracking The Code Interview Gayle Laakmann McDowell Data Structures and Algorithms: Deep Dive Using Java From 0 to 1: Data Structures and Algorithms in Java Data Structure and Algorithms Analysis — Job Interview My other articles you may like: 10 Books to Prepare Technical Programming/Coding Job Interviews 10 Algorithm Books Every Programmer Should Read Top 5 Data Structure and Algorithm Books for Java Developers My favorite free courses to learn Algorithms in depth 10 Free Data Structure Courses for Java Developers A list of courses to Crack Programming Job Interviews 10 Data Structure, Algorithms, and SQL Courses to Crack Coding Interview Closing Notes Thanks, You made it to the end of the article … Good luck with your programming interview! It’s certainly not going to be easy, but by following this searching and sorting algorithm questions, you are one step closer than others. If you like this article, then please share with your friends and colleagues, and don’t forget to follow on Twitter and and here on as well! javarevisited javinpaul javinpaul Medium P.S. — If you need some FREE resources, you can check out this list of to start your preparation. free data structure and algorithm courses

Stories, News & Mentions about MERGEPORT

Mergeport’s Stories on HackerNoon