CareerCup

Straightforward level order traversal using a queue. Solution in Python below.

from collections import deque
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def level_order(root):
    q = deque([root])
    while q:
        currLevel = []
        qSize = len(q)
        for _ in range(qSize):
            curr = q.popleft()
            currLevel.append(curr.val)
            if curr.left: q.append(curr.left)
            if curr.right: q.append(curr.right)
        print(currLevel)

'''
Construct the following tree
        1
      /   \
     2    3
     /
    4
    /
    5
'''

one_node = Node(1)
two_node = Node(2)
three_node = Node(3)
four_node = Node(4)
five_node = Node(5)

one_node.left = two_node
one_node.right = three_node
two_node.left = four_node
four_node.left = five_node

level_order(one_node)

Output:

[1]
[2, 3]
[4]
[5]

Hi DaveX, could we maybe try to use a Trie for this situation?. Like insert the word "ababac" and just take substrings of it by walking down the trie? I could be wrong, but wouldn't it be O(n) time then? What are your thoughts?

Oh I see, so do you mean like you can send queue messages and then it immediately prints whatever messages sent to the queue? Like would an example be like:

q = Queue()
q.issueMessage("Message 1")
q.issueMessage("Message 2")

and an implicit listener would analyze the incoming message for the queue and print

Message 1 printed
Message 2 printed

Also would it be printed when an element is dequeued or enqueued to the queue? Can you please give an example, Sameer?

The algorithm is pretty much to take the substrings of the main string (prefixes) and use two pointers to scan the two strings and move them at the same time until the characters do not match. I present a concise solution in Python below.

def lcpOfAllSubstrings(s):
  for i in range(len(s)):
    count = 0
    for l1, l2 in zip(s, s[i:]):
      if l1 != l2:
        break
      count += 1
    print('{}: len(LCP(s({}, {}), s)) = {}'.format(i + 1, i + 1, len(s), count))

# Test code
lcpOfAllSubstrings("ababac")

Output

1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

I believe this question tests knowledge on the Observer Design pattern. Implementations across languages vary but I present a solution in Swift (iOS) below using Property Observers.

import Foundation
import Queue

class Demo {

  var portNumber: Int16
  var userName: String
  var password: String
  var queue: Queue? {
    didSet {
      printListenerMessage()
    }
  }
  
  init(portNumber: Int16, userName: String, password: String) {
    self.portNumber = portNumber
    self.userName = userName
    self.password = password
  }
  
  private func printListenerMessage() {
    let message = """
    The queue is running on port : \(portNumber)
    Username : \(userName)
    Password : \(password)
    """
    print(message)
  }
}

// In Main.swift
let demoApp = Demo.init(portNumber: 8161, userName: "admin", password: "admin")
demoApp.queue = Queue()

Output

The queue is running on port : 8161
Username : admin
Password : admin

Pretty straightforward with Priority Queue / Heap. Enqueue the elements as you go along and extract min during every iteration and add it to the result. Presenting my short Python solution below:

Solution

import heapq

def mergeStreams(streams):
  heap = []
  res = []
  for stream in streams:
    if stream:
      # Get first element and enqueue it
      iterator = iter(stream)
      heapq.heappush(heap, (next(iterator), iterator))

  while heap:
    curElem, curIterator = heapq.heappop(heap)
    res.append(curElem)
    try:
      heapq.heappush(heap, (next(curIterator), curIterator))
    except StopIteration:
      continue

  return res

Test Code

streams = [[2,4,5,6,7,8], [1,3,9,12], [10,11,13,14]]
print(mergeStreams(streams))
'''
OUTPUT: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
'''

Perform a simple BFS on the graph and add the points to the queue until you find a building. I present a simple solution in Python below.

Code

from collections import deque

# This function returns the minimum cost
def bfs(googleMap, employeeLocation):
  if not googleMap or not googleMap[0] or not employeeLocation:
    return 0

  minCost = 0
  pathToBuilding = []
  rows, cols = len(googleMap), len(googleMap[0])
  # Perform a BFS here
  startX, startY = employeeLocation
  queue = deque([(startX, startY, 0, [])])
  visited = set([(employeeLocation)])

  while queue:
    x, y, currCost, path = queue.popleft()

    if googleMap[x][y] == 'B': # Destination Reached
      minCost = currCost
      pathToBuilding = path
      break

    for nextX, nextY, dir in [(x, y+1, 'R'), (x+1, y, 'D'), (x, y-1,'L'), (x-1, y, 'U')]:
      if 0 <= nextX < rows and 0 <= nextY < cols \
          and googleMap[nextX][nextY] != '#'\
          and (nextX, nextY) not in visited:

        visited.add((nextX, nextY))
        queue.append((nextX, nextY, currCost + 1, path + [dir]))

  return (minCost, pathToBuilding)

Test Code

# Test Case 1
googleMap = [
  ['.', '.', '.', '.', '.', '#'],
  ['.', '.', 'E', '.', '.', '#'],
  ['#', '#', '#', '#', '.', '#'],
  ['.', 'B', '.', '.', '.', '.'],
  ['.', '.', '.', '.', '.', 'B']
]
print(bfs(googleMap, (1, 2)))
# OUTPUTS: (6, ['R', 'R', 'D', 'D', 'R', 'D'])

# Test Case 2
googleMap = [
  ['.', '.', '.', '.', '.', '#'],
  ['.', '.', 'E', '.', '.', '#'],
  ['#', '#', '#', '#', '.', '#'],
  ['B', '.', '.', '.', '.', '.'],
  ['.', '.', '.', '.', '.', '.']
]
print(bfs(googleMap, (1, 2)))
# OUTPUTS: (8, ['R', 'R', 'D', 'D', 'L', 'L', 'L', 'L'])

This problem is very similar to the "Grouping Anagrams" problem. The idea is to use a hash table using the dishes as the key and the cuisines as values. Ex:-

"lettuce,cheese,pepper,tomato": ["Mexican", "French"]
"lettuce,cheese,olives,tomato": ["American", "Continental"]

However, the ingredients or dishes can be in any order, which is why you have to sort them before using them as the key.
I present a solution in Python below. I use a Python tuple to represent the key and the cuisines as values.
Time complexity would be O (n log k) where k is the max number of ingredients in the dish.
Space complexity would be O(n) since we are using a hash table to store all the meals.

Code

class Meal:
  def __init__(self, cuisine, dishes):
    self.cuisine = cuisine
    self.dishes = dishes

def findUniqueIngredients(meals):
  # If meals is empty, return 0
  if not meals:
    return 0

  dishesMap = collections.defaultdict(set)

  for meal in meals:
    # Sort it before inserting this as a key
    dishesMap[tuple(sorted(meal.dishes))].add(meal.cuisine)
  
  combinedCuisines = list(dishesMap.values())
  return (len(combinedCuisines), combinedCuisines)

Test Code

meals = [
  Meal("American", ["lettuce", "cheese", "olives", "tomato"] ),
  Meal("Mexican", ["lettuce", "cheese", "pepper", "tomato"] ),
  Meal("French", ["lettuce", "cheese", "pepper", "tomato"] ),
  Meal("Continental", ["lettuce", "cheese", "olives", "tomato"] )
]
uniqueDishesCount, uniqueDishesCuisines = findUniqueIngredients(meals)
print('The unique dishes cuisines are:', uniqueDishesCuisines)
print('Total unique dishes count:', uniqueDishesCount)

'''
OUTPUT:
The unique dishes cuisines are: [{'American', 'Continental'}, {'French', 'Mexican'}]
Total unique dishes count: 2
'''

Use Hashmap while traversing through array, first element already present in hashmap is the duplicate. Sharing my solution in Python below.

def secondDuplicate(nums):
  counterMap = {}
  for num in nums:
    if num not in counterMap:
      counterMap[num] = 0
    else:
      return num
  return -1

Test Code

print(secondDuplicate([1,2,3,4,5,3,7,2])) # Prints 3

A straightforward application of Kadane's algorithm. Sharing my solution in Python below:

def maximumSubarray(nums):
  localMax = globalMax = nums[0]
  for ind, num in enumerate(nums[1:]):
    localMax = max(num, num + localMax)
    globalMax = max(localMax, globalMax)

  return globalMax

Test code

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print('Maximum sum subarray ->' ,maximumSubarray(nums))
# OUTPUT: Maximum sum subarray -> 6

Classic Two-sum problem. Sharing my solution in Python below.

def twoSum(nums, target):
  seenNumbers = set()

  for ind, num in enumerate(nums):
    complement = target - num
    if complement not in seenNumbers:
      seenNumbers.add(num)
    else:
      return [complement, num]
  return []

Test Code

print('Two Sum ->', twoSum([2,4,5,9,13], 17)) # OUTPUT: Two Sum -> [4, 13]
print('Two Sum ->', twoSum([2,4,5,9,13], 100)) # OUTPUT: Two Sum -> []

A straightforward application of Kadane's algorithm. Sharing my solution in Python below:

def maximumSubarray(nums):
  localMax = globalMax = nums[0]
  for ind, num in enumerate(nums[1:]):
    localMax = max(num, num + localMax)
    globalMax = max(localMax, globalMax)

  return globalMax

Test code

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print('Maximum sum subarray ->' ,maximumSubarray(nums))
# OUTPUT: Maximum sum subarray -> 6

This question is very similar to the "Merge Intervals" question. Sharing my solution in Python below.

Order Class

class Order:
  def __init__(self, orderID, items):
    self.orderID = orderID
    self.items = items

  def __repr__(self):
    return '{}->Items{}'.format(self.orderID, self.items)

Group Orders Function

def groupOrders(orders):
  # First sort the items so that we can optimally merge them
  orders.sort(key=lambda o: o.items)

  res = [orders[0]]

  # Iterate through the orders
  for currentOrder in orders[1:]:

    # Represents the overlap / commonality between two orders
    # If overlap is found, then merge them and create a new order with the union of them
    # Else, simply append it to the end of the array.
    foundMerge = False

    for ind2, groupedOrder in enumerate(res):
      overlap = set(currentOrder.items) & set(groupedOrder.items)

      if overlap:
        # If the orderId is already a list, just append, ex:- [O1, O2], O3 -> [O1, O2, O3]
        if type(groupedOrder.orderID) is list:
           groupedOrder.orderID.append(currentOrder.orderID)

        else: # If not a list, create a new list, ex:- O1, O2 -> [O1, O2]
          groupedOrder.orderID = [groupedOrder.orderID , currentOrder.orderID]

        res[ind2] = Order(  groupedOrder.orderID ,
                           set(currentOrder.items) | set(groupedOrder.items) )
        foundMerge = True
        break

    # If there was no overlap, simply append at the end of the array
    if not foundMerge:
      res.append(currentOrder)

  # Return only the orderID as the output
  return [x.orderID for x in res]

Test Code

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['C', 'D'])]
print(groupOrders(orders)) # ['O1', 'O2']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['A', 'D'])]
print(groupOrders(orders)) # [['O1', 'O2']]

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['B', 'C']),
           Order('O3', ['D', 'E']) ]
print(groupOrders(orders)) # [['O1', 'O2'], 'O3']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['C', 'D']),
           Order('O3', ['E', 'F']) ]
print(groupOrders(orders)) # ['O1', 'O2', 'O3']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['A', 'D']),
           Order('O3', ['A', 'E']) ]
print(groupOrders(orders)) # [['O1', 'O2', 'O3']]

Here's the rough idea with half-working code in Python. The idea is simple and mainly involved serializing and deserializing.

import json
import psycopg2

jsonData = '''
{
    "data": [
    {
        "source": "A", 
        "target": "B", 
        "distance": 6
    }, 
    {
        "source": "A", 
        "target": "E", 
        "distance": 4
    }, 
    {
        "source": "B", 
        "target": "A", 
        "distance": 6
    }, 
    {
        "source": "B", 
        "target": "C", 
        "distance": 2
    }, 
    {
        "source": "B", 
        "target": "D", 
        "distance": 4
    }, 
    {
        "source": "C", 
        "target": "B", 
        "distance": 3
    }, 
    {
        "source": "C", 
        "target": "D", 
        "distance": 1
    }
]
}
'''
# Serialize the data
serializedData = json.dumps(jsonData)
# Connect to the database
conn = psycopg2.connect(database=db, user=user, password=password, host=host, port=port)
cursor = conn.cursor()
# Insert the data
cursor.execute('INSERT INTO GRAPH VALUES %s' % (serializedData))

conn.commit()
conn.close()

# Deserialize the data to find shortest path
graphData = json.loads(serializedData)
graph = buildGraph(graphData)
sourceVertex = 'A'
print(dijkstra(graph, sourceVertex))

Outlining a simple two-pass approach with dictionary/hashmap. TC:- O(n) and SC:- O(n) where n = number of elements.

Solution in Python:

def findMax(head):
  counter = collections.defaultdict(int)
  curr = head
  # First pass puts the values along with the counts in the map
  while curr != None:
    counter[curr.data] += 1
    curr = curr.next

  # Second pass obtains the value with the highest count
  # and iterates through the dictionary to find the correct element.
  maxCount = max(counter.values())
  curr = head
  while curr != None:
    if counter[curr.data] is maxCount:
      print(f'Element {curr.data} is the maxElement occuring {maxCount} times.')
      break
    curr = curr.next

Test code:

import collections
class Node:
  def __init__(self, data):
    self.next = None
    self.data = data

class SinglyLL:
  def __init__(self):
    self.head = None

  def constructSinglyLL(self, data):
    if self.head is None:
      self.head = Node(data)
    else:
      curr, prev = self.head, None
      while curr != None:
        prev = curr
        curr = curr.next
      prev.next = Node(data)
    return self.head

# Construct 1 2 3 4 2 3 2
singlyLL = SinglyLL()
head1 = None
for node in [1,2,3,4,2,3,3,2]:
  head1 = singlyLL.constructSinglyLL(node)
findMax(head1)

# Construct 4 3 5 3 4 5
singlyLL = SinglyLL()
head2 = None
for node in [4,3,5,3,4,5]:
  head2 = singlyLL.constructSinglyLL(node)
findMax(head2)

'''
OUTPUT:
Element 2 is the maxElement occuring 3 times.
Element 4 is the maxElement occuring 2 times.
'''

This sounds awfully lot like a homework problem.

A very large value is typically used for Hashcodes to avoid collisions. Simply put, a larger range provides more values, thereby preventing collisions.

I present two solutions to the above problem.
Appr 1:- We can essentially scan through the entire array and perform a linear search. But this would take O(n) time complexity and O(1) SC.

Appr 2:- Since the number is sorted, we can do a modified binary search and reduce search space at every step. This would take O(logn) and O(1) SC.

I present both solutions in Python below:

def findFirstOccLinear(nums, target):
  for ind, num in enumerate(nums):
    if num == target:
      return ind
  return -1

def findFirstOccurenceBS(nums, target):
  index = -1
  l, r = 0, len(nums) - 1
  while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target:
      index = mid
      r = mid - 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      l = mid + 1
   return index

The guy probably failed his interview which is why he probably has quit()? :P

Awesome suggestions! Thank you!

First Approach: Perform a dfs or bfs on the tree and retrieve the results. Check whether all of them are the same element. Second approach: As you are traversing, use a set or hash map to make sure they are all the same elements and if they are different return False.

Simple solution in Python outlining the first approach:

def preOrderRecursive(root):
  res = []
  def helper(root, res):
    if not root:
      return

    res.append(root.val)
    for child in root.children:
      helper(child, res)

  helper(root, res)
  return res

def isUnivalTree(root):
  result = preOrderRecursive(root)
  return all(result[0] == x for x in result[1:])

Test code:

class Node:
  def __init__(self, val):
    self.val = val
    self.children = []

'''
Construct the following tree:
            1
          / | \
        1   2  1
            /\  \
            1 3  1
'''
root = Node(1)
root.children = [Node(1), Node(2), Node(1)]
root.children[1].children = [Node(1), Node(3)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: False

'''
Construct the following tree:
            1
          / | \
        1   1  1
            /\  \
            1 1  1
'''
root = Node(1)
root.children = [Node(1), Node(1), Node(1)]
root.children[1].children = [Node(1), Node(1)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: True

Very similar to binary tree traversal but use an array of children as opposed to left and right. Complete solution in Python:

Recursive Solution in Python:

def preOrderRecursive(root):
  res = []
  def helper(root, res):
    if not root:
      return

    res.append(root.val)
    for child in root.children:
      helper(child, res)

  helper(root, res)
  return res

Iterative Solution in Python:

def preOrderIterative(root):
  st = []
  st.append(root)
  res = []
  while len(st):
    curr = st.pop()
    res.append(curr.val)
    for child in reversed(curr.children):
      st.append(child)
  return res

Test Code:

class Node:
  def __init__(self, val):
    self.val = val
    self.children = []

'''
Construct the following tree:
            1
          / | \
        2   3  6
            /\  \
            4 5  7
'''
root = Node(1)
root.children = [Node(2), Node(3), Node(6)]
root.children[1].children = [Node(4), Node(5)]
root.children[2].children = [Node(7)]

print(preOrderRecursive(root)) # Output: [1, 2, 3, 4, 5, 6, 7]
print(preOrderIterative(root)) # Output: [1, 2, 3, 4, 5, 6, 7]

@Silvimasss, checking whether they are digits is not enough since ip addresses always fall between ranges 0 - 255. So, you have to check that as well.

Elegant solution in Python:

def isValidIP(ip):
    parts = ip.split('.')
    if len(parts) != 4:
        return False
    if any(part.isalpha() for part in parts):
        return False
    return all(0 <= int(part) <= 255 for part in parts)

Test code:

valid, invalid = [], []
ip_addresses = ["192.100.0.1", "10.0.0.1", "aa.bb.cc.dd", "10.0", "999.10.10.1"]
for ip_addr in ip_addresses:
     valid.append(ip_addr) if isValidIP(ip_addr) else invalid.append(ip_addr)

print 'Valid IPs = ', valid
print 'Invalid IPs = ', invalid
'''
OUTPUT:
Valid IPs =  ['192.100.0.1', '10.0.0.1']
Invalid IPs =  ['aa.bb.cc.dd', '10.0', '999.10.10.1']
'''

Use two pointers, one for iterating through the array and another one for maintaining the last seen zero index. Every time you see a non-zero index, swap it with the previous seen zero index. Simple solution in Python

Solution:

def moveZeroes(arr):
    i, j = 0, 0
    while i < len(arr):
        if arr[i] != 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1
        i += 1
    return arr

Test code:

print(moveZeroes([0, 3, 1, 0, 2, 6, 7, 0])) # Output: [3, 1, 2, 6, 7, 0, 0, 0]
print(moveZeroes([0,0,1,0,0])) # Output: [1, 0, 0, 0, 0]
print(moveZeroes([0,3])) # Output: [3, 3]

UIThread -> This is the singular main thread which runs when Android first launches and triggers Application.onStart().

Services are processes which run on the main thread by default, but they can be pushed to the background. If intensive services run on the main thread, they can be Blocking (usually networking operations and such). So, in that case, it is much better to put networking operations on the background thread and use that instead of using the main or the UIThread.

Here is also a recursion version of the same idea in Python.

Solution (Recursive):

def printFunctionRecursive(functions):

    def recursiveHelper(functions, indendationLevel = 1, hasSubFunction = False):
        if '->' not in functions:
            print(' ' * indendationLevel + functions + ' start')
            if not hasSubFunction: # Single function
                print(' ' * indendationLevel + functions + ' end')

        else:
            stackTrace = functions.split('->')
            for sub_funcs in stackTrace:
                indendationLevel += 2
                recursiveHelper(sub_funcs, indendationLevel, True)
                print(' ' * indendationLevel + sub_funcs + ' end')

    for stackTrace in functions:
        recursiveHelper(stackTrace)

Test code:

printFunctionRecursive(['main->foo->bar', 'main2'])
'''
Output:
   main start
   main end
     foo start
     foo end
       bar start
       bar end
 main2 start
 main2 end

Use a stack or recursion to keep track of the function calls. This is very similar to printing the directory structure of a folder. I assume we are given a string which represents the function and I assume we are also given a marker which denotes whether this function calls other functions or is just a standalone function. For the sake of assumption, I assume '->' is the marker which denotes that this function will call other functions. I present my solution in Python below using an explicit stack.

Solution:

def printFunction(functions):
    functionStack = []
    for function in functions:
        if '->' in function:
            callStack = function.split('->')
            indentLevel = 0
            # Push the functions to stack
            for f in callStack:
                functionStack.append((indentLevel, f))
                print('%s %s start' % (' ' * indentLevel, f))
                indentLevel += 2

            # Pop the functions off the stack
            while len(functionStack):
                functionInfo = functionStack.pop()
                print('%s %s end' % (' ' * functionInfo[0], functionInfo[1]))
        else:
            print('%s start' % function)
            print('%s end' % function)

Test code:

printFunction(['main->foo->bar', 'main2'])
'''
Output:
 main start
   foo start
     bar start
     bar end
   foo end
 main end
main2 start
main2 end
'''

You can probably start out with the smallest flow [s1, s2] from the coffee machine. You would then compare the differences of [c1,c2] with [s1, s2], [m1, m2], [l1, l2]. Then, you could see that if the differences were negative i.e l1 > c1 or l2 > c2, it might overflow, so you wouldn't choose that particular intake flow. Like this, you can calibrate and choose the particular range (small, medium, or large) and still filling the cup.

@Mehdi. Haha true. I think he just gets the interview questions from various companies and posts them. I don't think he physically attends that many interviews or I might be wrong. Or he might be the interviewer himself and might share the questions. :P :D

@Andy. Excellent catch man! Thank you for pointing that out. :)

The tricky part of this problem is to make random() O(1). To achieve this, use a set/hashmap to achieve O(1) insertions/deletions. To obtain O(1) for random, use an auxiliary list and return a random index from the list. Another tricky part is to keep the list in sync with the hashmap/set. To achieve this swap the quote with the last element and then remove the element when you select the random() quote.

I have provided a toy example which represents this idea:

Solution in Python Below:

from random import randint

class QuoteManager:
    def __init__(self):
        self.quoteToIndicesMap = {}
        self.quotes = []

    def add(self, quote):
        if quote not in self.quoteToIndicesMap:
            # Add it
            self.quotes.append(quote)
            self.quoteToIndicesMap[quote] = len(self.quotes) - 1 # index
            return True
        return False # Already there return False

    def random(self):
        if len(self.quotes) == 0:
            print('All quotes are exhausted!')
            return 'INVALID!!'

        # Key trick is to swap with last element
        # and then delete it

        # Swap it with last position
        lastQuote = self.quotes[-1]
        randomIndex = randint(0, len(self.quotes) - 1)
        self.quotes[randomIndex], self.quotes[-1] = self.quotes[-1], self.quotes[randomIndex]

        # Delete it from list and the hashmap
        quoteToPop = self.quotes.pop()
        self.quoteToIndicesMap[lastQuote] = randomIndex
        del self.quoteToIndicesMap[quoteToPop]
        # Return the random quote
        return quoteToPop

Test code:

# Test code
q = QuoteManager()
print(q.add('Quote 1')) # True
print(q.add('Quote 2')) # True
print(q.add('Quote 3')) # True
print(q.add('Quote 4')) # True
print(q.add('Quote 1')) # False
print(q.random()) # Quote 2
print(q.random()) # Quote 4
print(q.random()) # Quote 3
print(q.random()) # Quote 1
print(q.random()) # All quotes are exhausted! INVALID!

Evaluate the product of the list and keep popping it off until the list is not empty.
Solution in Python:

class CartesianIterator:
  def __init__(self, sets):
    self.result = [[]]
    for pool in sets:
      self.result = [x + [y] for x in self.result for y in pool]

  def hasNext(self):
    return len(self.result) != 0

  def next(self):
    return self.result.pop(0)

Test Code:

Test code
# Example 1
c = CartesianIterator([[1,2,3], [4,5]])
while c.hasNext():
  print(c.next(), end=', ')
print()

# Example 2
c = CartesianIterator([['a','b','c'], ['p', 'q'], ['r', 's']])
while c.hasNext():
  print(c.next(), end=', ')
print()

Output:

[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5],

['a', 'p', 'r'], ['a', 'p', 's'], ['a', 'q', 'r'], ['a', 'q', 's'], ['b', 'p', 'r'], ['b', 'p', 's'], ['b', 'q', 'r'], ['b', 'q', 's'], ['c', 'p', 'r'], ['c', 'p', 's'], ['c', 'q', 'r'], ['c', 'q', 's'],

Given a current sim location, I would radially start exploring the presence of another sim. This means first looking at radius increments of 1,2,3, etc... (i.e look 1unit right / 1 unit left, then 2 units right / 2 units left, etc..) until another sim is found. Once we know the direction in which the other sim is found, we can start moving in that direction by calling moveLeft() or moveRight(). This way, eventually, both sims will collide. I have outlined a simple solution in Python below:

Solution:

def collide():
  # Mark current location
  currSim.markPosition()

  # Radially search for another marked location
  # (this indicates the presence of another sim)
  isRight = True
  increment = 1
  while True:
    rightLocation = currentLocation + increment
    leftLocation = currentLocation - increment
    if isCurrentLocationMarked(rightLocation):
      break
    elif isCurrentLocationMarked(leftLocation):
      isRight = False
      break
    increment += 1

  # If another sim is towards right
  # move right
  if isRight:
    currSim.moveRight()
    currSim.markPosition()
  else: # else move left
    currSim.moveLeft()
    currSim.markPosition()

Use a priority queue and insert elements into the queue as you go along and call next. Posting my solution below in Python:

from queue import PriorityQueue

class SuperIterator:
  def __init__(self, iterators):
    self.sortedQueue = PriorityQueue()
    for iterator in iterators:
      self.sortedQueue.put((next(iterator), iterator))

  def hasNext(self):
    return self.sortedQueue.qsize() != 0

  def next(self):
    value, iterator = self.sortedQueue.get()
    try:
      next_value = next(iterator)
      self.sortedQueue.put((next_value, iterator))
    except StopIteration:
      pass
    return value

Test code:

# Test code
# Example 1
list1 = [1, 4, 5,20]
list2 = [2,10,12,50]
s = SuperIterator([iter(list1), iter(list2)])
while s.hasNext():
  print(s.next(), end=', ')
print()
# Output: 1, 2, 4, 5, 10, 12, 20, 50,

# Example 2
list1 = [12,14,16]
list2 = [4,7,9,50,100]
list3 = [6,8,10,13]
s = SuperIterator([iter(list1), iter(list2), iter(list3)])
while s.hasNext():
  print(s.next(), end=', ')
print()
# Output: 4, 6, 7, 8, 9, 10, 12, 13, 14, 16, 50, 100,

Fairly straightforward problem. The only clarification we might need is if to include the second LL's element in the last interleaving (i.e whether to include 40) but going by your example, it doesn't seem to be the case. This solution is expressed in Python below.

Solution:

def interleaveLL(head1, head2):
  dummy = curr = Node(None)

  while head1 != None:
    # Append head1 and move its pointer forwards
    curr.next = head1
    curr = curr.next
    head1 = head1.next
    if head1 is None:
      break # If end of head then break

    # Append head2 and move its pointer forwards
    curr.next = head2
    curr = curr.next
    head2 = head2.next

  return dummy.next

Test code:

def printLL(head):
  curr = head
  while curr:
    print(curr.data, end='->')
    curr = curr.next
  print()

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None


head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)

head2 = Node(10)
head2.next = Node(20)
head2.next.next = Node(30)
head2.next.next.next = Node(40)
head2.next.next.next.next = Node(50)
head2.next.next.next.next.next = Node(60)

printLL(interleaveLL(head1, head2))
'''
Output:
1->10->2->20->3->30->4->
'''

Use two stacks, one for operands and one of operators. Whenever you notice parenthesis, take special action. Solution in Python below:

def evaluateInfix(expr):

  def helper(operator, x, y):
    if operator == '+': return x + y
    if operator == '-': return x - y
    if operator == '/': return y // x
    if operator == '*': return x * y

  operandStack = [] # for numbers
  operatorStack = [] # for arithmetic operators and parens.
  operators =  {
    '/': 1,
    '*': 1,
    '+': 2,
    '-': 2
  }
  for token in expr:

    if token.isdigit():
      operandStack.append(token)
    elif token == '(':
      operatorStack.append(token)

    elif token == ')':
      while operatorStack[-1] != '(':
        operandStack.append()

    elif token == ')':
      while operatorStack[-1] != '(':
        result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
        operandStack.append(result)
      operatorStack.pop()

    elif token in operators:
      while len(operatorStack) and operators[operatorStack[-1]] <= operators[token]:
        result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
        operandStack.append(result)

      operatorStack.append(token)

  while len(operatorStack):
    result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
    operandStack.append(result)

  return operandStack.pop()

Test Code:

print(evaluateInfix('2 + 3 * 5')) # 17
print(evaluateInfix('4 * 5 / 2')) # 10

@sbdul. Great approach. Using union find sounds cool! :)

The trickiest part about this problem is that random has to be O(1). We can achieve this by using a list + dictionary to keep a track of the servers. The removal operation will be tricky since we have to swap it with the last element and then pop it to obtain constant time. I present my solution below in Python with test code.

Solution:

import random
class Pool:
  def __init__(self):
    self.servers = []
    self.serverIndices = {}

  def addServer(self, serverNumber):
    if serverNumber not in self.serverIndices:
      self.servers.append(serverNumber)
      self.serverIndices[serverNumber] = len(self.servers)-1
      return True
    return False

  def deleteServer(self, serverNumber):
    if serverNumber in self.serverIndices:
      # Key trick is to swap with last element
      # and then delete it
      index = self.serverIndices[serverNumber]
      lastNumber = self.servers[-1]
      self.servers[-1] = serverNumber # Place it at last index

      # Remove it from the list and the hashmap
      self.servers.pop() # Remove the server
      del self.serverIndices[serverNumber]

      # Update the servers list and the hashmap
      if index != len(self.servers):
        self.servers[index] = lastNumber
        self.serverIndices[lastNumber] = index

      return True
    return False

  def getRandomServer(self):
    return self.servers[random.randint(0, len(self.servers)-1)]

  def __repr__(self):
    return 'Current pool: ' + str(self.servers)

Test Code:

# Test Code
p = Pool()
# Add servers
p.addServer(5)
p.addServer(3)
p.addServer(2)
p.addServer(10)
p.addServer(6)

# Print servers
print(p) # Current pool: [5, 3, 2, 10, 6]

# Get Random servers
print('Random server:', p.getRandomServer()) # Random server: 2
print('Random server:', p.getRandomServer()) # Random server: 5
print('Random server:', p.getRandomServer()) # Random server: 5

# Remove Servers
print(p.deleteServer(3)) # True
print(p.deleteServer(10)) # True
print(p.deleteServer(5)) # True
print(p.deleteServer(3)) # False
print(p.deleteServer(999)) # False
print(p) # Current pool: [2, 6]

# Get random servers
print('Random server:', p.getRandomServer()) # Random server: 6
print('Random server:', p.getRandomServer()) # Random server: 6

Elegant 4 line solution in Python (for small strings of course):

def sortStrings(strs, col):
  data = [tuple(word.split()) for word in strs]
  data = [(first_name, last_name, int(age)) for first_name, last_name, age in data]
  result = sorted(data, key=lambda x: x[col-1])
  return result

Test Code:

strings = ['john doe 33', 'smith black 9', 'diana yale 12']
print(sortStrings(strings, 1)) # Order by first name
print(sortStrings(strings, 2)) # Order by last name
print(sortStrings(strings, 3)) # Order by age
'''
Output:
[('diana', 'yale', 12), ('john', 'doe', 33), ('smith', 'black', 9)]
[('smith', 'black', 9), ('john', 'doe', 33), ('diana', 'yale', 12)]
[('smith', 'black', 9), ('diana', 'yale', 12), ('john', 'doe', 33)]
'''

However, in a distributed setting, when we have large amounts of strings to process, we can divide up the column that we are trying to sort by and process per chunks. We would create multiple chunks and use a sorting algorithm such as quicksort or mergesort to combine the data into a sorted order.

In case, some of you all want to test it, here are the helper functions I coded for my above solution:

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None
    
def insertAtBeggining(head, value):
  if head is None:
    head = Node(value)
  else:
    tempNode = Node(value)
    tempNode.next = head
    head = tempNode
  return head

def reverseLL(head):
  # Creates a new LL and returns the head
  # instead of modifying it in place
  stack = []
  curr = head
  while curr != None:
    stack.append(curr.value)
    curr = curr.next

  newHead = curr = Node(None)
  while len(stack):
    elem = stack.pop()
    if curr is None:
      curr = Node(elem)
    else:
      curr.next = Node(elem)
      curr = curr.next
  return newHead.next

def getLengthofLL(head):
  counter = 0
  while head != None:
    counter += 1
    head = head.next
  return counter

def constructLinkedList(word):
  head = curr = Node(None)
  for char in word:
    if curr is None:
      curr = Node(char)
    else:
      curr.next = Node(char)
      curr = curr.next
  return head.next

def printLL(head):
  curr = head
  while curr != None:
    print(curr.value, end='->')
    curr = curr.next
  print()

Scan from end of the string and compare each character in the word. I assume that we are given a singly linked list and I also assume we are given helper functions such as reverseLinkedList(), insertAtBeginning, length(), etc. The idea is pretty straightforward, compare each character from end and if they are different break, else append the result. If there are no common characters which are suffixes, return the minimum length of the two linked lists. I present a solution in Python below. The time complexity is O(n) where n is the length of the longest suffix.

Solution:

def longestCommonSuffix(str1, str2):
  suffix = None
  str1rev, str2rev = reverseLL(str1), reverseLL(str2)
  str1Len, str2Len = getLengthofLL(str1), getLengthofLL(str2)

  while str1rev and str2rev:
    if str1rev.value != str2rev.value:
      break

    suffix = insertAtBeggining(suffix, str1rev.value)
    str1rev = str1rev.next
    str2rev = str2rev.next

  if not suffix:
    if str1Len < str2Len:
      return str1
    else:
      return str2
  else:
    return suffix

Test code:

# Test code
str1 = constructLinkedList('walking')
str2 = constructLinkedList('listening')
rev = longestCommonSuffix(str1, str2)
printLL(rev) # Outputs 'i->n->g->'

str3 = constructLinkedList('party')
str4 = constructLinkedList('partying')
rev = longestCommonSuffix(str3, str4) # Outputs 'p->a->r->t->y->'
printLL(rev)

This problem is essentially summing a subarray/part of an array of nums from 1..len(nums). To do this, the only tricky part is to find out the starting index to sum and the how many elements to do so. Luckily, we can easily do this using the triangular numbers formula and we are also given an n. This leads to a simple solution. I present my 4-line solution in Python below.

Elegant Solution (Python):

def getNthRowSum(n):
  n = n - 1 # Since we offset by 0
  if n == 0:
    return 1 # First row
  starting_ind = (n*(n+1)//2)+1 # Adding 1 since arrays/lists start at 0
  return sum(range(starting_ind, starting_ind+n+1))

Test code:

for i in range(1, 7):
  print('%dth row: Sum = %d' % (i, getNthRowSum(i)))
'''
Output:
1th row: Sum = 1
2th row: Sum = 5
3th row: Sum = 15
4th row: Sum = 34
5th row: Sum = 65
6th row: Sum = 111
'''

I present a simple solution in Python below. Using a double-ended queue for O(1) pop/append times.

Solution:

from collections import deque
class PeekIterator:
  def __init__(self, nums):
    self.result = deque(nums)

  def peek(self):
    return self.result[0]

  def next(self):
    return self.result.popleft()

  def hasNext(self):
    return len(self.result) > 0

Test code:

p = PeekIterator([2,3,6,7,10,12])
while p.hasNext():
  print('Elem at top of stack = ', p.peek(), end=', ')
  print('and now popping elem using next: ', p.next())
'''
Output:
Elem at top of stack =  2, and now popping elem using next:  2
Elem at top of stack =  3, and now popping elem using next:  3
Elem at top of stack =  6, and now popping elem using next:  6
Elem at top of stack =  7, and now popping elem using next:  7
Elem at top of stack =  10, and now popping elem using next:  10
Elem at top of stack =  12, and now popping elem using next:  12
'''

Assuming we have to implement next() and hasNext() methods (just like traditional iterators), I propose the following solution. I am using a deque since removing/adding elements to the front or back of the structure is O(1). I also assume in the implementation that the user specifies the limit or the first 'n' fibonacci numbers that he wishes to see.

Solution:

from collections import deque
class FibonacciIterator:
  def __init__(self, limit):
    self.results = deque([0, 1])
    self.curPos = 0
    self.limit = limit

  def hasNext(self):
    return self.curPos < self.limit

  def next(self):
    firstNum = self.results.popleft()
    self.curPos += 1
    self.results.append(self.results[0] + firstNum)
    return firstNum

Test Code:

f = FibonacciIterator(15) # Want the first 15 fib numbers
while f.hasNext():
  print(f.next(),end=', ')
print()
# Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,

A simple solution for this problem is to store and generate 5 random indices from 0 - length of the array. Store these 5 indices, keep advancing the iterator, if you find that the iter position is equal to one of the indices, add that to the result. I present my solution below:

import random
def sample5Elements(nums, sampleSize=5):
  randomIndices = set()
  # Construct a set with random 5 indices
  while len(randomIndices) != sampleSize:
    randomIndex = random.randint(0, len(nums) - 1)
    if randomIndex not in randomIndices:
      randomIndices.add(randomIndex)

  counter = 0
  res = []
  # Obtain an iterator for the array
  nums_it = iter(nums)
  while counter < len(nums):
    elem = next(nums_it)
    if counter in randomIndices:
      res.append(elem)
    counter += 1
  return res

nums = list(range(1, 21)) # Generate nums from 1 - 20
print('Random 5 elements:', sample5Elements(nums))
# Output:- Random 5 elements: [1, 2, 6, 9, 11]

Simply iterate from 1 through n and n % i == 0, print the number. Elegant one liner in python below:

def getAllFactors(n):
  return [i for i in range(1, n+1) if n % i == 0]

Test code:

print(getAllFactors(12)) # Prints [1, 2, 3, 4, 6, 12]

The idea is to use a hashtable or a set for this problem. When the store is called, we store all the numbers into the set. This gives us constant O(1) access time. When we are testing whether the target exists in the set, we simply compute its complement and check whether it exists in the set which amounts to O(n) time complexity. I present my solution in Python below:

Solution:

class StoreNums:
  def __init__(self):
    self.numSet = set()

  # TC:- O(1) since we are using a hashable set
  def store(self, num):
    if num in self.numSet:
      return False
    else:
      self.numSet.add(num)
      return True

  # TC:- O(n) where n = number of nums stored
  def test(self, target):
    for num in self.numSet:
      complement = target - num
      if complement in self.numSet:
        return True
    return False

Test code:

# Test code
s = StoreNums()
print(s.store(1)) # True
print(s.store(3)) # True
print(s.store(5)) # True
print(s.store(3)) # False
print(s.store(6)) # True
print(s.test(4)) # True
print(s.test(5)) # False
print(s.test(6)) # True

Since we know the maximum result can be three digits i.e 12 * 12 = 144, we can use the string formatting function when printing our output to correctly align the output. In this case, we have 3 digits as our max length, so we can format it in that particular way.

Solution:

def printMultiplicationTableFor12():
  for row in range(1, 13):
    for col in range(1, 13):
      print('{:3} '.format(row * col),end='')
    print()

Test code:

printMultiplicationTableFor12()

'''
Output:
  1   2   3   4   5   6   7   8   9  10  11  12 
  2   4   6   8  10  12  14  16  18  20  22  24 
  3   6   9  12  15  18  21  24  27  30  33  36 
  4   8  12  16  20  24  28  32  36  40  44  48 
  5  10  15  20  25  30  35  40  45  50  55  60 
  6  12  18  24  30  36  42  48  54  60  66  72 
  7  14  21  28  35  42  49  56  63  70  77  84 
  8  16  24  32  40  48  56  64  72  80  88  96 
  9  18  27  36  45  54  63  72  81  90  99 108 
 10  20  30  40  50  60  70  80  90 100 110 120 
 11  22  33  44  55  66  77  88  99 110 121 132 
 12  24  36  48  60  72  84  96 108 120 132 144 
'''

A simple regex of the form \(?\d{3}\)?-(\d{3})-(\d{4}) will do for this problem. The idea is to compile or apply the regex to the text contained in various files from the directory. I present a simple solution in Python using regex below. I have used the verbose option to explain each symbol in my regex for clarity:

My solution:

import re
def findPhoneNumbers(text):
  phoneNumberPattern = re.compile(r'''
    \(?     # The particular regex might optionally start with a (
    (\d{3})   # Followed by the area code
    \)?     # Followed optionally by a parenthesis
    -       # Followed by a hyphen
    (\d{3}) # Followed by three digits 
    -       # And a hyphe
    (\d{4}) # And last 4 digits
    ''', re.VERBOSE)
  return phoneNumberPattern.findall(text)

Test code:

text = r'''
<p><b>This is a text string. Phone number is (111)-111-1111.
</b>This is a second phone number which follows a different format of 222-222-2222.</p>
<b>But if I have a phone number which is of the format 333.333.3333, then my regex shouldn't find it.
'''
print(findPhoneNumbers(text))

Output:

[('111', '111', '1111'), ('222', '222', '2222')]

Linked list is used in the case where you care about fast insertions and lookups are not performed that often. Due to insertions being constant time, the linked list does not need to resize as necessary but instead just append the node at the end or beginning of the linked list. This makes them a very flexible data structure.

On the other hand, an array is used when lookup via indexing is performed often. In this case, lookups give constant time but the downside is resizing or inserting elements into the array. Another advantage of arrays is that arrays offer is binary search for lookups in the case where the array is sorted. Unfortunately, with linked lists binary search can not be used.