Probing with Lalit Kundu

#CodingInterviewWeekly

Are you planning to obliterate a coding interview soon? Or, you're afraid of the time it'll take you to solve the vast number of questions that coding websites offer? Do you want to build concepts, instead of trying to find patterns? Are you looking for a community to discuss questions with, and build skills that'll help you crack coding interviews?

In this series, you'd find a unique problem every week - something that you may encounter in an interview. We'll discuss the problem in the comments, and a week later, on my YT channel I'll talk about the fundamental ideas needed to solve that problem - fundamentals which are applicable across any number of different problems. Further, I'll provide insights as someone who's conducted tons of interviews for companies like Google - how a typical interview will proceed, what are the common mistakes, what an interviewer expects from candidates, and so on.

Week 1: Dynamic programming and graphs

Problem

  • You are in a matrix where each cell has some coins placed on it. You can move in either of the 4 directions (up, left, right, bottom) where the movement is possible only if the cell you want to move to has strictly greater number of coins than your current cell. You can start from any cell. What is the maximum length of the path you can move?

  • Follow-up: Find a cell from which maximum number of cells are reachable using the rules we've mentioned.

Discussion

YT video

Follow-up reading and exercises


Week 2: Greedy algorithms

Problem

  • You have N objects where i^th object has a given integer weight W_i and integer value V_i. Your objective is to select a subset of these objects such that sum of objects' weights doesn't exceed K and the sum of objects' values is maximal. W_i is either 1 or 2, for all i.

  • Follow-ups:

    • W_i can be any integer, but only two distinct values.

    • W_i is either of 1, 2 or 3, for all i.

Discussion

YT video

  • https://www.youtube.com/watch?v=YMQj4ggigDI

Exercises

  • Given two strings A and B, find the smallest prefix of A that contains B as a subsequence (hint: greedy stays best)

  • Prove Kruskal's minimum spanning tree greedy algorithm.

  • Come up with a greedy algorithm for fractional knapsack problem (you can choose a fraction of the object) and prove it. (hint: exchange argument)

Follow-up reading

Week 3: Data structures

Problem

  • Design a key-value data structure which can support these operations

    • Increment key k by 1.

    • Decrement key k by 1.

    • Output the key with maximum value

    • Output the key with minimum value

There's no obvious best solution here, but try to come with many different options that can optimize for time complexity of these operations.

Discussion

YT video

Exercises

  • Design a data structure which can support following operations

    • Insert x.

    • Remove x.

    • Output a psuedo random value from the container.

  • Given an array of positive integers you have to print the number of subarrays whose XOR is less than K.

  • https://www.spoj.pl/problems/CUCKOO/

Follow-up reading

  • CLRS: section 10.2, Mark Allen Weies Chapter 3

Week 4: Strings

Problem

  • Given two strings A and B, find the longest common contiguous substring between them.

    • There are some very specific reasons for why this standard problem could belong in an interview and I'd go into the reasons for that in the explanation video.

    • Meanwhile, keep in mind that there are no inefficient solutions - just start somewhere and use basics of algorithms.

Discussion

YT video

Exercises

  • You have a string 𝑆 of length 𝑁 . Given an 𝑀≀𝑁 , find the number of substrings of S that are palindrome and are of size 𝑀 .

  • Given a string 𝑆 , find the size of substring of largest size which occurs atleast twice in the string.

  • https://www.spoj.com/problems/AGGRCOW/

Follow-up reading

Week 5: Ad-hoc

Problem

  • Given N positive integers, find the smallest impossible subset sum (each integer can be used only once in the subset). Example, for [1, 2, 5], possible subset sums are [1, 2, 3, 5, 6, 7, 8], and hence, the answer is 4.

  • Follow-up: Answer Q queries of the form - given integer x, is x a possible subset sum?

Discussion

YT video

Exercises

  • For all i, what is the answer is A_i is removed from the input array A?

  • Think of a divide and conquer approach to subset problem problem ("is integer X a possible subset sum?"); analyze the time and space complexity.

Follow-up reading