કસ્ટમ સ્ટ્રક્ચર ડિઝાઇન કરવાનો અર્થ હાલના સ્ટ્રક્ચરને કમ્પોઝ કરવું છે જેથી પ્રત્યેક આવશ્યક ઑપરેશન તેની લક્ષ્ય જટિલતાને હિટ કરે, એક સ્ટ્રક્ચરને બીજાની નબળાઈ આવરી લેવા દે. ક્લાસિક તકનીક એ hash map ને array, heap, અથવા linked list સાથે જોડવી છે.
માંગણી: , અને પ્રત્યેક O(1) માં. એક hash map એકલો O(1) રેન્ડમ કરી શકતો નથી; એક array એકલો O(1) remove કરી શકતો નથી. .
insert(x)remove(x)getRandom()import random
class RandomizedSet:
def __init__(self):
self.idx = {} # value -> index in list
self.vals = [] # values for O(1) random pick
def insert(self, x): # O(1)
if x in self.idx: return False
self.idx[x] = len(self.vals)
self.vals.append(x)
return True
def remove(self, x): # O(1): swap with last, pop
if x not in self.idx: return False
i, last = self.idx[x], self.vals[-1]
self.vals[i] = last # move last into the hole
self.idx[last] = i
self.vals.pop()
del self.idx[x]
return True
def getRandom(self): # O(1)
return random.choice(self.vals)
1. List every required operation + its target complexity.
2. For each, name a structure that hits it:
by key O(1) -> hash map
by index O(1) -> array
min/max O(log n) -> heap
ordered O(log n) -> balanced tree / skip list
O(1) splice -> doubly linked list
3. COMBINE them; use the hash map to map keys -> positions/nodes
in the other structure so updates stay O(1).
4. Verify each operation against its target.
| પેટર્ન | સ્ટ્રક્ચર્સ સંયુક્ત | સક્ષમ કરે છે |
|---|---|---|
| LRU cache | hash map + doubly linked list | O(1) get/put |
| O(1) randomized set | hash map + array | O(1) insert/remove/random |
| Min in O(1) on a stack | stack + auxiliary min-stack | O(1) getMin |
વાસ્તવિક સિસ્ટમ્સ ભાગ્યે જ એક પાઠ્યપુસ્તક સ્ટ્રક્ચર જરૂર હોય — તેમને ચોક્કસ એક્સેસ પેટર્નમાં ટ્યુન કરેલ કમ્પોઝીટ જરૂર હોય, જે બરાબર તે જ છે જે આ ડિઝાઇન્સ આપે છે.
ઇન્ટરવ્યુઅર્સ આ સમસ્યાઓનો ઉપયોગ કરે છે તમે કરી શકો છો કે નહીં તેમ આવતું પરીક્ષણ કરવા માટે ઑપરેશન કોસ્ટ્સથી કમ્પોઝીશનમાં તર્ક કરો, હાઇ-પરફોર્મન્સ સિસ્ટમ ડિઝાઇનની પાછળની મુખ્ય કુશળતા.