Write an iterative function to reverse a string. Do the same thing as a recursive function.
Technical Google Interview Questions
What are HTTP cookies? Explain how cookies work and how they are represented in the HTTP protocol.
Explain the following terms:
- Session cookie
- Persistent cookie
- Third party cookie
Explain final, finalize() and finally?
Explain the difference between a mutex and a semaphore? If you need to protect access to an increment operation which one would be the best choice?
Write a program to measure how long a context switch takes on the Unix operating system.
If you have access to a function that returns a random integer from one to five, write another function which returns a random integer from one to seven.
Discuss an algorithm to traverse a tree, depth first.
Describe a schema (or classes) to power an online car rental system. Describe the tables and the relationships beween the tables.
Construct a regular expression that matches a valid email address.
Implement a function with signature find_chars(string1, string2) that takes two strings and returns a string that contains only the characters found in string1 and string two in the order that they are found in string1. Implement a version of order N*N and one of order N.
You have to debug a crashing application. You are given the source. When you run it repeatedly in a debugger you observe that it never crashes in the same place twice. It uses only the C standard library and is single threaded.
What coding errors could cause the crashes? How would you find them?
Describe the congestion avoidance algorithm in the TCP protocol.
Explain what a deadlock is in multithreaded programming
Given a circular list of integers (when you reach the end of the list you come back to the beginning), what is the most efficient algorithm to find the smallest integer in the list?
circular_list = [22, 52, 66, 82, 5, 8, 12, 19].
Explain the terms static, final, and const
Given a N by N matrix of both negative and positive integers. Write an efficient algorithm to find the sub-matrix with the largest sum of all the contained elements.
Implement a function to divide two integers without using the divide operator.
Design a system to efficiently calculate the top 1MM Google search queries and create a report of these. Additionally:
- You are given twelve servers
- Each has two processors, 4GB of ram and four 400GB hard drives.
- The machines are networked
- The log data as roughly 100 Billion log lines in it.
- The log data comes in twelve, 320 Gb files.
- Each line of the files has roughly 40 search queries
- You can only use open source software or software that you write.
Given an array A[N] containing N numbers. Crate an array Output[N] where Output[i] is equal to the product of all the elements of A[N] except A[i].
For example Output is the product of A to A[N-1] and Output is the product of A and from A to A[N-1].
Do this without using the division operator. Do it in O(n).
You are given a linked list of integers of length N.
N is very large and you don’t know N.
Write a function to return k completely random numbers from the list.
Do this in O(n).
Hint: Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2.
Write a function to efficiently determine the result of a game of Tic Tac Toe.
The function takes as input the game and the sign (x or o) of the player. The function returns if this player has won the game or not.
Carefully consider both the data structure and the algorithm for your answer.
Explain why manhole covers are round. Why is this design better than, say, a square design.
You want to check that your friend, Bill, has your accurate phone number, but you can't ask him directly. You have to write a question on a card which and give it to Ava. She will take the card to Bill and then return the answer to you.
What should you write on the card to ensure Bill can encode the message so that Ava cannot read your phone number?
You have a closet with 300 shirts in it. Consequently, you find it hard to find a shirt quickly while dressing for work in the morning.
What can you do to organize your shirts to minimize the time that it takes to find the correct one?
Imagine you have eight balls, each of the same size.
One of the balls weights slightly more than the other seven.
Using a balance, find the heavier ball using only two weighings.
Write a function to efficiently find the fifth maximum element in a binary search tree. Try to do this without using significant additional storage.
Design the schema or the classes to implement a library for building card games with. This library should make it easy to build games like Rummy, Poker, Hearts, Whist etc.
Outline the implementation for two of the most important methods of the