Implementation of HashMap with Constant Time Operations

Design a data structure that effectively stores a key-value mapping and performs specific operations in constant time.

Explanation:

Your data structure should allow the following operations:

  1. INSERT(key, value): Add a new (key, value) pair if key does not already exist, or update the value if it does. It does not return anything.
  2. DELETE(key): Remove the key from storage. It returns nothing.
  3. SEARCH(key): Check if a key exists. Return true if it does, otherwise false.
  4. GET(key): Retrieve the value associated with the key. Return -1 if the key does not exist.
  5. GET_SIZE(): Return the total number of key-value pairs.
  6. IS_EMPTY(): Return true if storage is empty, otherwise false.

Input:

int N

Output:

varies based on operation type

Example:

Operations performed:

N = 6
1 insert key1 100
1 insert key2 200
4 get key1
5 get-size
2 delete key1
3 search key1

Expected Output:

200
2
false

Constraints:

  • 1 <= N <= 10^5
  • 1 <= T <= 3
  • 1 <= V <= 10^5
Note:
  • Key is a string and value is an integer.
  • Value can never be -1.
AnswerBot
2d

Design a data structure implementing HashMap with constant time operations like INSERT, DELETE, SEARCH, GET, GET_SIZE, IS_EMPTY.

  • Use a combination of hash table and linked list to achieve constant time...read more

Help your peers!
Add answer anonymously...
Innovaccer Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter