Coding Interview Cheat Sheet Python

1. Ask questions about the problem to clarify it.
2. Don’t jump into the code, think and discuss.
3. Don’t stay muted for a while, clarify when you are thinking, “Can I think for a second?”.
4. Think out loud.
5. Multiply the examples.
6. List the corner cases.
7. Ask for approval before coding, “Does it seem like a good strategy ?” “Should I start coding ?”

1. The definitive coding interview cheat-sheet. Datastructures & algorithms; Full CS course; Questions per data structures; Psychological tricks; Gold mine; Source of the sources; Interview tips. Ask questions about the problem to clarify it. Don’t jump into the code, think and discuss.
2. Browse through our collection of handy cheatsheets under a single place. Our cheatsheet contains useful code examples, web developer tools and more.

1. Can sorting input data help me ?
2. Can splitting input data help me ?
3. Can a dictionary help me ?
4. Can multiple pointers help me ?
5. Can a frequency array help me ?
6. Can multiple pass help me ?
7. Can case-based reasoning help me ?
8. Is there an ends here/with property ?

Pre-Interview Cheat Sheet Review A few notes to review before the a Software Engineer interview and freshen up. Some of these little facts may come up or be good to throw some keywords and impress. Simply put, the Python Cheat Sheet is your easiest and fastest way to finding all you need while coding! It's the perfect resource to find exactly what you need while working on homework and lab assignments! You can obtain the Python Cheat Sheet for FREE by entering your email below!

• Checking if $i in Stack$ in $O(1)$: just keep updated an “is_in” array is_in_stack where is_in_stack[i] tells whether $i in Stack$.
• Sets with fewer than 64 possible items can be coded as integers.
• For singly linked lists, creating 2 pointers $n$ nodes apart may be handy. It is also applicable to every sequence of elements. (find the middle / $n^{th}$ from the end, a cycle…)
• Use infinite boundariesfloat('inf') ormath.inf.
• Use frequency arrays when counting letters. A counting sort might also prove useful (as it is linear for frequencies) later on.
• To find $a$ and $b$ in a array so that $a+b = c$, save every seen number in a set $S$ and for every new $i$, check if $c-i in S$.

• sorted ➜ Bisection search

• iterative DFS ➜ stack

• BFS ➜ queue

  • Need to keep track of the depth? → 2 queues

• Optimal substructure ➜ Dynamic programming to compute all the optimal solution of size $0 ldots n$ and deduce the solution.

  • when it is possible to craft the optimal solution for an instance size $n$ using the solution to instances of size $i_1, ldots, i_p < n$.
  • Can be on a pair of parameters, solution of size $(n, k)$ can be deduced from solution of size $(i, j)$ where $i leq n$ and $j leq k$.

  Examples: subarray, knapsack, longest substring

Do It Yourself

Solve an example with your brain and hands and see what “algorithm” you used.

B.U.D.

Bottlenecks, Unnecessary work, Duplicated workWalk through your best algorithm and look for these flaws.

Space/Time tradeoffs

Can I save time by using more space ?

• Hash tables
• Frequency arrays
• Dynamic programming

• Stack

  • $O(1)$: l = [], l.append(), l.pop(), l[i], len(l)
  • $O(n)$: del l[i], l[inf:sup:step]
  • $O(nlog_2(n))$: l.sort(), sorted(l)

• Queue

  • $O(1)$: dq = deque(), dq.popleft() , dq.appendleft(x) + normal list operations except slices

• Dictionary / Hashtable

  • $O(1)$: dic = {}, key in dic, dic[key], del dic[key] on average, worst case $O(n)$

• Set

  • $O(1)$: s = set([]), x in s, s.add(x), del s[x]
  • $O(n_1)$: s1|s2 , s1&s2 , s1-s2, s1^s2

• Heap / Priority Queue

  • $O(1)$: h = []
  • $O(log_2(n))$: heappush(h, x), heappop(h)
  • $O(nlog_2(n) )$: heap = heapfy([1, 5, 2, 3...])
  • left = 2*i; right = left+1; father = i//2 if h[0] in a 1-based array
  • left = 2*i+1; right = 2*i+2; father = depends on parity otherwise

• Union find

  • to be continued

Bisection search ends when left and right cross.

When will they cross ?

• f(x, key) = x < key ➜ Move right when x key
  • Index of the first occurrence of key
• f(x, key) = x <= key ➜ Move left when x key
  • Index of the last occurrence of key + 1

• Might be necessary to check if the final value points to key

Merge sort

1. Split the list in 2
2. Recursively sort the left-most part and right-most part
3. Merges these parts

Counting sort

1. Count the occurences of each possible values
2. Put the number of occurence times each value in the array, starting from the smallest one

Simple steps

1. Recursive solution
2. Store intermediate results
3. Bottom up (Optional)

• Consider adding dummy values because things like res[x][y] may throw index errors on corner cases.
• It can be easier to find the size of the best solution and then backtrack to find the solution.

Recursive solution

Memoization

@lru_cache(maxsize=None) can automate the memoization process by using a dictionary to store the result of function calls (less efficient than an array).

Bottom up

Operation

• x << y Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.

• x >> y Returns x with the bits shifted to the right by y places. This is the same as //‘ing x by 2**y.

• x & y Does a “bitwise and”. Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it’s 0. Commutative and Associative.

• x | y Does a “bitwise or”. Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it’s 1. Commutative and Associative.

• ~ x Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

• x ^ y Does a “bitwise exclusive or”. Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it’s the complement of the bit in x if that bit in y is 1. Commutative and Associative.

Coding sets on bits

Efficient when there is less than 64 possible values

You should ideally now about:

(Most are overkill for an interview but nice to know as a software engineer)

Numeric/mathematical

• Kadane’s algorithm (maximum subarray)
  • every subarray has an ending
  • the maximum subarray ending at the spot i + 1 is either
    1. maximum subarray ending at the spot i + A[i + 1]
    2. A[i + 1]
• Boyer-Moore majority vote algorithm
  • find a candidate for the majority element
    1. keep a counter of the number of occurence of the current candidate while iterating through the list
    2. ++ if the current element is the candidate -- otherwise
    3. if counter reaches 0, candidate = current candidate
  • check if the candidate is the majority element
• Quickselect / Median-of-medians
• Reservoir sampling
• Sieve of Eratosthenes
• Alias method
• Euclid’s algorithm
  • if b != 1 return = gcd(b, a % b)
  • else return a
• Exponentiation by squaringMatrix exponentiation
  • Just square exponentiation with matrix
  • res = res * a if n odd
  • a = a * a otherwise
• Matrix exponentiation
  • use exponentiation by squaring
• Range minimum query

Tree/graph

• BFS
  • stack or recursion
• DFS
  • queue
• Dijkstra’s algorithm
• A* search
• Toposort
• Morris traversal
• Prim’s algorithm
• Kruskal’s algorithm
• Bellman-Ford algorithm
• Graham scan algorithm
• Ford-Fulkerson algorithm / Edmunds-Karp algorithm
• Floyd’s cycle finding algorithm
• Closest pair of points algorithm
• Hopcroft-Karp algorithm

String

• Longest common subsequence
  • lcs[p][q] = lcs ending at index p in str1 and q in str2 (DP)
  • lcs[p][q] = str1[p] str2[q] ? 1 + lcs[p-1][q-1] : max(lcs[p][q-1], lcs[p-1][q])
• Rabin-Karp algorithm
• Knuth-Morris-Pratt algorithm
• Aho-Corasick algorithm
• Ukkonen’s algorithm / SA-IS algorithm
• Manacher’s algorithm

Search

• Interpolation search
• Meta binary search

Sorting

• Heap sort
• Quicksort + Three way partitioning + Median of three
• Dutch national flag algorithm

Other

• Fisher-Yates shuffle
• Shunting-yard algorithm
• Minimax
• Mo’s algorithm
• Square root decomposition
• Rolling hash

• Questions about the stack, the tests, the integration process, documentation of production incidents…

• Standard dev environment ? Mandatory ?

• What are the weekly meetings ?

• What’s the remote policy ?

• What’s the product schedule and deployment frequency ?

• What about conference/event attending ?

• Is there any dedicated time for self-training ? Contributing to FOSS ?

• What does it take to be successful here ?

To evaluate the global software engineering quality using the joel (StackOverflow co-founder) test:

1. Do you use source control?
2. Can you make a build in one step?
3. Do you make daily builds?
4. Do you have a bug database?
5. Do you fix bugs before writing new code?
6. Do you have an up-to-date schedule?
7. Do you have a spec?
8. Do programmers have quiet working conditions?
9. Do you use the best tools money can buy?
10. Do you have testers?
11. Do new candidates write code during their interview?
12. Do you do hallway usability testing?

• Python is a multi-paradigm general-purpose, object-oriented programming language
• It is a cross-platform programming language so code python file written in one system can be run same on different systems.
• Easy to learn.
• Simple Syntax and akin to pseudocode.
• Automatic Garbage Collection.
• It is an open-source programming language.

Applications of Python

Python is a very versatile language and it is used in many IT fields such as:

• Web Development (back-end)
• Desktop Applications
• Data Science.
• Machine Learning
• Artificial Intelligence.

Major Characteristic of Python

• Very Simple Programming language.
• Python has the most libraries.
• Support Object-Oriented programming
• Ideal Programming language for a beginner.
• Robust and Secure
• Highly Scalable
• Use Interpreter
• Dynamic Programming language.
• Multi-threading.

Python IDE’s

There are many IDE’s on the internet for Python the two most recommended ones are:

• PyCharm (By Jetbrains)
• Atom (Powered by GitHub)

Standard Data Types in Python:

Python has two types of Data types:

• Base Type.
• Container Type.

Base Type

Container Type Data Types

Python Operators

Python has some standard operators which include arithmetic operators too.

Python Comparison Operator

There are some operators in python which are used to compare two objects or values and return a Boolean value True and False:

Logical Operators

Python has three logical Operators:

• and
• or
• not

Python Identifiers

Identifies are the name given to an object, identifiers can be also known as a variable name. There are some rules associated with an identifier or variable name. Using identifies we can give a name to variables, functions, modules, classes.

Identifiers rule:

• The first letter of an identifier could be a lowercase or upper case Alphabet or _ (underscore symbol), and it could be followed by any alphabet, digit (0,9) and _.
• There should be no special symbol in identifier except _.
• Do not use reserved keywords as an identifier.

Variable Assignment

We use equal to “=” symbol to assign an object to an identifier.

The identifier name should be on the left side and value on the right side of the assignment operator.

Example:

x =20

Python I/O

Example:

By default input() accept value as string.

Type Conversion

Using there are many reserved keywords in python which are used to convert the data type of a variable.

Indexing Calling in Python

In python String, List and tuple objects support indexing calling.

Example:

Boolean Logic in Python

In python, we often encounter with Boolean values when we deal with comparison operator conditional statements.

Types of Boolean

In python there are two types of Booleans:

• True
• False

Modules Name and Import

Python Math Module

Math is the most important and widely used standard module of python, it provides many methods related to mathematics.

Conditional Statement

Python Conditional statement consists of 3 keywords if, elif and else.

Example:

Loops

There are two loops statements present in python:

• for loop
• while loop

Example:

Break

It is a statement used inside the loop statement, and it is used to terminate the loop flow and exist from the loop immediately.

Example:

Continue

Continue is the opposite of break, it is also used in loop statements and directly jump to the next iteration.

Example:

Function

To create a user-defined function in python we use the def keyword and to exit from a function we return a value using the return keyword.

Example:

Python List

A list is a collection of different data types, and it stores all elements in a contagious memory location.

Create a list

To create a list we use square brackets [ ].

Example:

Indexing

List support indexing, with the help of indexing we can access the specific element of the list.

Example:

List Slicing

With list slicing, we can access a sequence of elements present in the list.

Example:

List Unpacking

Loop through a List:

Adding Elements in the list:

Removing Elements from a list

If condition with a list

List Comprehension

lst_2 = [i for i in lst ]

Condition inside list comprehension

Zip function to combine two lists

Map and Filter on a list

List Operations

Python Tuples

Tuples in python similar to a list, the only difference is tuples are immutable.

Create a tuple:

Convert a list into a tuple

Indexing In tuple

Python Arrays

Python does not have inbuilt support for arrays but it has standard libraries to for array data structure. Array is a very useful tool to perform mathematical concepts.

Create an Array:

Python Sets

Python set is similar to the mathematic sets, a python set does not hold duplicates items and we can perform the basic set operation on set data types.

Create a Set:

Basic Set operation

Dictionary

Dictionary is a collection of key: value pair and the key could only be an immutable data type.

Create a dictionary:

Convert a list into a dictionary:

Accessing Dictionary Elements

We use the key to access the corresponding value.

Looping Through a dictionary:

Generator Comprehension

Like a list comprehension, we have generator comprehension in generator comprehension we use parenthesis () instead of sq. brackets [].

Example:

Exception Handling:

In exception handling we deal with runtime error there are many keywords associated with exception handling:

Example:

Python Class

Class provides the Object-Oriented programming concepts to python.

Create a class

Create a constructor for a class:

The constructor is the special method of class which executes automatically during the object creation of the class.

Magic Methods of class

Class Private members:

Python Coding Questions Interview

Conventionally to declare an attribute private we, write it name starting with __ double underscore.

Example:

Inheritance:

An inheritance we can use the methods and property of another class:

Example:

Multiple Inheritance:

Basic Generic Operations on Containers

Python Basics Cheat Sheet

People Also Read: