Initializing an array in constant time
1,446.0K Views
Consider the following array operations. Init(N,d) initializes an array of N elements so that each element has value d. Once Init has been called, the following two operations can be applied: For any i such that 0 <= i < N, Get(i) returns the array element at position i and Set(i,v) sets the array element at position i to the value v.
Given any amount of memory you want, implement the three operations so that each operation has an O(1) time complexity.
Your Answer
More puzzles to try-
How can these parents tolerate such ingratitude and what put them in this situation?
A father goes to prison and the mother will have to sell her hotel, but their young daughter is happy. ...Read More »BOXES WITH MARBLES
You have three boxes full of marbles. There are stickers saying “white” “red” “red and white” on them indicating what ...Read More »34+89=400 Matchstick Equation Puzzle
Correct the equation by moving one matchstick 34+89=400 As given in the matchstick equation (34+89=400) in the above diagram, move ...Read More »Like to twirl body Riddle
I like to twirl my body but keep my head up high. After I go in, everything becomes tight. What ...Read More »Tricky addition riddle
20+20+20=60. How can you make 60 again by using the same number 3 times, but it can’t be 20?Read More »Who killed the sister?
A woman named Maria was at the funeral of her mother. She met a nice young man that she had ...Read More »The last thing you take off before bed
What is the last thing you take off before bed?Read More »What is written in the picture?
What is written in the picture?Read More »The Greek Philosophers
One day three Greek philosophers settled under the shade of an olive tree, opened a bottle of Retsina, and began ...Read More »Chairs around a table
How many chairs would you need around a table to sit for four Sons, four fathers, and two grandfathers ?Read More »Four Rectangle Riddle
Draw four rectangles on a piece of paper. Put nine x’s in the four rectangles so that there is an ...Read More »Relationships Puzzles
At a family reunion were the following people: one grandfather, one grandmother, two fathers, two mothers, four children, three grandchildren, ...Read More »Many Hands Tree puzzle
How many hands and fingers can you see in the picture?Read More »Measure Time with Candle
There are two candles. Both will only burn exactly for an hour. How will you use these two candles to ...Read More »Holes top and bottom
It has holes on the top and bottom. It has holes on my left and on my right. And it ...Read More »Three eyes but one leg puzzle
I have three eyes but only one leg. I still close one even if you beg. What am I?Read More »Balls in Bag
A bag contains 64 balls of eight different colours. There are eight of each colour (including red). What is the ...Read More »Book Numbering Riddle
I am compiling the Puzzlefry world almanac and it now contains lots of pages. I know that it takes 121 ...Read More »Farmer and sheep puzzle
A farmer had 17 sheep, All but 9 died. How many live sheep were left?Read More »Shepherd & Sheep riddle
4 shepherds were watching over their flocks and they were commenting on how many sheep they each had. If Alan ...Read More »
Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle