Hudson River Trading Interview Questions

What is the difference between a hash map and a map?

Find the k largest values in an array in average time O(n).

What does the system call fork do?

Suppose you are walking down the street and randomly observing people. On average, how many people will you see before encountering someone taller than you?

Choose a person X at random from the street. Let N be the random variable representing the number of additional people you must randomly select from the street before you find someone taller than X. What is the expected value E[N]?

1) A pretty number is a number in base 4 whose digits are all either 1 or 0. How many pretty numbers are there less than n? 2) Given a list of moves in Reversi, return the total number of pieces for each player at the end of the game. 3) Trees are given as lists of nodes, where each node is a list with data [key, value, *children], where the order of the children matters. Two trees must be merged (left and right). For a given merged node with the same key between left and right inputs, the merged value should come from the right tree. The list of the merged node's children should start with children from the left tree's child list, and then the leftover right tree's child list. Output (key1, value1, ...) in pre-order traversal.

Given a person, what is the expected number of people you must observe before seeing someone taller than that person?

Design an abstract class for task scheduling. What information do you need to store for each task?

How can you generate two random variables with correlation rho and variance 1 from two independent unit Gaussians?

What is the fastest way to sort an array? How does the solution change if you require the numbers to be sorted in place? How would your approach differ if you can make assumptions about the structure of the array?

Implement a number guessing game where the player tries to guess a randomly chosen integer between 0 and 1000. After each guess, provide feedback indicating whether the guess is closer or further from the target number than the previous guess.

What is the difference between a soft link and a hard link?

Given an array of integers, determine for each number if it can be written as the sum of two Fibonacci numbers.

Given a set of points on the coordinate plane, determine how many distinct squares can be formed using these points as vertices.

Given a set of points on a coordinate system, determine how many rectangles can be formed such that all four corners of the rectangle have their vertices among the given points.

Given only survey responses where each student reports the size of their own room, and with no other information, how would you estimate the average room size?

Given two dates, write a function to count the number of days between them.

What are the stages of a pipeline processor?

What are the differences between a vector and a linked list?

Given a race track with 5 lanes, 25 bunnies, and no timer, how many races are required to determine the top 3 fastest bunnies?

How do you support multi-threading without kernel involvement?

What is Principal Component Analysis?

Given two strings S1 and S2, find the length of their longest common subsequence. If there is no common subsequence, return 0.

You roll a six-sided fair die repeatedly until you obtain each face at least once. On average, how many times do you need to roll the die?

q1: Check if given numbers can be written as the sum of two numbers in the Fibonacci sequence. q2: Perform specified data manipulation tasks using pandas. q3: Count the number of non-axis-aligned squares that can be formed from a list of points. q4: Count the number of non-axis-aligned rectangles that can be formed from a list of points.

Explain, at the hardware level, what a SIGSEGV (segmentation fault) is, what causes it, and how it is generated.

Give an algorithm to find the k-th largest element in an unsorted vector of integers.

How do you implement a multiplexer in an FPGA?