Api design .. remember these things

by Deepak Dhakal 27. January 2020 17:06

API Design

 Statelessness – There’s one place you don’t want your API to be storing state, and that’s in your application servers. Always keep application servers state-free so that they can be easily and painlessly scaled.

Content Negotiation – If you want to support multiple representations of your resources, you can use content negotiation (eg. Accept headers), or differing URLs for different representations (eg. …?format=json), or you can combine both and have your content negotiation resources redirect to specific formats.

 URI Templates – URI Templates are a well-defined mechanism for providing URL composition capabilities to your clients, or for documenting your URL access patterns to your end-user.

Design for Intent – Don’t just expose your internal business objects through your API. Design your API to have semantic meaning and to match the use-cases that your users will have. Darrel Miller wrote a great post on API Craft describing this better than I could. (Edit: I tried my best in an article entitled Stop Designing Fragile Web APIs.)

 Versioning – Theoretically, if you designed a really great API up front, you might never need to create incompatibilities in your API. For the pragmatists in us, put versioning in your API URLs (eg. a /v1/ path), so that you have a safety net in case the API doesn’t work out like you wanted. (Edit: An expanded justification is my follow-up article: Ain’t Nobody Got Time For That: API Versioning)

 Authorization – Remember when designing your API that not all users will have access to all objects in the system. It’s great if you use or build an API framework with some form of declarative security so that it’s easy to assign and modify authorization rights on read and write access to resources.

 Bulk Operations – Most clients will perform better if they can issue fewer requests to fetch or modify more data. It’s a good idea to build bulk operations into your API to support this kind of use case.

 Pagination – Pagination serves two big purposes in an API; it reduces the amount of unneeded data delivered to the client, and it reduces the amount of unneeded computation on your application servers. There are many different patterns used for making paginated collection resources; if you don’t know where to start, browse through Stackoverflow for some hints. If you want to be my personal hero, implement consistent pagination by providing links to additional pages that are timestamped or versioned, such that you will never see duplicate results in pagination requests even if the objects involved change.

 Unicode – It’s pretty obvious these days that you need to support more than English characters in a web service; just remember to keep this in mind when designing and testing your API. In particular, Unicode characters can be interesting if you use them as natural keys in a URL (eg. /users/jimbob/ becomes /users/싸이/).

 Error Logging – Be sure you design how you want your API to perform error logging, rather than just throwing it together. In particular, I find it extremely valuable to distinguish between errors that are caused by the client’s input, and errors that are caused by your software. Keep these in two separate logs.



Broaden your knowledge with this well known company's blog

by Deepak Dhakal 11. August 2019 01:04

Tags: ,


Consistent Hashing : Save Your Weekends

by Deepak Dhakal 10. August 2019 06:01

Consistent Hashing

Consistent hashing is one of the techniques used to bake in scalability into the storage architecture of your system from grounds up.

In a distributed system, consistent hashing helps in solving the following scenarios:

  1. To provide elastic scaling (a term used to describe dynamic adding/removing of servers based on usage load) for cache servers.
  2. Scale out a set of storage nodes like NoSQL databases.

It is a very useful concept that frequently comes up in System Design Interviews. You might need to apply the concept while designing the backend of a system to alleviate bottlenecks . You could also be directly asked to design and implement  a consistent hashing algorithm. In this article, we'll look at:

Why do we need Consistent Hashing ?

Imagine that you want to create a scalable database backend with "n" database servers for your web application as depicted by the diagram below. For our simple example, we'll assume that we're just storing a key:value pair like "Country:Canada"in the DBs.

Figure 1: A distributed system with a cluster of database servers

Our goal is to design a database storage system such that:

  1. We should be able to distribute the incoming queries uniformly among the set of "n" database servers
  2. We should be able to dynamically add or remove a database server
  3. When we add/remove a database server, we need to move the minimal amount of data between the servers

So essentially we need to send each piece of incoming query to a  specific server. A simple approach is as follows:

  1. Generate a hash of the key from the incoming data :  hashValue = HashFunction(Key)"
  2. Figure out the server to send the data to by taking the modulo ("%") of the hashValue using the number of current db servers, n : "serverIndex = hashValue % n"

Let's walk through a simple example.

  • Imagine we have 4 database servers
  • Imagine our hashFunction returns a value from 0 to 7
  • We'll assume that "key0" when passed through our hashFunction, generates a hashvalue or 0, "key1" generates 1 and so on.
  • The serverIndex for "key0" is 0, "key1" is 1 and so on.

The situation assuming that the key data is unfirmly distributed, is depicted in the image below. We receive 8 pieces of data and our hashing algorithm distributes it evenly across our four database servers.

Figure 2: Sharding/ Distributing data across several database servers

Problem solved, right ?  Not quite – there's two major drawbacks with this approach, namely, Horizontal Scalability and Non-Uniform data distribution across servers.

Horizontal Scalability

This scheme is not horizontally scalable. If we add or remove servers from the set, all our existing mappings are broken. This is because the value of "n" in our function that calculates the serverIndex changes. The result is that all existing data needs to be remapped and migrated to different servers. This might be a herculean task because it'll either require a scheduled system downtime to update mappings or creating read replicas of the existing system which can service queries during the migration. In other words, a lot of pain and expenditure.

Here's a quick illustration of what happens when we add another server (server 5)  to the mix. Please refer back to figure 1 for the original key distribution. Notice that we'll need to update 3 out of the original 4 servers – i.e. 75% of servers needs to be updated!

Figure 3: Effect of adding a database server to the cluster

The effect is more drastic when a server goes down as depicted below. In this case, we'll need to update ALL servers, i.e.,100% of servers needs to be updated !

Figure 4: Effect of removing a server from the database cluster

Data Distribution – Avoiding  "Data Hot Spots" in Cluster

We cannot expect uniform distribution of data coming in all the time. There may be many more keys whose hashValue maps to server number 3 than any other servers , in which case server number 3 will become a hotspot for queries.

Consistent hashing allows up to solve both these problems. Read on to find out how !

How does Consistent Hashing Work ?

Consistent hashing facilitates the distribution of data across a set of nodes in such a way that minimizes the re-mapping/ reorganization of data when nodes are added or removed. Here's how it works:

1. Creating the Hash Key Space: Consider we have a hash function that generates integer hash values in the range [0,  2^32-1)

We can represent this as an array of integers with 2^32 -1 slots. We'll call the first slot x0 and the last slot xn – 1

Figure 5: A Hash Key Space 

2. Representing the hashSpace as a Ring: Imagine that these integers generated in step # 2 is placed on a ring such that the last value wraps around.

Figure 6: Visualizing the hash key space as a Ring

3. Placing DB Servers in Key Space (HashRing): We're given a list of database servers to start with. Using the hash function, we map each db server to a specific place on the ring. For example, if we have 4 servers, we can use a hash of their IP addressed to map them to different integers using the hash function. This simulates placing the four servers into a different place on the ring as shown below.

Figure 7: Placing database servers on a hash ring

  1. Determining Placement of Keys on Servers: To find which database server an incoming key resides on (either to insert it or query for it ), we do the following:
  • Run the key through the same hash function we used to determine db server placement on the ring.
  • After hashing the key, we'll get an integer value which will be contained in the hash space, i.e., it can be mapped to some postion in the hash ring. There can be two cases:
  1. The hash value maps to a place on the ring which does not have a db server. In this case, we travel clockwise on the ring from the point where the key mapped to untill we find the first db server. Once we find the first db server travelling clockwise on the ring, we insert the key there. The same logic would apply while trying to find a key in the ring.
  2. The hash value of the key maps directly onto the same hash vale of a db server – in which case we place it on that server.

Example: Assume we have 4 incoming keys : key0, key1, key2, key3 and none of them directly maps to the hash value of any of the 4 servers on our hash ring. So we travel clockwise from the point these keys maps to in our ring till we find the first db server and insert the key there. This is depicted in Figure 7 below.

Figure 8: Key placements on database servers in a hash ring

5. Adding a server to the Ring: If we add another server to the hash Ring, server 4, we'll need to remap the keys. However, ONLY the keys that reside between server 3 and server 0 needs to be remapped to server 4. On an average , we'll need to remap only k/n keys , where k is the number of keys and n is the number of servers. This is in sharp contrast to our modulo based placement approach where we needed to remap nearly all the keys.

The figure below shows the effect of inserting a new server4 – since server 4 now resides between key0 and server0, key0 will be remapped from server0 to server4.

Figure 9: Effect of adding a server to the hash ring

6. Removing a server from the ring: A server might go down in production and our consistent hashing scheme ensures that it has minimal effect on the number of keys and servers affected.

As we can see in the figure below, if server0 goes down, only the keys in between server3 and server 0 will need to be remapped to server 1( the area is circled in yellow). The rest of the keys are unaffected .

Figure 10: Effect of removing a server from the hash ring

At this point, consistent hashing has  successfully solved the horizontal scalability problem by ensuring that every time we scale up or down, we DO NOT have to re-arrange all the keys or touch all the database servers !

But what about the distribution of data across the various database servers? We can run into a situation where our server distribution across the hash ring is non uniform , i.e., the size of partitions each server is responsible for is not the same. But you might ask how will that happen ? Well, imagine that we started off with 3 servers (server0, server1, server2) that were more or less evenly distributed across the ring. If one of the servers fail, then the load seen by the server immediately following the failed server will be higher. This is assuming all the data that comes in has a uniform key distribution. In reality , the issue is more complicated because data does not have uniform distribution in most cases. So these two things coupled together can lead to a situation like the one shown below. Here, server0 is seeing a very high load because :

  1. Data was non-uniformly distributed to start with – so server2 was having a lot of hot spots
  2. Server2 eventually fails and had to be removed from the hash ring. (note that server 0 now gets all of server2's keys)

Figure 11: Keys can be non-uniformly distributed across servers in a hash ring

So how do we solve this ?

It turns out that there is a pretty standard solution to the problem. It involves the introduction of a number of replicas or virtual nodes for each server across the ring. For example,

Server 0 might have two replicas placed at different points across the ring.

Figure 12: Using Virtual Nodes to assign increase the key space covered by each server

But how does using replicas make the key distribution more uniform ? Here's a visual example – Figure 13 shows the key distribution with two serevers in the hash ring WITHOUT replicas. We can observe that server 0 is handling 100% of the keys.

Figure 13: Non-uniform key distribution in absence of replication of nodes in a hash ring

If we introduce one more replica of each server on the ring , then the key distribution looks like the one in figure 14. Now server0 is responsible for 50% ( 2 out of 4) keys and server 1 is responsible for the other 50% of the keys.

Figure 14: Using virtual nodes/ replication to create better key distribution in a hash ring

As the number of replicas or virtual nodes in the hash ring increase, the key distribution becomes more and more uniform. In real systems, the number of virtual nodes / replicas is very large (>100) .

At this point, Consistent Hashing has successfully solved the problem of non-uniform data distribution (hot spots) across our database server cluster.

Key things to remember about Consistent Hashing for System Design Interviews


  1. You have a cluster of databases and you need to elastically scale them up or down based on traffic load. For example, add more servers during Christmas to handle the the extra traffic.
  2. You have a set of cache servers that need to elastically scale up or down based on traffic load.


  1. Enables Elastic Scaling of cluster of database/cache servers
  2. Facilitates Replication and partitioning of data across servers
  3. Partitioning of data enables uniform distribution which relieves hot spots
  4. Points a-c enables higher availability of the system as a whole.

Implementation Consistent Hashing

Please note that this is for purely illustrative purposes only. There are no guarantees for robustness or stability if used in production code.

There are three key pieces we need to implement:

  1. A Hash table like data structure which can simulate the key space or the hash Ring. In our case, we'll use a SortedDictionary in C#
  2. A hash function that can generate a integer value for the servers ip address and incoming keys we need to map to the hash ring
  3. The server object themselves.

First we define a server class which basically encapsulates an ip address and represent a physical server.

  1. using System.Collections.Generic;
  2. using System.Linq;
  3. using System.Text;
  4. using System.Threading.Tasks;
  5. namespace ConsistentHashing
  6. {
  7. class Server
  8. {
  9. public String ipAddress;
  10. public Server(String ipAddress)
  11. {
  12. this.ipAddress = ipAddress;
  13. }
  14. }
  15. }

Next we define the hash function which will return an integer value for server ips and the keys.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. /*
  7. * This code is taken from the stackoverflow article:
  8. * https://stackoverflow.com/questions/12272296/32-bit-fast-uniform-hash-function-use-md5-sha1-and-cut-off-4-bytes
  9. */
  10. namespace ConsistentHashing
  11. {
  12. public static class FNVHash
  13. {
  14. public static uint To32BitFnv1aHash(string toHash, bool separateUpperByte = false)
  15. {
  16. IEnumerable<byte> bytesToHash;
  17. if (separateUpperByte)
  18. bytesToHash = toHash.ToCharArray()
  19. .Select(c => new[] { (byte)((c - (byte)c) >> 8), (byte)c })
  20. .SelectMany(c => c);
  21. else
  22. bytesToHash = toHash.ToCharArray()
  23. .Select(Convert.ToByte);
  24. //this is the actual hash function; very simple
  25. uint hash = FnvConstants.FnvOffset32;
  26. foreach (var chunk in bytesToHash)
  27. {
  28. hash ^= chunk;
  29. hash *= FnvConstants.FnvPrime32;
  30. }
  31. return hash;
  32. }
  33. }
  34. public static class FnvConstants
  35. {
  36. public static readonly uint FnvPrime32 = 16777619;
  37. public static readonly ulong FnvPrime64 = 1099511628211;
  38. public static readonly uint FnvOffset32 = 2166136261;
  39. public static readonly ulong FnvOffset64 = 14695981039346656037;
  40. }
  41. }

Finally, we define the consistent hash class which enacpsulates the logic for :

  1. Creating the hash ring
  2. Adding a server to the hash ring
  3. Removing a server from the hash ring
  4. Getting the location of the server on the hash ring where a key needs to be added / retrieved from.
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace ConsistentHashing
  7. {
  8. class ConsistentHash
  9. {
  10. private SortedDictionary<uint, Server> hashRing;
  11. private int numberOfReplicas; // The number of virtual nodes
  12. public ConsistentHash(int numberOfReplicas, List<Server> servers)
  13. {
  14. this.numberOfReplicas = numberOfReplicas;
  15. hashRing = new SortedDictionary<uint, Server>();
  16. if(servers != null)
  17. foreach(Server s in servers)
  18. {
  19. this.addServerToHashRing(s);
  20. }
  21. }
  22. public void addServerToHashRing(Server server)
  23. {
  24. for(int i=0; i < numberOfReplicas; i++)
  25. {
  26. //Fuse the server ip with the replica number
  27. string serverIdentity = String.Concat(server.ipAddress, ":", i);
  28. //Get the hash key of the server
  29. uint hashKey = FNVHash.To32BitFnv1aHash(serverIdentity);
  30. //Insert the server at the hashkey in the Sorted Dictionary
  31. this.hashRing.Add(hashKey, server);
  32. }
  33. }
  34. public void removeServerFromHashRing(Server server)
  35. {
  36. for (int i = 0; i < numberOfReplicas; i++)
  37. {
  38. //Fuse the server ip with the replica number
  39. string serverIdentity = String.Concat(server.ipAddress, ":", i);
  40. //Get the hash key of the server
  41. uint hashKey = FNVHash.To32BitFnv1aHash(serverIdentity);
  42. //Insert the server at the hashkey in the Sorted Dictionary
  43. this.hashRing.Remove(hashKey);
  44. }
  45. }
  46. // Get the Physical server where a key is mapped to
  47. public Server GetServerForKey(String key)
  48. {
  49. Server serverHoldingKey;
  50. if(this.hashRing.Count==0)
  51. {
  52. return null;
  53. }
  54. // Get the hash for the key
  55. uint hashKey = FNVHash.To32BitFnv1aHash(key);
  56. if(this.hashRing.ContainsKey(hashKey))
  57. {
  58. serverHoldingKey = this.hashRing[hashKey];
  59. }
  60. else
  61. {
  62. uint[] sortedKeys = this.hashRing.Keys.ToArray();
  63. //Find the first server key greater than the hashkey
  64. uint firstServerKey = sortedKeys.FirstOrDefault(x => x >= hashKey);
  65. // Get the Server at that Hashkey
  66. serverHoldingKey = this.hashRing[firstServerKey];
  67. }
  68. return serverHoldingKey;
  69. }
  70. }
  71. }

Finally, here's a test program which exercises the functionality of the above code.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. using System.Security.Cryptography;
  7. namespace ConsistentHashing
  8. {
  9. class Program
  10. {
  11. static void Main(string[] args)
  12. {
  13. List<Server> rackServers = new List<Server>();
  14. rackServers.Add(new Server(""));
  15. rackServers.Add(new Server(""));
  16. int numberOfReplicas = 1;
  17. ConsistentHash serverDistributor = new ConsistentHash(numberOfReplicas, rackServers);
  18. //add a new server to the mix
  19. Server newServer = new Server("");
  20. serverDistributor.addServerToHashRing(newServer);
  21. //Assume you have a key "key0"
  22. Server serverForKey = serverDistributor.GetServerForKey("key0");
  23. Console.WriteLine("Server: " + serverForKey.ipAddress + " holds key: Key0");
  24. // Now remove a server
  25. serverDistributor.removeServerFromHashRing(newServer);
  26. // Now check on which server "key0" landed up
  27. serverForKey = serverDistributor.GetServerForKey("key0");
  28. Console.WriteLine("Server: " + serverForKey.ipAddress + " holds key: Key0");
  29. }
  30. }
  31. }


  1. Server: holds key: Key0
  2. Server: holds key: Key0

Consistent Hashing in Action in Production Systems

There are a number of live systems which use consistent hashing including:

Further Reading On Consistent Hashing

1. Tom White's article on Consistent Hashing is the one i used to initially learn about this technique. The C# implementation in this article is loosely based on his java implementation.

2. Tim Berglund's Distributed System in One Lesson is a fantastic resource to learn about read replication, sharding and consistent hashing. Unfortunately, you'll need a safari membership for this.

3. David Karger and Eric Lehman's original paper on Consistent Hashing

4. David Karger and Alex Sherman's paper on Web Caching with Consistent Hashing

If you have any feedback, please add it to the comment section below. And if you enjoyed the article, please share it on your favorite social media platform 🙂

Tags: ,


Useful software engineering stuff

by Deepak Dhakal 9. August 2019 23:37













https://m.stopa.io/10-offers-100-days-the-journey-16a0407b8d95 interview https://habr.com/ru/post/454264/ . Inteview

https://habr.com/ru/post/455260/ Merkel’s tree



https://www.solutionfactory.in/posts/Floyd-Cycle-Detection-Algorithm-in-Java Cycle detection






https://cses.fi/book/ . Competitive programming book

https://www.amazon.com/dp/1793296634 Algo Book



http://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf Algo book


https://www.youtube.com/watch?v=9clnwaqOU2E string algo



https://habr.com/ru/post/442352/ Бинарные деревья поиска

https://www.youtube.com/watch?v=lpO_arK69vg LCA

https://habr.com/ru/post/438512/ алгоритм Хаффмана






https://habr.com/ru/post/112222/ heap

https://habr.com/ru/post/437702/ Разбор задачи с собеседования в Google: синонимичные запросы



https://algoexpert.io/rachit Use “rachit” as coupon code to get 30% off


https://www.youtube.com/watch?v=TeZqKnC2gvA Visitor design pattern









disjoint set union (DSU) или Union-Find. https://habr.com/ru/post/104772/ создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя. Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).

Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

http://iolivia.me/posts/4-bloom-filter-part-3/ Bloom filter



https://www.youtube.com/playlist?list=PLMCXHnjXnTnvo6alSjVkgxV-VH6EPyvoX . system design questions

https://www.youtube.com/watch?v=bBPHpH8aKjw look fo links here!

https://blog.sqreen.io/demystifying-radix-trees/ . Radix tree https://news.ycombinator.com/item?id=18921058 . Radix trees


http://www.interviewdruid.com/ https://github.com/parineeth/tbboci-3rd-edition-python https://www.amazon.com/dp/1983861189





https://habr.com/ru/post/457042/ . Tree traversal using 2 threads (Java)


https://en.wikipedia.org/wiki/Lowest_common_ancestor https://sites.google.com/site/mytechnicalcollection/algorithms/trees/lca-of-binary-tree https://stackoverflow.com/questions/1484473/how-to-find-the-lowest-common-ancestor-of-two-nodes-in-any-binary-tree



















https://www.youtube.com/watch?v=1CxyVdA_654 Running mediam in stream

https://www.youtube.com/watch?v=IHsX70r-fIQ Max sub-sequence in string






https://news.ycombinator.com/item?id=18236396 . Favorite algos




http://csc.kth.se/~jsannemo/slask/main.pdf Book

https://cses.fi/book.pdf Book






<http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/ https://medium.com/engineering-brainly/locality-sensitive-hashing-explained-304eb39291e4 Local sensitive hash https://sagi.io/2017/07/bloom-filters-for-the-perplexed/https://news.ycombinator.com/item?id=15346337 https://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms/3260905#3260905

http://yucoding.blogspot.com/2017/01/leetcode-question-range-sum-query.html http://massivealgorithms.blogspot.com/http://ruslanledesma.com/ http://algorithms.tutorialhorizon.com/

https://www.youtube.com/watch?v=GiCWlXEhht8 https://www.youtube.com/watch?v=il_t1WVLNxk https://www.youtube.com/watch?v=e5D3NepYvLE https://www.youtube.com/watch?v=eaYX0Ee0Kcg https://www.youtube.com/watch?v=zGv3hOORxh0

http://quiz.geeksforgeeks.org/amazons-most-frequently-asked-interview-questions-set-2/ https://www.geeksforgeeks.org/amazons-asked-interview-questions/

https://www.youtube.com/watch?v=eaYX0Ee0Kcg https://www.udemy.com/11-essential-coding-interview-questions/?couponCode=AMAZON2

Google interview







https://habr.com/post/419725/ Non-symmetric dime simulation


https://saru.science/tech/2017/01/18/judy-arrays.html Judy array







Egg drop



Find 1st element in rotated sorted array

def bs(lst, start, end):
   print ("start=",start, "end=", end)
   if start == end:  return start
   m = (start+end)//2
   print ("middle=",m, lst[m])

   if m < end and lst[m+1] < lst[m]:
      return m+1
   if m > start and lst[m] < lst[m-1]:
      return m

   if lst[end] > lst[m]:
      return bs(lst, start, m -1)
      return  bs(lst, m+1, end)

def find(l):
  i= bs(l, start, end)
  return i

if __name__ =="__main__":
  print ("main")
  l1=[5,10,20, 1,2,3,4]
  print ("index=",i)

  l2=[20, 1,2,3,4]
  print ("index=",i)

Hash function and hashtable









Consistent Hashing


https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8 Consistent hashing


Locality sensitive hashing



https://dev.to/s_awdesh duplicates in array, dual pivot sort

Dynamic programming











Dynamic Programming- Python implementation of Min Cost Path on grid problem

def minCost(cost, m, n):

# Instead of following line, we can use int tc[m+1][n+1] or 
# dynamically allocate memoery to save space. The following 
# line is used to keep te program simple and make it working 
# on all compilers. 
R = 3
C = 3
tc = [[0 for x in range(C)] for x in range(R)] 
tc[0][0] = cost[0][0] 
# Initialize first column of total cost(tc) array 
for i in range(1, m+1): 
    tc[i][0] = tc[i-1][0] + cost[i][0] 
# Initialize first row of tc array 
for j in range(1, n+1): 
    tc[0][j] = tc[0][j-1] + cost[0][j] 
# Construct rest of the tc array 
for i in range(1, m+1): 
    for j in range(1, n+1): 
        tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j] 
return tc[m][n] 

Driver program to test above functions

cost = [[1, 2, 3], 
        [4, 8, 2], 
        [1, 5, 3]] 
print(minCost(cost, 2, 2)) 

Count number of ways to reach mat[m-1][n-1] from mat[0][0] in a matrix mat[][]

Returns The number of way from top-left to mat[m-1][n-1]

def countPaths(m, n):

dp = [[0 for i in range(m + 1)]  
         for j in range(n + 1)] 
for i in range(1, m + 1): 
    for j in range(1, n + 1): 
        if (i == 1 or j == 1): 
            dp[i][j] = 1
            dp[i][j] = (dp[i - 1][j] + 
                        dp[i][j - 1])              
return dp[m][n] 

Driver code

if name ==”main”:

n = 5
m = 5
print(countPaths(n, m)) 






Regular expression









Inerpretators Compiles




General | java | SQL


Design Design Design

by Deepak Dhakal 17. July 2019 19:31




How to remove a file from PR -Git

by Deepak Dhakal 14. October 2017 03:49

Let's say if you have three files but you want to not merge a File using PR. There is a way.

Switch to the branch

$ git checkout YourBranch

Override from the master:

git checkout origin/master -- src/main/java/yourfile.jsp

Commit and push it to the remote:

git commit -m "Removed a modified file from pull request"
git push origin YourBranch



Powered by BlogEngine.NET
Original Design by Laptop Geek, Adapted by onesoft