URL 단축 알고리즘 - 인터뷰

Question

참조 - 너 한테 위 https://stackoverflow.com/a/742047/161243

우리는 데이터를 저장하는 DB를 사용하는 것이 말했다. 이제 면접관이 DB를 사용할 수 없다고 말하면됩니다.

st_short_url* hashTable[N]; 이제 우리는 때마다 또는 base62로 변환됩니다 난수 생성 된 ID를 증가되는 int id을 가질 수있다 - 그런 다음 해시 테이블을

struct st_short_url{ 
    char * short_url; 
    char * url; 
} 

: 그런 경우에 우리는 stucture을 가질 수 있습니다.

문제는 내가 볼 :

을 -이 과정이 해지되면 내가 int id의 트랙 및 RAM에서 전체 해시 테이블을 잃게됩니다. 그래서 계속 보존되도록 hashTable을 디스크에 다시 작성합니까? 그렇다면 B- 트리가 사용됩니까? 또한 id도 디스크에 작성해야합니다.

P. 디스크에 Hashtable + 쓰기는 Database이지만, DBMS를 사용할 수 없다면 어떻게해야합니까? 내 구현을 생각해 내야 할 때 어떻게해야합니까?

생각하십시오 ...

또 다른 질문 : 일반적으로

, 우리는 URL 단축 무한 리디렉션을 처리하는 방법은?

Answer 1

데이터베이스는 항목의 삽입, 제거 및 검색을 지원하는 데이터 구조입니다. OP에 대한 의견에서 지적한 바와 같이 거의 모든 것이 데이터베이스이므로이 제약은 다소 정보가없는 것 같습니다.

기존 DBMS를 사용할 수없는 경우 tmpnam() 또는 경쟁 조건이없는 유사한 기술을 사용하여 디스크에 항목을 저장하는 것이 좋습니다. tmpnam()은 고유 한 ID를 산출하며 관련 파일을 사용하여 정보를 저장할 수 있습니다.

Answer 2

DB를 사용할 수 없다면 (즉, 영구 저장소가 없으면 파일 시스템은 원시 DB입니다!) 내가 볼 수있는 유일한 방법은 무손실 압축 + 허용 된 인코딩입니다 문자. 압축 알고리즘은 URL에 대한 지식을 사용할 수 있습니다 (예 : http:// 또는 https://으로 시작하는 경우가 많고 www.으로 계속 진행되며 도메인 이름이 대부분 .com, .org 또는 .net으로 끝나는 경우가 많습니다. 호스트 이름 다음에 슬래시 (http://example.org과 http://example.org/가 동일하므로) URL에 유효한 문자 만 포함될 수도 있고 특별한 경우 URL에 발생할 가능성이 매우 높은 일부 하위 문자열 (예 : 자주 링크 된 도메인 또는 알려진 특정 사이트에 대한 명명 스키마). 압축 스키마를 수정하면 사용 패턴이 변경 될 때 알고리즘을 업데이트 할 수있는 버전 필드가 있어야합니다 (예 : 새 웹 사이트가 인기를 얻고 특수한 경우 또는 인기있는 사이트 특별하게 케이스 된 URL 패턴을 변경하지 않고 이전 링크가 무효화 될 위험이 있습니다.

이러한 구성표는 확장 프로그램을 통해 브라우저에서 직접 지원되기 때문에 서버 대역폭을 절약 할 수 있습니다 (브라우저 확장이없는 서버는 서버가 있어야하고 확장 프로그램이 아직 최신 버전이 아닌 경우 폴백해야합니다). 압축 데이터).

Answer 3

요구 사항은 실용적이지 않지만 실제로 대답 할 필요는 없습니다. 그냥 파일 시스템을 사용하면 그는 그것을 깨닫지 못할 것입니다.

를 저장하려면 :

1. 변환 입력 URL을 문자열로 예를 들면, base64 변환.
   1. 이 얻을 :
   2. 는

   검색 할 등 그 이름

2. 복귀 아이 노드 짧은 URL로 번호 (예 : LS -i 파일 이름) 또는 합계()의 파일을 사용자의 inode 번호.
3. find/-inum n -print 또는 다른 메커니즘.
4. 파일 이름에서 URL로 다시 변환하십시오.