Amazon Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

what are the id's used for? is it desired that they are sequential (e.g. used for keys) or rather randomly distributed? How much of the range can we leave unused without overusing the range? How many keys per second? Bursts? Is a conflict acceptable or must the keys be truely unique for ever?

An approach I could imagine works is, if we have a slower transactional storage, where we can store block assignments to servers. A server picks such a block and generates sequential numbers. If he runs out of numbers (obviously k cycles before) in his blocks, he picks the next block. This has the advantage that if a server goes down, we use max blocksize numbers, usually such a transactional storage is around in the infrastructure - they are comparably slow, reliable for little data. Alternatively, the block assignment can be implemented on this same machines that delivers the key using a protocol (such as PAXOS) that allows machine failures as long as a majority of machines stays online.

I would as well try to persist the current block counter, so in the worst case, it can be read and a safe offset can be added that will waste a lot of numbers but since it should never occure it's an acceptable safety mechanism.

- ChrisK October 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Each box in the server farm to generate sequential IDs prefixed with unique box id.

class UID
{
  static ulong  srvId; //unique server id
  static ulong  mask;  //mask to | srvId and val
  static long   val;   //current uid value

  public static void Init(int id, int lenght) {
    mask  = ~0ul >> lenght;  //size of id in bits
    srvId = ((ulong)id) << (sizeof(ulong) * 8 - lenght);
  }

  public static ulong Get() {
    Interlocked.Increment(ref val);
    return (ulong)val & mask | srvId;
  }
}

- kanukadze October 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisZ
use of the IDs or desired structure/distribution not specified; the only requirement is uniqueness for as long as possible.

- kanukadze October 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Time stamp with date?

- TM October 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Generate a random number between 0 & 2^64
2. Check if random number exists in db.
3, if exists go to step 1. if does't exist. go to step 4.
4. a. Take write lock
4. b. again check if random number exist in db.
4. c. if exists unlock db and go to step 2. if doesn't exist. insert the random number in db.
5. d. return the random number.

Now to scale this service we can use sharding to divide our data source.

Big problem : if number of retry for random number is directly proportional to current number of keys in db.

Second solution: generate keys sequencially.

1. take lock on db. increment the counter unlock the lock and return the count.

problem its hard to scale because now we need to create many many shards to handle the concurrent requests.

- Paras November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Questions to ask - 1) Can the Id be sequential or random ? 2) Any input which needs to be used in generation of ID 3) Numeric or can contain other characters 4) Service Interface (GUI/API) 5) Number of requests per second

Assuming that sequential is allowed and no input required, One way to generate it will be

BigInteger SMALLEST_64_BIT_NUM = BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE);

Long seq = <current sequence value from DB sequence which is reset every day>;
Long currDate = 8 digit representation in format MMDDYYYY

return SMALLEST_64_BIT_NUM.add(currDate ).add(seq);

- turukmakto1990 December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use the Mac address plus a sequenced number to generate the uniq Id, The Mac address is 48 bits, plus two bytes for unique number.
Here we partition the unique numbers into set, hence it reduced the available unique ids. as well as non shareable nature of the ids belong to a certain mac address(as prefix).

If distribution is not required. (and not used in a sorted data structure e.g binary tree for look up purposes), then one can use a static counter. Increment when ever next id is requested.

- suhaib.realtor July 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

In Java size of char is 2 bytes whereas it is 1 byte in 'C'. How to handle this conflict?

- Shiva October 19, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More