X

# Amazon  Questions

View By:

Q1 Log parser

Each time a visitor requests a page from our website, our webserver writes a log entry recoding the visitor's identity and the kind of page requested. Entries are written in chronological order to a plain-text file, with one entry per line. The format of each entry is:

user-id page-type-id

User IDs are arbitrary strings that uniquely represent a given user; if a user visits multiple pages, each log entry will have the same user ID. Page type IDs are arbitrary strings that uniquely represent a given kind of page on our site, such as the homepage, a product detail pages, or the shopping cart. Tons of users visit our website, but there are only a few dozen types of pages.

Q2 Given a 2-D MxN matrix having each value as difficulty for the block

Given a 2-D MxN matrix having each value as difficulty for the block. A frog is starting from a point Matrix[0][0] and will have to reach Matrix[M-1][N-1]. It can jump any step in one go [ 1, 2, ..... M-1] horizontally OR [ 1,2,3,.... N-1] vertically Each difficulty value is positive. Write code to give path trace for frog. Two structure to use -

struct node { int x; int y; struct node *next; };

struct path { int difficulty; struct node *pathlink; }

Ex matrix - 4X4 matrix

7 9 2 11 13 23 1 3 14 11 20 6 22 44 3 15

Minimum difficulty = 7 (a[0][0])+ 2(a[0][2]) +3(a[3][2])+15(a[3][3]) = 27 Path trace will have = 7->2->3->15

Q3 Find the number of times each character occurs in the string.

Calculate the frequency of each character in a given string

eg teddy d= 2 e=1 t=1 y=1

Q4 How to add two integers without using arithmetic operators?

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

Q5 check sign of two numbers

Detect if two integers have opposite signs

Given two signed integers, write a function that returns true if the signs of given integers are different, otherwise false. For example, the function should return true -1 and +100, and should return false for -100 and -200. The function should not use any of the arithmetic operators.

Q6 How to save a Binary Search Tree to a disk and then retrieve it?

Save a Binary Search Tree to a disk and then retrieve it.

Q7 Given an array containing 0s and 1s, find the maximum contiguous sub sequence which has equal number of 1s and 0s

You are given an array containing 0s and 1s. Give an O(n) time algorithm to find the maximum contiguous sub sequence which has equal number of 1s and 0s.

Examples

1) 10101010

The longest contiguous sub sequence that satisfies the problem is the input itself

2)1101000

The longest sub sequence that satisfies the problem is 110100

Q8 How to find all elements that appear more than n/2 times in a given list.

Design an algorithm to find all elements that appear more than n/2 times in a given list. Then do the same for elements that appear more than n/4 times.

Q9 Given a file with a lot of words (10 million) find out the top 10% most frequently occurring words

Given a file with a lot of words (10 million) find out the top 10% most frequently occurring words.

Q10 Change making problem.

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount.