In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ( listen)) is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, and automated reasoning tasks.

P versus NP

  1. P
    • The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P".
    • P usually means Deterministic Problem which can say True or False in a polynomial time.
    • P is also known as consists of certain set of Decision Problems like Checklist.
  2. NP
    • The class of questions for which an answer can be verified in a polynomial time is called as NP, which stands for "Non-deterministic Polynomial time".

Note Polynomial Time means like Computing Time.

Software Algorithms

Many computer science problems are contained in NP, like decision versions of many search and optimization problems.

  • Two Sum — Given an array of integers, return indices of the two numbers such that they add up to a specific target.
  • Add Two Numbers — You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
  • Longest Substring Without Repeating Characters — Given a string, find the length of the longest substring without repeating characters.
  • Median of Two Sorted Arrays — There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
  • Longest Palindromic Substring — Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
  • ZigZag Conversion — The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
  • Reverse Integer — Given a 32-bit signed integer, reverse digits of an integer.
  • String to Integer (atoi) — Implement atoi which converts a string to an integer.
  • Integer to Roman — Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
  • Roman to Integer — Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
  • Longest Common Prefix — Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".
  • 3Sum — Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
  • 4Sum — Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
  • Remove Nth Node From End of List — Given a linked list, remove the n-th node from the end of list and return its head.
  • Pow(x, n) — Implement pow(x, n), which calculates x raised to the power n (xn).
  • Valid Parentheses — Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
  • Merge Two Sorted Lists — Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
  • Generate Parentheses — Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
  • Merge k Sorted Lists — Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
  • Swap Nodes in Pairs — Given a linked list, swap every two adjacent nodes and return its head.
  • Reverse Nodes in k-Group — Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
  • Remove Duplicates from Sorted Array — Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
  • Remove Element — Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.
  • Climbing Stairs ★ — You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
  • Flip Equivalent Binary Trees — For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees. A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations. Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.
  • Maximum Width Ramp ★ — Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i. Find the maximum width of a ramp in A. If one doesn't exist, return 0.
  • Find First and Last Position of Element in Sorted Array — Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n).
  • Next Permutation ★ — Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory.
  • Safe Add function by checking integer overflow — When we implement add function by operator + in C++, sometimes we face over error - actually system does not show any error and that should be continuously increased, but there is a possibility to change into minus value suddenly.
  • Divide number without / operator — Dividing number without operator can be implemented in two approaches - loop and bit operation
  • Equation for surface area of a right rectangular pyramid