CareerCup

Design a service that keeps track of mobile users as they check in at different locations. This service will get informed of each check-in in real time (a user/location pair) and must be able to answer the following queries in real time:

1. Where is user U right now?
2. What users are at location L right now?

The following requirements apply:

1. A user can only be at one location at a time. If user U checks in at location X and then at location Y, they are no longer at location X.

2. A check-in only valid for at most 2 hours. If user U checks in at location X and then does nothing for 2 hours, they are no longer at location X.

The service should have durable enough storage that you can restart it without losing all of your data It should not store everything in memory.

what kind of DB will you use and how data will be organized and any indexes. If storage is spread out over multiple databases(locations), how is that done?

scalability/availability consideration, how will be distribute multiple servers. what happens when the traffic goes 10x all of sudden. What happens if one of the server goes down.

Design a suggestions list [system design] for words starting with prefix that user has typed on kindle device . The search is based on most frequent item occurring at the top to least frequent item at the bottom. Most frequent item depends on the usage of word globally.

For e.g user types "dra" . There should be a list of suggestions starting with dra such as dragon, drape, dracula etc based on their frequency of usage.

Design a image slide show 1) put image method 2) get image 3) random method. Random method should return a list of images such that images should be in randomized order and no image should be displayed twice without exhausting all images at once. I used list to store images . I used random class to generate randomly generated images based on the interval {0,list.size()}. But he insist on using randomization without depending on the list size.

Given a set of points in a plane, determine the position/angle where a yacht of 30 degree angle could be placed such that it could cover maximum points

Balance a string with parentheses. "a(b)" -> "a(b)"; "(((((" -> ""; "(()())" -> "(()())"; ")ab(()" -> "ab()"; etc...

design an employee swap in swap out system.
The system will have a machine which records the swap in and swap out.
The user can also login in a portal where he can check his swap in /swap out time. He can correct his time also.
There will be managers for employee who can check the entry for all the employees which are under them and correct their subordinates timings also
There will be HR who can only view the entries for all the employees.
We have to come up with the HLD and LLD for the system

Make 100 HTTP GET requests to http://en.wikipedia.org/wiki/Main_Page and print the following statistics for the response time to stdout:

• 10th, 50th, 90th, 95th, 99th Percentile

• Mean

• Standard Deviation

Your solution must be parallel. You must make at least N (say 10, but should be configurable). Use ExecutorService in Java for making the requests at a time.

Explain design choices, known limitations and edge cases.

What challenges did you face? How would you improve the code if you had more time?

Design an algorithm that provided your current location and a list of ATMs locations in the area, get you the closest K ATMs to your location.
Assume you have a method getDistance(a, b) that calculates the distance between a and b.

Follow Up:
Make your solution O(k) space and O(n) time

Design an algorithm to find the shortest substring in a synopsis such that it contains all the words in a provided list.

So, search for the shortest substring that contains ['Hello', 'World'].

Design a system for a parking lot where drivers can also have memberships (but also support guest drivers). The parking lot has counter screens on each row.

Design a message board system like Reddit were users can reply with messages on posted topics. How will you handle system scalability.

Google full-time phD candidate w/ work experience.

Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?

Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)

Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.

Q4.
Design merchandising product data storage service

There is a tree of nodes . each node is of type either place, area name, city, district , state, country

they are in tree like order like country contains multiple states ,states contain multiple cities ...so on

i want define the node structure and define the strategy to print the address of any node given from parent to all the child address of the node

package com.girish.sample;

import java.util.ArrayList;
import java.util.List;

public class Node {

	private String name;
	private Node parent;
	private List<Node> childNodes;
	private String nodeType;
	
	
	public Node(String name,String nodeType){
		this.name = name;
		this.nodeType = nodeType;
	
	}

	/**
	 * @return the name
	 */
	public String getName() {
		return name;
	}

	/**
	 * @param name
	 *            the name to set
	 */
	public void setName(String name) {
		this.name = name;
	}

	/**
	 * @return the parent
	 */
	public Node getParent() {
		return parent;
	}

	/**
	 * @param parent
	 *            the parent to set
	 */
	public void setParent(Node parent) {
		this.parent = parent;
	}

	/**
	 * @return the childNodes
	 */
	public List<Node> getChildNodes() {
		return childNodes;
	}

	/**
	 * @param childNodes
	 *            the childNodes to set
	 */
	public void setChildNodes(List<Node> childNodes) {
		this.childNodes = childNodes;
	}

	/**
	 * @return the nodeType
	 */
	public String getNodeType() {
		return nodeType;
	}

	/**
	 * @param nodeType
	 *            the nodeType to set
	 */
	public void setNodeType(String nodeType) {
		this.nodeType = nodeType;
	}

	public String getAddress() {
		return getparentAddress();
	}

	public String getparentAddress() {
		if (parent == null)
			return "";

		return parent.getparentAddress().concat("," + this.nodeType + ": " + this.name);
	}

	public List<String> getchildAddress() {

		List<String> childAddress = new ArrayList();

		for (Node node : childNodes) {

			childAddress.add(node.getchildAddress());

		}

		return null;
	}

}

Question regarding largest possible sum of subarray of size K.

6 8 7
3 64 4
24 48 ?

producer consumer problem

Define a singleton class

Find the number of ways you can have breakfast in 'n' days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days.

First asked how you can write a tree in a file?
Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d

Give you an unsorted integer iterator
and a percentage that is expressed in double (for example, 0.4 for 40%),
and find the number of the sorted array at the percentage position.
Example: Enter [1 3 2 5 4 6 7 9 8 10], and 0.6, you will return 6
public int findNumber(Iterator<Integer> nums, double percent){
}

/*Find minimum size of text window which contain all keywords of a search query from document.
Order of keywords don't matter.


Input:
Document: "MS(1) x y Is MS(5) x y MS(8) x Is Awesome x y z Awesome"

doc index dictionary:

{
Keyword: Index Position for keyword in doc
"MS": [1,5,8],
"Is": [4,10]
"Awesome": [ 11, 15] (n)
}
Search Input 1 : "MS is" ( k)
Result: "Is MS Ms" --> [Ms: 5 ; "Is" : 4] --> 2
Search Input 2: "Ms is Awesome",
Result : "MS x is Awesome" --> [Ms:8, Is: 10, Awesome: 11] ---> 4

for -> n
n^k

[1 4 5 8 10 11 15]

*/

An ABC notation in a tree is defined as folllows:
1. "0" means travel left
2. "1" means travel right
3. "Undefined" means hit the root
4. "Not Found" means not present in tree

Given a BST insertion order, {5,2,8,3,6,9,1} find the ABC notation for 6, 1, 10, 2 which is "10","00","NotFound", "0"

Design an IEvictionPolicy interface that allows users to perform put , get, delete functions based on user specified eviction policy.

Tried to use the strategy pattern here but the interviewer wasn't happy. He did not want me to have reference to the cache in the eviction policy's concrete implementation

DELL is a very well known leader in manufacturing computers worldwide. Company has already given its best to manufacture a user friendly computer. But sometimes due to improper use and incorrect configuration, a technical issue arises and make the user upset. So, In this situation, a user can directly connect to professional technicians by just dialing DELL customer support phone number +1-800-582-2826. User will get the instant solution here.http://www.customersupport-help.com/dell

Google On-site in May

Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.


Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time

can you use union find to Detect Cycle in a Directed Graph? why or why not

Rotate a Cube without Using Any Predefined Functions or Libraries

There are around 40 million files in a directory which needs to be transferred to another system via FTP in order of oldest file first. What's the ideal way to iterate over files and store it in a data structure from where it can be transferred?

Shell command, there is a log file, you want all the "error" inside the line to find out into another file inside,
What instruction,

how to design github