Prolog Cheat Sheet

 




This blog post is a coding and system design interview cookbook/cheatsheet compiled by me with code pieces written by me as well. There is no particular structure nor do I pretend this to be a comprehensive guide. Also there are no explanations as the purpose is just to list important things. Moreover, this blog post. Prolog Cheatsheet Cheat Sheet by riccard tommasini (tomma156) via cheatography.com/9200/cs/1225/ List Prolog Empty List Car and Cdr X L string are list, ' hel lo' stands for 104, 101, 108, 108, 111 atoms are symbols 'anatom' Higher-order and meta predicates Call, which is used to perform a query in a program call(G1, A1, A2.) adds arguments.

-Eric

Exit gprolog

halt.

Trace or Debug

trace.

debug.
% exit trace or debug
notrace.

run file

['~/cs345/file.p'].

['file.p'].

The following commands are typed in at the Prolog prompt. listing. --creates a listing of the current data base of Prolog facts and rules.
CheatRead File

[filename]. --``consults' (reads) the file named filename for input to the data base; assumes that the file extension is .pl. Other files can be consulted by surrounding their full filename (with extension) in quotes.

Prolog interrupt options

When running Prolog, Control-c interrupts execution and results in the Prolog prompt for help. If you reply to the prompt h thus asking for help, the following choices are open to you:
a abort - cause abort
b break - cause break
c continue - do nothing
e exit - cause exit
d debug - start leaping
z zip - start zipping
t trace - start creeping
h help - get this list
t will turn on a step-by-step trace of your execution (see below).
d turns on a ``skipping' trace.
e allows you to exit from Prolog gracefully.

Functions from HW14 Prolog1.p

[See Attachment]

% Problem 15.4
% define new relation 'cousin' (any two people who's parents are siblings) write a query for this expanded program that will identify cousins of 'ron'

% ******** testing *******
%sibling sibling(sue,bill). sibling(bill,sue). sibling(nancy,jeff). sibling(jeff,nancy).
%cousin sibling(ron,jeff). sibling(jeff,ron). sibling(ron,nancy). sibling(nancy,ron).
%grandparent sibling(john,nancy). sibling(john,jeff). sibling(john,ron). sibling(mary,nancy). sibling(mary,jeff). sibling(mary,ron).
%married sibling(john,mary). sibling(mary,john).

Parent

parent(A,B) :- father(A,B).parent(A,B) :- mother(A,B).

Grandparent

grandparent(C,D) :- parent(C,E), parent(E,D).

mother(mary, sue).
mother(mary, bill).
Prolog Cheat Sheetmother(sue, nancy).
mother(sue, jeff).
mother(jane, ron).
father(john, sue).
father(john, bill).
father(bob, nancy).
father(bob, jeff).
father(bill, ron).

Prolog Cheat Sheet


Cousin

cousin(X,Y) :- parent(M,X), parent(D,Y), sibling(M,D), t, X=Y. % Fill in before the comma.Cheat sheet pdf
Prolog Cheat Sheet

Sibling

sibling(B,G) :- parent(P,B), parent(P,G), B=G.
% write a Prolog program to find the max, minimum, and range of values in a list of numbers. L=Lenght, Range=List of value between min and max
mmr([H|T], R) :- max([H|T], Max), min([H|T], Min), R is Max - Min.
mmr([H|T], Max, Min, R) :- max([H|T], Max), min([H|T], Min), R is Max - Min.

Max

max([H|T], M) :- max(T, H, M).
max([], M, M).
max([H|T], Y, M) :- H =< Y, max(T, Y, M).
max([H|T], Y, M) :- H > Y, max(T, H, M).

Min

min([H|T], M) :- min(T, H, M).% + means 'not'
min([], M, M).
min([H|T], Y, M) :- H =< Y, min(T, H, M).
min([H|T], Y, M) :- H > Y, min(T, Y, M).
% fac2(N, 1) :- N < 1, !.
% fac2(N, R) :- M is N - 1, fac2(M, S), R is N * S.
% lsum([], X) :- X is 0.
% lsum([A|B], R) :- lsum(B, S), X is S + A.
% Problem 15.6

% write a prolog program 'remdup' that removes all duplicates from a list. for example, the query 'remdup([a, b, a, a, c, b, b, a], X)' should return 'X = [a. b, c]

Member of list

member(X, [X|_]).

member(A, [_|B]) :- member(A, B).

Remove Duplicate

remdup([X],[X]).

remdup([X|Y], Z) :- member(X,Y), remdup(Y,Z).Sheet

remdup([X|Y], [X|Z]) :- + (member(X,Y)), remdup(Y,Z).

removedups([],[]).

removedups([X|Rest], Result) :- member(X,Rest), removedups(Rest,Result), !.

removedups([X|Rest], [X|Rest1]) :- not(member(X,Rest)), removedups(Rest,Rest1), !.

% + means 'not'

% end of HW14 Prolog1

This blog post is a coding and system design interview cookbook/cheatsheet compiled by me with code pieces written by me as well. There is no particular structure nor do I pretend this to be a comprehensive guide. Also there are no explanations as the purpose is just to list important things. Moreover, this blog post is work-in-progress as I’m planning to add more things to it.

As always, opinions are mine.

Binary Search

Breadth First Search

Depth First Search

Just replace the queue in BFS with stack and you are done:

Backtracking

Generally a recursive algorithm attempting candidates and either accepting them or rejecting (“backtracking”) based on some condition. Below is an example of permutations generation using backtracking:

Dynamic Programming

Technique to determine result using previous results. You should be able to reason about your solution recursively and be able to deduce dp[i] using dp[i-1]. Generally you would have something like this:

Dynamic Programming: Knapsack

Union Find

When you need to figure out if something belongs to the same set you can use the following:

Binary Tree Traversals

  • Inorder: left-root-right
  • Postorder: left-rigth-root
  • Preorder: root-left-right
  • Plus each one of them could have reverse for right and left

Below are recursive and iterative versions of inorder traversal

Segment Tree

Djikstra

Simplest way to remember Djikstra is to imagine it as BFS over PriorityQueue instead of normal Queue, where values in queue are best distances to nodes pending processing.

Multi-threading: Semaphore

Multi-threading: Runnable & synchronized

Strings: KMP

Hopefully no one asks you this one. It would be too much code here, but the idea is not that difficult: build LPS (example “AAABAAA” -> [0,1,2,0,1,2,3]); use LPS to skip when comparing as if you were doing it in brute-force.

Strings: Rolling Hash (Rabin-Karp)

Let’s imagine we have window of length k and string s, then the hash for the first window will be:

H(k) = s[0]*P^(k-1) + s[1]*P^(k-2) + … + s[k]*P^0

Cheat Sheet Pdf

Moving the window by one, would be O(1) operation:

H(k+1) = (H(k) – s[0]*P^(k-1)) * P + s[k+1]*P^0

Here is some sample code:

Unit Testing

JUnit User guide: https://junit.org/junit5/docs/current/user-guide/

Data Structures

Many interview problems can be solved by using right data structure.

  • hashmap
  • stack
  • queue
  • priority queue
  • trees
  • linked list
  • …
  • Actually, better to go here: https://www.geeksforgeeks.org/data-structures/

System Design Topics

  • requirements gathering
  • capacity planning
  • high level design
  • components design
  • database design
  • API design
  • queue
  • map reduce
  • long poll and push models
  • load balancing
  • partitioning
  • replication
  • consistency
  • caching
  • distributed caching
  • networking

Some System Design Problems

  • TinyURL
    • Coming up with good encoding or better pre-building keys
    • Handling collisions (if encoding or if different users have to have different key)
    • Use distributed caching, CDN, LB
    • Consider API throttling, eviction (maybe not), capacity
    • HTTP 302
  • Pastebin
    • Separate data from metadata and store separately
    • Otherwise similar to TinyURL
  • Instagram
    • Data partitioning is important here
    • Pull vs push (via long polling) applied based on number of following
    • Separate servers for viewing and posting for stability
    • Generating feed of images requires sorting, consider timestamp for photoId
  • Dropbox
    • Client and Server
    • Splitting files into chunks
    • Saving metadata about chunks
    • Local metadata database for the client
    • Queues for load handling
    • Data deduplication (user has same file in 100 places)
  • Facebook Messenger
    • poll vs push model with long polling
    • push notifications
    • Dedicate chat servers per user
    • “seeing into the future” problem solving with seq number
    • active status
  • Twitter
    • prebuild feed
    • handle celebrities differently
    • caching
    • monitoring
  • Youtube or Netflix
    • Splitting files into chunks (time and quality) via MapReduce
    • Distribution of content
    • Thumbnail generator & distribution
    • Store metadata separately (likes, views, comments, etc)
    • CDN
  • Typeahead Suggestion
    • Trie
    • For frequencies store them in nodes with suggestions
    • Propagate suggestions independently from queries (mapreduce)
    • Client implementation should delay request allowing for typing
    • Client having local history
  • API Rate Limiter
    • DDoS
    • Client identifier
    • Sliding window with counters
    • HTTP 429
  • Web Crawler
    • BFS
  • Facebook’s Newsfeed
    • Different feed components stored separately but joined
  • Yelp
    • Quad-Tree
  • Uber
    • Dynamic Quad-Tree
    • HashMap
  • Ticketmaster
    • Relational DB design
    • Concurrency handling

Prolog Cheat Sheet Printable

Resources

Well, internet is just full of all kinds of resources and blog posts on how to prepare for the technical interview plus there are numerous books and websites available. LeetCode is probably the most known of practicing websites. “Cracking The Coding Interview” is probably the most known book. I can also recommend “Guide to Competitive Programming”. As of system design, preparation resources are not so readily available. One good resource is “Grokking System Design Interview”, but it would be more valuable to practice designing large distributed systems. I also found the book “Designing Data-Intensive Applications” to be extremely helpful.

Asking for help

What are other “must know” algorithms and important system design topics to be listed in this post?