Another Casual Coder

Daily Coding Problem: This problem was asked by Facebook. Given a array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy before you can sell it. For example, given [9, 11, 8, 5, 7, 10], you should return 5, since you could buy the stock at 5 dollars and sell it at 10 dollars. It seems very straightforward, and maybe I'm mistaken (although my solution seems to work fine), but here is the approach:  Keep track of min thus far  Check whether the current profit is larger than max  Make sure to return 0 if the max profit is negative (better to not buy/sell anything!)  Linear time, constant space GitHub:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10312018.cs Code: using System; using System.Collections.Generic; using System.Linq; using System.Text; usi...

Here is the Daily Coding Problem: This problem was asked by Amazon. Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one. For example, the longest palindromic substring of "aabcdcb" is "bcdcb". The longest palindromic substring of "bananas" is "anana". There is an O(n^3) solution: For i 0..n-1   For j i..n-1     Check whether substring(i,j) is a palindrome Don't do it. There is a better O(n^2) solution, which is the one I'll implement in this post: For i 0..n-1   (1) Assume position i is the center of a palindrome   (2) Move left and right from i while (1) is true Ultimately, there is actually a linear solution to this problem:  https://articles.leetcode.com/longest-palindromic-substring-part-ii/ , however, this blog post is narrow enough to fit the solution. Jk, I don't get that solution.... Cheers, Marcelo. GitHub:  https://githu...

Daily Coding Problem: This problem was asked by Google. Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null. Integers can appear more than once in the list. You may assume all numbers in the list are positive. For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since it sums up to 24. I'm sure there is a more efficient solution, but I decided to implement an all combinations brute-force approach:  - Have a base case  - Control the code with an index i  - Either don't add s[i] and move along  - Or add s[i] and move along  - Found the very first solution? Bail Seems to work, but 2^n: Code is in github:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10262018.cs And here: using System; using System.Collections.Generic; using System.Linq; using System.Text; using S...

From Daily Coding Problem, here comes a classic problem: This problem was asked by Microsoft. You have an N by N board. Write a function that, given N, returns the number of possible arrangements of the board where N queens can be placed on the board without threatening each other, i.e. no two queens share the same row, column, or diagonal. This is a well-known CS problem, with a vast literature:  https://www.bing.com/search?q=eight+queens+problem&qs=AS&pq=eight+queens&sc=6-12&cvid=909319BFEDC54FB4AACA2EB2B1274ACB&FORM=QBLH&sp=1 And I've written about this problem before, just search for "super queens" in my blog. Problem is actually simpler than it looks, at least the version that generates all the solutions - there is another one that uses DP, but I don't know the details of that one. For the traditional problem: Use backtracking Have 4 hash tables which will indicate, respectively: Whether a row has been taken by a queen ...

Three quick problems here, again from Daily Coding Problem: 1. This problem was asked by Google. Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array. Do this in linear time and in-place. For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G', 'G', 'B', 'B']. 2. Given the root to a binary search tree, find the second largest node in the tree. 3. This problem was asked by Google. The power set of a set is the set of all its subsets. Write a function that, given a set, generates its power set. For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. The ideas to solve these problems are...

Common problem being asked these days (this problem has been asked actually since 2016 at least), by Amazon (via Daily Coding Problem): Good morning! This is your coding interview problem for today. This problem was asked by Amazon. Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string "AAAABBBCCDAA" would be encoded as "4A3B2C1D2A". Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters. You can assume the string to be decoded is valid. We will be sending the solution tomorrow, along with tomorrow's question. As always, feel free to shoot us an email if there's anything we can help with. Have a great day! First I want to say that encoding one simple character like "A" as "1A" is actually a bad thi...

Hi, today's problem is a relatively common one in technical interviews, here it is from Daily Coding Problem: This problem was asked by Facebook. Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed). For example, given the string "([])[]({})", you should return true. Given the string "([)]" or "((()", you should return false. Here is the approach:  - First have a hash table which you can use to (quickly) map an open bracket to a closed bracket. You can also use it as an open bracket checker  - Then use a standard stack. Push open brackets. Pop closed ones, check for matches.  - Stack should be empty at the end That's it, code is on Github https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10112018.cs and below, thanks, Marcelo using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.T...

Two-pointers is a common technique to solving problems in O(n)-time and O(1)-space. It has been demonstrated here before:  https://anothercasualcoder.blogspot.com/2018/09/two-pointers-for-linear-solution.html Problem today is this one: This problem was asked by Google. Given a singly linked list and an integer k, remove the k th  last element from the list. k is guaranteed to be smaller than the length of the list. The list is very long, so making more than one pass is prohibitively expensive. Do this in constant space and in one pass. Strategy: keep track of a "behind" node and also a "previousBehind" node. Have another node which is running thru the list and once a counter goes beyond k, start moving the two behind pointers. Once the third pointer hits the end of the list, you're ready to delete the "behind" node using the previous pointer. Code is here and down below too, cheers, Marcelo https://github.com/marcelodebarros/dailycodin...

This post contains the solutions to two problems, from Daily Coding Problem: 1) This is your coding interview problem for today. 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. 2) This is your codin...

Today's problem is this, from Daily Coding Problem: Good morning! Here's your coding interview problem for today. This problem was asked by Google. You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on. Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board. For example, given the following board: [[f, f, f, f], [t, t, f, t], [f, f, f, f], [f, f, f, f]] and start =  (3, 0)  (bottom left) and end =  (0, 0)  (top left), the minimum number of steps required to reach the end is 7, since we would need to go through  (1, 2)  because there is a wall everywhere else on the second row...

This problem came from Daily Coding Problem , but I've modified it a bit.  First the original definition: Good morning! Here's your coding interview problem for today. 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']. The modification ...

Here is today's problem, from Daily Coding Problem: Good morning! Here's your coding interview problem for today. This problem was asked by Google. Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical. For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8. In this example, assume nodes with the same value are the exact same node objects. Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space. In such problems you can never (should never) ignore any of the information given. For example, the key information here is this: "...that intersect at some point". This means that the two lists end with the same sublist. An approach then is to:  - Reverse the two lists (O(n))  - Walk both of them while the node values match (O(n))  - Reverse back (O(n)) For a total of 3n passes (time) and constant space...

Problem:  https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/ Given two integers  L  and  R , find the count of numbers in the range  [L, R]  (inclusive) having a prime number of set bits in their binary representation. (Recall that the number of set bits an integer has is the number of  1 s present when written in binary. For example,  21  written in binary is  10101  which has 3 set bits. Also, 1 is not a prime.) Example 1: Input: L = 6, R = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits , 2 is prime) 10->1010 (2 set bits , 2 is prime) Example 2: Input: L = 10, R = 15 Output: 5 Explanation: 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set...