DSA foundations: check what you know

Already know some DSA? Answer these 9 questions, about 5 minutes. Each topic you get fully right is marked Known on the DSA roadmap, so you can skip it. Each one you miss is listed for you to study.

Don’t guess. Pick “I don’t know yet” when you’re not sure: a lucky guess would mark a topic Known that you still need to learn.

The 6 topics it checks

1. Big-O for time and space
2. Arrays and strings
3. Hashing and hash maps
4. Recursion
5. Basic sorting
6. Stacks and queues

1. Question 1 of 9 · Multiple choiceA loop over n items has another loop over the same n items inside it. n grows from 1,000 to 10,000. About how much longer does it take?

   The same timeAbout 10 times longerAbout 20 times longerAbout 100 times longerI don’t know yet
2. Question 2 of 9 · Predict the outputAbout how many times does the loop run?

   n = 1_000_000
   while n > 1:
       n //= 2
   

   About 20About 1,000About 500,000About 1,000,000I don’t know yet
3. Question 3 of 9 · Multiple choicenums is a Python list of n items. Which line takes O(n) time?

   nums.append(x)nums[-1]nums.insert(0, x)len(nums)I don’t know yet
4. Question 4 of 9 · Multiple choiceFind the first letter that appears twice in a string of n letters. Which way is best?

   For each letter, count it in the whole string with s.count().Sort the letters and look for two neighbors that match.Compare every pair of letters with two loops.Go left to right, keeping a set of letters seen. Return the first letter already in the set.I don’t know yet
5. Question 5 of 9 · Multiple choiceWhat does this cost for a list of n numbers, in time and in extra memory?

   def has_pair(nums, target):
       seen = set()
       for x in nums:
           if target - x in seen:
               return True
           seen.add(x)
       return False
   

   O(n) time and O(n) memoryO(n) time and O(1) memoryO(n²) time and O(1) memoryO(n log n) time and O(n) memoryI don’t know yet
6. Question 6 of 9 · Predict the outputWhat happens when you call f(-1)?

   def f(n):
       if n == 0:
           return 0
       return n + f(n - 1)
   

   It returns -1.It returns 0.It stops with a RecursionError.It returns None.I don’t know yet
7. Question 7 of 9 · Multiple choiceFind out if a list has any duplicates. You may not build a set or a dict. What is the best plan?

   Compare every pair with two loops. Nothing is faster without a set.Sort the list, then compare each item with the next one.Sort the list, then compare the first and last items.Sorting cannot help with duplicates.I don’t know yet
8. Question 8 of 9 · Multiple choiceTasks must be handled in the order they arrive, and there are millions of them. What should you use?

   A list, adding with append() and taking with pop(0)A list, adding with append() and taking with pop()collections.deque, adding with append() and taking with popleft()A set, so each task is found in one stepI don’t know yet
9. Question 9 of 9 · Multiple choiceYou check that brackets like "([]{})" are balanced. What fits best?

   A stack: push each opening bracket, and pop it when its closing bracket comes.A queue: take brackets out in the order they came in.A count of how many ( and ) there are.Sorting the brackets first.I don’t know yet

See my results

Answered 0 of 9.