InMobi & ShareChat: AI/ML Engineer

• Static array: a prefix XOR, px[i] = a[0]^…^a[i−1], so XOR(l..r) = px[r+1] ^ px[l]. O(1) per query.
• With updates: a Fenwick tree or segment tree storing XOR. O(log n) per update and query.

class BIT:
    def __init__(self, n): self.n, self.t = n, [0] * (n + 1)
    def upd(self, i, v):          # xor v at index i (0-based)
        i += 1
        while i <= self.n: self.t[i] ^= v; i += i & -i
    def pre(self, i):             # xor of [0, i)
        r = 0
        while i: r ^= self.t[i]; i -= i & -i
        return r
    def query(self, l, r): return self.pre(r + 1) ^ self.pre(l)

• To set a value instead of XOR-ing it in, apply upd(i, old ^ new).

• If the goal is to turn A into a supersequence of the alphabet order (or of string B) with the fewest insertions: answer = len(B) − LCS(A, B), since the characters in the LCS already line up and the others must be inserted.

def lcs(a, b):
    dp = [0] * (len(b) + 1)
    for x in a:
        prev = 0
        for j, y in enumerate(b, 1):
            cur = dp[j]
            dp[j] = prev + 1 if x == y else max(dp[j], dp[j - 1])
            prev = cur
    return dp[-1]

• O(|A|·|B|) time with O(|B|) space.

• Features:
• User: device, OS, geo, app category, time of day, user embeddings.
• Ad: creative, advertiser, format.
• Context: placement, frequency caps.
• Crosses: user × ad category.
• Models: logistic regression with hashing as a baseline → FM / DeepFM / DCN for feature interactions; train on billions of impressions, update daily or online.
• Calibration is essential, because bids depend on pCTR × value. Monitor with log-loss and calibration plots.
• Challenges: extreme imbalance (CTR about 1%), delayed conversions, privacy changes (limited IDs), fraud.

• The flow: tokens → embeddings + positions → N decoder blocks (causal self-attention + MLP) → logits → sampling → append → repeat.
• Costs:
• Prefill (processing the prompt) is compute-bound.
• Decode is memory-bandwidth-bound and proportional to the number of output tokens.
• The KV cache grows with batch × sequence × layers.
• Optimisations: batching (continuous), quantization, FlashAttention, GQA, speculative decoding, shorter prompts.

• (4/52) × (3/51) = 12/2652 = 1/221 ≈ 0.0045.
• General approach: the multiplication rule for dependent events, or combinations: C(4,2)/C(52,2) = 6/1326 = 1/221.

• Candidates: the user's language and region, followed creators, trending items, content similar to past engagement (multilingual embeddings).
• Ranker: multi-task prediction of P(like), P(share), P(watch time), P(report); a value function weights them, and integrity filters remove harmful or spam content.
• Language: Indic multilingual models (IndicBERT, MuRIL) for text; video and audio embeddings.
• Creator fairness and freshness boosts; cold start for new creators via exploration.
• Metrics: daily active users, session time, shares, retention; guardrails on reports and blocks.