Horia Toma

45 minute coding

[45minutescoding]

Next Bigger Integer

Given a number, find the next bigger integer composed of the same digits as the original one.

Example: 34265 -> 34526

The idea is to find the pivot meaning the point where a digit is lower than the next one. Starting from that point and until the end of the digit array, every position will be changed.

I will use a queue, put all ascending digits in it and find the first one bigger than the inflexion point. It will be that digit that will replace the value at the inflexion point.

For our example, the pivot is 2 and it will be replaced with the lowest digit found when enumerating the digits from the right, which is 5.

From there on, the number will be assembled by using the original left part and on the right we will try to build the smallest possible number by dequing the digits stored previously.

The code below:

public static int GetNextBiggerInteger(int n) { if (n < 10) { return n; } // last digit int digit = n % 10; // queue storing digits that will be moved var queue = new Queue(); queue.Enqueue(digit); n /= 10; while (n > 0) { int tempDigit = n % 10; n /= 10; if (tempDigit > digit) { queue.Enqueue(tempDigit); digit = tempDigit; } else { // found the rotation point if (n > 0) { // set the left part using the digits already stored in the queue n *= (int) Math.Pow(10, queue.Count + 1); } // right part consists on retrieving digits stored in the queue // and assembling them int result = 0; int pos = 0; // switching the pivot bool switched = false; while (!switched || queue.Count > 0) { int el = queue.Dequeue(); pos++; result *= 10; if (!switched && el > tempDigit) { result += tempDigit; result += el * (int)Math.Pow(10, pos); switched = true; } else if (switched || el < tempDigit) { result += el; } } return n + result; } } return -1; }

More examples:

21765 --> 25167 27865 --> 28567 25468 --> 25486 34265 --> 34526 54321 --> -1

[45minutescoding]

Longest Increasting Subsequence and Patience Sorting

What this dynamic programming problem and the Solitaire game have in common is the Patience Sorting algorithm. It's easy to see how the elements are arranged, but it's not obvious how to reconstruct the longest increasing subsequence.

Suppose you have this list of numbers (if you want to play with cards, take a look here):

3, 2, 4, 7, 1, 5, 9, 6, 8

Let's try building piles by using these values such that each number can be placed only in the first pile whose top is larger than our number (Solitare game like). If no such pile can be found, a new pile is created.

Here is how it goes:

3, no pile found, it becomes the top of the new pile

2, it goes on first pile and becomes the new top

4, no pile found with larger top, create new pile

7, no pile found with larger top, create new pile

1, it goes on first pile and becomes the new top

5, it goes on the third pile  and becomes the new top

9, no pile found with larger top, create new pile

6, it goes on the fourth pile  and becomes the new top

8, no pile found with larger top, create new pile

Each time we add an element to a pile, we keep a reference to the top of the previous pile at that moment (if any), which represents, in fact, the previous element in the longest subsequence ending on the element we're adding.

Below how the piles look at the end (I added the references):

The number of piles represent the length of the longest increasing subsequence. We start with the top of the last pile and, by using references, we build the sequence.

Every time we add an element, we have to find the pile it belongs to. We are going to use a list that contains the top of each pile. This structure is ordered by the way of building it. Looking for the first element equal or greater than a value has the complexity of binary search, O(logN), therefore the time complexity of the algorithm is O(NlogN).

We will need additional structures for keeping the references and the piles, so the space complexity is O(N) (you can say P where P is the number of piles).

The code:

class HelperElement { public int Value { get; set; } public int? PreviousRef { get; set; } } public static IList<int> GetLongestIncreastingSubsequence(IList<int> list) { var result = new List<int>(); if (list.Count == 0) { return result; } var piles = new List<List<HelperElement>>(); var pileTops = new List<int>(); foreach (int element in list) { int pileIndex = 0; if (piles.Count == 0) { var pile = new List<HelperElement> { new HelperElement { Value = element } }; piles.Add(pile); } else { // find the pile to place the element pileIndex = Utils.FindFirstEqualOrHigher(pileTops, element, 0, pileTops.Count - 1); if (pileIndex == -1) { // no pile found, we'll create a new one pileIndex = piles.Count; piles.Add(new List()); } var pile = piles[pileIndex]; pile.Add(new HelperElement { Value = element }); // add pointer to the previous pile top element // will be used for tracking the sequence if (pileIndex > 0) { pile[pile.Count - 1].PreviousRef = piles[pileIndex - 1].Count - 1; } } if (pileTops.Count <= pileIndex) { pileTops.Add(element); } else { pileTops[pileIndex] = element; } } // build the longest increasing subsequence in descending order int? index = piles[piles.Count - 1].Count - 1; for (int i = piles.Count - 1; i >= 0; i--) { if (index.HasValue) { HelperElement element = piles[i][index.Value]; result.Add(element.Value); index = element.PreviousRef; } } // this can be avoided if the list is walked from right to end // searching for decreasing subsequences // however, it doesn't change complexity order result.Reverse(); return result; }

And if you want to take a look at the code that finds the first element equal or greater than a value:

public static int FindFirstEqualOrHigher(int[] array, int value, int left, int right) { if (left > right) { return -1; } if (left == right) { return array[left] >= value ? left : -1; } int half = left + (right - left) / 2; if (array[half] == value) { return half; } if (array[half] > value) { return FindFirstEqualOrHigher(array, value, left, half); } return FindFirstEqualOrHigher(array, value, half + 1, right); }

[45minutescoding]

Longest increasing subsequence

Find the longest increasing subsequence in a list of integers. According to the classic description, the sequence doesn't have to be contiguous and the solution is not necessary unique. 

A well known problem and usually among the first ones to look at when learning dynamic programming. In this blog entry, the simple solution that requires O(n^2) time complexity and O(n) in space since I'm going to use an additional structure with the same number of elements as the original list.

For each element, determine the longest increasing subsequence that ends on it. In order to do that, look at the previous elements that are lower than the current and pick the one with the longest increasing subsequence ending with it. This implies storing some additional data for each element.

/// /// Store helping data for an element /// in order to count the longest increasing subsequence ending with it /// and previous element in that subsequence /// class HelperElement { /// /// max length of a subsequence ending with this element /// a sequence with no previous elements has length 1 /// public int MaxLength { get; set; } /// /// previous position in the subsequence corresponding to the index in the initial list /// public int? PreviousIndex { get; set; } }

You have to traverse all previous elements for every element.

public static IList<int> GetLongestIncreastingSubsequence(IList<int> list) { var result = new List<int>(); if (list.Count == 0) { return result; } var helperList = new List<HelperElement>(); int maxLength = 1; int maxLengthEndIndex = 0; for (int i = 0; i < list.Count; i++) { var current = new HelperElement { MaxLength = 1 }; // will compare all previous elements with the current one // in order to find a lower element on which the subsequence can be extended for (int j = 0; j < i; j++) { // the +1 will take the closest neighbor in case of equality of subsequences' length if (list[j] <= list[i] && helperList[j].MaxLength + 1 >= current.MaxLength) { current.MaxLength = helperList[j].MaxLength + 1; current.PreviousIndex = j; } } helperList.Add(current); if (current.MaxLength >= maxLength) { maxLength = current.MaxLength; maxLengthEndIndex = i; } } // reconstruct the subsequence result.Add(list[maxLengthEndIndex]); HelperElement tmp = helperList[maxLengthEndIndex]; while (tmp.PreviousIndex.HasValue) { int index = tmp.PreviousIndex.Value; tmp = helperList[index]; result.Add(list[index]); } // this can be avoided if the list is walked from right to end // searching for decreasing subsequences // however, it doesn't change complexity order result.Reverse(); return result; }

Example:

3, 2, 4, 7, 1, 5, 9, 6, 8

produces (there are two solutions of length 5, the algorithm picks only one):

2, 4, 5, 6, 8

[45minutescoding]

Matrix in spiral

A quick one this time. Given a matrix, print the elements in a spiral starting from the upper left corner and going right, down, left, up and so on.

I find this picture from Bees & Bombs inspiring.

I'm using four indexes representing the current step four corners. They will update depending on the direction. Here is the code:

public static IEnumerable<T> Traverse<T>(T[,] matrix, int width, int height) { int iStart = 0; int iEnd = width - 1; int jStart = 0; int jEnd = height - 1; int direction = 0; while (iStart <= iEnd && jStart <= jEnd) { if (direction == 0) { for (int j = jStart; j <= jEnd; j++) { yield return matrix[iStart, j]; } iStart++; } else if (direction == 1) { for (int i = iStart; i <= iEnd; i++) { yield return matrix[i, jEnd]; } jEnd--; } else if (direction == 2) { for (int j = jEnd; j >= jStart; j--) { yield return matrix[iEnd, j]; } iEnd--; } else { for (int i = iEnd; i >= iStart; i--) { yield return matrix[i, jStart]; } jStart++; } direction = ++direction % 4; } }

With an example:

var matrix = new[,] { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20} }; MatrixInSpiral.Traverse(matrix, 4, 5).ToList().ForEach(x => Console.Write("{0} ", x));

1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12 

[45minutescoding]

Median for two sorted arrays in O(logn)

Better than merging the arrays? It's possible to get the median by sequentially splitting the two arrays in half and always choosing the half that contains the median.

Let's take an example:

1  3  7  8  9

2  4  5  6  10

The median of the first array is 7 and the median of the second is 5. Now it doesn't make sense to continue analyzing the right half of the first array nor the left half of the second array as those elements will be outside of what constitutes the middle elements of a pontentially merged array.

Cutting off the mentioned parts, leaves us with these two arrays:

1 3 7

5 6 10

Comparing the medians, 3 < 6, makes us use the right half of the first array and the left one of the second. Remember, we always include the median in the cut:

3 7

5 6

Obviously, the median will be the average of two values, but how to choose them? When the arrays get down to only two elements, we can choose the maximum of the left edges and the minimum of the right ones to compute the median (values in the middle if you arrange the elements like this: 3 5 6 7)

Thus the median is (5 + 6) / 2

The complexity of this algorithm is determined by the number of cutting points and since we are always splitting in half, it will look like a binary search with the known O(logn)

Below is the code:

/// /// Compute median of two sorted lists /// ///first list ///left index in the fist list ///right index in the first list ///second list ///left index in the second list ///right index in the second list /// median public static double GetMedianInLogN(List<int> first, int firstLeft, int firstRight, List<int> second, int secondLeft, int secondRight) { // the two lists will always have the same size int size = firstRight - firstLeft + 1; if (size == 1) { return ((double)first[firstLeft] + second[secondLeft])/2; } if (size == 2) { return ((double)Math.Max(first[firstLeft], second[secondLeft]) + Math.Min(first[firstRight], second[secondRight]))/2; } double medianFirst = GetMedianForArray(first, firstLeft, firstRight); double medianSecond = GetMedianForArray(second, secondLeft, secondRight); if (medianFirst == medianSecond) { return medianFirst; } // compare the medians of the two lists // take one half of the first list // and the other half of the second list for further processing int rightHalf; int leftHalf; int splitPoint = size % 2 == 0 ? size / 2 - 1 : size / 2; if (medianFirst > medianSecond) { leftHalf = firstLeft + size / 2; rightHalf = secondLeft + splitPoint; return GetMedianInLogN(first, firstLeft, leftHalf, second, rightHalf, secondRight); } leftHalf = secondLeft + size / 2; rightHalf = firstLeft + splitPoint; return GetMedianInLogN(first, rightHalf, firstRight, second, secondLeft, leftHalf); }

[45minutescoding]

Median for two sorted arrays of same size

Median is the middle value for a list of sorted numbers. If the list has an even number of elements in the list, median is computed as the average of the two middle values.

Median for a sorted array:

public static double GetMedianForArray(List<int> values, int left, int right) { int half = (right + 1 - left) / 2 + left; return (right + 1 - left) % 2 == 0 ? ((double)values[half] + values[half - 1]) / 2 : values[half]; }

Now how to get the median of two sorted lists?

Remember that both lists have the same size, so the median will be computed as an average of two values that would be placed in the middle of a virtually merged list, something like this (indexing starts at 0):

median = (list[n-1] + list[n]) / 2

This means that it's enough to do n comparisons between the elements of the two lists in order to get the median.

The code is below (the edge cases where all elements of a list are lower than the smallest element of the other list are included):

public static double GetMedianForTwoSortedArraysComplexityN(List<int> first, List<int> second) { int n = first.Count; if (n == 1) { return ((double)first[0] + second[0]) / 2; } // start merging elements and stop when you hit n // where n is the size of each array // index in the first array int i = 0; // index in the second array int j = 0; int pos = 0; // middle left for computing the average median int left = 0; // middle right for computing the average median int right = 0; while (pos <= n) { if (i == n) { // hit the end of the first list return ((double)first[n - 1] + second[0]) / 2; } if (j == n) { // hit the end of the second list return (double)(first[0] + second[n - 1]) / 2; } if (first[i] < second[j]) { left = right; right = first[i]; i++; } else if (first[i] > second[j]) { left = right; right = second[j]; j++; } pos++; } return ((double)left + right) / 2; }

Running a test:

1 3 5 6 8 9 2 4 7 10 11 12 Median: 6.50

Can we do better than O(n) for finding the median?

[45minutescoding]

Vertical view and horizontal distance in a binary tree

The horizontal distance is a metric for the binary trees that is computed in relation to the parent and the position of the node (left, right). 

Here is the formula:

0 for the root the left child has the distance of its parent -1 the right child has the distance of its parent +1

Between the two children of the same node, there is a horizontal distance of two. As the tree is expanded, the nodes may form vertical lines and in this case they will have the same horizontal distance. 

Using horizontal distance, it's possible to have a nice visual representation of the tree. We are able to measure the necessary width of the window that contains the tree as the absolute difference of max distance and min distance of all nodes.

Apparently, the implementation of the binary tree pictured below ignores this ingenuous trick.

I associated integer values to the nodes that transform it into a BST, but this is not important for the example. What's relevant is the value between the parenthesis which represents the horizontal distance. The root has 0, as we go down in the left subtree, the node with value 3 has the distance -1 (0-1), node with value 2 the distance -2 (-1-1) and so on.

If you put your imagination to work, you will be able to see vertical lines connecting nodes with the same horizontal distance. There's a special case I wanted to include in here, the nodes 5 and 7 have both horizontal distance 0 so they would overlap in a graphic representation.

The code for computing horizontal distances and the complete vertical view is below. The result is a sorted dictionary that stores the horizontal distance as key that points to a list of nodes with this distance .

/// Vertical view works with the concept of horizontal distance /// The horizontal distance is computed like this: /// 0 for the root /// the left child has the distance of its parent -1 /// the right child has the distance of its parent +1 /// nodes having the same horizontal distance form a line /// the vertical view means displaying the collection of those vertical lines /// public static SortedDictionary<int, List<T>> VerticalView(NodeTree root) { var distances = new SortedDictionary<int, List<T>>(); horizontalDistance(root, 0, distances); return distances; } private static void horizontalDistance(NodeTree<T> node, int distance, SortedDictionary<int, List<T>> distances) { if (node == null) { return; } updateHorizontalDistance(x => x - 1, distance, node.Left, distances); updateHorizontalDistance(x => x + 1, distance, node.Right, distances); } private static void updateHorizontalDistance(Func<int, int> horizontalDistanceComputer, int distance, NodeTree<T> node, SortedDictionary<int, List<T>> distances) { if (node != null) { int leftDistance = horizontalDistanceComputer(distance); List<T> values; if (!distances.TryGetValue(leftDistance, out values)) { values = new List(); distances[leftDistance] = values; } values.Add(node.Data); horizontalDistance(node, leftDistance, distances); } }

[45minutescoding]

Different length permutations

Given a string, print all possible permutations of different lengths in sorted order.

Input: abc Output: a ab abc ac b bc c

I generate permutations recursively by using the current element and adding it to all permutations computed with the rest of the elements (then adding the element alone, too, as required by the problem statement)

public static class PermutationsOfDifferentLength { /// /// return sorted list of permutations /// public static List Compute(string str) { var result = compute(str); result.Sort(); return result; } /// /// compute permutations recursively /// private static List compute(string str) { var result = new List(); if (string.IsNullOrWhiteSpace(str)) { return result; } string firstChar = str[0].ToString(); result.Add(firstChar); foreach (string substr in compute(str.Substring(1))) { result.Add(substr); result.Add(firstChar + substr); } return result; } }

[45minutescoding]

Inorder traversals

Everybody's favorite way of traversing a tree since it's so visual. Plus, it gets you the nodes sorted in a binary search tree.

If I see a tree picture, I can write down the inorder of nodes just by reading all of their projections from left to right. Very useful when testing BT algorithms.

Now for coding. The inorder recursion is obvious, but what if recursion should be avoided? Going back and forth in the tree suggests using the stack, so my solution will do just that. I keep pushing nodes to the stack while they have a left child and when I backtrack, I add the node to the result and continue on its right child.

With recursion:

public static List<T> Inorder(NodeTree<T> node) { if (node == null || Equals(node.Data, default(T))) { return null; } List<T> left = Inorder(node.Left) ?? new List(); left.Add(node.Data); List<T> right = Inorder(node.Right); return right != null ? left.Concat(right).ToList() : left; }

and with a stack:

public static List<T> InorderWithStack(NodeTree<T> node) { var result = new List<T>(); if (node == null) { return result; } var stack = new Stack<NodeTree<T>>(); stack.Push(node); // when backtracking, avoid reading the left child since it was processed bool finishedWithLeftChild = false; while (stack.Count > 0) { NodeTree<T> cur = stack.Peek(); if (!finishedWithLeftChild && cur.Left != null) { stack.Push(cur.Left); } else { result.Add(cur.Data); stack.Pop(); finishedWithLeftChild = true; if (cur.Right != null) { stack.Push(cur.Right); finishedWithLeftChild = false; } } } return result; }

[45minutescoding]

Kth last element in a list

Given a linked list, find the element that is k steps away from the end of the list.

In order to get to the end of the list and count the number of its elements, we will have to traverse the entire list. Then, for providing the result, restart from the head and stop after we get to the N-k element.

However, the second traversal can be avoided if we use a tentative pointer set initially at k steps away from the head. This way, we will advance at the same pace with both pointers and we will stop when the tentative one has hit the end. It's like you're in a dark room and you use the length of your arms to check for the walls in order to avoid banging your head against them.

Here's the code:

public static ListNode<T> FindLastKthElement<T>(ListNode head<T>, int k) { if (head == null || k < 0) { return head; } // advance a pointer k steps away from the current var temp = head; for (int i = 0; i < k; i++) { if (temp.Next == null) { // list doesn't have k + 1 elements return head; } temp = temp.Next; } // temp is now k steps ahead // when it will the end of the list, the current pointer will indicate the result var current = head; while (temp.Next != null) { current = current.Next; temp = temp.Next; } return current; }

[45minutescoding]

Distances in Binary Tree

Try imagining a binary tree with a decent set of nodes. How would you do to find all the nodes that are situated at a certain distance from the root? How would you do to find all the nodes that are at a certaing distance from the leaves?

Let's look at a tree picture that I took from geeksforgeeks.org:

If the root is the node having the value 60, there are two nodes at one step distance, 41 and 74. How many of them are at distance 3 then? In a manner similar to breadth first search, we can look at all the nodes on level 3 to find the answer.

In my code, I start searching from the root node and use recursion to go down on a node's left and right children. Whenever a node is at the required distance, I add it to the result.

public static List<NodeTree<T>> NodesAtDistanceK(NodeTree<T> node, int distance, int curDistance = 0) { var result = new List<NodeTree<T>>(); // not a valid node if (node == null) { return result; } if (distance == curDistance) { // found a node that qualifies return Enumerable.Repeat(node, 1).ToList(); } // check for the nodes in the left subtree List<NodeTree<T>> foundLeft = NodesAtDistanceK(node.Left, distance, curDistance + 1); if (foundLeft.Any()) { result = foundLeft; } //check the nodes on the right subtree List<NodeTree<T>> foundRight = NodesAtDistanceK(node.Right, distance, curDistance + 1); return foundRight.Any() ? (result.Any() ? result.Concat(foundRight).ToList() : foundRight) : result; }

For a distance of 3, the answer is: 25, 46, 55, 63, 70.

Now onto the second problem, searching all nodes that find themselves at a given distance from a leaf. Descending from our node to the leaves may be done using various paths, so the node may be closer to a leaf than to the others. The problem can be restated as: find all the nodes that have at least a leaf at given steps away.

In the code, at each step, I return an array of distances from the current node to all reachable leaves. The collection of all nodes that validate the distance is passed as a parameter and it can be augmented as we traverse the tree.

public static List<int> DistanceFromLeaves(NodeTree<T> currentNode, int distanceToHit, List<NodeTree<T>> result) { if (currentNode == null) { return Enumerable.Empty<int>().ToList(); } // check the left side List<int> distanceLeft = DistanceFromLeaves(currentNode.Left, distanceToHit, result); // check the right side List<int> distanceRight = DistanceFromLeaves(currentNode.Right, distanceToHit, result); if (!distanceLeft.Any() && !distanceRight.Any()) { // a leaf return Enumerable.Repeat(1, 1).ToList(); } // check all leaf distances, avoid duplicated distances List<int> distances = distanceLeft.Concat(distanceRight).Distinct().ToList(); if (distances.Any(x => x == distanceToHit)) { result.Add(currentNode); } // increment distances to take into account current step for (int i = 0; i < distances.Count; i++) { distances[i]++; } return distances; }

If we use the same binary tree depicted in the photo, the list of nodes at distance 3 from a leaf is: 41, 74, 60

[45minutescoding]

Reverse a linked list with step K

A while ago, we used to do a first screening on the candidates applying for a developer position in our team by using the reverse linked list problem.

Last week, I found a variation that looks a bit more interesting:

Given a link list and a step K, reverse the link list in K size slots

Example Input 12--> 13--> 3--> 20--> 55--> 87--> 20--> 77--> 90 For k =3 Output 3--> 13--> 12--> 87--> 55--> 20--> 90--> 77--> 20

When I reverse a linked list in one traversal, I switch the current element with its next neighbor and make the latter point to the former head.

To write it quickly (p is the current node):

while (p.Next) { Node q = p.Next; p.Next = q.Next; q.Next = head; head = q; }

This time, since we have to create cycles of length k, we should reverse each cycle and link its end node to the beginning of the next cycle. I'm using a currentCycleHead while reversing which, for the first cycle, represents the head.

public static ListNode<T> ReverseWithStepK<T>(ListNode<T> head, int k) { if (head == null || k <= 1) { return head; } // run the k-length cycle and reverse values ListNode<T> currentCycleHead = head; int cycleLength = 1; bool firstCycle = true; // link the end of the previous cycle to the current cycle head ListNode<T> previousCycleNode = null; // use p to switch two positions var p = head; while (p.Next != null) { if (cycleLength == k) { // start new cycle firstCycle = false; cycleLength = 1; // no need to reverse this node previousCycleNode = p; p = p.Next; //for the new cycle, the head is the current node currentCycleHead = p; previousCycleNode.Next = currentCycleHead; continue; } // advance one node var q = p.Next; p.Next = q.Next; // make the switch so that the node will go to the beginning q.Next = currentCycleHead; currentCycleHead = q; if (firstCycle) { head = currentCycleHead; } else { previousCycleNode.Next = currentCycleHead; } // one more element in the cycle cycleLength++; } return head; }

[45minutescoding]

Count the number of times digit 2 appears in all numbers less than N

I like this problem. It lets you think that you can solve it in no time, then you start choosing your examples and counting and it takes a little bit until you come up with the recursive formula.

if N=22, how many 2s are there to be found in all numbers less than N?

If you were to check each digit of each number less or equal to n, then the complexity would be O(nk), where k is the average number of digits.

This k has the complexity of decimal logarithm squared. The number of digits in a number is log10(n). Then each ~10^k numbers have the same k number of digits and so on.

So the idea is to reduce this complexity to log10(n) which means only looking at each digit once and feeding it into a formula.

It's easy to understand with an example. Suppose we have N=1425, then the result is computed like this:

count(1000) + count(400) + count(20) + count(5)

But how can we compute count(400)? Well, imagine you know the result for count(100), would it be easier? How about count(100)? Well, if only you could compute count(10).

We start processing the number starting from the lowest digit (at right) and then shifting to the left and using the previously computed values for each digit level.

Result: sum(nd[k]) nd[k] = base[k] * 10 + 10^k, if d < 2 nd[k] = base[k] * d + 1 + (n % (10^k)), if d == 2 nd[k] = base[k] * d + 10^k, if d > 2 base[k] = base[k] * 10 + 10^k base[0] = 0

If this is too abstract, take a look at the code:

public static int Count(int n) { if (n < 2) { return 0; } // change digit to generalize const int digitToCount = 2; int previousLevelCount = 0; int digitPosition = 0; int result = 0; int number = n; while (n > 0) { int currentDigit = n % 10; int currentLevelMax = previousLevelCount * 10 + (int) Math.Pow(10, digitPosition); previousLevelCount = previousLevelCount * currentDigit; if (currentDigit == digitToCount) { previousLevelCount += 1 + number % ((int)Math.Pow(10, digitPosition)); } else if (currentDigit > digitToCount) { previousLevelCount += (int)Math.Pow(10, digitPosition); } result += previousLevelCount; previousLevelCount = currentLevelMax; digitPosition++; n /= 10; } return result; }

And the next time somebody asks you how many digits 2 are in all numbers less than 100.000, you can whisper the result: 50k

[45minutescoding]

10 posts!

[45minutescoding]

The Next Greater Element (NGE)

Saw this problem today and I remember solving it a while ago:

Given a array of number find the next greater number to the right of each element

Input 12 15 22 09 07 02 18 23 27 Output 15 22 27 18 18 18 23 27 -1

The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exists, will consider next greater element to be -1.

What you need to do here is to avoid the O(n^2) complexity, where for each element you will have to traverse the list to identify the first bigger value.

If you try to think you can do it the other way around, starting from the last element and checking back to the first position, you will be soon trapped since you will have to compare multiple elements and keep references to changing order of sequences.

public static List<Tuple<int, int>> ComputeNge(IEnumerable<int> values) { var result = new List<Tuple<int, int>>(); var stack = new Stack(); foreach (var value in values) { if (stack.Count == 0) { stack.Push(value); continue; } int current = stack.Peek(); // keep on popping until we find a bigger number in the stack while (current < value) { stack.Pop(); result.Add(new Tuple<int, int>(current, value)); if (stack.Count > 0) { current = stack.Peek(); } else { break; } } stack.Push(value); } // for all remaining numbers in the stack, the next bigger number is -1 while (stack.Count > 0) { int current = stack.Pop(); result.Add(new Tuple<int, int>(current, -1)); } return result; }

I return a list of pairs containing the initial element and its NGE. The order of elements is not the original one, since they are added to the result list depending on the moment when they are popped from the stack. Using an additional info field for the index, the result list can be reordered.

Running random list of numbers:

24 72 42 48 64 74 16 35 36 4 24 < 72 42 < 48 48 < 64 64 < 74 72 < 74 16 < 35 35 < 36 4 < -1 36 < -1 74 < -1

[45minutescoding]

Generate all possible strings by replacing ? with 0 and 1

Found this problem today:

Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1. Example: Input : a?b?c? Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

Seems to be a good candidate for coding fast since it's not complicated at all. Plus, the fact that they say replace with 0 or 1 already gives you the hint that you may use some binary tricks.

How many solutions will there be? Which can be translated into how many ways to combine the 0s and the 1s. Well, depends on how many positions you have to fill.

Suppose there are 3 question marks as in the problem example. Then the last solution will have 1 replacing ? on every position. That spells 111.

I isolate all the question marks, I form a binary representation which, on its max value, gives the number of solutions for this problem. In our example case, that is 8.

You will see below how I coded the algorithm using a data structure to store the words in the text delimited by "?" . This means space complexity, but saves time when you reconstruct the solution. If you don't like storing text, use a substr call when you build a solution.

The time complexity is dependent on the number of solutions to be built. Suppose you have m questions marks in the text of length N, then the total solutions is 2^m equivalent to the number of times you have to walk the text to do the the replacements. If you glue the words with the new delimiters, you won't have to parse the text again.

To recap. the complexity is O(m*2^m) and when m is close to logN, it becomes O(n*logN).

As a note, the code works even if you have multiple questions marks on adjacent positions.

const string text = "danser?un?slow?avec?toi?"; QuestionMarkIntoBinary.Replace(text).ForEach(Console.WriteLine);

public static List Replace(string text) { var result = new List(); if (string.IsNullOrWhiteSpace(text)) { return result; } // isolate the string parts string[] parts = text.Split(new[] { '?' }); // need at least a question mark in order to build a solution // otherwise the only solution is the original text if (parts.Length < 2) { result.Add(text); return result; } // we have to generate the following series of values: // starting from 00000...0 // up to 11111...1 for (int i = 0; i < Math.Pow(2, parts.Length - 1); i++) { // get the string binary representation string bits = Convert.ToString(i, 2); // add the built solution result.Add(buildSolution(parts, bits)); } return result; } /// /// built solution using string parts /// and generated separators /// private static string buildSolution(string[] parts, string bits) { var builder = new StringBuilder(); int offset = parts.Length - 1 - bits.Length; // pad with initial 0 if needed since the binary representation // may have only a limited positions for the low value numbers for (int i = 0; i < offset; i++) { builder.Append(parts[i]); builder.Append("0"); } // alternate string with bit value for (int i = offset; i < parts.Length - 1; i++) { builder.Append(parts[i]); builder.Append(bits[i - offset]); } // don't forget the last part builder.Append(parts[parts.Length - 1]); return builder.ToString(); }

Here is an example:

const string text = "danser?un?slow?avec?toi?"; QuestionMarkIntoBinary.Replace(text).ForEach(Console.WriteLine); danser0un0slow0avec0toi0 danser0un0slow0avec0toi1 danser0un0slow0avec1toi0 danser0un0slow0avec1toi1 danser0un0slow1avec0toi0 danser0un0slow1avec0toi1 danser0un0slow1avec1toi0 danser0un0slow1avec1toi1 danser0un1slow0avec0toi0 danser0un1slow0avec0toi1 danser0un1slow0avec1toi0 danser0un1slow0avec1toi1 danser0un1slow1avec0toi0 danser0un1slow1avec0toi1 danser0un1slow1avec1toi0 danser0un1slow1avec1toi1 danser1un0slow0avec0toi0 danser1un0slow0avec0toi1 danser1un0slow0avec1toi0 danser1un0slow0avec1toi1 danser1un0slow1avec0toi0 danser1un0slow1avec0toi1 danser1un0slow1avec1toi0 danser1un0slow1avec1toi1 danser1un1slow0avec0toi0 danser1un1slow0avec0toi1 danser1un1slow0avec1toi0 danser1un1slow0avec1toi1 danser1un1slow1avec0toi0 danser1un1slow1avec0toi1 danser1un1slow1avec1toi0 danser1un1slow1avec1toi1

[45minutescoding]

Parentheses, brackets and braces

For today, the fast to code problem of matching brackets.

Imagine a text, like a source code resource, where every open parentheses creates a scope. The open parentheses of every scope should be matched by a closing one that ends the scope. A scope may have inner scopes that satisfy the same rules.

Let's take an example of a valid string: { { [ () () ] } }

In order to determine the validity of a text, we will use a stack since the closing order of parentheses is the reversed of openining them.

At each step, we check if the character in the text is a parentheses. If it's an open one, just add it to the stack. If it's a closing one, check if what tops the stack is the matching opening one. If so, remove it from the stack and go on.

public static bool CheckBraces(string text) { if (string.IsNullOrEmpty(text)) { return true; } var stack = new Stack(); var dictionary = new Dictionary<char, char> { { ']', '[' }, { '}', '{' }, { ')', '(' } }; var opening = dictionary.Values; var closing = dictionary.Keys; foreach (char c in text) { if (opening.Contains(c)) { stack.Push(c); } else if (closing.Contains(c)) { if (stack.Count == 0) { return false; } char lastBrace = stack.Pop(); if (lastBrace != dictionary[c]) { return false; } } } return stack.Count == 0; }

A nice exercise would be to imagine how to apply this algorithm to a very large text where space complexity is vital (an online stream of data, for example). Time complexity is at least O(n) since we have to see each element. A first step could be to regroup the same type of parentheses that come in a series, eg: "{{{..." can be stored as "{3..."