Real Amazon Interview Experience

function rowWithMaxOnes(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;

  let maxRow = -1;
  let col = cols - 1; // Start top-right corner

  for (let row = 0; row < rows; row++) {
    // Move left while we see 1s
    while (col >= 0 && matrix[row][col] === 1) {
      col--;
      maxRow = row;
    }
  }

  return maxRow;
}

// How it works:
// Start at top-right. If current cell is 1, move left (this row has more 1s).
// If current cell is 0, move down (this row can't beat current best).
// The "staircase" path guarantees we visit at most m + n cells.

// Time: O(m + n) — much better than O(m * log n) binary search approach
// Space: O(1)

// Test
console.log(rowWithMaxOnes([
  [0, 0, 1, 1],
  [0, 1, 1, 1],  // ← This row (index 1) has max ones
  [0, 0, 0, 1],
  [0, 0, 1, 1]
])); // Output: 1

class GraphNode {
  constructor(val, neighbors = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map(); // original → clone mapping
  const queue = [node];

  // Create clone of starting node
  visited.set(node, new GraphNode(node.val));

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of current.neighbors) {
      if (!visited.has(neighbor)) {
        // Clone unvisited neighbor
        visited.set(neighbor, new GraphNode(neighbor.val));
        queue.push(neighbor);
      }
      // Connect clone's neighbor
      visited.get(current).neighbors.push(visited.get(neighbor));
    }
  }

  return visited.get(node);
}

// DFS alternative (recursive):
function cloneGraphDFS(node, visited = new Map()) {
  if (!node) return null;
  if (visited.has(node)) return visited.get(node);

  const clone = new GraphNode(node.val);
  visited.set(node, clone);

  for (const neighbor of node.neighbors) {
    clone.neighbors.push(cloneGraphDFS(neighbor, visited));
  }

  return clone;
}

// Time: O(V + E) — visit every vertex and edge once
// Space: O(V) — HashMap stores all nodes

// With var
for (var i = 0; i < 3; i++) {
  setTimeout(() => console.log('var:', i), 100);
}

// With let
for (let j = 0; j < 3; j++) {
  setTimeout(() => console.log('let:', j), 100);
}

// Output:
// var: 3
// var: 3
// var: 3
// let: 0
// let: 1
// let: 2

// Fix 1: IIFE
for (var i = 0; i < 3; i++) {
  ((index) => {
    setTimeout(() => console.log(index), 100);
  })(i);
}

// Fix 2: setTimeout's third argument
for (var i = 0; i < 3; i++) {
  setTimeout((index) => console.log(index), 100, i);
}

console.log('start');

setTimeout(() => console.log('timeout'), 0);

Promise.resolve()
  .then(() => {
    console.log('promise 1');
    return Promise.resolve();
  })
  .then(() => console.log('promise 2'));

async function run() {
  console.log('async start');
  await Promise.resolve();
  console.log('async end');
}

run();

console.log('end');

// prototype — property on constructor FUNCTIONS
function Dog(name) { this.name = name; }
Dog.prototype.bark = function() { return this.name + ' barks'; };

// __proto__ — internal link on every OBJECT (instance)
const rex = new Dog('Rex');
rex.__proto__ === Dog.prototype;           // true
rex.__proto__.__proto__ === Object.prototype; // true (chain ends here)
rex.__proto__.__proto__.__proto__ === null;   // true (end of chain)

// Object.create — creates object with specified prototype
const animal = { breathe() { return 'breathing'; } };
const cat = Object.create(animal);
cat.breathe(); // 'breathing' (inherited via prototype chain)
cat.__proto__ === animal; // true

// Summary:
// prototype   → exists on functions, shared by all instances made with 'new'
// __proto__   → exists on objects, points to constructor's prototype (use Object.getPrototypeOf)
// Object.create → manually sets __proto__ without using new/constructor

// Component Tree
<HomePage>
  <BreakingNewsBanner />      // WebSocket/SSE for real-time
  <NavigationBar />
  <HeroSection />             // Top 3-5 stories, above the fold
  <ContentFeed>
    <FeedSection category="top-stories">
      <ContentCard type="article" />
      <ContentCard type="video" />
      <ContentCard type="ad" />     // Discriminator-based rendering
    </FeedSection>
    <FeedSection category="sports" />
    <FeedSection category="tech" />
    <InfiniteScrollTrigger />       // Intersection Observer
  </ContentFeed>
  <Sidebar>
    <TrendingWidget />
    <WeatherWidget />
  </Sidebar>
</HomePage>

// Unified card schema — type field determines rendering
interface BaseCard {
  id: string;
  type: 'article' | 'video' | 'ad';   // Discriminator
  position: number;
  timestamp: string;
}

interface ArticleCard extends BaseCard {
  type: 'article';
  headline: string;
  summary: string;
  thumbnail: string;
  author: string;
  category: string;
  readTime: number;
}

interface VideoCard extends BaseCard {
  type: 'video';
  title: string;
  duration: number;
  thumbnailUrl: string;
  hlsUrl: string;
}

interface AdCard extends BaseCard {
  type: 'ad';
  adProvider: string;
  adSlotId: string;
  size: 'banner' | 'medium-rect' | 'native';
}

type FeedCard = ArticleCard | VideoCard | AdCard;

// Renderer uses discriminator to pick component
function CardRenderer({ card }: { card: FeedCard }) {
  switch (card.type) {
    case 'article': return <ArticleCardComponent data={card} />;
    case 'video': return <VideoCardComponent data={card} />;
    case 'ad': return <AdCardComponent data={card} />;
  }
}

// API Design — cursor-based (not offset-based)
// GET /api/feed?cursor=abc123&limit=20&category=top-stories

// Response:
{
  "items": [...FeedCard],
  "nextCursor": "xyz789",    // Opaque cursor for next page
  "hasMore": true
}

// Why cursor > offset:
// - Offset breaks when new items are inserted (duplicates/skips)
// - Cursor is stable even when feed changes
// - Better for real-time content where items are constantly added

// Client implementation with Intersection Observer
function useInfiniteScroll(fetchFn) {
  const [items, setItems] = useState([]);
  const [cursor, setCursor] = useState(null);
  const [hasMore, setHasMore] = useState(true);
  const observerRef = useRef(null);

  const loadMore = useCallback(async () => {
    const { items: newItems, nextCursor, hasMore } = await fetchFn(cursor);
    setItems(prev => [...prev, ...newItems]);
    setCursor(nextCursor);
    setHasMore(hasMore);
  }, [cursor]);

  // Intersection Observer for trigger element
  const lastItemRef = useCallback((node) => {
    if (observerRef.current) observerRef.current.disconnect();
    observerRef.current = new IntersectionObserver(([entry]) => {
      if (entry.isIntersecting && hasMore) loadMore();
    }, { rootMargin: '200px' }); // Pre-fetch 200px before visible
    if (node) observerRef.current.observe(node);
  }, [hasMore, loadMore]);

  return { items, lastItemRef, hasMore };
}

// Architecture for real-time breaking news:

// Option 1: Server-Sent Events (SSE) — simpler, one-directional
const eventSource = new EventSource('/api/breaking-news/stream');
eventSource.onmessage = (event) => {
  const news = JSON.parse(event.data);
  showBreakingBanner(news);
};

// Option 2: WebSocket — bidirectional, if needed
const ws = new WebSocket('wss://api.example.com/breaking');
ws.onmessage = (event) => {
  const news = JSON.parse(event.data);
  showBreakingBanner(news);
};

// Backend flow:
// 1. Editor publishes breaking news via CMS
// 2. CMS triggers event to pub/sub (Redis/Kafka)
// 3. WebSocket server receives event, broadcasts to all connected clients
// 4. Client receives, shows banner with animation
// Total latency: < 2 seconds end-to-end

// Fallback for disconnected users:
// - Poll /api/breaking-news every 30s
// - Service Worker push notification
// - On reconnect, fetch latest breaking news

// Native lazy loading (simplest)
<img src="article.jpg" loading="lazy" alt="..." />

// With blur-up placeholder pattern:
// 1. Serve tiny base64 thumbnail inline (< 1KB)
// 2. Use Intersection Observer to load full image
// 3. Crossfade from placeholder to full image

// Priority hints for above-the-fold:
<img src="hero.jpg" fetchpriority="high" alt="..." />    // Above fold
<img src="article.jpg" loading="lazy" alt="..." />        // Below fold

function lowestCommonAncestor(root, p, q) {
  // Base cases
  if (!root) return null;
  if (root === p || root === q) return root;

  // Search in left and right subtrees
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // If both sides return non-null, current node is the LCA
  if (left && right) return root;

  // Otherwise, LCA is on whichever side returned non-null
  return left || right;
}

// How it works:
// 1. If current node IS p or q, return it
// 2. Recurse left and right
// 3. If BOTH sides found something → current node is the LCA
// 4. If only ONE side found → propagate that up (LCA is deeper)

// Time: O(n) — visit each node once
// Space: O(h) — recursion stack, h = height of tree

// Example:
//        3
//       / \
//      5   1
//     / \
//    6   2
//
// LCA(5, 1) = 3  (split at root)
// LCA(5, 6) = 5  (5 is ancestor of 6)