l30.lisp 28.1 KB
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 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768
;;;; -*- mode:lisp; coding:utf-8 -*-

;; Read more: http://javarevisited.blogspot.com/2015/06/top-20-array-interview-questions-and-answers.html


#|
1. How to find missing number in integer vector of 1 to 100? 

You have given an integer vector which contains numbers from 1 to 100
but one number is missing, you need to write a Lisp program to find
that missing number in vector.

One trick to solve this problem is calculate sum of all numbers in
vector and compare with expected sum, the difference would be the
missing number.
|#

(defun sum-to (n)
  (check-type n (integer 1))
  (* 1/2 n (1+ n)))

(defun missing-integer (vector)
  (check-type vector vector)
  (assert (plusp (length vector)) (vector))
  (let* ((n         (1+ (length vector)))
         (expected  (sum-to n))
         (sum       (reduce (function +) vector)))
     (- expected sum)))

(assert (equalp (missing-integer #(1 2 3 5 6))  4))


        
#|
2. How to find duplicate number on Integer vector in Lisp? 

An vector contains n numbers ranging from 0 to n-2.  There is exactly
one number is repeated in the vector.  You need to write a program to
find that duplicate number.  For example, if an vector with length 6
contains numbers {0, 3, 1, 2, 3}, then duplicated number is 3.
Actually this problem is very similar to previous one and you can
apply the same trick of comparing actual sum of vector to expected sum
of series to find out that duplicate.
|#

(defun duplicate-integer (vector)
  (check-type vector vector)
  (assert (plusp (length vector)) (vector))
  (let* ((n         (1- (length vector)))
         (expected  (sum-to n))
         (sum       (reduce (function +) vector)))
    (- sum expected)))


(assert (equalp (duplicate-integer #(1 2 3 4 5 6 1)) 1))



#|
3. How to check if vector contains a number in Lisp? 

Another interesting vector problem, because vector doesn't provide any
builtin method to check if any number exists or not.  This problem is
essentially how to search an element in vector.  There are two options
sequential search or binary search.  You should ask interviewer about
whether vector is sorted or not, if vector is sorted then you can use
binary search to check if given number is present in vector or
not.  Complexity of binary search is O(logN).  BTW, if interviewer say
that vector is not sorted then you can still sort and perform binary
search otherwise you can use sequential search.  Time complexity of
sequential search in vector is O(n).
|#

(defun sequential-search (n vector)
  (position n vector :test (function =)))

(defun binary-search (n vector lessp)
  "RETURN: the index of the smalest element e such as (<= n e) ;
           (= n e)
When (< n (aref vector 0)) the results are 0 nil
When (< (aref vector (1- (length vector))) n) the results are (length vector) nil"
  (let* ((min 0)
         (max (length vector))
         (cur (truncate (+ min max) 2)))
    (flet ((lt (a b) (funcall lessp a b))
           (ne (a b) (or (funcall lessp a b)
                         (funcall lessp b a))))
     (if (or (zerop max) (lt (aref vector (1- max)) n))
         (values max nil)
         (loop
           ;; :do (print (list min max cur '-> n (aref vector cur)))
           :while (and (< min max) (ne n (aref vector cur)))
           :do (cond
                 ((lt n (aref vector cur))
                  (setf max cur))
                 ((= min cur)
                  (return (values (1+ cur) nil)))
                 (t
                  (setf min cur)))
               (setf cur (truncate (+ min max) 2))
           :finally (return (values cur (not (ne n (aref vector cur))))))))))


(assert (equalp (sequential-search 42 #(1 2 42 33 24)) 2))
(assert (equalp (sequential-search 12 #(1 2 42 33 24)) nil))

(assert (equalp (multiple-value-list (binary-search 0 #(1 2 24 33 42) (function <))) '(0 nil)))
(assert (equalp (multiple-value-list (binary-search 1 #(1 2 24 33 42) (function <))) '(0 t)))
(assert (equalp (multiple-value-list (binary-search 2 #(1 2 24 33 42) (function <))) '(1 t)))
(assert (equalp (multiple-value-list (binary-search 3 #(1 2 24 33 42) (function <))) '(2 nil)))
(assert (equalp (multiple-value-list (binary-search 24 #(1 2 24 33 42) (function <))) '(2 t)))
(assert (equalp (multiple-value-list (binary-search 25 #(1 2 24 33 42) (function <))) '(3 nil)))
(assert (equalp (multiple-value-list (binary-search 33 #(1 2 24 33 42) (function <))) '(3 t)))
(assert (equalp (multiple-value-list (binary-search 35 #(1 2 24 33 42) (function <))) '(4 nil)))
(assert (equalp (multiple-value-list (binary-search 42 #(1 2 24 33 42) (function <))) '(4 t)))
(assert (equalp (multiple-value-list (binary-search 45 #(1 2 24 33 42) (function <))) '(5 nil)))






#|
4. How to find largest and smallest number in unsorted vector? 

You have given an unsorted integer vector and you need to find the
largest and smallest element in the vector.  Of course you can sort
the vector and then pick the top and bottom element but that would
cost you O(NLogN) because of sorting, getting element in vector with
index is O(1) operation.
|#


(defun extremums (vector)
  (loop
    :for n :across vector
    :maximize n :into max
    :minimize n :into min
    :finally (return (list min max))))


#-(and) (
         (list (extremums #())
               (extremums #(1))
               (extremums #(1 2))
               (extremums #(2 1))
               (extremums #(3 2 1))
               (extremums #(1 2 3))
               (extremums #(4 5 6 2 1 9 8 7)))
         --> ((0 0) (1 1) (1 2) (1 2) (1 3) (1 3) (1 9))
         )

#|
5. How to find all pairs on integer vector whose sum is equalp to given number? 

This is an intermediate level of vector coding question, its neither
too easy nor too difficult.  You have given an integer vector and a
number, you need to write a program to find all elements in vector
whose sum is equalp to the given number.  Remember, vector may contain
both positive and negative numbers, so your solution should consider
that.  Don't forget to write unit test though, even if interviewer is
not asked for it, that would separate you from lot of developers.  Unit
testing is always expected from a professional developer.
|#

(defun find-binary-sums (n vector)
  (loop
    :for i :below (length vector)
    :append (loop
              :for j :from (1+ i) :below (length vector)
              :for sum = (+ (aref vector i) (aref vector j))
              :when (= sum n)
              :collect (list (aref vector i) (aref vector j)))))

(assert (equalp (find-binary-sums 5 #(1 2 3 4 5 6 7 8 9 10 -3 -4 -5))
                '((1 4) (2 3) (8 -3) (9 -4) (10 -5))))
(assert (equalp (find-binary-sums 30 #(1 2 3 4 5 6 7 8 9 10 -3 -4 -5))
                '()))


#|
6. How to find repeated numbers in an vector if it contains multiple duplicate? 

This is actually the follow-up question of problem 2, how to find
duplicate number on integer vector.  In that case, vector contains only
one duplicate but what if it contains multiple duplicates? Suppose, an
vector contains n numbers ranging from 0 to n-1 and there are 5
duplicates on it, how do you find it? You can use the approach, we
have learned in similar String based problem of finding repeated
characters in given String.
|#

(defun duplicate-integers (n vector)
  (check-type vector vector)
  (assert (plusp (length vector)))
  (let ((counts (make-array n :initial-element 0)))
    (loop
      :for e :across vector
      :do (incf (aref counts e)))
    (loop
      :for e :below n
      :when (< 1 (aref counts e))
        :collect e)))

(assert (equalp (duplicate-integers 6 #(1 2 3 4 5 0 2 5))
                '(2 5)))
(assert (equalp (duplicate-integers 6 #(1 2 3 4 5 0))
                '()))



#|
7. Write a program to remove duplicates from vector in Lisp? 

This is another follow-up question from problem 2 and 6.  You have
given an vector which contains duplicates, could be one or more.  You
need to write a program to remove all duplicates from vector in
Lisp.  For example if given vector is {1, 2, 1, 2, 3, 4, 5} then your
program should return an vector which contains just {1, 2, 3, 4,
5}.
|#

(defun remove-duplicates-from-vector (vector)
  (let ((h (make-hash-table :test (function eql))))
    (loop :for n :across vector
          :do (incf (gethash n h 0)))
    (let ((result (make-array (hash-table-count h)))
          (i -1))
      (loop
        :for n :across vector
        :for c = (gethash n h)
        :do (when (plusp c)
              (setf (aref result (incf i)) n)
              (when (< 1 c)
                (setf (gethash n h) 0))))
      result)))

(assert (equalp (remove-duplicates-from-vector #(1 2 1 2 3 4 5)) #(1 2 3 4 5)))
(assert (equalp (remove-duplicates-from-vector #(1 1 1 1)) #(1)))
(assert (equalp (remove-duplicates-from-vector #()) #()))


#|
8. How to sort an vector in place using QuickSort algorithm? 

You will often see sorting problems on vector related questions,
because sorting mostly happen on vector data structure.  You need to
write a program to implement in place quick sort algorithm in
Lisp.  You can implement either recursive or iterative quick sort, its
your choice but you cannot use additional buffer, vector or list, you
must sort vector in place.
|#



#|
9. Write a program to find intersection of two sorted vector in Lisp? 

Another interesting vector interview question, where you need to treat
vector as Set.  Your task is to write a function in your favorite
language e.g.  Lisp, Python, C or C++ to return intersection of two
sorted vector.  For example, if the two sorted vectors as input are {21,
34, 41, 22, 35} and {61, 34, 45, 21, 11}, it should return an
intersection vector with numbers {34, 21}, For the sake of this problem
you can assume that numbers in each integer vector are unique.
|#

(defun sorted-vector-intersection (a b)
  (cond
    ((or (zerop (length a)) (zerop (length b)))
     #())
    ((> (aref a 0) (aref a (1- (length a))))
     (sorted-vector-intersection (reverse a) b))
    ((> (aref b 0) (aref b (1- (length b))))
     (sorted-vector-intersection a (reverse b)))
    (t
     (let ((intersection (make-array (min (length a) (length b)) :fill-pointer 0)))
       (loop
         :with i = 0
         :with j = 0
         :while (and (< i (length a)) (< j (length b)))
         :do (cond
               ((< (aref a i) (aref b j))
                (incf i))
               ((> (aref a i) (aref b j))
                (incf j))
               (t
                (vector-push (aref a i) intersection)
                (incf i) (incf j))))
       intersection))))

(assert (equalp (sorted-vector-intersection #(21 22 34 35 41) #(11 21 34 45 61)) #(21 34)))
(assert (equalp (sorted-vector-intersection #(41 35 34 22 21) #(61 45 34 21 11)) #(21 34)))


#|
10. There is an vector with every element repeated twice except one.  Find that element? 

This is an interesting vector coding problem, just opposite of question
related to finding duplicates in vector.  Here you need to find the
unique number which is not repeated twice.  For example if given vector
is {1, 1, 2, 2, 3, 4, 4, 5, 5} then your program should return
3.  Also, don't forget to write couple of unit test for your solution.
|#

(defun unique-vector-element (vector)
  (let ((h (make-hash-table :test (function eql))))
    (loop :for n :across vector
          :do (incf (gethash n h 0)))
    (maphash (lambda (n c)
               (when (= 1 c)
                 (return-from unique-vector-element n)))
             h)
    nil))

(assert (equalp (unique-vector-element #(1 1 2 2 3 4 4 5 5)) 3))
(assert (equalp (unique-vector-element #(1 2 3 4 5 1 2 4 5)) 3))
(assert (equalp (unique-vector-element #(42)) 42))
(assert (member (unique-vector-element #(1 2 3)) '(1 2 3)))
(assert (equalp (unique-vector-element #(2 4 2 4)) nil))
(assert (equalp (unique-vector-element #()) nil))


#|
11. How to find kth smallest element in unsorted vector? 

You are given an unsorted vector of numbers and k, you need to find the
kth smallest number in the vector.  For example if given vector is {1, 2,
3, 9, 4} and k=2 then you need to find the 2nd smallest number in the
vector, which is 2.  One way to solve this problem is to sort the vector
in ascending order then pick the k-1th element, that would be your kth
smallest number in vector because vector index starts at zero, but can
you do better? Once you are able to solve this vector coding question,
you can solve many similar questions easily e.g.  our next question.
|#

(defun k-extremums (vector k lessp)
  (let ((extremums (sort (subseq vector 0 (min k (length vector))) lessp)))
    (unless (< (length vector) k)
      (flet ((insert (e)
               (multiple-value-bind (index found) (binary-search e extremums lessp)
                 (declare (ignore found))
                 (replace extremums extremums :start1 (1+ index) :start2 index)
                 (setf (aref extremums index) e))))
        (loop
          :for i :from k :below (length vector)
          :for e = (aref vector i)
          :unless (funcall lessp (aref extremums (1- k)) e)
            :do (insert e))))
    extremums))

(assert (equalp (k-extremums #(49 64 1 2 24 5 33 42 72 11 96)
                            3 (lambda (a b)
                                (< (abs (- a 33)) (abs (- b 33)))))
               #(33 42 24)))
(assert (equalp (k-extremums #(49 64 1 2 24 5 33 42 72 11 96)
                     3 (function >))
               #(96 72 64)))
(assert (equalp (k-extremums #(49 64 1 2 24 5 33 42 72 11 96)
                            4 (function <))
               #(1 2 5 11)))

(defun kth-smallest-element (vector k)
  (let ((extremums (k-extremums vector k (function <))))
    (aref extremums (1- (length extremums)))))

(assert (equalp (kth-smallest-element #(49 64 1 2 24 5 33 42 72 11 96) 1)    1))
(assert (equalp (kth-smallest-element #(49 64 1 2 24 5 33 42 72 11 96) 2)    2))
(assert (equalp (kth-smallest-element #(49 64 1 2 24 5 33 42 72 11 96) 3)    5))
(assert (equalp (kth-smallest-element #(49 64 1 2 24 5 33 42 72 11 96) 4)   11))
(assert (equalp (kth-smallest-element #(49 64 1 2 24 5 33 42 72 11 96) 100) 96)) ; feature.

#|
12. How to find kth largest element in unsorted vector? 

This problem is exactly same as previous question with only difference
being finding kth largest element instead of kth smallest number.  For
example if given vector is {10, 20, 30, 50, 40} and k = 3 then your
program should return 30 because 30 is the 3rd largest number in
vector.  You can also solve this problem by sorting the vector in
decreasing order and picking k-1th element.  I often seen this vector
question on Lisp interviews with 2 to 3 years experienced guys.
|#

(defun kth-largest-element (vector k)
  (let ((extremums (k-extremums vector k (function >))))
    (aref extremums (1- (length extremums)))))

(assert (equalp (kth-largest-element #(49 64 1 2 24 5 33 42 72 11 96) 1)   96))
(assert (equalp (kth-largest-element #(49 64 1 2 24 5 33 42 72 11 96) 2)   72))
(assert (equalp (kth-largest-element #(49 64 1 2 24 5 33 42 72 11 96) 3)   64))
(assert (equalp (kth-largest-element #(49 64 1 2 24 5 33 42 72 11 96) 4)   49))
(assert (equalp (kth-largest-element #(49 64 1 2 24 5 33 42 72 11 96) 100)  1)) ; feature.


#|
13. How to find common elements in three sorted vector? 

Now we are coming on territory of tough vector questions.  Given three
vectors sorted in non-decreasing order, print all common elements in
these vectors.

Examples:

input1 = {1, 5, 10, 20, 40, 80}
input2 = {6, 7, 20, 80, 100}
input3 = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80
|#

(defun sorted-vector-intersection-3 (a b c)
  (sorted-vector-intersection (sorted-vector-intersection a b) c))

(assert (equalp (sorted-vector-intersection-3 #(1 5 10 20 40 80)
                                              #(6 7 20 80 100)
                                              #(3 4 15 20 30 70 80 120))
                #(20 80)))

(defun sorted-vector-intersection-3* (a b c)
  (declare (optimize (space 3) (speed 3) (debug 0) (safety 0)))
  (check-type a vector)
  (check-type b vector)
  (check-type c vector)
  (assert (every (function realp) a))
  (assert (every (function realp) b))
  (assert (every (function realp) c))
  (let ((lena (length a))
        (lenb (length b))
        (lenc (length c)))
   (cond
     ((or (zerop lena) (zerop lenb) (zerop lenc))
      #())
     ((> (aref a 0) (aref a (1- lena)))
      (sorted-vector-intersection-3* (reverse a) b c))
     ((> (aref b 0) (aref b (1- lenb)))
      (sorted-vector-intersection-3* a (reverse b) c))
     ((> (aref c 0) (aref c (1- lenc)))
      (sorted-vector-intersection-3* a b (reverse c)))
     (t
      (let ((intersection (make-array (min lena lenb lenc) :fill-pointer 0)))
        (loop
          :with i = 0
          :with j = 0
          :with k = 0
          :while (and (< i lena) (< j lenb)  (< k lenc))
          :do (macrolet ((skip-if-smallest (a i b j c k)
                           ;; if (aref a i) is strictly less than the
                           ;; two others, then increment i and return
                           ;; true else return nil.
                           `(when (and (< (aref ,a ,i) (aref ,b ,j))
                                       (< (aref ,a ,i) (aref ,c ,k)))
                              (incf ,i))))
                (cond
                  ((skip-if-smallest a i b j c k))
                  ((skip-if-smallest b j a i c k))
                  ((skip-if-smallest c k a i b j))
                  (t
                   (vector-push (aref a i) intersection)
                   (incf i) (incf j) (incf k)))))
        intersection)))))

(assert (equalp (sorted-vector-intersection-3* #(1 5 10 20 40 80)
                                               #(6 7 20 80 100)
                                               #(3 4 15 20 30 70 80 120))
                #(20 80)))

(defun generate-random-vector (length min-value max-value)
  (map-into (make-array length) (lambda () (+ min-value (random (- max-value min-value))))))

(let ((a (generate-random-vector 1000000 100000000 600000000))
      (b (generate-random-vector 1000000 200000000 700000000))
      (c (generate-random-vector 1000000 300000000 800000000)))
  (let ((r1  (time (sorted-vector-intersection-3  a b c)))
        (r2  (time (sorted-vector-intersection-3* a b c))))
    (assert (equalp r1 r2))))

;; With ccl, without declare optimize sorted-vector-intersection-3 is
;; faster than sorted-vector-intersection-3*.


#|
14. How find the first repeating element in an vector of integers? 

Given an vector of integers, find the first repeating element in it.  We
need to find the element that occurs more than once and whose index of
first occurrence is smallest.

Examples:

Input:  input [] = {10, 5, 3, 4, 3, 5, 6}
Output: 5 [5 is the first element that repeats]
|#

(defun first-repeating-element (vector)
  (let ((h (make-hash-table :test (function eql))))
    (loop :for n :across vector
          :for i :from 0
          :do (if (gethash n h)
                  (incf (car (gethash n h)))
                  (setf (gethash n h) (cons 1 i))))
    (let ((min-n nil)
          (min-i nil))
      (maphash (lambda (n e)
                 (when (and (< 1 (car e))
                            (or (null min-n) (< (cdr e) min-i)))
                   (setf min-n n
                         min-i (cdr e))))
               h)
      min-n)))

(assert (equalp (first-repeating-element #(10 5 3 4 3 5 6)) 5))


#|
15. How to find first non-repeating element in vector of integers? 

This vector interview question is exactly opposite of previous problem,
In that you need to find first repeating element while in this you
need to find first non-repeating element.  I am sure you can use
similar approach to solve this problem, just need to consider non
repeating element though.
|#

(defun first-non-repeating-element (vector)
  (let ((h (make-hash-table :test (function eql))))
    (loop :for n :across vector
          :for i :from 0
          :do (if (gethash n h)
                  (incf (car (gethash n h)))
                  (setf (gethash n h) (cons 1 i))))
    (let ((min-n nil)
          (min-i nil))
      (maphash (lambda (n e)
                 (when (and (= 1 (car e))
                            (or (null min-n) (< (cdr e) min-i)))
                   (setf min-n n
                         min-i (cdr e))))
               h)
      min-n)))

(assert (equalp (first-non-repeating-element #(10 5 3 4 3 5 6)) 10))


#|
16. How to find top two numbers from an integer vector? 

This is another one of the easy vector questions you will find on
telephonic round of Interviews, but its also little bit tricky.  You
are asked to find top two numbers not just the top or highest numbers?
Can you think of how you would do it without sorting? before looking
at solution.
|#



#|
17. How to find the smallest positive integer value that cannot be represented as sum of any subset of a given vector? 

This is another tough vector question you will see on Amazon, Microsoft
or Google.  You have given a sorted vector (sorted in non-decreasing
order) of positive numbers, find the smallest positive integer value
that cannot be represented as sum of elements of any subset of given
set.  What makes it more challenging is expected time complexity of
O(n).

Examples:

Input: {1, 3, 6, 10, 11, 15};
Output: 2


18. How to rearrange vector in alternating positive and negative number? 

Given an vector of positive and negative numbers, arrange them in an
alternate fashion such that every positive number is followed by
negative and vice-versa maintaining the order of appearance.   Number
of positive and negative numbers need not be equal.  If there are more
positive numbers they appear at the end of the vector.  If there are
more negative numbers, they too appear in the end of the vector.  This
is also a difficult vector problem to solve and you need lot of
practice to solve this kind of problems in real interviews, especially
when you see it first time.  If you have time constraint then always
attempt these kind of questions once you are done with easier ones.  

Example:

Input: {1, 2, 3, -4, -1, 4}
Output: {-4, 1, -1, 2, 3, 4}

Input: {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0} 


19. How to find if there is a sub vector with sum equal to zero? 

There is whole set of vector related questions which are based upon
sub-vector or only selective elements of vector e.g.  from some range,
this is one of such problem.  Here you are given an vector of positive
and negative numbers, find if there is a sub-vector with 0 sum.

Examples:

Input: {4, 2, -3, 1, 6}
Output: true 
There is a sub-vector with zero sum from index 1 to 3.

20. How to remove duplicates from vector in place? 

Given a sorted vector, remove the duplicates in place such that each
element appear only once and return the new length.

Do not allocate extra space for another vector, you must do this in
place with constant memory.

For example,
Given input vector A = [1,1,2],

Your function should return length = 2, and A is now [1,2].  

When you see a questions which asked you do to sorting or task in
place, it means you cannot use additional vector or buffer, but using
couple of variables is fine.


21. How to remove a given element from vector in Lisp? 

This is another vector coding questions similar to previous one.  Here
you don't have to find and remove duplicates but a given number.  In
this problem you are given an vector and a value, remove all instances
of that value in place and return the new length.  The order of
elements can be changed.  It doesn't matter what you leave beyond the
new length.  


22. How to merge sorted vector? 

Given two sorted integer vectors A and B, merge B into A as one sorted
vector.  You may assume that A has enough space (size that is greater or
equal to m + n) to hold additional elements from B.  The number of
elements initialized in A and B are m and n respectively.  This is
another intermediate vector coding question, its not as simple as
previous one but neither very difficult.


23. How to find sub vector with maximum sum in an vector of positive and
negative number? 

Another vector coding question based upon sub-vector.  Here you have to
find the contiguous sub-vector within an vector (containing at least one
number) which has the largest sum.

For example, given the vector [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subvector [4,−1,2,1] has the largest sum = 6.  


24. How to find sub vector with largest product in vector of both
positive and negative number?  

In this problem, your task is to write a program in Lisp or C++ to
find the contiguous sub-vector within an vector (containing at least one
number) which has the largest product.

For example, given the vector [2,3,-2,4],
the contiguous subvector [2,3] has the largest product = 6.  


25. Write a program to find length of longest consecutive sequence in
vector of integers? 

Given an unsorted vector of integers, find the length of the longest
consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4].  Return its
length: 4.

Challenging part of this question is that your algorithm should run in
O(n) complexity.  


26. How to find minimum value in a rotated sorted vector? 

This is  another advanced level  vector coding question and  you should
only attempt this one, once you have solved the easier ones.  Suppose a
sorted vector is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the vector.  One follow-up
question of this question is What if duplicates are allowed? Would
this affect the run-time complexity? How and why?


27. Given an vector of of size n and a number k, find all elements that appear more than n/k times? 

Another tough vector based coding questions from Interviews.  You are
given an vector of size n, find all elements in vector that appear more
than n/k times.  For example, if the input vectors is {3, 1, 2, 2, 1, 2,
3, 3} and k is 4, then the output should be [2, 3].  Note that size of
vector is 8 (or n = 8), so we need to find all elements that appear
more than 2 (or 8/4) times.  There are two elements that appear more
than two times, 2 and 3.

    1.  Returns the largest sum of contiguous integers in the vector
        Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8

    2.  Return the sum two largest integers in an vector

    3.  Given an vector of integers write a program that will determine
        if any two numbers add up to a specified number N.  Do this
        without using hash tables
|#


#|
28.  How to reverse vector in place in Lisp? 

Now let's see one of the most frequently asked vector interview
question.  You need to write a program which accepts an integer vector
and your program needs to reverse that vector in place, which means
you cannot use additional buffer or vector, but one or two variables
will be fine.  Of course you cannot use NREVERSE or REVERSE to
directly solve this problem, you need to create your own logic.
|#


(defun vector-nreverse (vector)
  (when (plusp (length vector))
   (loop :for i :from 0
         :for j :from (1- (length vector)) :by -1
         :while (< i j)
         :do (rotatef (aref vector i) (aref vector j))))
  vector)

(assert (equalp (vector-nreverse (vector)) (vector)))
(assert (equalp (vector-nreverse (vector 1)) (vector 1)))
(assert (equalp (vector-nreverse (vector 1 2)) (vector 2 1)))
(assert (equalp (vector-nreverse (vector 1 2 3)) (vector 3 2 1)))
(assert (equalp (vector-nreverse (vector 1 2 3 4)) (vector 4 3 2 1)))


#|
29.  Difference between vector and linked list data structure? 

This is a theoretical questions from phone interviews.  There are
several differences between vector and linked list e.g.  vector stores
element in contiguous memory location while linked list stores at
random places, this means linked list better utilizes the
places.  Consequently, its possible to have large linked list in
limited memory environment compare to vector of same size.  Advantage of
using vector is random access it provides if you know the index, while
in linked list you need to search an element by traversing which is
O(n) operation.


30.  How to check if vector contains a duplicate number? 

This may look a repeated question because we have already done similar
question, but in this question, most from Lisp interviews, you need to
write a contains() like method from Collections, which returns true or
false if you pass an element and it is repeated or not.


|#