SIG (Susquehanna) Interview Questions

Explain how hash tables work.

Since the average time complexity of a hashtable is O(1), why do we still use binary search trees? Can you describe some occasions where we use a binary search tree instead of a hashtable?

What is garbage collection, and how is it performed in Java?

Why do we use hashtables, and what is their time complexity?

What is a Binary Search Tree, and what is its time complexity for search, insert, and delete operations?

Implement a Stack data structure with methods such as push(), pop(), and top(), in a programming language of your choice (preferably C#). The stack should accept only 12-bit integer numbers as input, and all exceptions should be handled properly.

How does a dictionary work?

Reverse a given string.

Given two strings, return the characters that are common to both strings.

A group of friends are tracking the miles per gallon (MPG) for each of their cars. Each time they fill up their gas tank, they record the following in a CSV file: person name, car name, miles driven since last fill-up (float), gallons filled at this fill-up (integer), and the fill-up date. Write a program that lets a group member determine the MPG for each of their cars during a specific time range. The principal function for querying MPG is: GetRangeMPG(PersonName, StartDate, EndDate), which returns a list of objects containing (CarName, MPG), where MPG is calculated as (total miles driven during the time period) / (total gallons filled during that time period). The query's date range should be treated inclusively.

Check if a string is a permutation of a palindrome without using any additional data structures.

Given an array of integers, write a program in the language of your choice to do the following: (1) reverse the array; (2) find all perfect numbers in the array.

How would you implement a garbage collector for a programming language?

Develop an algorithm to reverse a string.

How do you reverse a linked list?

Given an array of numbers, find the maximum value in the array.

A frog is traveling from point A(0, 0) to point B(4, 6), and each step can only be 1 unit up or 1 unit to the right. The frog also refuses to move three steps in the same direction consecutively. Compute the number of ways the frog can move from A to B.

If you are playing a game and your opponent doubles the stakes, what probability of winning should you require to prefer accepting the doubled stakes over resigning from the game?

How many ways can five people sit in a circle such that you are sitting next to your best friend?

Given a character array representing a sentence, reverse the order of words in the sentence in place.

It costs $1 to play a game where you flip a fair coin four times. If you get four consecutive heads, you win $10. Should you play the game?

A bag contains 30 balls: 10 black, 5 orange, 10 green, and 5 blue. Without replacement, what is the probability that the second black ball is drawn on the third draw?

A painting has a 20% chance of being real and an 80% chance of being fake. If it's fake, you can sell it for $10,000; if it's real, it's worth $500,000. 1. What is the expected value of the painting? 2. If you could buy the option to purchase the painting for $100,000 after learning whether it is real or fake (but are not obligated to buy), what is the value of this option?

What is inheritance? What is polymorphism? What is the probability that three people have their birthdays on the same day of the week?

We are racing, and at any time we may signal to double our bet. We have each put down 100 to start. If, during the race, I signal that I want to double the bet, what is the minimum probability of winning that you would need in order to accept continuing with the doubled bet?

Suppose you and your opponent each have three fair coins and flip all three at once. After flipping, if both of you have the same number of heads from your own coins, your opponent pays you $1. If the numbers are different, you pay your opponent $2. Should you agree to play this game?

If the probability of seeing a meteor outside within one hour is 84 percent, what is the probability of seeing at least one meteor outside in 30 minutes?

Flip coins sequentially until the sequence 'HT' or 'TT' appears. What is the probability that 'HT' appears before 'TT'?

A frog is traveling from point A(0, 0) to point B(4, 6). Each step can only be 1 unit up or 1 unit to the right. The frog refuses to move three steps in the same direction consecutively. Compute the number of ways the frog can move from A to B.

A painting is on sale for X amount. The probability that it is real is Y. If it is real, it is worth A; if it is a fake, it is worth B. What is the expected gain on purchasing this painting?