coding-test_result.txt

Test 1 description: given an array of integers and a value, determine if there are any three
integers in the array whose sum equals the given value.

The integer array is 3, 7, 1, 2, 8, 4, 5

Use brute force method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21

Sort it before attempting it
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21

Use Divide & Conquer and Binary way of brute force method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21

Use brute force but simple recursive method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21


Test 2 description: given a list of intervals, merge all the overlapping intervals to produce a list
that has only mutually exclusive intervals.

1...3, 4...6, 5...8, 9...12, 10...15, 14...16, 17...18
after merged

1...3, 4...8, 9...16, 17...18


Test 3 description: search for a given number in a sorted array, with unique elements,
that has been rotated by some arbitrary number. Return -1 if the number does not exist.

On none-rotated list
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 
data  3, key = 1
data  7, key = 3
data  8, key = -1
data 17, key = 8

On rotated list
15, 17, 19, 1, 3, 5, 7, 9, 11, 13, 
data  3, key = 4
data  7, key = 6
data  8, key = -1
data 17, key = 1


Test 4 description: given a positive integer, target, print all possible combinations of
positive integers that sum up to the target number.

find all sum combination of 5
4, 1
3, 2
3, 1, 1
2, 3
2, 2, 1
2, 1, 1, 1
1, 4
1, 3, 1
1, 2, 1, 1
1, 1, 1, 1, 1


Test 5 description: reverse the order of words in a given sentence (an array of characters).

String = "1 23 45 6 789"
Reversing words, result string = "789 6 45 23 1"
Reversing words again, result string = "1 23 45 6 789"

String = " abc  xyz "
Reversing words, result string = " xyz  abc "
Reversing words again, result string = " abc  xyz "


Test 6 description: find total ways to achieve a given sum with `n` throws of dice having `k` faces
if throw is 2 and sum value is 10, then we have the following: (6, 4), (4, 6), (5, 5).

Number of throws = 2, desired sum = 10
4, 6
5, 5
6, 4

Number of throws = 3, desired sum = 8
1, 1, 6
1, 2, 5
1, 3, 4
1, 4, 3
1, 5, 2
1, 6, 1
2, 1, 5
2, 2, 4
2, 3, 3
2, 4, 2
2, 5, 1
3, 1, 4
3, 2, 3
3, 3, 2
3, 4, 1
4, 1, 3
4, 2, 2
4, 3, 1
5, 1, 2
5, 2, 1
6, 1, 1


Test 7 description: given a double, x and an integer n, write a function to calculate x raised to the power n.

  2 ^  5 = 32.000000
  3 ^  4 = 81.000000
1.5 ^  3 = 3.375000
  2 ^ -2 = 0.250000


Test 8 description: given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.

Adding  5, median =  5.00
Adding 15, median = 10.00
Adding  1, median =  5.00
Adding  3, median =  4.00
Adding  2, median =  3.00
Adding  4, median =  3.50


Test 9 description: the permutations of string ABC is "ABC ACB BAC BCA CBA CAB".

ABC
BAC
CBA
BCA
CBA
CAB


Test 10 description: implementing AVL (Adelson-Velsky and Landis) self-balancing binary search tree.

Adding a list of integer arrays in the following order1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
The tree topology:

8 (L=4, R=3)
     10 (L=1, R=2)
          12 (L=1, R=1)
               13 (L=0, R=0)
                    -
                    -
               11 (L=0, R=0)
                    -
                    -
          9 (L=0, R=0)
               -
               -
     3 (L=2, R=3)
          6 (L=2, R=1)
               7 (L=0, R=0)
                    -
                    -
               5 (L=1, R=0)
                    -
                    4 (L=0, R=0)
                         -
                         -
          2 (L=1, R=0)
               -
               1 (L=0, R=0)
                    -
                    -


Test 11 description: finding the largest possible sum of a contiguous subarray, within
a given one-dimensional array A[1…n] of numbers.

The integer array is -4, 2, -5, 1, 2, 3, 6, -5, 1

Maximum subarray is 1, 2, 3, 6


Test 12 description: Find the rotating point of an array that is sorted, but the starting point can be in middle.

The integer array1 is 5, 1, 2, 3, 4
The rotating point is at index 1 and value is 1

The integer array2 is 4, 5, 6, 1, 2, 3
The rotating point is at index 3 and value is 1

The integer array3 is 4, 5, 6, 7, 8, 0, 1, 2, 3
The rotating point is at index 5 and value is 0


Test 13 description: check if a binary tree is binary search tree.

root1 is a binary search tree
The tree topology:
2 (L=1, R=2)
     3 (L=0, R=1)
          4 (L=0, R=0)
               -
               -
          -
     1 (L=0, R=0)
          -
          -

root2 is not a binary search tree
The tree topology:
4 (L=2, R=1)
     5 (L=0, R=0)
          -
          -
     2 (L=0, R=1)
          6 (L=0, R=0)
               -
               -
          -


Test 14 description: check that two lists are combined into a final list in a 1st come 1st serve ordering.

list1 = 17, 8, 24
list2 = 12, 19, 2
list3 = 17, 8, 12, 19, 24, 2

list1 and list2 are served in order

list4 = 1, 3, 5
list5 = 2, 4, 6
list6 = 1, 2, 4, 6, 5, 3

list4 and list5 are not served in order


Test 15 description: given two strings s1 and s2, find the length of the longest substring common in both the strings.

The common longest substring of "abdca" and "cbda" is bd
The common longest substring of "passport" and "ppsspt" is ssp


Test 16 description: given a sequence, find the length of its Longest Palindromic Subsequence (or LPS).
In a palindromic subsequence, elements read the same backward and forward.

The longest palinidromic subsequence of "axbba" is 4
The longest palinidromic subsequence of "abdbca" is 5
The longest palinidromic subsequence of "cddpd" is 3
The longest palinidromic subsequence of "pqr" is 1
The longest palinidromic subsequence of "abbdcacb" is 5


Test 17 description: given two strings s1 and s2, find the length of the longest subsequence which is common in both the strings

The longest substring of "abdca" and "cbda" is 3
The longest substring of "passport" and "ppsspt" is 5
The longest substring of "abc" and "xzabtttabcg" is 3