Python Coding Interview Cheat Sheet

 admin



  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 ?”
Questions
  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 ?

00:00 Let’s go through what you learned in this course. You learned a bunch of different concepts, and it’s always good to revisit what you learned. It’s also good to go through them and maybe make a cheat sheet or put them somewhere so you don’t forget. 00:11 I have an interview prep document where I’ve written a lot of this down, just so I don’t forget. Python Coding Interview Questions And Answers 2021. Here Coding compiler sharing a list of 35 Python interview questions for experienced. These Python questions are prepared by expert Python developers.This list of interview questions on Python will help you to crack your next Python job interview. All the best for your future and happy python learning.

  • 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$.

Python Basics Cheat Sheet

  • 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

  1. I've been wanting to update the Beginner's Python Cheat Sheets that accompany Python Crash Course for a while now. I finally made time over the last month to go through the entire set. I originally developed the sheets in Word, which was not a particularly sustainable approach.
  2. View CheatSheet-Python-6-Coding-Interview-Questions-Email-Course-Ad.pdf from CSE 110 at BRAC University. Python Cheat Sheet: 14 Interview Questions “ A puzzle a day to learn, code,.
  3. Python Interview Cheat Sheet Python Cheat Sheet can be used also for your Python Job interview. Before your technical interview, you can check this sheet and you can use it as Python Interview Cheat Sheet. You can find all the basic terms of Python programming languages in this cheat sheet.

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.

Python Coding Interview Cheat Sheet

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

Python Cheat Sheet

Efficient when there is less than 64 possible values

SetBinary
$emptyset$0
${i}$1 << i
${0, 1, ldots, n-1}$(1 << n) - 1
$A cup B$`A
$A cap B$A & B
$(A setminus B) cup (B setminus A)$A ^ B
$A subseteq B$A & B A
$i in A$(1 << i) & A
${min(A)}$-A & A

You should ideally now about:

Python

(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

Python Coding Questions Interview

SheetPython coding interview cheat sheet 2020

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

Python Cheat Sheet Download

  • 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?