Consider a sequence `u` where u is defined as follows:

1. The number `u(0) = 1` is the first one in `u`.
2. For each `x` in `u`, then `y = 2 * x + 1` and `z = 3 * x + 1` must be in `u` too.
3. There are no other numbers in `u`.

Ex: 
`u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]`

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

## Task: 
Given parameter `n` the function `dbl_linear` (or dblLinear...) returns the element `u(n)` of 
the ordered (with <) sequence `u` (so, there are no duplicates).

## Example:
`dbl_linear(10) should return 22`

## Note:
Focus attention on efficiency

Difficulty: interview

Starter code:

def dbl_linear(n):
	

Solutions:
from collections import deque

def dbl_linear(n):
    h = 1; cnt = 0; q2, q3 = deque([]), deque([])
    while True:
        if (cnt >= n):
            return h
        q2.append(2 * h + 1)
        q3.append(3 * h + 1)
        h = min(q2[0], q3[0])
        if h == q2[0]: h = q2.popleft()
        if h == q3[0]: h = q3.popleft()
        cnt += 1



from collections import deque

def dbl_linear(n):
    u, q2, q3 = 1, deque([]), deque([])
    for _ in range(n):
        q2.append(2 * u + 1)
        q3.append(3 * u + 1)
        u = min(q2[0], q3[0])
        if u == q2[0]: q2.popleft()
        if u == q3[0]: q3.popleft()
    return u

def dbl_linear(n):
  num_list = [1]
  for i in num_list:
    num_list.append((i * 2) + 1)
    num_list.append((i * 3) + 1)
    if len(num_list) > n *10:
      break
  return sorted(list(set(num_list)))[n]

def dbl_linear(n):
    u = [1]
    i = 0
    j = 0
    while len(u) <= n:
        x = 2 * u[i] + 1
        y = 3 * u[j] + 1
        if x <= y:
            i += 1
        if x >= y:
            j += 1
        u.append(min(x,y))
    return u[n]

# This is a Python implementation of the excellent algorithm user g964 wrote in C. Credit goes to him/her.

def dbl_linear(n):
    arr = [1]
    xi = yi = 0
    
    for i in range(n):
        x,y = arr[xi]*2+1, arr[yi]*3+1 
        arr.append( min(x,y) )
        if min(x,y) == x:
            xi += 1
        if min(x,y) == y:
            yi += 1
    return arr[n]

def dbl_linear(n):
    u, i, c = {1}, 0, 1
    while i < n:
        if c / 2 in u or c / 3 in u:
            u.add(c + 1)
            i += 1
        c += 1
    else:
        return c

def dbl_linear(n):
    """Brute force first loop populates the set of u.  The second loop 
    fills any gaps"""
    r = {1}
            
    while len(r) <= n:
        q = sorted(list(r))
        r.update([e * 2 + 1 for e in q] + [e * 3 + 1 for e in q])

    for _ in range(3):
        q = sorted(list(r))[:n]
        r.update([e * 2 + 1 for e in q] + [e * 3 + 1 for e in q])
        
    return sorted(list(r))[n]

from bisect import insort

def dbl_linear(n):
    u = [1]
    u0 = 123
    for i in range(n):
        while u[0] == u0:
            u.pop(0)
        u0 = u.pop(0)
        insort(u, 2*u0+1)
        insort(u, 3*u0+1)
    return u[0]

def dbl_linear(n):
    x = 1
    ys = []
    zs = []

    for i in range(n):
        ys.append(2*x + 1)
        zs.append(3*x + 1)
        miny = ys[0]
        minz = zs[0]
        x = miny if miny < minz else minz
        if x == miny: ys.pop(0)
        if x == minz: zs.pop(0)

    return x


def dbl_linear(n):
    u = [1]
    indexY = 0
    indexZ = 0
    y = lambda x: 2*x + 1
    z = lambda x: 3*x + 1
    while len(u) <= n:
        if y(u[indexY]) < z(u[indexZ]): 
            if y(u[indexY]) != u[len(u) - 1]: u.append(y(u[indexY]))
            indexY += 1
        else:
            if z(u[indexZ]) != u[len(u) - 1]: u.append(z(u[indexZ]))
            indexZ += 1
    return u[n]