{"id":6830,"date":"2013-01-22T19:59:59","date_gmt":"2013-01-23T00:59:59","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=6830"},"modified":"2013-01-22T19:59:59","modified_gmt":"2013-01-23T00:59:59","slug":"how-to-pair-socks-efficiently","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2013\/01\/22\/how-to-pair-socks-efficiently\/","title":{"rendered":"How to Pair Socks Efficiently"},"content":{"rendered":"<a href=\"http:\/\/stackoverflow.com\/questions\/14415881\/how-to-pair-socks-from-a-pile-efficiently\">amit<\/a> (via <a href=\"http:\/\/kottke.org\/13\/01\/how-to-efficiently-sort-socks\">Jason Kottke<\/a>):\n<blockquote cite=\"http:\/\/stackoverflow.com\/questions\/14415881\/how-to-pair-socks-from-a-pile-efficiently\"><p>Given a pile of <code>n<\/code> pairs of socks, containing <code>2n<\/code> elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space?<\/p><\/blockquote>\n<p>I like this answer from <a href=\"http:\/\/stackoverflow.com\/questions\/14415881\/how-to-pair-socks-from-a-pile-efficiently#comment20062948_14415881\">Srinivas<\/a>, although it assumes that each sock has more than one pair:<\/p>\n<blockquote cite=\"http:\/\/stackoverflow.com\/questions\/14415881\/how-to-pair-socks-from-a-pile-efficiently#comment20062948_14415881\"><p>I use pigeon hole principle to pair exactly one from the laundry pile. I have 3 different colors of socks (Red, Blue and Green) and 2 pairs of each color. I pick up 4 number of socks each time and I always make up a pair and get to work.<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"<p>amit (via Jason Kottke): Given a pile of n pairs of socks, containing 2n elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space? I like this answer from Srinivas, although it assumes that each sock has more than one [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,71],"class_list":["post-6830","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-programming"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/6830","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=6830"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/6830\/revisions"}],"predecessor-version":[{"id":6831,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/6830\/revisions\/6831"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=6830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=6830"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=6830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}