Finding K closest elements from the median of an unsorted Array
Given an unsorted array, I am trying to find the K nearest elements to the median of an Array. I am having trouble finding the solution in linear running time.
A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34 # assume sorting part is done
Median here is 6.
Answer for this is 2,3,4,5,6.
Any help or hint will be appreciated.
1 answer

My suggestion for this would be a two step approach.
First, use the Median of Medians algorithm to find the Median of an unsorted array in linear time.
Second, scan the array and fill a Min Heap (of size k), where elements are organized according to distance to the median, in order to find the k nearest elements.
The above should have a runtime of O(N log(k)) which is linear in N.
See also questions close to this topic

Expected Number of Collision Pairs
I have been attempting to solve this problem for hours, but cannot seem to comprehend how to come to the solution.
Let H be a universal family of hash functions from U = {0, 1, . . . , u − 1} into a table of size m. Let S ⊆ U be a set of m elements we wish to hash. Prove that if we choose h from H at random, the expected number of pairs (x, y) in S that collide is ≤ (m−1)/2.
My first method was to come up with an example for m=2 such that the possible outcomes for pairings are
0 0 1 0 0 1 1 1
but I cannot understand how the expected number of pairs that collide can be fractional (unless it means that the chance of picking a collision is 1/2, but this would not make sense as the number of maps increases, I don't think). Can anyone clarify this?

I am trying to understand how exactly time complexity is calculated
I found this question online when practicing:
def test1: limit = 2 x="a" for i in range(limit): for j in range(limit): print x def test2: limit = 2 x="a" for i in range(limit): print x for i in range(limit): print x
The question was what are the time complexities for
test1
andtest2
? I guess the answer to both is O(n²).If the limit had been 20 or 30, is it correct that
test2
's complexity would be be O(2n), which is the same as O(n), andtest1
's complexity would be O(n²)?Also what is the complexity if the
for
loop intest2
is repeatedlimit1
times, wherelimit = n
? 
How do I add alpha beta pruning to a minimax tic tac toe game?
I'm making an unbeatable tic tac toe program using the minimax algorithm. The program control has to traverse through a LOT (over 20k) of nodes in the tree to choose a position (obviously it decreases with every move). But, I want to make the program faster using alpha beta pruning specifically. I checked out some of the ways to do it on the internet but it seems to me like my code is not compatible with those methods.
Any ideas on how to get this done will be really useful for me. This program is for an assignment I need to submit tonight, so it would be super nice if anyone could help me out with this.
The code I've written for the program is below (it is in Python 3.6)
Thanks in advance!
import sys move = 1 n = 0 nodes = 0 def evaluateBoard(board): global n #Checking for rows cnt = 0 for i in range(n): res = 0 for j in range(n): res += board[cnt * n + j] cnt += 1 if res == n: return 1 elif res == n: return 1 #Checking for columns for i in range(n): res = 0 for j in range(n): res += board[i + n * j] if res == n: return 1 elif res == n: return 1 #Checking for diagonals res = res2 = 0 for i in range(n): res += board[i * (n + 1)] res2 += board[(i + 1) * (n  1)] if n in [res, res2]: return 1 elif n in [res, res2]: return 1 return 0 def checkNonTerminal(board): for pos in board: if pos == 0: return 1 return 0 def getScore(board, depth): if evaluateBoard(board) == 1: return 10  depth elif evaluateBoard(board) == 1: return depth  10 else: return 0 def minimax(board, turn, depth, alpha, beta): global nodes if evaluateBoard(board) == 0 and checkNonTerminal(board) == 0: return getScore(board, depth) global move moves = list() scores = list() for square, pos in enumerate(board): if pos == 0: nodes += 1 #print(board) new_board = board.copy() new_board[square] = turn moves.append(square) #print("Moves:", moves, "depth:", depth, "turn:", turn, checkNonTerminal(new_board) == 0) if evaluateBoard(new_board) in [1, 1] or checkNonTerminal(new_board) == 0: move = square return getScore(new_board, depth) scores.append(minimax(new_board, turn * 1, depth + 1, alpha, beta)) # print("moves",moves) # print("scores", scores) if turn == 1: move = moves[scores.index(max(scores))] return max(scores) elif turn == 1: move = moves[scores.index(min(scores))] return min(scores) def displayBoard(board): global n for i in range(n): for j in range(n): if board[n*i+j] == 1: print("x",end=" ") elif board[n*i+j] == 1: print("o", end=" ") else: print(".", end = " ") print() print() def main(): global n global move n = 3 first_turn = input("Would you like to go first (Y/N)?: ") if first_turn in ['Y', 'y']: first_turn = 1 cnt = 1 else: first_turn = 1 cnt = 2 board = [0] * 9 displayBoard(board) while evaluateBoard(board) == 0 and checkNonTerminal(board) == 1: if cnt % 2 == 0: minimax(board, 1, 0) #print(score) board[move] = 1 displayBoard(board) else: choice = eval(input("Enter your choice (19): ")) if board[choice  1] != 0: print("No cheating!") sys.exit([0]) else: board[choice  1] = 1 displayBoard(board) cnt += 1 if evaluateBoard(board) == 1: print("You lose!") elif evaluateBoard(board) == 1: print("You win!") else: print("It's a draw!") print(nodes,"nodes") main()

Sort nested divs inside unordered list
I have the following html ul:
<ul id="actionList"> <li> <span> <h4>xyz</h4> <div class="list"> <div class="item"> <p class="title">test2</p> <button class="deleteButton" tabindex="1">Delete</button> </div> <div class="item"> <p class="title">test3</p> <button class="deleteButton" tabindex="1">Delete</button> </div> <div class="item"> <p class="title">test1</p> <button class="deleteButton" tabindex="1">Delete</button> </div> </div> </span> </li> <li> <span> <h4>abc</h4> <div class="list"> <div class="item"> <p class="title">test5</p> <button class="deleteButton" tabindex="1">Delete</button> </div> <div class="item"> <p class="title">test4</p> <button class="deleteButton" tabindex="1">Delete</button> </div> <div class="item"> <p class="title">test6</p> <button class="deleteButton" tabindex="1">Delete</button> </div> </div> </span> </li> </ul>
I'm trying to sort the
.item
divs alphabetically based on the.title
div.What I tried:
var alphabeticallyOrderedDivs = $('.action').sort(function(a, b) { var $aTopic = $(a).find('.topic'), $bTopic = $(b).find('.topic'); return String.prototype.localeCompare.call($aTopic.text().toLowerCase(), $bTopic.text().toLowerCase()); }); var container = $(".list"); container.detach().empty().append(alphabeticallyOrderedDivs); container.parent().append(container);
Unfortunately, it doesn't seem to come out with any output.
I'm thinking this has to do with the fact that the
.list
is a class instead of id and therefore there are multiple.I tried replacing
container.parent()
with$('body')
just to see if it is even outputting anything, and I found that it was sorting the.item
divs... just gathering them all and sorting them. This was causing it to have two sets of all test{16}.Is this even possible to accomplish?

How to sort an array with unique values
Quicksort gives us a pretty nice O(nlogn); However, I was thinking is there a way to sort an array with unique values that is faster than Quicksort?

Scala Spark DataFrame, drop duplicate after sorting
I have a use case that I want to deduplicate the data frame, but it's important which row I am going to keep. let's say I have this data frame:
++++ server_received_timeevent_id transaction_id  ++++ 20181014T23:32:35Z8accd9b4730d499ea13820c1a231188b778d19a88b8342218fab371cd2a5163b 20181014T23:42:23Z0793ca21d5b347a19130da8ddd3a58527fed388cdc7e4d22b76e06dc6df8477c 20181014T23:29:31Z8accd9b4730d499ea13820c1a231188b778d19a88b8342218fab371cd2a5163b 20181014T23:33:51Z478a9b3b5b734b71b254e3bef60413747cca61f49c3b43d4b24ce86de34ef508 20181014T23:37:16Z643bd562e2d6457a97a296dd26a98092bc131c2ce40e4d119b2ff8a61553becd 20181014T23:55:26Z3b6b7bdb4d994435b4184fa0481c9e5718067f52ead94e4588dcc9d9ddbea055 20181014T23:25:40Z001594f6ed8d47678b528e8640e2f34f6b24727b361e41339e5bb5909938a2c4 20181014T23:29:26Z7844a53195694e23b5e3e14f754a47a3c9890234ce2d4155825b8cffac34828b 20181014T23:12:36Z7cc0e5763b6c49cb929e69c14f4cbd8bcccd32358f484073809dfe5ac79ebe49 20181014T23:02:33Z8ba26272d8eb423099f29375f0a2dc25a486d075526a41d5b34ebc7238bbff71 20181014T23:03:44Z9a98f0ed69574a34a652a2a61e6015d9429417aa72674ce2b06236d164fa9d9e
As you can see the 1st row and 3rd row both have
transaction_id = 778d19a88b8342218fab371cd2a5163b
I only want to keep the one with the earliest server received time
20181014T23:29:31Z21f3ec3aaa414ff79c8bf3dfbef6c539778d19a88b8342218fab371cd2a5163b
But if I try something like this:
df.orderBy(desc("server_received_time")).groupBy("transaction_id").agg(first("server_received_time")).as("time"))
Since
groupby
doesn't maintain the order it wont work.I was wondering if there is any way that can I can achieve this?
Or if I can sort each partition after the group by individually and take the first row?