Loading Question...
Jobra drops you into a broken repo. Find it, fix it, ship it. AI helps you debug like on the job.
Jobra drops you into a broken repo. Find it, fix it, ship it. AI helps you debug like on the job.
1st DSA Question
The interviewer asked the following problem:
You are given an integer array cardPoints and an integer k. You can pick exactly k cards from either the beginning or the end of the array. Your task is to maximize the total score.
Discussion / Approach:
Initially, I discussed the first optimal approach: selecting i cards from the left and k-i cards from the right while maintaining the running sum.
Then, we discussed a more elegant approach using Sliding Window.
The key observation was that if we select exactly k cards from the two ends, the remaining n-k cards will always form a contiguous subarray.
So, instead of maximizing the selected sum, we can minimize the sum of a subarray of size n-k.
Answer = Total Sum - Minimum Sliding Window Sum
Complexities:
The discussion focused on deriving the sliding window optimization from the initial approach rather than jumping directly to the final solution.
Design and implement a data structure for a Least Recently Used (LRU) Cache.
The cache should support the following operations, both in O(1) average time complexity:
LRUCache(int capacity) — Initialize the cache with a positive integer capacity.
int get(int key) — Return the value associated with the key if it exists; otherwise, return -1.
Accessing a key counts as using it, so the key becomes the most recently used key.
void put(int key, int value) — Update the value of the key if it already exists.
Otherwise, add the key-value pair to the cache.
If the number of keys exceeds the cache capacity, evict the least recently used key.
LRUCache cache = new LRUCache(2); // capacity = 2
cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {1=1, 2=2}
cache.get(1); // returns 1
// cache: {2=2, 1=1}
// 1 is now the most recently used
cache.put(3, 3); // evicts key 2 (LRU)
// cache: {1=1, 3=3}
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1 (LRU)
// cache: {3=3, 4=4}
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Also, some students were asked LLD (Low-Level Design) questions during the interview, so make sure you prepare LLD concepts and practice basic design problems as well. Don't focus only on DSA!