Interview Help

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def jumpingOnClouds(c):
    pointer,jumps = 0,0
    while pointer<(len(c)-2):
        pointer = pointer + 1 if c[pointer+2] else pointer +2
        jumps += 1
    
    if pointer < len(c)-1:
        jumps += 1

    return jumps

1
2
3
4
5
6
7
8

    count=0
    for i in range(len(arr)):
        while(arr[i]!=i+1):
            count+=1
            temp=arr[i]
            arr[i]=arr[temp-1]
            arr[temp-1]=temp 
    return count

1
2
3
4

def makeAnagram(a, b):
    a,b =Counter(a),Counter(b)
    a.subtract(b)
    return sum(abs(i) for i in a.values())

1
2

def alternatingCharacters(s):
    return (len([i for i in range(1,len(s)) if s[i-1] == s[i]]))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

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

class linked_list:
    def __init__(self):
        self.head=None
        self.count=0

    def insertEnd(self, newNode):
        if self.head is None:
            self.head=newNode
        else:
            lastNode=self.head
            while True:
                if lastNode.next is None:
                    break
                lastNode=lastNode.next
            lastNode.next=newNode

    def insertHead(self, newNode):
        tempNode = self.head
        self.head = newNode         
        self.head.next = tempNode        
        del tempNode


    def insertAt(self, newNode, position):
        currentNode=self.head
        currentPosition=0
        while True:
            if currentPosition == position:
                previousNode.next=newNode
                newNode.next=currentNode
                break
            previousNode=currentNode
            currentNode=currentNode.next
            currentPosition += 1

    def deleteEnd(self):
        lastNode=self.head
        while lastNode.next is not None:
            prevNode=lastNode
            lastNode=lastNode.next
        prevNode.next=None

    

    def deleteAt(self, position):
        currentNode=self.head
        currentPosition=0
        while True:
            if currentPosition == position:
                prevNode.next=currentNode.next
                currentNode.next=None
                break
            prevNode=currentNode
            currentNode=currentNode.next
            currentPosition +=1

          
            

    def isEmpty(self):
        if self.head is None:
            return True
        else:
            return False

    def traversal(self):
        currentNode=self.head
        while currentNode is not None:
            print(currentNode.data)
            currentNode=currentNode.next
    

    def deleteHead(self):
        if self.isEmpty() is False:
            prevHead=self.head
            self.head=self.head.next
            prevHead.next=None
            print("The first item is deleted successfully")
        else:
            print("Linked List is empty, Delete Failed")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def factorialList (n):
    if n == 1:
        ansList = [0] * n
        ansList [0] = 1
    else :
        ansList = factorialList(n-1)
        ansList.append(n*ansList[n-2])
    return ansList

value=int (input("Enter the range : "))
print( factorialList ( value ))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def recursiveSum ( aList ):
    return recSum( aList ,0)
def recSum( aList , pos ):
    if pos == len( aList ):
        return 0
    else :
        return aList [ pos ] + recSum( aList , pos+1)

a=[1,2,3,4,5]
print(recursiveSum(a))

1
2
3
4
5
6

def printToN(N):
    if N<1:
        return
    else :
        printToN(N-1)
        print(N)

1
2
3
4
5
6
7

def findMinimum(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return min(lst[0], findMinimum(lst[1:]))
listA = [9,-2,6,1,80,9,-2, -8, 90, -9]
print(findMinimum(listA))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import random  # for testing

# merge sort (naive version) -------------------------------------------


def merge(l,r):
    """Take two *sorted* lists, return the merged result."""
    result=[]
    while len(l)>0 and len(r)>0:
        if l[0] < r[0]:
            result.append(l[0])
            del l[0]
        else:
            result.append(r[0])
            del r[0]
    # one of either l or r may still have elements in; we need
    # to make sure these are included in the result
    result.extend(l)
    result.extend(r)
    return result



def mergesort(xs):
    """Mergesort."""
    if len(xs) <= 1:
        # NOTE list is very small... and already sorted
        return xs
    midpoint = len(xs)//2  # NOTE integer division
    l, r = xs[0:midpoint], xs[midpoint:]
    l2, r2 = mergesort(l), mergesort(r)
    return merge(l2,r2)


# example --------------------------------------------------------------

print("Merge example:",str(merge([4,7,9],[1,2,10,11,12])))


arr=[9,8,1,2,3,7,6,5,1,2,3]
print("Mergesort example: ",str(mergesort(arr)))


# testing -------------------------------------------------------------

def sorted(xs):
    return all(xs[i] <= xs[i+1] for i in range(0,len(xs)-1))

    
arr=[9,8,1,2,3,7,6,5,1,2,3]
for x in range(0,100):
    random.shuffle(arr)
    print("Unsorted:", str(arr))
    arr=mergesort(arr)
    assert sorted(arr)
    print("Sorted!:", str(arr))
    print()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

# simple binary trees --------------------------------------------------

# we represent a binary tree using simple objects
from contextlib import redirect_stdout


class Object(object):
    pass


def node(l, v, r):
    n = Object()
    n.type = "node"
    n.left = l
    n.label = v
    n.right = r
    return n


def copy_node(n1,n2):
    n2.type = n1.type
    n2.left = n1.left
    n2.label = n1.label
    n2.right = n1.right


def leaf(v):
    n = Object()
    n.type = "leaf"
    n.label = v
    return n


def is_leaf(n):
    if n.type == "leaf":
        return True
    else:
        return False

# NOTE really this should be "is_internal_node"
def is_node(n):
    if n.type == "node":
        return True
    else:
        return False


def left(n):
    assert is_node(n)
    return n.left


def label(n):
    if is_node(n):
        return n.label
    else:
        assert is_leaf(n)
        return n.label


def right(n):
    assert is_node(n)
    return n.right


def print_tree(t0):
    def aux(t,n:int):
        print(" "*n,end='')
        if is_leaf(t):
            print(t.label)
        else:
            assert is_node(t)
            print(t.label)
            aux(t.left,n+1)
            aux(t.right,n+1)
    aux(t0, 0)


def tree_to_string(t0):
    s=""
    def aux(t,n:int):
        nonlocal s
        s+=" "*n
        if is_leaf(t):
            s+=str(t.label)+"\n"
        else:
            assert is_node(t)
            s+=str(t.label)+"\n"
            aux(t.left,n+1)
            aux(t.right,n+1)
    aux(t0, 0)
    return s


t2s=tree_to_string


# example tree ---------------------------------------------------------

def example_tree():
    ex = node(
        leaf(2),
        3,
        node(
            leaf(4),
            5,
            leaf(6)))
    return ex


ex = example_tree()


print("Example tree:", tree_to_string(ex),sep='\n')


# subtree_at -----------------------------------------------------------

# take a string like "llrl" which tells you which subtree to go to,
# and return the corresponding subtree in the tree
def subtree_at(s, t):
    # print((s,str(t)))
    if s == "": return t
    if is_leaf(t):
        raise RuntimeError("subtree_at: found a leaf, could not descend further: " + str(t))
    if s[0] == 'l': return subtree_at(s[1:], left(t))
    if s[0] == 'r': return subtree_at(s[1:], right(t))
    raise RuntimeError("subtree_at: unknown character: " + str(s[0]))

with open('ignore.txt', 'w') as f:
    with redirect_stdout(f):
        print("Subtree_at example 1:",tree_to_string(subtree_at("l", ex)))
        print("Subtree_at example 2:",tree_to_string(subtree_at("r", ex)))
        print("Subtree_at example 3:",tree_to_string(subtree_at("rl", ex)))


# leaves -----------------------------------------------------------

def count_leaves(n):
    if is_leaf(n):
        return 1
    else:
        return (count_leaves(left(n)) +
                count_leaves(right(n)))


print("Count_leaves example:", count_leaves(ex))


def leaves(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return leaves(left(t)) + leaves(right(t))


print("Leaves example:", str(leaves(ex)))


# values ---------------------------------------------------------------

# NOTE same as "leaves", except also includes inner node labels
def values(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return values(left(t)) + [label(t)] + values(right(t))


# eval -----------------------------------------------------------------

def eval_(n):
    if is_leaf(n):
        # NOTE we assume a leaf has a value that is an int
        return label(n)
    else:
        v = label(n)
        if v == "+":
            return eval_(left(n)) + eval_(right(n))
        elif v == "*":
            return eval_(left(n)) * eval_(right(n))
        else:
            raise RuntimeError(
                "eval_: unexpected node value: " + str(v))


def eval_test():
    print("Eval leaf(3):", str(eval_(leaf(3))))
    t1 = node(leaf(1),"+",leaf(2))
    print("Eval t1:", str(eval_(t1)))
    t2 = node(leaf(1),"+",
              node(leaf(2),"+",leaf(3)))
    print("Eval t2:", str(eval_(t2)))

eval_test()



# challenge: tree_contains ---------------------------------------------------

def tree_contains(t,i):
    if is_leaf(t):
        return (t.label == i)
    else:
        if t.label == i: return True
        else: return (tree_contains(t.left,i) or
                      tree_contains(t.right,i))


print("Tree contains 1, should be False:", str(tree_contains(ex,1)))
print("Tree contains 3, should be True:", str(tree_contains(ex,3)))





# challenge: nodes_at_level --------------------------------------------------

def nodes_at_level(t,i):
    if i == 0: return [t.label]
    else:
        if is_leaf(t): return []
        else: return (nodes_at_level(t.left,i-1)+
                      nodes_at_level(t.right,i-1))


print("Nodes at level (should be [4,6]):", nodes_at_level(ex,2))




# challenge: nodes_less_than -------------------------------------------

def nodes_less_than(t,i):
    if is_leaf(t):
        if t.label < i: return [t.label]
        else: return []
    else:
        ls = nodes_less_than(t.left,i)
        rs = nodes_less_than(t.right,i)
        if t.label < i:
            at_this_node = [t.label]
        else:
            at_this_node = []
        return at_this_node+ls+rs


print("Nodes less than (should be [3,2,4]):", nodes_less_than(ex,5))


# pre-order ------------------------------------------------------------

def pre_order(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return ([label(t)] +
                pre_order(left(t)) +
                pre_order(right(t)))


print("pre-order example:", str(pre_order(ex)))


# in-order ------------------------------------------------------------

def in_order(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return (in_order(left(t)) +
                [label(t)] +
                in_order(right(t)))


print("in-order example:",str(in_order(ex)))



# binary search tree ---------------------------------------------------

# NOTE some of the leaves may be None!

def bst_insert(t, i0):
    # print(str(t))
    if is_node(t):
        if i0 == label(t): return
        if i0 < label(t):
            bst_insert(left(t), i0)
        else:
            bst_insert(right(t), i0)
    else:
        # we have a leaf with a single value
        assert is_leaf(t)
        v = label(t)
        # NOTE leaf values can now be None
        if v is None:
            t.label = i0  # just replace None with i
        elif i0 == v:
            return  # do nothing
        elif i0 < v:
            new_node = node(leaf(i0), v, leaf(None))
            copy_node(new_node,t)
        else:
            # NOTE i>v
            new_node = node(leaf(None), v, leaf(i0))
            copy_node(new_node, t)
    return


# example --------------------------------------------------------------

import random


def bst_ex1():
    ex = leaf(99)

    for x in range(0, 9):
        i = random.randrange(30)
        print("bst, inserting: " + str(i))
        bst_insert(ex, i)

    print()
    print("bst example")
    print("bst: " + t2s(ex))
    print("bst values: " + str(values(ex)))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

# bst_contains -------------------------------------------------------------

def bst_contains(t, i):
    # uncomment the following to see how bst_contains executes
    # print("bst_contains: looking at: ",t2s(t),sep="\n")  # show how search progresses
    if is_leaf(t):
        return label(t) == i
    else:
        if i == label(t):
            return True
        elif i < label(t):
            return bst_contains(left(t), i)
        else:
            return bst_contains(right(t), i)


# see http://jimblackler.net/treefun/index.html for a way to visualize
# the example tree that follows; also see file tree_example.png
viz="""
99
 17
  11
   5
    2
     1
     None
    None
   13
  23
   None
   26
 None
"""

ex1 = node(
    node(leaf(1),2,leaf(None)),
    5,
    leaf(None))

ex11 = node(
    ex1,
    11,
    leaf(13))

ex2 = node(leaf(None),23,leaf(26))

ex3 = node(ex11,17,ex2)

ex = node(ex3, 99, leaf(None))

print("Example bst:", t2s(ex), sep='\n')


print("Bst_contains 2:",bst_contains(ex, 2))
print("Bst_contains 3:",bst_contains(ex, 3))








# breadth-first -------------------------------------------------------

# breadth-first search/traversal: root, all nodes at depth 1 (from left to right), all at depth 2, etc.

bfs_order=[]

# NOTE "pure" bfs doesn't return anything - bfs is a way of traversing through a tree
def bfs(t0):
    """Traverse a tree in breadth-first order."""
    q=[t0]
    while len(q) > 0:
        t = q[0]
        del q[0]
        # At this point, we do something with the
        # node; for the time being, we just
        # append the label to some global variable
        bfs_order.append(t.label)
        if is_leaf(t): pass
        else: q.append(t.left); q.append(t.right)

bfs(ex)
print("Bfs example 1:", str(bfs_order))


ex = node(
    node(leaf(4),2,leaf(5)),
    1,
    node(leaf(6),3,leaf(7)))

bfs_order=[]  # reset to empty
bfs(ex)

print("Bfs example 2:", str(bfs_order))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

# BFS to find a path through a maze
import csv

maze=[]
with open('maze.txt') as csv_file:
    csv_reader = csv.reader(csv_file, delimiter=',')
    for row in csv_reader:
        maze.append(row)

print(str(maze))

print(maze[0][1])  # row 0, column 1

# assume we start at position 0,0; then we have to get to position ...

rows=len(maze)
cols=len(maze[0])  # assume maze is rectangular
end=(rows-1,cols-1)

def is_empty(x,y):
    # first take care of the blocks that are off the map
    if x<0: return False
    if y<0: return False
    if x>3: return False
    if y>3: return False
    if (maze[x][y]).strip() != "": return False
    else: return True


def bfs_maze0():
    q=[(0,0)]
    while len(q) > 0:
        x,y = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!")
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        q.append((x+dx,y+dy))
        del q[0]

fuel=1000
# we stop searching if we run out of fuel;
# this stops the search from hanging if there is no path through the maze


def bfs_maze():
    q=[(0,0)]
    while len(q) > 0:
        global fuel
        fuel-=1
        if fuel <= 0: return
        x,y = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!")
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        q.append((x+dx,y+dy))
        del q[0]

# NOTE if there is no path to the exit, the search will continue for ever unless we have something like
# "fuel"
bfs_maze()

fuel=1000  # reset fuel

# this version prints out the path
def bfs_maze2():
    q=[(0,0,[(0,0)])]
    while len(q) > 0:
        global fuel
        fuel-=1
        if fuel <= 0: return
        x,y,path = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!", str(path))
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        print(x+dx,y+dy)
                        updated_path=list(path)  # copy old path
                        updated_path.append((x+dx,y+dy))
                        q.append((x+dx,y+dy,updated_path))
        del q[0]

bfs_maze2()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# depth-first search -------------------------------------------------

# NOTE this is a global variable!
dfs_order=[]

# pre-order (since binary tree)
# NOTE dfs does not "return" anything - dfs is a way of searching
# through a tree
def dfs(t0):
    if is_leaf(t0):
        # At this point we do something with the node.
        # For the time being, we just append it to
        # some global variable
        dfs_order.append(t0.label)
    else:
        assert is_node(t0)
        # See previous comment
        dfs_order.append(t0.label)
        dfs(t0.left)
        dfs(t0.right)


dfs(ex)
print("Dfs example:", str(dfs_order))