最近做了一场 IBM OA ，整體難度偏基礎，但節奏較快。本次 OA 共 2 道程式設計題，限時 10 分鐘，更偏向對基礎演算法理解與程式碼熟練度的考察，而不是複雜的資料結構或技巧題。下面整理本次 OA 的題目結構、解題思路以及對應的 Python 實現，供後續準備 IBM 軟體工程類崗位的同學參考。
IBM OA 整體概覽
- 題目數量：2 題
- 時間限制：10 分鐘
- 難度定位：Easy
- 語言支援：多語言（本文示例使用 Python）
從題型設計來看，IBM OA 更關注：
- 是否能快速讀懂題意
- 是否能用清晰、穩定的邏輯完成實現
- 是否避免不必要的複雜度
Question 1
There is a list of items in the shopping cart, each having a cost associated with it.
There are n items, the cost of the ith item is i dollars and m items have already been bought represented in the array arr. Currently, there are k dollars, find the maximum number of distinct items one can have in total after purchasing any number of items from that money.
為了解決這個問題，我們必須在給定約束的情況下可以購買的不同物品的最大數量。考慮到已經購買的物品數量和有限的支出，我們的目標應該是最大限度地增加我們的不同購買總數。
To solve this problem, so we need identify the maximum number of distinct items we can purchase given our constraints. Due to given a set number of alreadypurchased items and limited money to spend, the goal should be to maximize our total number of distinct purchases.
Steps to solve the problem:
- Identify the Remaining Items: Out of all available products, we need to determine which are still available for purchase (i.e. not yet purchased by someone else).
- Sort the Remaining Items by Cost: In order to maximize our purchase capacity, it’s often beneficial to start buying cheaper items first.
- Purchase Items Until the Budget Runs Out: Start purchasing cheap items until either we run out of funds or cannot purchase any more without exceeding budget constraints.
- Calculating the Total Distinct Items: Add up the quantities of already purchased and newly acquired items, because of arriving at an estimate for total distinct items.
Python Code
def findMaxDistinctItems(n, arr, k):
# Convert arr to a set for O(1) average time complexity lookups
already_bought = set(arr)
# Calculate remaining items
remaining_items = [i for i in range(1, n+1) if i not in already_bought]
# Sort remaining items based on their cost (which is equal to their value)
remaining_items.sort()
total_distinct_items = len(already_bought)
current_budget = k
# Try to buy items starting from the cheapest one
for item_cost in remaining_items:
if current_budget >= item_cost:
current_budget -= item_cost
total_distinct_items += 1
else:
break
return total_distinct_items
# Example usage
n = 10
m = 3
k = 10
arr = [1, 3, 8]
print(findMaxDistinctItems(n, arr, k)) # Output: 5Question 2
A Domain Name System (DNS) translates domain names to IP addresses which are then used by browsers to load internet resources. For quicker DNS lookups,browsers often store a number of recent DNS queries in a DNS cache. Retrieving data from the cache is often faster than retrieving it from a DNS server. Thistask aims to simulate DNS resolution and determine the time taken to process different URLs.
為了解決這個問題，我們可以使用最近最少使用（LRU）緩存策略。 這種方法確保了當緩存達到其最大大小，並請求新的 URL 時，會驅逐最近使用最少的 URL，為新 URL 騰出空間。 我們可以使用 Python 的集合。 OrderedDict 有效地實現了這一點。
To address this issue, the Least Recently Used (LRU) cache strategy can provide an effective solution. When our cache reaches its maximum capacity and anew URL request comes through, when evicting older URLs to make room for newer ones is decided upon in accordance with this plan – we can usePython collections.OrderedDict to implement this efficiently.
Steps to solve the problem:
- Initialize the Cache: Use an
OrderedDictto maintain the cache where the keys are URLs and values can be arbitrary since we only need to track the presence and order of URLs. - Process Each URL: For each URL in the list:
- If the URL is already in the cache, it takes
cache_timeunits to resolve, and we need to move this URL to the end to mark it as recently used. - Or if the URL is not in the cache, it takes
server_timeunits to resolve. If the cache is full, remove the least recently used URL. Add the new URL to the cache.
- If the URL is already in the cache, it takes
- Calculate Total Time: Sum the time taken to resolve each URL.
Python Code
from collections import OrderedDict
def dns_resolution_time(cache_size, cache_time, server_time, urls):
cache = OrderedDict()
total_time = 0
for url in urls:
if url in cache:
# URL is in cache
total_time += cache_time
# Move the accessed URL to the end to mark it as recently used
cache.move_to_end(url)
else:
# URL is not in cache
total_time += server_time
if len(cache) >= cache_size:
# Cache is full, remove the least recently used item
cache.popitem(last=False)
# Add the new URL to the cache
cache[url] = None # The value doesn't matter, we're just using keys for URLs
return total_time
# Example usage
cache_size = 3
cache_time = 2
server_time = 5
urls = [
"http://www.hackerrank.com",
"http://www.google.com",
"http://www.yahoo.com",
"http://www.gmail.com",
"http://www.yahoo.com",
"http://www.hackerrank.com",
"http://www.gmail.com"
]
print(dns_resolution_time(cache_size, cache_time, server_time, urls)) # Output: 24Read More
Contact Us
經過我們的面試輔助，OA 代寫，候選人通過這些面試題的解析和溝通，面試官不僅瞭解了候選人的程式設計能力，也看到了我在解決問題過程中清晰的思路和有效的溝通技巧。 這些不僅有助於應對 IBM 的面試，同時也能提升我們解決實際程式設計問題的能力。 祝大家面試順利！
如果你也需要我们的面试辅助服务，请聯絡我們。
