Second or last but one

jmurthy

Walking through the code interviews of IT international companies I run into interesting problem.

How many comparisons do we have to make to figure out what element out of six is the second smallest or the second largest.

None of these six elements have the same value.

  • we have main function with six arguments (v1, ..., v6)

     def solve(v1, v2, v3, v4, v5, v6):
         # the worst case -> 9 comparisons
         if isLarger(v1, v2):
             v1, v2 = v2, v1
         if isLarger(v1, v3):
             v1, v3 = v3, v1
         if isLarger(v1, v4):
             v1, v4 = v4, v1
         if isLarger(v1, v5):
             v1, v5 = v5, v1
         if isLarger(v1, v6):
             v1, v6 = v6, v1
         if isLarger(v2, v3):
             v2, v3 = v3, v2
         if isLarger(v2, v4):
             v2, v4 = v4, v2
         if isLarger(v2, v5):
             v2, v5 = v5, v2
         if isLarger(v2, v6):
             v2, v6 = v6, v2
         print(f"#comparisons = {CntComparisons}")
         return v2
    

    which returns the second smallest or the second largest value.

  • Determine this value by comparison (i.e. it cannot use indexing by that value).

  • For pairwise comparison we can use only the below function

    CntComparisons = 0
    def isLarger(v1, v2):
        global CntComparisons
        CntComparisons += 1
        return v1 > v2
    
  • Values are compared only by calling the comparison function isLarger(v1, v2).

The goal is to find an algorithm that requires (even in the worst case) as few comparisons as possible!

Any ideas or hint how to solve this?

trincot

A trivial, but not optimal way is using the first two passes of bubble sort: this will swap pairs of variables and so bubble the 2 greatest values to the "right" and assign them to v5 and v6, and so v5 will be returned as correct answer. This requires 9 comparisons: 5 in the first pass, 4 in the second. So we have an upper bound of 9 comparisons.

A lower bound is 5, since that is the number of comparisons needed to find either the minimum or the maximum, and that will be needed to be sure a value is the second least or second greatest.

Here is an idea:

  • Perform 2 to 3 comparisons to sort v1, v2, v3 through swaps from least to greatest. We then know that v2 is not the least nor the greatest.

  • Perform 3 comparisons between v2 and the last 3 values (v3, v4 and v5).

  • If these comparisons all give the same boolean result, it means that v2 is indeed the answer.

  • If among those boolean results there is only one True (i.e. v2 is only greater than one of them), then let vx be the one among v3, v4 or v5 for which v2 is greater than vx. Return the greatest of v1 and vx: this needs another, 7th comparison.

  • If among those boolean results there is only one False (i.e. v2 is greater than two of them), then let vx be the one among v3, v4 or v5 for which v2 is not greater than vx. Return the least of v3 and vx: this needs another, 7th comparison.

So in the worst case we get the result with 7 comparisons. The best case needs 5 comparisons (2 for the sorting step, and c4, c5 and c6).

Here is an implementation of this idea:

def solve(v1, v2, v3, v4, v5, v6):
    # Sort (v1, v2, v3)
    if isLarger(v1, v2):
        v1, v2 = v2, v1
    if isLarger(v2, v3):
        v2, v3 = v3, v2
        if isLarger(v1, v2):
            v1, v2 = v2, v1
    # v2 is now certainly not the greatest nor the least
    # Check how it compares with v4, v5 and v6
    c4 = isLarger(v2, v4)
    c5 = isLarger(v2, v5)
    c6 = isLarger(v2, v6)
    if c4 == c5 == c6:  # All true or all false
        return v2
    if c4 ^ c5 ^ c6:  # Only one of them is true
        vx = v4 if c4 else (v5 if c5 else v6)
        return v1 if isLarger(v1, vx) else vx
    else:  # Only one of them is false
        vx = v4 if not c4 else (v5 if not c5 else v6)
        return vx if isLarger(v3, vx) else v3

I ran this on all permutations of [1,2,3,4,5,6] and these are the results:

  • 5 comparisons needed for 96 permuations
  • 6 comparisons needed for 336 permutations
  • 7 comparisons needed for 288 permutations

On average: 6.266667 comparisons

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集
0

コメントを追加

0

関連記事

In Python, how should one extract the second-last directory name in a path?

Select second last element with css

Replace the "pattern" on second-to-last line of a file

How to get second last commit hash in git

SQL query in vba by last month down to the second

How to read only the second last line of a file

Find the last one to change a file?

Insert data to MySQL table every second (one time per second)

Insert data to MySQL table every second (one time per second)

ruby array, get all elements from second to last

How do I index from the second position to the last to the first?

How can I sum the second digit to the last digit in an integer on java?

get second last component of a path from a string with js regex

How do I extract the second to last occurrence of a string in MySQL?

How to modify second-to-last line inside a range in sed

Bibtex in Rmarkdown - First and and last names of second author get swapped in citation

Get the second last ID by date, based on the current ID

How can i insert elements of one array into second one?

How to select range in Excel ListColumn's DataBodyRange from second to second last cell with VBA

Display second last record in TextBox (show user when he last Login)

Place the last child next to the previous one - Flexbox

Set a static element as the last one in a Dropdown list?

replace last 2 characters with one in notepad++

Reorder one row in tibble - move it to the last row

switchIfEmpty does not emit vales from second observable if first one is empty

nested loop to fill values in one df based on conditions in second df

why dose the first loop always runs faster than the second one?

Sort by two fields, with the second being reverse alphabetical one-liner

How to increase a date field with one second value in a MongoDB 3.6?

TOP 一覧

  1. 1

    セレンのモデルダイアログからテキストを抽出するにはどうすればよいですか?

  2. 2

    Railsで宝石のレイアウトを使用するにはどうすればよいですか?

  3. 3

    Chromeウェブアプリのウェブビューの高さの問題

  4. 4

    Ansibleで複数行のシェルスクリプトを実行する方法

  5. 5

    アンドロイド9 - キーストア例外android.os.ServiceSpecificException

  6. 6

    Windows 10 Pro 1709を1803、1809、または1903に更新しますか?

  7. 7

    CSSのみを使用して三角形のアニメーションを作成する方法

  8. 8

    Google Playストア:アプリページにリーダーボードと実績のアイコン/バッジが表示されない

  9. 9

    GoDaddyでのCKEditorとKCfinderの画像プレビュー

  10. 10

    PyCharmリモートインタープリターはプロジェクトタブにサイトパッケージのコンテンツを表示しません

  11. 11

    Windows 7では、一部のプログラムは「ビジュアルテーマを無効にする」レジストリ設定を行いませんか?

  12. 12

    Get-ADGroupMember:このリクエストのサイズ制限を超えました

  13. 13

    Pyusb can't find a device while libusb can

  14. 14

    MySQLでJSON_LENGTHとJSON_EXTRACTを組み合わせる方法は?

  15. 15

    Postmanを使用してファイル付きの(ネストされた)jsonオブジェクトを送信する

  16. 16

    Swiftのブロックのパラメーターに関するドキュメントのマークアップ形式は何ですか?

  17. 17

    Reactでclsxを使用する方法

  18. 18

    追加後、ブートストラップマルチセレクトがテーブルで機能しない

  19. 19

    MongoDB Compass: How to select Distinct Values of a Field

  20. 20

    「埋め込みブラウザのOAuthログイン」を有効にしてコールバックURLを指定した後でも、Facebookのコールバックエラーが発生する

  21. 21

    複数行ヘッダーのJTableヘッダーテキストの折り返し(カスタムTableCellRenderer)

ホットタグ

アーカイブ