Programming Puzzles

Prepping for programming interviews can be a challenging, especially if you're over worked, and don't have a lot of time to study, because of family commitments.  The following is list of problems I studied and solved recently to get ready for interviews.

Problem 1

1) Implement a breadth first search non-recursively
2) Implement a depth first search non-recursively
3) Implement a breadth first search recursively
4) Implement a depth first search recursively

Code:

---

Output:

Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 2, index = 2
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 2, index = 2
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 2, index = 2
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3
Currently searching level = 1, index = 0
Currently searching level = 2, index = 1
Currently searching level = 2, index = 2
Currently searching level = 3, index = 3
Currently searching level = 3, index = 4
Currently searching level = 3, index = 5
Currently searching level = 3, index = 6
Found = 7, index = 6, level = 3

Problem 2

Given a binary tree return the level with maximum number of nodes

        1
       / \
      2   3
      /\  /\
     4 5 6 7
    /       \
   8         9 

Code:

---

Output:

• result: success     time: 0.07s    memory: 380160 kB     returned value: 0
  input: no
  output:
  

  2
  

Question 1

What are the uses of a b-tree, avl-tree and rb-tree?

When would you use a b-tree over an avl-tree?

Which one, out of the balanced BSTs is most the efficient?

Why don't we always use a b-tree?

Answer:
A b-tree is a generalization of a binary search tree in which nodes can have more than 2 children.  B-trees are used for applications such as databases and file systems.  B-trees are ideals for systems that need to store large blocks of data.  An avl-tree and an rb-tree are two types of automatically balanced tree structures that guarantee O(log n) for all operations (lookup, insertion, removal).

You would use a b-tree when something is disk backed, because b-trees group large blocks of data they can reduce HD seek time to improve performance of retrieving large data blocks from disk.

Efficiency depends on usage.  Avl-trees have stricter (more frequent) rebalancing, but faster retrieval time because of this.  Rb-trees rebalance less often, so they are faster for insertions and deletions, but slower for retrieval.

You could always use a b-tree or b+tree, but avl-trees and rb-tree provide other advantages, such as less tree maintenance, and memory flexibility.  In an avl-tree and rb-tree, nodes in memory can be easily detached from the tree structure, not so in a b-tree.  Avl-trees and rb-trees can be easily converted to linked lists without additional memory usage (which can allow you perform other operations easily with the tree, such as merging).

Problem 3

Crete a method hasUniqueChars(String a), do not use any type of built-in collection.

result: success     time: 0.07s    memory: 380160 kB     returned value: 0

input: no

output:

  hasUniqueChars("abc")
! hasUniqueChars("abcc")
  hasUniqueChars("abcdefhi")
! hasUniqueChars("abcdefhiabcdefhi")
! hasUniqueChars("ccc")
! hasUniqueChars("xxxkjsdfkjqqqdkjfd")
  hasUniqueChars("abcdefghijklmnopqrstuvwxyz")

Problem 4

Convert an infix expression to postfix.

result: success     time: 0.07s    memory: 380160 kB     returned value: 0

input: no

output:

1 2 3 + +
1 2 + 3 +
1 2 + 3 4 + + 3 +

Problem 5

Given a Tuple for eg. (a, b, c)..

Output : (*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c) 

The core of the problem involves generating ordered permutations of the indexes

  to replace with '*' ...

result: success     time: 0.08s    memory: 381184 kB     returned value: 0

input: no

output:

a,b,c
*,b,c
a,*,c
a,b,*
*,*,c
*,b,*
a,*,*
*,*,*
a,b,c,d
*,b,c,d
a,*,c,d
a,b,*,d
a,b,c,*
*,*,c,d
*,b,*,d
*,b,c,*
a,*,*,d
a,*,c,*
a,b,*,*
*,*,*,d
*,*,c,*
*,b,*,*
a,*,*,*
*,*,*,*

EOT