coding questions

Question 1

fib recursive vs iter

Answer 1

0 and 1 as special case , start iterating at 2, in python in range(2,n+1) as the last one is not counted

Question 2

reverse linked list

Answer 2

use 3 pointers, current and previous, tmp is set not to lose the next. initiatialize previous with None, while on tmp(next), at the end of the loop do the last reversal by hand and return the lat element to print it right

Question 3

test for anagram

Answer 3

test for length first exit
add frequency by letter in hash on first string
decrement frequency on second string
should be all zero at the end
in python there is a Counter data structure which is a specialized hash that count frequency in strings

Question 4

test for balance parentheses, one kind, many kinds

Answer 4

one kind simple counter increment decrement
several kind assume proper scoping push open, pop closed, one stack per type of parenthesis, otherwise will allow crossing which is not standard syntax, should be empty at the end

Question 5

stock max draw

Answer 5

brute force all pairs
maintain index of buy, sell, and min, all at zero initially
always keep the profit as invariant of buy/sell
if new min is found change
keep on testing profit from new min, if over, change the current buy/sell and profit

Question 6

find the first non repeating character in a string

Answer 6

put character is a fixed size array with their frequency and position, get min of 1s

Question 7

reverse a string in place

Answer 7

swap from both end, test for odd vs. even, if immutable go from the end

Question 8

reverse a text

Answer 8

reverse the whole string, then reverse each word, 2 passes

Question 9

test for palindrome

Answer 9

walk from both end, test of even vs. odd

Question 10

If I give you coins of denominations {3, 7, 9} (a coin worth 3 cents, a coin worth 7 cents, etc.), can you tell me the minimum number of coins that are needed to make a total of 37? You can assume that an infinite supply of all these coins are available to you.

Answer 10

instance of knapsack problem, the general knapsack problem is NP Complete, no better solution than compute all combination, greedy also, dynamic programming means precomputing solution on smaller sizes, need to keep an array , use lots of memory

Question 11

explain first classic PK crypto and trapdoor (RSA)

Answer 11

asymmetry based on the fact that multiplying to very large prime is easy but finding the factorization is NP_complete cannot be computed in a reasonable time. The multiplication is the public key, the 2 prime the private key that can be used to decrypt

Question 12

smallest or biggest number made of same digit

Answer 12

just programming challenge, break it down in list of digit as powers of 10, sort in ascending or descending order and reconstruct by power of 10.

Question 13

how to compute all subsets of a list/array a.k.a Powerset

Answer 13

used a binary representation bit position turn into index in the list/array. go from 0 to 2^n. Or recursive definition, slicing one element is sub problem with n -1
recursive method, or bottom up starting with 2,3,…n binomial coefficients but best using bit encoding with power set cardinality 2^n

Question 14

how to compute parity bit of long string

Answer 14

do it byte of word at a time, shift and mask with 1 a count mod 2. Cache each word in a hash

Question 15

given a string of n char, write a function that computes the maximum number of ‘a’ can be added anywhere without creating any sequence ‘aaa’

Answer 15

go through the string if not a, add ‘aa’ in front end after, if ‘a’ ad just another ‘a’. start and end with ‘aa’

Question 16

Find the smallest integer that is greater than N and the sum of whose digit is twice as big as the sum of the digit of N. Go for correctness not performance

Answer 16

brute force from N. equation with powers to find exact answer

Question 17

server side receives N requests that can be though as in an array A, the time of each is A[k] , the index from 0 to n-1 can be understood as the request and A[k] it time to process.
load balancer has to drop 2 and distribute the rest over 3 workers. the distribution has to be such that all 3 work receive tasks that are continuous in the array and the sum of time of each has to be exactly the same for each worker so that they finish at the same time.
Write function that return if it is possible and the time for each of the 3 contiguous parts. So basically pick to cutoff and with 3 equal sum left.

Variation : how many contiguous fragments with average m

Answer 17

3 sliding cutoff to explore all possibilities and prune every time it becomes impossible. All start at zero. the move together until the first candidate subset is pick, then 2 move together, then 3, then start again.

optimization is to keep partial sum and down adjust as cutoffs are moved up and down

Question 18

How to design excel numbering scheme, map column rank to that AA notation

Answer 18

base 26, without zeroes, remainder is just number modulo 26, the map remainder with Z for zero, the floor division

Question 19

two sum or 3 sum problem, special case of subset sum problem, special case of knapsack problem. how many/which pairs or array sum to x. Please relate to the de Medici and Galilo 9 vs. 10 3 dice sum probability

Answer 19

general knapsack or subset sum problem Non deterministic Polynomial testable Complete (NP complete)

All of them: brute force: compute powerset, sums, then iterate over power set. Complexity exponential.

. variation of knapsack. For the 2 SUM
brute force N^2 for 3 SUM n^3

2 sum
1 n insert in has as i increment, avoid duplicates

3 Sum, sort the array, then decrement from end if in N, has to both decrement from end then increment from bottom if in Z

could reuse 2sum but need to remove duplicates.

General Solution with Dynamic Programming, establish the recursion relationship then compute bottom up by exploring all possible values starting with small ones.

Question 20

reservoir sampling algo: how to pick a good random sample in one pass from a stream of data (I.e no replacement) . a.k.a online sampling

Answer 20

First define what random sampling is. Here we want random sampling without replacement. The R agorithm first fill in the k reservoir with first k of of the stream, for iterate start at k + 1, for each candidate genrate a uniform random random for 0 to i, if random < k, swap, if not do nothing. reservoir stays invariant as k/n probability. proof by induction and conditional prob of staying if swap needs to happen

https://richardstartin.github.io/posts/reservoir-sampling#algorithm-r

Question 21

dedupe in place

Answer 21

double loop , skipping and shifting

Question 22

Efficient n-choose-k random sampling a.k.a offline data sampling from array or indexable structure

Answer 22

Mathematically correct but crazy inefficient generate C(n,k) and pick one randomly

some naive stuff :if k i small relative to n, uniformly draw from the index space, marked picked, and reloop in case of collision. If k close to n, company the array a few times. more efficient than reservoir sampling

Better sample from n, n-1, n-2 … but recompact each time by swiping the found element with the one dropping because of the index iteration. Inductive proof of correctness

Question 23

find the median in unordered array

Answer 23

sort, dedupe then iterate from both end if the number is all that matter.
without deducing if the actual slots matter. Connect to the De Medici problem
sort n log(n)
but there are linear algorithm
https://brilliant.org/wiki/median-finding-algorithm/

Question 24

find the k largest element of an array

Answer 24

Brute force sorting
One pass with an auxiliary min heap
Best with a randomized pivot tbd

Question 25

suffix tree

Answer 25

https://en.wikipedia.org/wiki/Suffix_tree

Representation of string where each path in the tree is o f of the n suffix . Computable in n then allow some efficient operation like substring search.