Quick Revision

GK One-Line Question & Answer

15541+ short questions with short answers, covering every category and sub-category on the site — no long articles to scroll through. Good for a fast recap before an exam, or a few minutes of daily practice.

Looking for exam process/strategy questions instead? Try the Exam Preparation FAQ →

Computer Fundamentals → Introduction to Computer 39

Intro sort (std::sort in C++) combines?
Quicksort, Heapsort, and Insertion sort for optimal performance
click to copy
TimSort (Python's default sort) is based on?
Natural runs + merge sort — optimized for real-world partially sorted data
click to copy
Patience sorting achieves?
O(n log n) and finds longest increasing subsequence
click to copy
LIS (Longest Increasing Subsequence) optimal solution is?
O(n log n) using patience sort/binary search
click to copy
LCS (Longest Common Subsequence) has time complexity?
O(n×m) using dynamic programming
click to copy
Edit distance (Levenshtein) DP has complexity?
O(n×m)
click to copy
Manacher's algorithm finds?
All palindromic substrings in O(n) time
click to copy
Z-algorithm for string matching runs in?
O(n+m)
click to copy
Suffix array construction optimal time is?
O(n log n) or O(n)
click to copy
Longest common prefix (LCP) array with suffix array enables?
O(n) or O(1) answers to many string queries after O(n log n) preprocessing
click to copy
Aho-Corasick algorithm is used for?
Multi-pattern string matching in O(n+m+k) time
click to copy
Rabin-Karp algorithm uses?
Rolling hash for average O(n+m) pattern matching
click to copy
Convex hull algorithms (Graham scan) run in?
O(n log n)
click to copy
Which algorithm finds nearest neighbor in k-d tree?
O(log n) average using branch-and-bound
click to copy
Bloom filter is a?
Probabilistic space-efficient structure for set membership — no false negatives, possible false positives
click to copy
HyperLogLog is used for?
Approximate count of distinct elements using minimal memory
click to copy
Count-Min Sketch provides?
Approximate frequency counts with controllable error using sub-linear space
click to copy
Cuckoo hashing achieves?
O(1) worst-case lookup using two hash functions and eviction-based insertion
click to copy
Robin Hood hashing reduces?
Variance in probe length by displacing rich entries for poor ones
click to copy
LSB (Least Significant Bit) radix sort processes digits?
Least to most significant — stable sort enables correct ordering
click to copy
MSD radix sort is better for?
Variable-length strings — can short-circuit early on differing prefixes
click to copy
Huffman coding is a?
Lossless variable-length encoding minimizing average code length
click to copy
LZ77 compression is used in?
ZIP files and deflate (gzip) — dictionary-based sliding window
click to copy
LZW compression is used in?
GIF and early PDF — dictionary-based compression
click to copy
Arithmetic coding achieves?
Compression closer to Shannon entropy limit than Huffman coding
click to copy
Burrows-Wheeler Transform (BWT) is used in?
bzip2 compression — reorganizes data for better compression by RLE/Huffman
click to copy
Delta encoding stores?
Difference from reference value — efficient for slowly changing data
click to copy
Run-Length Encoding (RLE) is most effective for?
Data with long runs of identical values (BMP images, fax)
click to copy
Which compression is used in PNG image format?
DEFLATE (LZ77 + Huffman) applied to filtered image data
click to copy
JPEG compression uses?
Lossy DCT (Discrete Cosine Transform) based block compression
click to copy
JPEG 2000 improves on JPEG by using?
Discrete Wavelet Transform (DWT) — better quality at high compression
click to copy
WebP image format by Google provides?
Both lossy and lossless compression with ~30% smaller than JPEG/PNG
click to copy
AVIF image format is based on?
AV1 video codec — excellent compression for photos and graphics
click to copy
Lossless vs lossy compression: main tradeoff is?
File size reduction vs perfect data recovery
click to copy
Steganography hides data by?
Concealing information within ordinary data (images, audio) invisibly
click to copy
LSB steganography in images?
Changes least significant bits of pixel values to embed hidden data
click to copy
Homomorphic encryption allows?
Computation on encrypted data without decrypting — result is encrypted correct answer
click to copy
Zero-knowledge proof allows?
Proving knowledge of a secret without revealing it
click to copy
Differential privacy adds?
Carefully calibrated noise to query results protecting individual privacy while allowing statistics
click to copy

Computer Fundamentals → Memory Units 1

Digital watermarking differs from steganography in?
Watermarking is for copyright — visible or invisible but robust to removal
click to copy