Another Casual Coder

Here is the problem Good morning! Here's your coding interview problem for today. 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. Upgrade to premium  and get in-depth solutions to every problem. If you liked this problem, feel free to forward it along so they can  subscribe here ! As always, shoot us an email if there's anything we can help with! The key here is to use a simple count and always decide on the following:  - If when picking a random number between 0 and count (inclusive) gives you 0, then pick the new element  - Otherwise, don't change elements The probability that you will switch elements is always 1/(count+1), which over time will give you a fair and equal probability across all the elements. Code is below and on Github:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09292018.cs usi...

Problem today was: Good morning! Here's your coding interview problem for today. This problem was asked by Amazon. Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters. For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb". The solution I came up with has two pointers: one moves in front, the other one in the back, and you control when each pointer moves depending on what has been added to a hash table. Worst case scenario each pointer will go thru each element of the string once, for a total of O(2N)-time. Here is the code, also on GitHub:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09272018.cs  cheers, Marcelo using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; namespace DailyCodingProblem { class ...

Good morning! Here's your coding interview problem for today. This problem was asked by Amazon. There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Dynamic Programming (aka DP) is by far the most loathed algorithm type for those studying algorithms and/or preparing for technical interviews. I don't like it either. I mean, I actually like it, but as I said before, it just doesn't come naturally to me, unlike recursion, queues, tries, trees, stacks, search problems, ML, which are usually more straightforwa...

The daily coding problem for today was this one: Good morning! Here's your coding interview problem for today. 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. The problem is begging for you to use a Trie data structure . I've written about tries many years ago (you can search for "Trie" in the anothercasualcoder blog), but I thought of an even simpler implementation. Honestly you only need two member variables for your Trie class: A boolean that indicates whether this node is a leaf node (meaning it is the end of a word) A hashtable of Tries corresponding to its children Honest...

Given a binary tree, return its deepest node Got an article by Daily Coding Problem claiming that this was an interview question asked during a Facebook or Google interview. The question is relatively simple, both recursively or non-recursively. Recursively can be done with a post-order traversal as demonstrated in the previous post. In this post the solution will be non-recursive. The idea is very simple: use a stack, push the node and the level. Pop. Check for the max level. Push the children. Can be done with either a stack or a queue, it doesn't really matter. That's it! Code is here:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09232018.cs Thanks, Marcelo public class StackItem { public Tree tree; public int level; public StackItem(Tree tree, int level) { this.tree = tree; this.level = level; } } public int DeepestNode(Tree tree) { if (tree == null) return 0; StackItem si = new StackItem(tree, 1)...

Here was today's problem, asked (so they say) by Google: Good morning! Here's your coding interview problem for today. This problem was asked by Google. A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value. Given the root to a binary tree, count the number of unival subtrees. For example, the following tree has 5 unival subtrees: 0 / \ 1 0 / \ 1 0 / \ 1 1 Not sure you'll ever run into such a problem in real life, but in the rare case you do... My approach was to do a post-order traversal of the tree. The function actually returns whether the current (sub)tree is a unival or not. It also carries a variable by reference which increments the number of unival subtrees seen so far. The base case returns true for when the tree is null, and the unival count is set to zero. After you call for left and right, the unival count is incremented right away with the values coming from the...

Daily Coding Problem  gives you a daily coding problem (LOL) every day (LOL#2). Here is the very first one I got: Good morning! Here's your coding interview problem for today. This problem was recently asked by Google. Given a list of numbers and a number  k , return whether any two numbers from the list add up to  k . For example, given  [10, 15, 3, 7]  and  k  of  17 , return true since  10 + 7  is  17 . Bonus: Can you do this in one pass? Notice that it doesn't say that the list contains unique numbers, so you can't assume that and your code needs to handle the case of dupes. My strategy is the following: Push all the numbers to a hash-table (HT) In the HT each number will have a count corresponding to how many times that number shows up in the list of numbers The code above runs in O(n)-time and O(n)-space Then for each number i, get the difference d=k-i If d is equal to i, make sure that there is at least ...

This problem is a mix of simple design, coding and math. Question asks to design a class to shuffle and array, take a look:  https://leetcode.com/problems/shuffle-an-array/description/ Shuffle a set of numbers without duplicates. Example: // Init an array with set 1, 2, and 3. int[] nums = {1,2,3}; Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. solution.shuffle(); // Resets the array back to its original configuration [1,2,3]. solution.reset(); // Returns the random shuffling of array [1,2,3]. solution.shuffle(); What I decided to do was: Keep a private member which is the original array. Use the clone function in C# to copy the array from/to Create a private random object too The reset returns the original array The shuffling first makes a copy of the original again OK, now for the actual shuffling: for each index i, pick a random index between [i, array le...

To solve this problem:  https://leetcode.com/problems/subtree-of-another-tree/description/ : Given two non-empty binary trees  s  and  t , check whether tree  t  has exactly the same structure and node values with a subtree of  s . A subtree of  s  is a tree consists of a node in  s  and all of this node's descendants. The tree  s  could also be considered as a subtree of itself. What you want to do is to have two nested  pre-order traversal  functions: the inner function checks whether two tree are identical matches (notice the null checks in the beginning), the outermost function traverses all the nodes in s and checks whether the subtree rooted at that current node is an exact match with t. Time-complexity: O(|s| * |t|). Thanks, Marcelo public class Solution { public bool IsSubtree(TreeNode s, TreeNode t) { if (ExactMatch(s, t)) return true; return s != null && (IsSubtree(s.left, ...

New LeetCode medium problem:  https://leetcode.com/problems/open-the-lock/description/ : You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . The wheels can rotate freely and wrap around: for example we can turn  '9'  to be  '0' , or  '0'  to be  '9' . Each move consists of turning one wheel one slot. The lock initially starts at  '0000' , a string representing the state of the 4 wheels. You are given a list of  deadends  dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it. Given a  target  representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible. Given the small number of permutations and the fact that ...