Daily Coding Problem

People find their paths in the strangest of ways.

On September 03, 2020, I found this website Daily Coding Problem, where you can subscribe to a newsletter and get one problem a day. I like the initiative: Solving one problem every day.

Also, after college, the daily job cycle began, which led to my breakup with competitive programming. But I wanted to start solving problems again to keep it up, but could never begin.

So, I decided to subscribe the newsletter and to solve one problem every day.
Since then I have solved #67 problems. You can find the problems and solutions in their directories: here.

Solutions are mainly in C++ and Golang, and some problems may also have Python solution too, depending on what is asked in question.

Checkout my blog post on my habit of solving a problem daily here

Want to join me? or Just need to stay upto date?
Start watching this repository or connect with me.

And if you want to review my solutions or want to add something, I am open for accepting PRs, code reviews.
Anything you feel that needs correction.

Next problem:   #089
Missed problems:   #068   •   #069   •   #070   •   #071   •   #072   •   #073   •   #074   •   #075   •   #076   •   #077   •   #078   •   #079   •   #080   •   #081   •   #082   •   #083   •   #084   •   #085   •   #086   •   #087   •   #088

Some of the worthy problems I have solved are listed here...

Problem:  #010

Date: September 12, 2020
This problem was asked by Apple.

Implement a job scheduler which takes in a function f and an integer n, and calls f after n milliseconds.

Solution(s):
      • C++
      • Golang
      • Python

Problem:  #052

Date: October 24, 2020
This problem was asked by Google.

Implement an LRU (Least Recently Used) caching system. It should be able to be initialized with a cache size n, and contain the following methods:

set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.

get(key): gets the value at key. If no such key exists, return null. Each operation should run in O(1) time.

Solution(s):
      • C++
      • Golang

Problem:  #067

Date: November 08, 2020
This problem was asked by Google.

Implement an LFU (Least Frequently Used) caching system. It should be able to be initialized with a cache size n, and contain the following methods:

set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least frequently used item. If there is a tie, then the least recently used key should be removed.

get(key): gets the value at key. If no such key exists, return null. Each operation should run in O(1) time.

Solution(s):
      • Golang

Problem:  #011

Date: September 13, 2020
This problem was asked by Twitter.

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Solution(s):
      • C++
      • Golang

Problem:  #059

Date: October 31, 2020
This problem was asked by Google.

Implement a file syncing algorithm for two computers over a low-bandwidth network. What if we know the files in the two computers are mostly the same?

Solution(s):
      • Golang

Problem:  #015

Date: September 17, 2020
This problem was asked by Facebook.

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
i.e. UniformSelection

Solution(s):
      • C++
      • Golang

Problem:  #055

Date: October 27, 2020
This problem was asked by Microsoft.

Implement a URL shortener with the following methods:

• shorten(url), which shortens the url into a six-character alphanumeric string, such as zLg6wl.
• restore(short), which expands the shortened string into the original url. If no such shortened string exists, return null.

Hint: What if we enter the same URL twice?

Solution(s):
      • C++
      • Golang

Problem:  #024

Date: September 26, 2020
This problem was asked by Google.

Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.

Design a binary tree node class with the following methods:

• is_locked, which returns whether the node is locked.
• lock, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true.
• unlock, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true.

You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree.

Solution(s):
      • C++

Problem:  #045

Date: October 17, 2020
This problem was asked by Two Sigma.

Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive).

Solution(s):
      • C++
      • Golang

Problem:  #022

Date: September 24, 2020
This problem was asked by Microsoft.

Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null.

For example, given the set of words 'quick', 'brown', 'the', 'fox', and the string "thequickbrownfox", you should return ['the', 'quick', 'brown', 'fox'].

Given the set of words 'bed', 'bath', 'bedbath', 'and', 'beyond', and the string "bedbathandbeyond", return either ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond']

Solution(s):
      • C++

Problem:  #039

Date: October 11, 2020
This problem was asked by Dropbox (System Design).

Conway's Game of Life takes place on an infinite two-dimensional board of square cells. Each cell is either dead or alive, and at each tick, the following rules apply:

Any live cell with less than two live neighbours dies. Any live cell with two or three live neighbours remains living. Any live cell with more than three live neighbours dies. Any dead cell with exactly three live neighbours becomes a live cell. A cell neighbours another cell if it is horizontally, vertically, or diagonally adjacent.

Implement Conway's Game of Life. It should be able to be initialized with a starting list of live cell coordinates and the number of steps it should run for. Once initialized, it should print out the board state at each step. Since it's an infinite board, print out only the relevant coordinates, i.e. from the top-leftmost live cell to bottom-rightmost live cell.

You can represent a live cell with an asterisk (*) and a dead cell with a dot (.).

Solution(s):
      • C++

Problem:  #056

Date: October 28, 2020
This problem was asked by Google.

Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be colored such that no two adjacent vertices share the same color using at most k colors.

Solution(s):
      • Golang

People find their paths in the strangest of ways. Let's find our own!
Let's connect here.