SORU
7 EKİM 2011, Cuma


Mağaza bin telefon numaraları için en verimli şekilde

Bu google mülakat sorusu:

Bin telefon numaraları 10 haneli olan her saklanabilir vardır. Bin numara üzerinden aynı olması için her ilk 5 basamak kabul edilebilir. Aşağıdaki işlemleri gerçekleştirmek için: bir. Eğer belirli bir sayı varsa arama. b. Tüm baskı sayısı

En verimli yer tasarrufu bunu yapmanın yolu nedir ?

Karma tablo açtım ve daha sonra huffman kodlama ama benim spiker doğru yöne doğru yolda olduğunu söyledi. Bana yardım edin lütfen.

Olabilir soneki sükunet yardım kullanarak?

İdeal olarak 1000 numaralarından bütün 4000 1000 bayt sayısını saklamak için o sayı başına 4 bayt alır. Nicelik, depolama < 4000 azaltmak istiyorum bayt, bu benim spiker bana açıkladı.

CEVAP
7 EKİM 2011, Cuma


Aşağıda, tamsayı değişkenleri dizeleri aksine) gibi sayılar davranıyorum:

  1. Numaraları sıralama.
  2. İlk beş basamaktan her ayırarak son beş basamak.
  3. İlk beş basamak arasında aynı sayılar vardır, bu yüzden sadece bir kez onları saklayın. Bu depolama 17 bit gerektirir.
  4. Tek tek her sayının son beş basamaklı mağaza. Bu sayı yüzde 17 bit gerektirir.

İlk 17 bit ortak önek, 17 bit sonraki 1000 grupları, her sayıda artan düzende saklı son beş basamak vardır. özetlemek gerekirse:

Toplam 1000 sayı veya 10 haneli telefon numaranızı başına 17.017 bit için 2128 bayt bakıyoruz.

Arama O(log n) (ikili arama) ve tam numaralandırma O(n).

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • mahalodotcom

    mahalodotcom

    8 HAZİRAN 2007
  • martin shervington

    martin sherv

    7 EKİM 2011
  • Crossover

    Crossover

    18 HAZİRAN 2007