You are provided a string with only digits [0 - 9], your task is to count the number of subsequences of string divisible by 6. For e.g. The given string is 1234566 The subsequences divisible by 6 are 12, 24, 36, 6, 6, 66 Hence the answer should be 6 The most obvious approach which comes is to generate all the subsequences and do a divisibility check and return the count satisfying the condition. But it is too expensive and overall complexity is 2^n (where n is the size of the string) Can we make it better?
14

Given a dictionary, on which the below operations are required  1. Update the dictionary 2. Find a word in a dictionary. What are the possible options? One of the most intuitive approach is to store the strings in a sorted manner. Lets have a look at the complexity of the operations

Given a string you are provided with the possible operations. We can group the adjacent substrings, for e.g ABCABCBC can be compressed as 2ABC1BC or 1ABCA2BC Among all the possible options, task is to find the resultant string with the minimum length. In case if there are multiple solutions return the lexicographically smallest string. So for the above example the solution would be 2ABC1BC Another example would be FLFLAFLAFLAF Solution: 1FLF3LAF

A sorted array is rotated around a pivot element. Find the pivot element in the rotated sorted array. Analysis Lets start with an example Original array:           2, 4, 6, 8, 9, 10, 12, 15 Rotated array:           10, 12, 15, 2, 4, 6, 8, 9 Output:                      3

Given a string, inplace remove the duplicate elements form the string.

For e.g. the given string is "codersstop is  a programming blog"

Result: "coderstp iagmnbl"

Approach:

Maintain a lookup table of the 256 entries to mark the occurrence of each of the characters, and only copy the elements which are occurring for the first time.

Given a binary tree(not BST) and two nodes in the tree(not necessarily leaf nodes), find the minimum distance between them. Approach: The minimum distance can be computed by first finding the LCA of the two nodes, and then finding the heights of the all the three nodes(2 nodes + 1 LCA) from the root.  (For finding the LCA in the binary tree refer to the previous post and finding the height of the element in the binary tree is self explanatory.)

Given a binary tree(not a binary search tree) find the LCA of the 2 given nodes. The lowest common ancestor(LCA) for the nodes u and v is defined as the lowest node w in tree  that has both u and v as the descendants (where a node can be a descendant of itself). Approach: Lets consider the below tree LCA of node 30, 5 is 100 LCA of node 15, 50 is 50 and so on

Coin change has been a very famous computing problem which can be easily solved by Dynamic programming. So what is coin change ? If we want to make change for N cents, and we have infinite supply of each of valued coins, how many ways can we make the change? (The order does not matter.) For example, for N = 4,S = {1,2,3}, there are 7 possible solutions: {1,1,1,1},{1,1,2}, {1, 2, 1}, {2, 1, 1}, {2,2},{1,3}, {3, 1}. So how to compute the number of ways efficiently?
2

Find the maximum area of a rectangle that fits entirely in the Histogram. For e.g in the below histogram the maximum area of the rectangle is 2 * 80  = 160 The length of each bar will be the input, and the width of each bar is same, 1 Approach: The naive approach can be to select one histogram at a time, find the maximum area which can be formed with this, finally return the maximum value over all the histogram. Time Complexity O(n^2), Space Complexity O(1) Can we do better. Lets have a look if we are computing some of the results over and over or if any of the computations are unnecessary.
1

Given that an array consists of only 0s 1s and 2s sort the array in one pass. Approach:  Lets view the problem if the constraint of one pass wouldn't have been there Scan over the array and count the number of 0, 1, and 2. Now initialise the array with the 0, 1, 2 with the number of elements, the idea is similar to the counting sort. To solve the above problem in one pass we can use the famous Dutch national flag algorithm. The basic idea is to traverse over the array and keep track of the current 0s and 2s and the read pointers(initialised with -1, n and 0). Now traverse the array and keep swapping the current element in the respective buckets of interest.
Contributors
Contributors
Blog Archive
Blog Archive
Labels
Labels
Subscribe
Subscribe
Total Pageviews
Total Pageviews
1 3 3 2 6 8
Popular Posts
Popular Posts
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.